Распределенные транзакции — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показано 13 промежуточных версий 2 участников)
Строка 1: Строка 1:
== Набор требований к распределенным базам данных, которых хотят достигнуть ==
+
Участвует несколько узлов. Транзакция должна быть либо зафиксирована на всех узлах, либо на всех откачена. Бывают сбои как самих участников, так и каналов коммуникаций между ними.<br>
=== Требования по децентрализации ===
+
*Локальная независимость - узел должен функционировать даже в изоляции
+
== Задача двух генералов ==
(имеется в виду отвечать как на запросы на чтение, так и на изменение).<br>
+
 
* Отсутствие центрального узла, так как при его наличии и отключении не выполнится локальная независимость.<br>
+
=== Описание ===
* Непрерывное функционирование;<br>
+
 
** Надежность;<br>
+
[[Файл:Distributed TwoGenerals.png|300px|right]]
** Доступность.<br>
+
 
=== Требования по прозрачности ===
+
Две армии, каждая руководимая своим генералом, готовятся к штурму города. Лагеря этих армий располагаются на двух холмах, разделённых долиной. Единственным способом связи между генералами является отправка посыльных с сообщениями через долину. Но долина занята противником и любой из посыльных может быть перехвачен. Проблема заключается в том, что, генералы заранее (пока была связь) приняли принципиальное решение о штурме, но не согласовали точное время штурма.
* Независимость от расположения;<br>
+
 
** Программы могут работать на любом узле (данные действительно хранятся распределенно в отличие от репликации);<br>
+
Для успешного штурма генералы должны атаковать город одновременно. Штурм, предпринятый только одной армией, приведет к катастрофическим последствиям для атакующих. Требуется найти алгоритм обмена сообщениями, после которого каждый генерал был бы уверен, что они оба атакуют в указанное время.
** Удаленный доступ к данным (должны уметь сделать любой запрос на любом узле);<br>
+
 
Распределенная БД должна логически себя вести как одна большая БД.<br>
+
=== Вероятностное решение ===
=== Независимость от фрагментации ===
+
Послать гонца, засечь время и ждать подтверждения. Если по истечению времени гонец не вернулся, посылаем следующего.<br>
* Программы не знают на каком узле находятся данные.<br>
+
 
* Унифицированный доступ к данным.<br>
+
=== Доказательство отсутствия гарантированного решения ===
* Географическое секционирование.<br>
+
Пусть существует конечный протокол, тогда существует минимальное по включению множество сообщений. Пусть последнее сообщение не доставлено, тогда принять решение нельзя.<br>
=== Независимость от репликации ===
+
 
* Автоматическая поддержка репликации.<br>
+
 
* Выбор узла для обновления.<br>
+
== Протокол двухфазной фиксации ==
=== Распределенные транзакции ===
+
 
* Поддержка распределенных запросов.<br>
+
Протокол двухфазной фиксации (фаза подготовки и фаза фиксации) нужен для того, чтобы при завершении транзакции все изменения, произведенные над всеми ресурсами, либо полностью фиксировались, либо полностью откатывались. После завершения транзакции результат сообщается всем участникам.
** Один запрос получает данные с разных узлов;<br>
+
 
** Несколько узлов могут участвовать в одной транзакции;<br>
+
=== Описание алгоритма ===
** Должна быть согласованность фиксаций и отката.<br>
+
 
* Независимость от окружения.<br>
+
[[Файл:Двухфазная_фиксация.png|600px|right]]
** От аппаратуры, то есть должны быть унифицированное представление данных;<br>
+
Один из узлов выбирается координатором, обычно узел, к которому пришел исходный запрос.<br>
** От ОС, то есть должна быть конвертация данных и поддержка разных ОС;<br>
+
В реальности в системе могут исполняться параллельно несколько транзакций, у которых разные координаторы.<br>
** От сети, например, в дата центрах будет быстрая локальная связь;<br>
+
 
** От типа СУБД, хотелось бы уметь делать распределенную БД, которая обслуживается разными системами управления БД (Oracle, Postgres, etc). Но в реальности все очень печально.<br>
+
 
 +
 
 +
==== Первая фаза ====
 +
* Координатор всем участникам посылает сообщение приготовиться к коммиту;<br>
 +
* Узлы, участвующие в транзакции, присылают информацию что они готовы зафиксировать данные, что нет несогласованности в данных, ничего не сломалось;<br>
 +
* Когда координатор подтверждение от всех, он принимает решение;<br>
 +
* Если от всех узлов было положительное решение, то он примет решение выполнить.<br>
 +
 
 +
==== Вторая фаза ====
 +
* Координатор всем участникам пришлет свое положительное решение, а они ему присылают информацию в ответ, что запрос был выполнен.<br>
 +
 
 +
После завершения второй фазы, когда было получен положительный  ответ от всех участников, координатор говорит, что транзакцию была завершена и шлет это в ответ на исходный запрос.<br>
 +
 
 +
У реплики есть момент неопределенности: между моментом, как была послана информация, что данные готовы быть зафиксированы, но ответ от координатора, что делать с транзакцией, еще не пришел.<br>
 +
 
 +
=== Обработка сбоев координатора ===
 +
* До принятия решения {{---}} транзакция должна быть откачана.<br>
 +
* При принятии решении координатор сразу же записывает его в transaction log и при восстановении он вспомнит о принятом решении и исполнит его.<br>
 +
 
 +
=== Обработка сбоев участников ===
 +
* До отправки готовности координатору {{---}} откат после восстановления;<br>
 +
* До получения решения {{---}} запрашивает у координатора;<br>
 +
* При получении решения {{---}} записывает в transaction log;<br>
 +
* После получения решение {{---}} выполняет решение, отправляет подверждение, записывает в transaction log.<br>
 +
 
 +
Данные обработки все работает при краткосрочных сбоях, однако, так как в общем случае задача неразрешима, существуют вырожденные случаи последовательных сбоев в коммуникации, которые не позволят ни координатору, ни участнику продвинуться.
 +
 
 +
=== Улучшение протокола ===
 +
 
 +
Координатору требуется помнить решение между принятием и подтверждениями исполнения.<br>
 +
 
 +
====Протокол предполагаемой фиксации====
 +
* При решении «фиксировать» {{---}} «забыть» транзакцию.<br>
 +
* Неизвестная транзакция {{---}} фиксировать.<br>
 +
 
 +
Работает, когда количество фиксированных транзакций сильно превышает количество откаченных, экономим таким образом память.<br>
 +
 
 +
Может произойти ложная фиксация.<br>
 +
 
 +
Сбой на первой фазе.<br>
 +
 
 +
Если происходит «потеря» транзакции, а информация не была записана в лог, то участникам придет ответ «фиксировать»<br>
 +
 
 +
====Протокол предполагаемого отката====
 +
* При решении «откатить» {{---}} «забыть» транзакцию.<br>
 +
* Неизвестная транзакция {{---}} откатить.<br>
 +
 
 +
Не можем случайно зафиксировать транзакцию {{---}} надежнее.<br>
 +
 
 +
Тратим гораздо больше памяти, но не всегда это критично.<br>

Текущая версия на 19:06, 4 сентября 2022

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

Задача двух генералов

Описание

Distributed TwoGenerals.png

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

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

Вероятностное решение

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

Доказательство отсутствия гарантированного решения

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


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

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

Описание алгоритма

Двухфазная фиксация.png

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


Первая фаза

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

Вторая фаза

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

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

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

Обработка сбоев координатора

  • До принятия решения — транзакция должна быть откачана.
  • При принятии решении координатор сразу же записывает его в transaction log и при восстановении он вспомнит о принятом решении и исполнит его.

Обработка сбоев участников

  • До отправки готовности координатору — откат после восстановления;
  • До получения решения — запрашивает у координатора;
  • При получении решения — записывает в transaction log;
  • После получения решение — выполняет решение, отправляет подверждение, записывает в transaction log.

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

Улучшение протокола

Координатору требуется помнить решение между принятием и подтверждениями исполнения.

Протокол предполагаемой фиксации

  • При решении «фиксировать» — «забыть» транзакцию.
  • Неизвестная транзакция — фиксировать.

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

Может произойти ложная фиксация.

Сбой на первой фазе.

Если происходит «потеря» транзакции, а информация не была записана в лог, то участникам придет ответ «фиксировать»

Протокол предполагаемого отката

  • При решении «откатить» — «забыть» транзакцию.
  • Неизвестная транзакция — откатить.

Не можем случайно зафиксировать транзакцию — надежнее.

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