Предисловие

Недавно прочитал очередную статью из серии: "мы лучше двухфазного коммита". Здесь я не буду анализировать содержания этой статьи (хотя, подумываю о том, чтобы дать развернутый анализ). Задача моего опуса — предложить самый эффективный вариант распределенного коммита с точки зрения временных задержек. Конечно, такой коммит дается высокой ценой. Однако цель — дать оценку и показать, что двухфазный коммит не является тормозным, как многие считают.

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

После такого предисловия приступим.

Введение

Определение. RTT — время сообщения туда и обратно.
Определение. Хоп — время одной пересылки.

Теорема. Время 1 RTT равно времени двух хопов.
Доказательство. Это очевидно.

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

Определение. Двухфазный коммит — это коммит из двух фаз. Первая фаза — атомарная операция по проверке возможности начала транзакции и блокировки участников коммита. Вторая фаза — сбор ответов от участников и применение транзакции с отпусканием блокировок.

Теорема. Двухфазный распределенный коммит нельзя сделать быстрее, чем 1 RTT.
Доказательство. Для проведения двухфазного коммита необходимо, как минимум, отослать запрос от клиента до всех участников и получить ответ о завершении. Для этого необходимо 2 хопа или 1 RTT.

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

Теорема. Двухфазный отказоустойчивый распределенный коммит за 1 RTT возможен.

Для доказательства этой теоремы, достаточно привести способ и условия, когда это возможно. Понятно, что такое возможно далеко не всегда, т.к. в случае конкурентного доступа распределенных транзакций к одному и тому же ресурсу, такие транзакции должны выстраиваться в очередь к этому ресурсу. А значит — будут исполняться последовательно. В этом случае говорить об 1 RTT будет несколько забавно. Тем не менее, даже обычные алгоритмы при благоприятных условиях дают времена заметно больше 1 RTT.

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

Двухфазный коммит

Рассмотрим классическую схему двухфазного коммита с координатором.

Последовательность выглядит следующим образом:

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

Итого 3 RTT.

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

Лемма. Распределенный консенсус на основе лидера нельзя совершить быстрее 1 RTT.
Доказательство. Для достижения консенсуса запрос должен быть направлен на лидера. При этом:

1-й хоп. Лидер отсылает запрос другим участникам консенсуса (follower).
2-й хоп. Участники отсылают подтверждение лидеру.
Без этих фаз консенсус невозможен.

Лемма. Консенсус возможен за 1 RTT.
Доказательство: возьмем алгоритм Raft. В случае живости лидера и большинства участников консенсуса принятие согласованного решения на лидере происходит после получения ответов от участников, т.е. спустя 1 RTT.

Определение. Принятие согласованного решения консенсус группы называется соглашением.

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

Эту теорему можно обобщить, доказав, что невозможно достичь консенсуса быстрее 1 RTT, выкинув условие о наличии лидера. Однако это выходит за рамки данной статьи. Идея доказательства состоит в рассмотрении распространения знания о других участниках системы и наличия у них соответствующего сообщения: за 1 хоп можно только отослать данные, но не узнать, дошли ли они и какое при этом состояние было у получателя.

Итак, для отказоустойчивости возьмем консенсус с 1 RTT и добавим в наш двухфазный коммит:

1-й хоп. Клиент отправляет запрос лидеру координатора.
2-й и 3-й хоп. Лидер координатора согласует начало транзакции.
4-й хоп. Координатор транзакций отправляет запрос лидерам участников на блокировку — 1-я фаза.
5-й и 6-й хоп. Участники успешно берут блокировки с сохранением знания в своих консенсус группах.
7-й хоп. Лидеры участников отправляют ответ, что они готовы для проведения транзакций.
8-й и 9-й хоп. Лидер координатора согласует информацию обо всех участниках системы.
10-й хоп. Лидер координатора рассылает всем лидерам участников сообщение о применении операций — 2-я фаза.
11-й и 12-й хоп. Лидеры согласуют коммит и применяют изменения.
13-й хоп. Участники рапортуют об успешности применения лидеру координатора.
14-й хоп. Координатор отвечает клиенту.

Итого 7 RTT. Неплохо. Отказоустойчивость стоит "всего лишь" 4 RTT. Они возникают из-за того, что координатор и участники по 2 раза последовательно приходят каждый к своему консенсусу, на что и тратится это время.

В приведенной схеме можно заметить некоторые неоптимальности. Давайте их устранять.

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

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

Заключается он в том, что на самом деле координатор принимает окончательное решение о том, коммитить окончательную транзакцию или нет. Т.е. даже если все участники сказали ОК, но какой-то участник затупил по причине, например, смены лидера, то координатор имеет полное право откатить транзакцию. А раз так, то можно убрать только 10-13 хопы, но не 8-й и 9-й. Но и это уже неплохо, так как мы имеем уменьшение на 2 RTT, т.е. 5 RTT вместо 7.

При этом 10-13 хопы никуда не деваются, просто клиенту не нужно их ждать. Координатор и участники будут доделывать свои дела параллельно с клиентом. А клиент получит свое подтверждение несколько раньше. Эти знания обязательно будут в системе, просто несколько позже. Тут мы используем магию асинхронности, консенсуса и невозможности доказать внешнему участнику, что мы немного смухлевали и срезали угол. Т.е. если клиент внезапно захочет сразу же прочитать данные, которые мы только что закоммитили и пойдет сразу к какому-то участнику, то наткнется на блокировку (если она не была снята к тому времени 2-й фазой), и этот запрос подвиснет до момента ее снятия. Однако нас в рамках наших теоретических изысканий данный факт абсолютно не важен, т.к. мы себе готовим идеальные условия. А в случае неидеальных, как уже было сказано выше, мы будем ждать несколько вечностей (т.к. консенсус потребует вечность, а нам надо провести их несколько, причем последовательно).

Следующий ход конем несколько сложнее и элегантнее.

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

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

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

Оптимизация консенсуса

Казалось бы, что тут можно оптимизировать? Ведь мы с Raft достигаем минимально возможного времени исполнения — 1 RTT. На самом деле можно быстрее — за 0 RTT.

Для этого вспомним, что помимо самого консенсуса требуется еще 1 RTT для отсылки запроса от клиента до лидера и получение ответа. Т.е. для удаленной группы консенсуса требуется в этом случае 2 RTT, что мы и видим в двухфазном коммите на 2-х примерах: отсылка и коммит на координаторе, отсылка и коммит на участниках. Итого сразу 4 RTT, и еще 1 RTT — на коммит второй фазы на координаторе.

Понятно, что консенсус на основе лидера для удаленного клиента никак не может быть быстрее 2 RTT. В самом деле, сначала нам требуется доставить сообщение до лидера, а затем лидер обязан уже переслать участникам группы и получить от них ответ. Без вариантов.

Единственный вариант — это избавиться от слабого звена — лидера. Действительно, мало того, что все записи должны проходить через него, так и в случае его падения группа становится недоступной достаточно продолжительное время. Лидер консенсуса есть самое слабое звено, и восстановление лидера — самая хрупкая и нетривиальная часть консенсуса. Поэтому надо просто от него избавиться.

Определение. Броадкаст сообщения — это посылка одного и того же сообщения всем участникам группы.

Для этого возьмем широко известный в узких кругах консенсус без мастера. Основная идея заключается в том, чтобы броадкастами добиться одинакового состояния на участниках. Для этого достаточно сделать 2 броадкаста, т.е. как раз 1 RTT. Первый броадкаст до участников системы может сделать сам клиент. Ответные броадкасты от участников могут дойти и до клиента. Если клиент видит одинаковое состояние (а он это увидит это в случае, например, отсутствия конкурентных запросов), то он на анализе содержимого ответных броадкастов сможет понять, что его запрос будет закоммичен рано или поздно. По факту, используя такой алгоритм, все участники консенсуса, включая клиента, одновременно осознают, что запрос был закоммичен. И это произойдет после 2 броадкастов, т.е. 1 RTT. Т.к. клиент все равно должен потратить 1 RTT на отсылку сообщения группе и получения ответа, то мы имеем парадоксальный вывод, что консенсус эффективно произошел за 0 RTT.

Аналогия

Чтобы пойти дальше, воспользуемся мощнейшим инструментом анализа — аналогией. Вернемся к Raft алгоритму. Что в нем происходит? Он состоит из двух фаз:

1-я фаза: лидер отсылает запрос участникам и ожидает ответа.
2-я фаза: после ответа лидер принимает согласованное решение единолично и отсылает его участникам системы.

Ничего не напоминает? Правильно, это и есть двухфазный коммит, только с некоторыми оговорками:

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

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

Соответственно, все что нам нужно, это отказаться от координатора в двухфазном коммите, т.е. сделать в точности то же самое, что мы сделали и для консенсуса, отказавшись от лидера.

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

Самокоординация

Определение. Двухфазный коммит без координатора состоит из 2-х фаз:

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

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

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

Определение. Самокоординирующиеся транзакции — транзакции, не требующие выделенного координатора.

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

Теорема. Самокоординирующиеся транзакции дают строгую консистентность (strict consistency = linearizability + serializability).
Доказательство. Собственно, доказательство основано на том простом факте, что двухфазный коммит также предоставляет такую гарантию. Действительно, в схеме без координатора каждый участник сам себе является координатором, т.е. там проходит двухфазный коммит как будто он и является самым главным. А значит, сохраняет все инварианты двухфазного коммита. В этом легко убедиться, если вспомнить, что каждый участник рассылает броадкастом ответы всем остальным. Т.е. каждый получает ответы ОК от всех остальных, выполняя роль координатора для совершения коммита транзакции.

Опишем минимальное количество хопов при благоприятном стечении обстоятельств:
1-й хоп. Клиент отсылает сообщение всем участникам транзакции.
2-й хоп. Все участники пересылают клиенту и друг другу ответ.

После 2-го хопа у клиента есть вся необходимая информация, чтобы принять решение о коммите. Таким образом требуется всего 1 RTT для коммита.

Отказоустойчивость и доступность

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

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

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

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

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

Алгоритм коммита будет выглядеть следующим образом:

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

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

Выводы

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

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

Литература

Michael J. Fischer, Nancy A. Lynch, and Michael S. Paterson, 1983,
Impossibility of distributed consensus with one faulty process

G. Demchenko, 2016, Masterless Consensus Algorithm

Jim Gray, Leslie Lamport, 2003, Consensus on Transaction Commit