Протокол двухфазной фиксации - Two-phase commit protocol

«2PC» перенаправляется сюда. О игре в американский и канадский футбол см. Двухточечное преобразование. Для криптографического протокола см. Схема обязательств.

В обработка транзакции, базы данных, и компьютерная сеть, то протокол двухфазной фиксации (2ПК) является разновидностью протокол атомарной фиксации (ACP). Это распределенный алгоритм который координирует все процессы, участвующие в распределенная атомарная транзакция о том, стоит ли совершить или же прервать (откатиться) сделка (это специализированный вид консенсус протокол). Протокол достигает своей цели даже во многих случаях временного сбоя системы (включая сбои процесса, сетевого узла, связи и т. Д.), Поэтому он широко используется.[1][2][3]Однако он не устойчив ко всем возможным конфигурациям сбоя, и в редких случаях для исправления ситуации требуется ручное вмешательство. Для обеспечения восстановления после сбоя (в большинстве случаев автоматически) участники протокола используют протоколирование состояний протокола. Записи журнала, которые обычно создаются медленно, но переживают сбои, используются протоколом. процедуры восстановления. Существует множество вариантов протоколов, которые в первую очередь различаются стратегиями ведения журналов и механизмами восстановления. Хотя процедуры восстановления обычно предназначены для нечастого использования, они составляют значительную часть протокола из-за множества возможных сценариев сбоя, которые должны учитываться и поддерживаться протоколом.

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

  1. В этап коммита-запроса (или же этап голосования), в котором координатор процесс пытается подготовить все участвующие в транзакции процессы (названные участники, когорты, или же рабочие), чтобы предпринять необходимые шаги для фиксации или прерывания транзакции и голосование, либо «Да»: зафиксировать (если выполнение локальной части участника транзакции завершилось должным образом), либо «Нет»: прервать (если была обнаружена проблема с локальной частью), и
  2. В фаза фиксации, в котором на основе голосование участников, координатор принимает решение о фиксации (только если все проголосовали «Да») или прервать транзакцию (в противном случае) и уведомить о результате всех участников. Затем участники выполняют необходимые действия (фиксация или прерывание) со своими локальными транзакционными ресурсами (также называемыми извлекаемые ресурсы; например, данные базы данных) и их соответствующие части в другом выводе транзакции (если применимо).

Обратите внимание, что протокол двухфазной фиксации (2PC) не следует путать с протоколом двухфазная блокировка (2PL) протокол, a контроль параллелизма протокол.

Предположения

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

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

Базовый алгоритм

Фаза запроса фиксации (или голосования)

  1. Координатор отправляет запрос на фиксацию сообщение всем участникам и ждет, пока не получит ответ от всех участников.
  2. Участники выполняют транзакцию до момента, когда их попросят зафиксировать. Каждый из них пишет запись в свой журнал отмены и вход в их журнал повторного выполнения.
  3. Каждый участник отвечает соглашение сообщение (участник голосов да совершить), если действия участника увенчались успехом, или прервать сообщение (участник голосов Нет, не совершать), если участник столкнулся с ошибкой, из-за которой совершить фиксацию невозможно.

Фаза фиксации (или завершения)

Успех

Если координатор получил соглашение Сообщение от все участники на этапе коммит-запрос:

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

Отказ

Если любой голоса участников Нет во время фазы запроса фиксации (или тайм-аута координатора истекает):

  1. Координатор отправляет откат сообщение всем участникам.
  2. Каждый участник отменяет транзакцию, используя журнал отмены, и освобождает ресурсы и блокировки, удерживаемые во время транзакции.
  3. Каждый участник отправляет подтверждение координатору.
  4. Координатор отменяет транзакцию после получения всех подтверждений.

Поток сообщений

Координатор Участник ЗАПРОС ДЛЯ ЗАВЕРШЕНИЯ --------------------------------> ГОЛОСОВАТЬ ДА / НЕТ подготовить * / отменить * <- ----------------------------- фиксация * / прерывание * COMMIT / ROLLBACK ------------- -------------------> ПОДТВЕРЖДЕНИЕ фиксация * / прерывание * <----------------------- ---------  конец

Значок * рядом с типом записи означает, что запись принудительно помещена в стабильное хранилище.[4]

Недостатки

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

Реализация протокола двухфазной фиксации

Общая архитектура

Во многих случаях протокол 2PC распространяется в компьютерной сети. Его легко распространять, реализуя несколько выделенных 2PC-компонентов, похожих друг на друга, обычно называемых Менеджеры транзакций (TM; также именуемые 2PC агенты или мониторы обработки транзакций), которые выполняют выполнение протокола для каждой транзакции (например, Открытая группа с X / Открыть XA ). Базы данных, участвующие в распределенной транзакции, участники, как координатор, так и участники, регистр для закрытия TM (обычно находящихся на соответствующих узлах сети, что и участники) для завершения транзакции с использованием 2PC. Каждая распределенная транзакция имеет специальный набор TM, TM, в которых регистрируются участники транзакции. Лидер, TM координатора, существует для каждой транзакции, чтобы координировать для нее 2PC, обычно TM базы данных координатора. Однако роль координатора может быть передана другому TM по причинам производительности или надежности. Вместо того, чтобы обмениваться сообщениями 2PC между собой, участники обмениваются сообщениями со своими соответствующими TM. Соответствующие TM взаимодействуют между собой, чтобы выполнить указанную выше схему протокола 2PC, «представляющую» соответствующих участников для завершения этой транзакции. В этой архитектуре протокол полностью распределен (не требует какого-либо компонента центральной обработки или структуры данных) и эффективно масштабируется с увеличением количества сетевых узлов (размера сети).

Эта общая архитектура также эффективна для распространения других протоколы атомарных обязательств кроме 2PC, поскольку все такие протоколы используют один и тот же механизм голосования и передачи результатов участникам протокола.[1][2]

Оптимизация протокола

База данных было проведено исследование способов получить большую часть преимуществ протокола двухфазной фиксации при одновременном сокращении затрат за счет оптимизация протокола[1][2][3] и сохранение протокольных операций при определенных предположениях о поведении системы.

Предполагаемое прерывание и предполагаемая фиксация

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

Протокол двухфазной фиксации дерева

В Дерево Протокол 2PC[2] (также называемый Вложенный 2PC, или же Рекурсивный 2PC) - распространенный вариант 2PC в компьютерная сеть, который лучше использует базовую коммуникационную инфраструктуру. Участники распределенной транзакции обычно вызываются в порядке, определяющем древовидную структуру, дерево вызовов, где участники - это узлы, а ребра - это вызовы (каналы связи). Это же дерево обычно используется для завершения транзакции по протоколу 2PC, но в принципе для этого может использоваться и другое дерево связи. В дереве 2PC координатор считается корнем («вершиной») дерева связи (инвертированное дерево), а участники - другими узлами. Координатором может быть узел, который инициировал транзакцию (рекурсивно (транзитивно) вызываемый другими участниками), но также другой узел в том же дереве может взять на себя роль координатора. Сообщения 2PC от координатора распространяются «вниз» по дереву, в то время как сообщения координатору «собираются» участником от всех участников ниже него, прежде чем он отправит соответствующее сообщение «вверх» по дереву (за исключением прервать сообщение, которое распространяется "вверх" сразу после его получения или если текущий участник инициирует прерывание).

В Динамическая двухфазная фиксация (Динамическое двухфазное обязательство, D2PC) протокол[2][6] это вариант Tree 2PC без заранее определенного координатора. Он включает несколько оптимизаций, которые были предложены ранее. Соглашение Сообщения (да голосов) начинают распространяться со всех листьев, каждый лист при выполнении своих задач от имени транзакции (становится готовы). Промежуточный (не листовой) узел отправляет готовы когда соглашение сообщение последнему (единственному) соседнему узлу, из которого соглашение сообщение еще не получено. Координатор определяется динамически гонками соглашение сообщения по дереву транзакций в том месте, где они сталкиваются. Они сталкиваются либо в узле дерева транзакций, чтобы быть координатором, либо на краю дерева. В последнем случае один из двух узлов ребра выбирается координатором (любой узел). D2PC является оптимальным по времени (среди всех экземпляров определенного дерева транзакций и любой конкретной реализации протокола Tree 2PC; все экземпляры имеют одно и то же дерево; каждый экземпляр имеет другой узел в качестве координатора): при выборе оптимального координатора D2PC фиксирует оба координатора и каждый участник за минимально возможное время, что позволяет как можно раньше высвободить заблокированные ресурсы каждого участника транзакции (узел дерева).

Смотрите также

Рекомендации

  1. ^ а б c Филип А. Бернштейн, Вассос Хадзилакос, Натан Гудман (1987): Контроль параллелизма и восстановление в системах баз данных, Глава 7, Издательство Addison Wesley Publishing Company, ISBN  0-201-10715-5
  2. ^ а б c d е ж Герхард Вейкум, Готфрид Фоссен (2001): Системы транзакционной информации, Глава 19, Elsevier, ISBN  1-55860-508-8
  3. ^ а б c Филип А. Бернштейн, Эрик Ньюкомер (2009): Принципы обработки транзакций, 2-е издание В архиве 2010-08-07 на Wayback Machine, Глава 8, Морган Кауфманн (Эльзевьер), ISBN  978-1-55860-623-4
  4. ^ К. Мохан, Брюс Линдси и Р. Обермарк (1986): «Управление транзакциями в системе управления распределенной базой данных R *»,Транзакции ACM в системах баз данных (TODS), Volume 11 Issue 4, декабрь 1986, страницы 378 - 396
  5. ^ К. Мохан, Брюс Линдси (1985): «Эффективные протоколы фиксации для модели дерева процессов распределенных транзакций»,Обзор операционных систем ACM SIGOPS, 19 (2), с. 40-52 (апрель 1985)
  6. ^ Йоав Раз (1995): «Протокол динамического двухфазного обязательства (D2PC)»,Теория баз данных - ICDT '95, Конспект лекций по информатике, Volume 893/1995, pp. 162-176, Springer, ISBN  978-3-540-58907-5

внешняя ссылка