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

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

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

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

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

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

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

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

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

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

Основной алгоритм

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

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

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

Успех

Если координатор получил сообщение о согласии от всех участников на этапе запроса на фиксацию:

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

Отказ

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

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

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

Coordinator                                          Participant
                             QUERY TO COMMIT
                 -------------------------------->
                             VOTE YES/NO             prepare*/abort*
                 <-------------------------------
commit*/abort*               COMMIT/ROLLBACK
                 -------------------------------->
                             ACKNOWLEDGEMENT          commit*/abort*
                 <--------------------------------  
end

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

Недостатки

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

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

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

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

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

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

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

Предполагаемое прерывание и предполагаемое завершение

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

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

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

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

См. также

Ссылки

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

[bernstein1987-1] Jump up to: ^а ^б ^с Филип А. Бернштейн , Вассос Хадзилакос, Натан Гудман (1987): Управление параллелизмом и восстановление в системах баз данных , Глава 7, Издательство Addison Wesley Publishing Company, ISBN 0-201-10715-5

[weikum2001-2] Jump up to: ^а ^б ^с ^д ^и ^ж Герхард Вейкум , Готфрид Воссен (2001): Транзакционные информационные системы , Глава 19, Elsevier, ISBN 1-55860-508-8

[Bern2009-3] Jump up to: ^а ^б ^с Филип А. Бернштейн, Эрик Ньюкомер (2009): Принципы обработки транзакций , 2-е издание, архивировано 7 августа 2010 г. в Wayback Machine , глава 8, Морган Кауфманн (Elsevier), ISBN 978-1-55860-623-4

[mohan1986-4] К. Мохан , Брюс Линдси и Р. Обермарк (1986): «Управление транзакциями в системе управления распределенными базами данных R *» , Транзакции ACM в системах баз данных (TODS) , том 11, выпуск 4, декабрь 1986 г., страницы 378–396

[mohan1983-5] К. Мохан , Брюс Линдси (1985): «Эффективные протоколы фиксации для модели дерева процессов распределенных транзакций» , Обзор операционных систем ACM SIGOPS , 19(2), с. 40–52 (апрель 1985 г.)

[raz1995-6] Йоав Раз (1995): «Протокол динамического двухфазного обязательства (D2PC)» , Теория баз данных - ICDT '95 , Конспект лекций по информатике , том 893/1995, стр. 162-176, Springer, ISBN 978-3-540-58907-5

[1]

[2]

[3]

[4]

[5]

[6]