Методы поддержки непротиворечивости распределенных данных
Теорема CAP (известная также как теорема Брюера), в информатике — эвристическое утверждение о том, что в любой реализации распределённых вычислений возможно обеспечить не более двух из трёх следующих свойств:
согласованность данных (англ. consistency) — во всех вычислительных узлах в один момент времени данные не противоречат друг другу;
доступность (англ. availability) — любой запрос к распределённой системе завершается корректным откликом;
устойчивость к разделению (англ. partition tolerance) — расщепление распределённой системы на несколько изолированных секций не приводит к некорректности отклика от каждой из секций.
http://mrivkin.narod.ru/Publ/RASPBD.htm:
Очень мощный и сложный алгоритм реализации протокола двухфазной фиксации изменений реализован в 7 версии СУБД Oracle. Он состоит из следующих этапов:
1. Запускается распределенная транзакция, включающая команду COMMIT.
2. Этап подготовки
a) Узел-родитель обращается к каждому из своих узлов-детей с просьбой "дать обещание", что он зафиксирует или откатит свою часть изменений только после получения определенной команды;
b) После того, как все узлы-дети готовы к работе, узел-родитель записывает в журнал redo log информацию о транзакции и устанавливает специальный флаг в состояние, говорящее о готовности узла к работе;
c) Узел сообщает своему узлу-родителю о том, что он готов к работе;
d) Узел не может завершить транзакцию до тех пор, пока не получит на это разрешение от узда родителя.
3. Этап фиксации
a) Узел записывает в журнал redo log информацию о том, что он фиксирует сделанные изменения (или откатывает их если были ошибки во время этапа подготовки);
b) Узел дает команду своим узлам-детям выполнить фиксацию изменений (или откатить изменения);
c) Узел информирует свой узел-родитель о том, что фиксация выполнена (или откачена);
d) После того, как все узлы зафиксировали или откатили изменения, снимается блокировка ресурсов.
Ключом к пониманию этого алгоритма является фраза "дать обещание", которая говорит о том, что некоторые совместные действия (фиксация или откат) будут выполнены в будущем. Фиксация изменений выполняется в каждом узле самостоятельно, поэтому узлы не должны ждать пока закончится фиксация в других узлах.
"ПРОЗРАЧНЫЙ ПРОТОКОЛ ДВУХФАЗНОй ФИКСАЦИИ ИЗМЕНЕНИЙ. Этот протокол обеспечивает непротиворечивость данных. При выполнении транзакции, изменяющей данные в нескольких узлах, протокол двухфазной фиксации обеспечивает успешное выполнение всей транзакции только в том случае, если успешно выполнилась обработка в каждом узле. Если же в одном из узлов обработка не выполнена успешно, то анулируются результаты работы всей транзакции.
http://www.denizzone.com/baset5r4part2.html
Требования к распределенным базам данных
прозрачность относительно сети – СУБД должна одинаково работать в условиях разнородных сетей;
· поддержка распределенных запросов – пользователь должен иметь возможность объединять данные из любых баз, даже размещенных в разных системах;
· поддержка распределенных изменений – пользователь должен иметь возможность изменять данные в любых базах, на доступ к которым у него есть права;
· поддержка распределенных транзакций – СУБД должна выполнять транзакции, выходящие за рамки одной вычислительной системы, и поддерживать целостность БД при возникновении отказов как в системах, так и в сети;
· безопасность – СУБД должна обеспечивать защиту всей распределенной БД от несанкционированного доступа;
· универсальность доступа – СУБД должна обеспечивать единую методику доступа ко всем данным.
Транзакция – это законченная совокупность действий над БД, которая переводит ее из одного целостного состояния в другое. Если операторы транзакции выполняются, происходит ее нормальное завершение и БД переходит в обновленное (целостное) состояние (ситуация COMMIT на рис. 42). При сбое происходит откат к исходному состоянию БД (ситуация ROLLBACK на рис. 42).
Рис. 42. Выполнение и откат транзакции
К транзакциям предъявляется набор требований, известный под названием ACID (Atomicity, Consistency, Isolation, Durability).
Атомарность (atomicity). Транзакция представляет собой набор законченных действий. Система обеспечивает их выполнение по принципу «все или ничего» – либо выполняются все действия, тогда транзакция фиксируется, либо (при сбое) транзакция откатывается назад, а БД остается в исходном состоянии.
Согласованность (consistency). Предполагается, что в результате выполнения транзакции система переходит из одного корректного состояния в другое.
Изолированность (isolation). При выполнении транзакции данные могут временно находиться в несогласованном состоянии. Такие данные не должны быть видны другим транзакциям до завершения изменений. Система обеспечивает каждой транзакции иллюзию изолированного выполнения, как если бы прочие транзакции либо завершились, либо начнут выполняться после ее завершения.
Долговечность (durability). Если транзакция зафиксирована, то ее результаты должны быть долговечными. Новые состояния всех объектов сохранятся даже в случае аппаратных или системных сбоев.
Автоматическое выполнение транзакций. автоматически начинается с выполнения пользователем или программой первой инструкции. Далее происходит последовательное выполнение инструкций, пока транзакция не завершится.
Управляемое выполнение транзакций. · инструкция BEGIN TRANSACTION сообщает о начале транзакции (начало транзакции задается явно);
· инструкция COMMIT TRANSACTION сообщает об успешном выполнении транзакции (при этом новая транзакция автоматически не начинается);
· инструкция SAVE TRANSACTION позволяет создать внутри транзакции точку сохранения и присвоить сохраненному состоянию имя точки сохранения, указанное в инструкции;
· инструкция ROLLBACK отменяет выполнение текущей транзакции и возвращает БД к состоянию, где была выполнена инструкция SAVE TRANSACTION (если в инструкции указана точка сохранения – ROLLBACK TO имя_точки_сохранения) или к состоянию начала транзакции.
Средства обработки транзакций позволяют изолировать пользователей друг от друга.
Проблема утраченных обновлений заключается в том, что если пользователи параллельно обновляют одни и те же данные, то запомнится обновление, проведенное последним.
Проблема зависимости от незафиксированных обновлений состоит в том, что пользователь А может увидеть данные, которые были обновлены пользователем В, но эти обновления не были окончательно зафиксированы. Пользователь В может провести откат БД в исходное состояние Пользователь А будет предпринимать действия над ошибочными данными. Иногда для такого рода проблем используется термин преждевременное чтение.
Еще одна проблема возникает, если пользователь проводит групповую обработку данных, не связанную с корректировкой (вычисляет сумму или среднюю величину), а какие-то значения обрабатываемого множества в этот момент претерпевают изменения в результате выполнения параллельной транзакции.
Метод сериализации транзакций – это механизм их выполнения по такому плану, когда результат совместного выполнения транзакций эквивалентен результату некоторого последовательного выполнения этих же транзакций. Обеспечение такого механизма является основной функцией управления транзакциями.
Между транзакциями могут существовать следующие виды конфликтов:
· транзакция 2 пытается изменять объект, измененный незакончившейся транзакцией 1 (конфликт W-W, запись-запись);
· транзакция 2 пытается изменять объект, прочитанный незакончившейся транзакцией 1 (конфликт R-W, чтение-запись);
· транзакция 2 пытается читать объект, измененный незакончившейся транзакцией 1 (конфликт W-R, запись-чтение).
Для обеспечения сериализации транзакций применяются методы захвата и освобождения объектов по инициативе транзакции. Транзакция захватывает объект, что приводит к его блокировке для других транзакций, и освобождает его только при своем завершении.
два основных режима захватов:
· совместный режим – S(Shared), означающий разделяемый захват объекта и необходимый для выполнения операции чтения объекта;
· монопольный режим – X(eXclusive), означающий монопольный захват объекта и необходимый для выполнения операций записи, удаления и модификации.
протокола двухфазного блокированияобъектов БД. Перед выполнением любой операции над объектом БД от имени транзакции запрашивается захват объекта в совместном или монопольном режиме. Выполнение транзакции разбивается на две фазы:
· фаза роста – накопление захватов (установление блокировок);
· фазафиксации или отката – освобождение захватов (снятие блокировок).
динамическую схему блокировки, заключающуюся в том, что сначала транзакция блокирует большой объект, например страницу. Если проявляется другая транзакция, претендующая на какую-то запись внутри этой страницы, то первая транзакция автоматически уменьшает зону блокировки до уровня записи.