Распределенная СУБД - обработка тупиков

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

Что такое тупиковые ситуации?

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

Например, в следующем графике ожидания транзакция T1 ожидает элемента данных X, который заблокирован T3. T3 ожидает Y, который заблокирован T2, а T2 ожидает Z, который заблокирован T1. Следовательно, формируется цикл ожидания, и ни одна из транзакций не может быть продолжена.

Обработка тупиков в централизованных системах

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

Предотвращение тупиковых ситуаций.
Избегание тупиковых ситуаций.
Обнаружение и устранение тупиковых ситуаций.

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

Предотвращение тупиковых ситуаций

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

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

Избежание тупиковых ситуаций

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

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

Для этого есть два алгоритма, а именно wait-die и wound-wait. Предположим, что есть две транзакции, T1 и T2, где T1 пытается заблокировать элемент данных, который уже заблокирован T2. Алгоритмы следующие -

Wait-Die- Если T1 старше, чем T2, T1 может ждать. В противном случае, если T1 младше T2, T1 прерывается и позже перезапускается.
Wound-Wait- Если T1 старше T2, T2 прерывается, а затем перезапускается. В противном случае, если T1 младше T2, T1 может подождать.

Обнаружение и устранение тупиковых ситуаций

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

Поскольку при предоставлении запросов на блокировку нет никаких мер предосторожности, некоторые транзакции могут зайти в тупик. Для обнаружения взаимоблокировок диспетчер блокировок периодически проверяет наличие циклов в графе ожидания. Если система зашла в тупик, менеджер блокировок выбирает транзакцию-жертву из каждого цикла. Жертва прерывается и откатывается назад; а затем перезапустился позже. Некоторые из методов, используемых для выбора жертвы:

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

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

Обработка тупиков в распределенных системах

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

Местоположение транзакции

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

Эта проблема может быть решена с помощью модели Daisy Chain. В этой модели транзакция несет определенные детали при перемещении с одного сайта на другой. Некоторые из деталей - это список необходимых таблиц, список требуемых сайтов, список посещенных таблиц и сайтов, список таблиц и сайтов, которые еще предстоит посетить, а также список полученных блокировок с типами. После того, как транзакция завершается фиксацией или прерыванием, информация должна быть отправлена на все заинтересованные сайты.

Контроль транзакций

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

Один сервер может быть выбран в качестве центра управления.
Центр управления может перемещаться с одного сервера на другой.
Ответственность за контроль может разделять несколько серверов.

Предотвращение распределенных тупиков

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

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

Хотя реализация проста, у этого подхода есть некоторые недостатки:

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

Избежание распределенных тупиков

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

Конфликт между двумя транзакциями на одном сайте.
Конфликт между двумя транзакциями на разных сайтах.

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

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

Distributed Wound-Die
- Если T1 старше, чем T2, T1 может подождать. T1 может возобновить выполнение после того, как сайт P получит сообщение о том, что T2 успешно завершил или прервал выполнение на всех сайтах.
- Если T1 младше T2, T1 прерывается. Управление параллелизмом на сайте P отправляет сообщение всем сайтам, которые посещал T1, чтобы прервать T1. Управляющий сайт уведомляет пользователя об успешном прерывании T1 на всех сайтах.
Distributed Wait-Wait
- Если T1 старше T2, T2 необходимо прервать. Если T2 активен на сайте P, сайт P прерывает и откатывает T2, а затем транслирует это сообщение на другие соответствующие сайты. Если T2 покинул сайт P, но активен на сайте Q, сайт P транслирует, что T2 был прерван; Затем сайт L прерывает работу, откатывает T2 и отправляет это сообщение всем сайтам.
- Если T1 младше T1, T1 может подождать. T1 может возобновить выполнение после того, как сайт P получит сообщение о том, что T2 завершил обработку.

Распределенное обнаружение тупиков

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

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

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

Centralized Deadlock Detector - Один объект обозначен как центральный детектор тупика.
Hierarchical Deadlock Detector - Ряд детекторов тупика организован в иерархию.
Distributed Deadlock Detector - Все сайты участвуют в обнаружении тупиковых ситуаций и их устранении.