7. Управление одновременным доступом.

Для поддержания согласованного состояния данных необходимо обеспечить синхронизацию доступа. Синхронизация достигается путем применения алгоритмов управления одновременным доступом, который обеспечивает:

• Свойство сериализуемости, требующее чтобы эффект множества одновременно выполняемых транзакций был эквивалентен эффекту от их последовательного выполнения.

• Свойство изолированности выполнения транзакций, заключается в том, что результат транзакций не может зависеть от других параллельно выполняемых транзакций.

Наиболее популярный алгоритм управления одновременным доступом, основанный на механизме блокировок. В такой схеме всякий раз, когда транзакция пытается получить доступ к какой-либо единице памяти, на эту единицу накладывается блокировка в одном из режимов:

1) Разделяемом;

2) Исключительном.

Блокировки накладываются в соответствии с правилами совместимости блокировок, исключающими конфликты:

• чтение-запись;

• запись-чтение;

• запись-запись.

Существует теорема, что сериализуемость транзакций заведомо гарантируется, если блокировки, относящиеся к одновременно выполняемым транзакциям удовлетворяют правилам:

«Ни одна блокировка от имени какой-либо транзакции не должна устанавливаться, пока не будет снята ранее установленная блокировка» - это правило известно под названием двухфазового блокирования.

Для РСУБД те же задачи переносятся на распределенную среду, т.е. транзакции могут выполняться на нескольких узлах, где располагаются необходимые данные.

Выполнение множества распределенных транзакций сериализуемо (глобальная сериализуемость) тогда и только тогда, когда:

1) Выполнение этого множества транзакций сериализуемо на каждом узле.

2) Упорядочение транзакций на всех узлах одинаково.

В алгоритмах, основанных на блокировании для обеспечения свойств глобальной сериализуемости применяется один из протоколов:

• Централизованный протокол двухфазной блокировки;

• Двухфазная блокировка первичной копии;

• Распределенный протокол двухфазной блокировки;

• Протокол блокировки большинства.

1) При централизованном блокировании для всей РБД поддерживается единая таблица блокировок. Эта таблица располагается на одном из узлов, находящемся под управлением единого менеджера блокировок. Он отвечает за установку и снятие блокировок от имени всех транзакций.

Поскольку управление блокировок сосредоточено на одном узле, то оно аналогично централизованному управлению одновременным доступом и глобальная сериализуемость обеспечивается достаточно легко.

Общая схема:

1) Координатор транзакций в узле S1 разделяет глобальную транзакцию на несколько субтранзакций, отвечая за их согласованность. Если транзакция включает обновление элементов данных, координатор должен гарантировать, что все копии этого элемента будут обновлены, для этого должны быть установлены блокировки на все копии и начато обновление каждой из них.

2) Локальный менеджер транзакций приступает к выполнению запросов глобальной транзакции, обращаясь к менеджеру блокировок с соблюдением обычных правил протокола двухфазной блокировки.

3) Менеджер блокировок проверяет совместимость поступающих запросов на блокировку элементов данных и либо устанавливает блокировку, либо ставит запрос в очередь.

С алгоритмом связаны 2 проблемы:

• Центральный узел может стать узким местом, как из-за большого объема обработки данных, так и из-за генерируемого вокруг него интенсивного сетевого трафика.

• Надежность такой системы ограничена, поскольку отказ или недоступность центрального узла приводит к выходу из стоя всей системы.

2) Блокирование первичной копии – это алгоритм управления одновременным доступом, применяемый для БД с репликациями, где копии одних и тех же данных могут храниться на множестве узлов.

Одна из таких копий выделяется как первичная и для доступа к любому элементу данных необходимо установить блокировку на его первичную копию. Множество первичных копий элементов данных известно всем узлам распределенной системы, и запросы транзакций на блокирование направляются к узлам, где хранятся первичные копии.

При обновлении элемента данных достаточно установить блокировку для записи только его первичной копии. После того, как первичная копия будет обновлена, внесенные изменения могут быть распространены на все ведомые копии. Этот алгоритм хорош для нечастых обновлений данных.

3) Алгоритм распределенного блокирования. Предполагает распределение обязанностей по управлению блокировками между всеми узлами системы. Для выполнения транзакций необходимо участие и координация менеджеров блокировок на нескольких узлах, каждый менеджер отвечает за свой узел.

Блокировки устанавливаются на всех узлах, данные которых участвуют в транзакциях. Для операции считывания используется любая копия, при выполнении операции обновления блокируются все копии, где содержится обновляемый элемент.

Такому алгоритму не свойственны недостатки механизма централизованного блокирования, связанные с перегруженностью центрального узла. Однако алгоритмы этого типа сложнее, а коммуникационные затраты, необходимые для установки всех требуемых блокировок – выше.

4) В протоколе блокирования большинства, когда транзакции требуется считать или записать элемент данных, копии реплики которого имеются в n узлах, она должна заблокировать этот элемент на числе узлов большем n/2.

Транзакция не продолжается пока не установлены блокировки. Если это не сделано за определенный промежуток времени, транзакция отменяет запрос и информирует все узлы.

Если большинство достигнуто, то об этом информируются все узлы и устанавливается либо разделяемая блокировка для чтения, либо монопольная блокировка для записи.

Общий побочный эффект всех алгоритмов управления одновременным доступом по средствам блокирования: это возможность тупиковых ситуаций. Задача обнаружения и преодоления тупиков особенно важна в распределенных системах, тем не менее, благодаря относительной простоте и эффективности алгоритма блокирования они имеют значительно большую популярность, чем альтернативные алгоритмы:

1) Алгоритм, основанный на временных метках. Они выполняют конфликтующие операции транзакций в соответствии с временными метками, присвоенными транзакциями при их регистрации.

2) Алгоритм оптимистичного управления одновременным доступом. Они исходят из предположения о том, что конфликты между транзакциями редки и доводят транзакцию до конца, а затем производят проверку корректности. Если выясняется, что фиксация данной транзакции повлечет нарушение сериализуемости, то транзакция откатывается и запускается снова.

Пример взаимной блокировки в распределенной среде: пусть есть 3 транзакции Т1, Т2, Т3. Транзакция Т1 записана в узле S1 и создает агента в S2. Транзакция Т2 записана в узле S2 и создает агента в узле S3. Транзакция Т3 записана в узле S3 и создает агента в S1.

Локальный граф ожидания для каждого узла не содержит циклов:

Однако объединение индивидуальных графов в единый граф дает петлю, указывающую на наличие взаимной блокировки:

Существует 3 метода выделения взаимных блокировок в распределенной среде:

1) Централизованный. При централизованном выявлении взаимных блокировок один из узлов назначается координатором взаимных блокировок, и каждый менеджер блокировок с определенным интервалом направляет свой локальный граф ожидания координатору. Координатор строит глобальный граф и анализирует его, находя циклы координат – разрушает их, выбрав транзакцию, которая должна быть отменена.

Недостаток этого метода – узел с координатором является узким местом.

2) Иерархический. При иерархическом методе выявления взаимных блокировок узлы в сети образуют некоторую иерархию, и каждый из узлов посылает для анализа свой локальный граф ожидания узлу, стоящему выше в иерархии.

Координатор взаимных блокировок, расположенный в вышестоящем узле, строит и анализирует глобальный граф ожидания на основании информации, полученной с нижестоящих узлов.

3) Распределенный. В распределенном методе к локальному графу ожидания добавляется внешний узел (Text), отражающий наличие агента на удаленном узле.

Когда транзакция в Т1 в узле S1 создает агента в узле S2, к локальному графу добавляется ребро, соединяющее Т1 и Text, и помеченное именем узла S2.

Если в другом узле запущена транзакция, создавшая агента в узле S1, то узел Text соединяется ребром с транзакцией Т3, запущенной в этом узле S1.

Локальный граф ожидания имеет следующий вид (аналогично строятся графы и на других узлах):

Н аличие циклов в графе ожиданий не включающих Text, свидетельствует о возможности существования глобальной взаимной блокировки. Для уточнения существования взаимной блокировки первый обнаруживший вероятность существования узел посылает свой локальный граф ожидания в тот узел, где в состоянии ожидания находится транзакция, созданная в этом узле. Там графы сливаются, анализируются и, если подозрения остаются, слитый граф пересылается далее до тех пор, пока возможность существования глобальной взаимной блокировки не будет установлена или опровергнута.

Например во втором узле S2: Text -> T3 -> T1 -> T2 -> Text. Пересылаем весь этот граф в 3 узел, там получаем S3: Text -> T3 -> T1 -> T2 -> T3 -> Text. Есть цикл (T3 -> T1 -> T2 -> T3), что доказывает наличие взаимной блокировки.