В этой главе рассматриваются механизмы обработки тупиковых ситуаций в системах баз данных. Мы изучим механизмы обработки тупиковых ситуаций как в централизованной, так и в распределенной системе баз данных.
Что такое тупики?
Deadlock — это состояние системы базы данных, имеющей две или более транзакций, когда каждая транзакция ожидает элемент данных, который блокируется какой-либо другой транзакцией. О тупике можно указать циклом в графике ожидания. Это ориентированный граф, в котором вершины обозначают транзакции, а ребра — ожидания элементов данных.
Например, в следующем графике ожидания транзакция 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 может ждать.
Wait-Die — если T1 старше T2, T1 может ждать. В противном случае, если T1 моложе, чем T2, T1 прерывается и позже перезапускается.
Wound-Wait — если T1 старше T2, T2 прерывается и позже перезапускается. В противном случае, если T1 младше, чем T2, T1 может ждать.
Обнаружение и устранение тупиковых ситуаций
Подход обнаружения и удаления взаимоблокировки периодически запускает алгоритм обнаружения взаимоблокировки и устраняет взаимоблокировку, если она есть. Он не проверяет тупик, когда транзакция размещает запрос на блокировку. Когда транзакция запрашивает блокировку, менеджер блокировок проверяет, доступна ли она. Если он доступен, транзакция может заблокировать элемент данных; в противном случае транзакции разрешено ждать.
Поскольку при предоставлении запросов на блокировку нет мер предосторожности, некоторые транзакции могут быть заблокированы. Для обнаружения взаимоблокировок диспетчер блокировок периодически проверяет наличие циклов ожидания форграфа. Если система заблокирована, менеджер блокировок выбирает транзакцию жертвы из каждого цикла. Жертва прерывается и откатывается; а потом перезапустил позже. Некоторые методы, используемые для выбора жертвы:
- Выберите самую молодую транзакцию.
- Выберите транзакцию с наименьшим количеством элементов данных.
- Выберите транзакцию, которая выполнила наименьшее количество обновлений.
- Выберите транзакцию с минимальными издержками на перезапуск.
- Выберите транзакцию, которая является общей для двух или более циклов.
Этот подход в первую очередь подходит для систем с низким уровнем транзакций, где требуется быстрый ответ на запросы блокировки.
Обработка тупиковых ситуаций в распределенных системах
Обработка транзакций в распределенной системе баз данных также распределена, то есть одна и та же транзакция может обрабатываться более чем на одном сайте. Двумя основными проблемами обработки взаимоблокировок в системе распределенных баз данных, которых нет в централизованной системе, являются местоположение транзакции и управление транзакцией . Как только эти проблемы решаются, взаимоблокировки обрабатываются с помощью любого из предотвращения взаимоблокировок, предотвращения взаимоблокировок или обнаружения и удаления тупиков.
Местоположение транзакции
Транзакции в распределенной системе баз данных обрабатываются на нескольких сайтах и используют элементы данных на нескольких сайтах. Объем обработки данных неравномерно распределен между этими сайтами. Период времени обработки также варьируется. Таким образом, одна и та же транзакция может быть активной на некоторых сайтах и неактивной на других. Когда две конфликтующие транзакции находятся на сайте, может случиться, что одна из них находится в неактивном состоянии. Это условие не возникает в централизованной системе. Эта проблема называется проблемой местоположения транзакции.
Эта проблема может быть решена с помощью модели Daisy Chain. В этой модели транзакция несет определенные детали при перемещении с одного сайта на другой. Некоторые детали — это список необходимых таблиц, список требуемых сайтов, список посещенных таблиц и сайтов, список таблиц и сайтов, которые еще предстоит посетить, и список полученных блокировок с типами. После того, как транзакция завершается либо фиксацией, либо прерыванием, информация должна быть отправлена всем заинтересованным сайтам.
Контроль транзакций
Управление транзакциями связано с назначением и контролем сайтов, необходимых для обработки транзакции в распределенной системе баз данных. Существует много вариантов выбора места обработки транзакции и назначения центра управления, например:
- Один сервер может быть выбран в качестве центра управления.
- Центр контроля может перемещаться с одного сервера на другой.
- Ответственность за управление может быть разделена между несколькими серверами.
Распределенное предотвращение тупиковой ситуации
Так же, как в централизованном предотвращении взаимоблокировок, в подходе предотвращения распределенных взаимоблокировок транзакция должна получить все блокировки перед началом выполнения. Это предотвращает тупики.
Сайт, на который входит транзакция, обозначен как контролирующий. Контролирующий сайт отправляет сообщения на сайты, на которых расположены элементы данных, для блокировки элементов. Затем он ждет подтверждения. Когда все сайты подтвердят, что они заблокировали элементы данных, начинается транзакция. В случае сбоя какого-либо сайта или канала связи транзакция должна ждать, пока они не будут восстановлены.
Хотя реализация проста, у этого подхода есть некоторые недостатки —
-
Предварительное приобретение замков требует длительного времени для задержек связи. Это увеличивает время, необходимое для транзакции.
-
В случае сбоя сайта или ссылки транзакция должна долго ждать, чтобы сайты восстановились. Между тем на запущенных сайтах элементы заблокированы. Это может помешать выполнению других транзакций.
-
Если контролирующий сайт не работает, он не может связаться с другими сайтами. Эти сайты продолжают сохранять заблокированные элементы данных в заблокированном состоянии, что приводит к блокировке.
Предварительное приобретение замков требует длительного времени для задержек связи. Это увеличивает время, необходимое для транзакции.
В случае сбоя сайта или ссылки транзакция должна долго ждать, чтобы сайты восстановились. Между тем на запущенных сайтах элементы заблокированы. Это может помешать выполнению других транзакций.
Если контролирующий сайт не работает, он не может связаться с другими сайтами. Эти сайты продолжают сохранять заблокированные элементы данных в заблокированном состоянии, что приводит к блокировке.
Распределенное предотвращение тупиковой ситуации
Как и в централизованной системе, распределенное предотвращение взаимоблокировок обрабатывает взаимоблокировку до возникновения. Кроме того, в распределенных системах необходимо решить проблемы с расположением транзакций и управлением транзакциями. Из-за распределенного характера транзакции могут возникнуть следующие конфликты:
- Конфликт между двумя транзакциями на одном сайте.
- Конфликт между двумя транзакциями на разных сайтах.
В случае конфликта одна из транзакций может быть прервана или разрешена на ожидание в соответствии с распределенным алгоритмом ожидания или распределенным алгоритмом ожидания.
Предположим, что есть две транзакции, T1 и T2. T1 прибывает на сайт P и пытается заблокировать элемент данных, который уже заблокирован T2 на этом сайте. Следовательно, существует конфликт на сайте P. Алгоритмы следующие:
-
Распределенная рана
-
Если T1 старше, чем T2, T1 может ждать. T1 может возобновить выполнение после того, как Сайт P получит сообщение о том, что T2 либо зафиксировал, либо успешно прервал на всех сайтах.
-
Если T1 моложе, чем T2, T1 отменяется. Управление параллелизмом на сайте P отправляет сообщение всем сайтам, которые посетили T1, чтобы прервать T1. Контролирующий сайт уведомляет пользователя, когда T1 был успешно прерван на всех сайтах.
-
-
Распределенный Wait-Wait
-
Если T1 старше, чем T2, T2 необходимо прервать. Если T2 активен на сайте P, сайт P прерывает и откатывает T2, а затем передает это сообщение на другие соответствующие сайты. Если T2 покинул сайт P, но активен на сайте Q, сайт P сообщает, что T2 был прерван; Затем сайт L прерывает и откатывает T2 и отправляет это сообщение всем сайтам.
-
Если T1 младше, чем T1, T1 может ждать. T1 может возобновить выполнение после того, как узел P получит сообщение о том, что T2 завершил обработку.
-
Распределенная рана
Если T1 старше, чем T2, T1 может ждать. T1 может возобновить выполнение после того, как Сайт P получит сообщение о том, что T2 либо зафиксировал, либо успешно прервал на всех сайтах.
Если T1 моложе, чем T2, T1 отменяется. Управление параллелизмом на сайте P отправляет сообщение всем сайтам, которые посетили T1, чтобы прервать T1. Контролирующий сайт уведомляет пользователя, когда T1 был успешно прерван на всех сайтах.
Распределенный Wait-Wait
Если T1 старше, чем T2, T2 необходимо прервать. Если T2 активен на сайте P, сайт P прерывает и откатывает T2, а затем передает это сообщение на другие соответствующие сайты. Если T2 покинул сайт P, но активен на сайте Q, сайт P сообщает, что T2 был прерван; Затем сайт L прерывает и откатывает T2 и отправляет это сообщение всем сайтам.
Если T1 младше, чем T1, T1 может ждать. T1 может возобновить выполнение после того, как узел P получит сообщение о том, что T2 завершил обработку.
Распределенное обнаружение тупиковой ситуации
Точно так же, как и при централизованном обнаружении взаимоблокировок, взаимоблокировки могут возникать и удаляются при обнаружении. Система не выполняет никаких проверок, когда транзакция размещает запрос на блокировку. Для реализации созданы глобальные графы ожидания. Наличие цикла в глобальном графике ожидания указывает на взаимные блокировки. Однако трудно обнаружить взаимоблокировки, так как транзакция ожидает ресурсы по сети.
Альтернативно, алгоритмы обнаружения тупиков могут использовать таймеры. Каждая транзакция связана с таймером, который установлен на период времени, в течение которого ожидается завершение транзакции. Если транзакция не завершается в течение этого периода времени, таймер отключается, указывая на возможную тупиковую ситуацию.
Другим инструментом, используемым для обработки тупиков, является детектор тупиков. В централизованной системе есть один тупиковый детектор. В распределенной системе может быть более одного детектора тупиковой ситуации. Детектор взаимоблокировки может находить взаимоблокировки для сайтов, находящихся под его контролем. Существует три варианта обнаружения взаимоблокировок в распределенной системе, а именно:
Централизованный детектор тупиков — один сайт обозначен как центральный тупиковый детектор.
Иерархический детектор взаимоблокировки — ряд детекторов взаимоблокировки расположен в иерархии.
Распределенный детектор тупиков — Все сайты участвуют в обнаружении тупиков и их устранении.