Calvin Protocol для распределенных транзакций

Многие знают про протокол двухфазной фиксации (two-phase commit, 2PC), но мало кто слышал про протокол Calvin. Честно говоря, до недавних пор я тоже относился к этому меньшинству, поэтому решил поделиться своей находкой с вами. Однако для начала предлагаю освежить память и вспомнить про распределенные транзакции и 2PC. :)

Распределенная транзакция - это транзакция, затрагивающая несколько ресурсов распределенной системы. Как и обычные транзакции в монолитных базах данных, распределенные действуют по принципу “всё или ничего”. Тематика достаточно стара, хорошо проработана, отражена в стандарте X/Open XA (1991), который реализован на многих платформах. Таким образом, концепция распределенных транзакций появилась задолго до появления шумихи вокруг микросервисов, но сейчас особенно актуальна и рассматривается как возможный инструмент обеспечения согласованности данных.

2PC

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

В протоколе описаны три три типа компонента:

• клиентское приложение (application);
• координатор транзакций (transaction manager);
• владелец ресурса (resource manager).

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

Процесс фиксации транзакции состоит из следующих шагов.

• Начало транзакции. Координатор отправляет всем владельцам команду “приготовиться” (prepare), передавая сведения о транзакции и производимых изменениях.

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

• Фаза фиксации. Если все владельцы подтвердили свою готовность произвести изменения, координатор отправляет им команду “фиксировать” (commit). Если кто-то ответил отказом, все получают команду “откатить” (rollback).

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

Главными преимуществами 2PC является его прикладная универсальность и относительная простота реализации. Главными недостатками 2PC являются длительные блокировки, неустойчивость к сбоям, отсутствие изоляции. Существует необходимость дождаться подтверждения от всех владельцев; возможно недетерминированное поведение в случае отказа координатора, который является узким местом всего алгоритма; имеется ненулевая вероятность получить промежуточное состояние системы. Вместе с этим блокировки все-таки локальны по отношению к ресурсу и не мешают конкурентному выполнению транзакций (в отличие от Calvin).

Calvin

В 2012 была опубликована статья “Calvin: Fast Distributed Transactions for Partitioned Database Systems” с описанием нового подхода к реализации распределенных транзакций. В его основу положена идея формирования журнала транзакций и подачи его на вход исполнителю, вместо того чтобы позволить ему самому формировать журнал. (Под исполнителем понимается какой-то ресурс, например, реплика базы данных.) Такой подход позволяет уменьшить число сетевых взаимодействий, обеспечив высокую скорость выполнения распределенных транзакций.

Подход был назван не в честь производителя трусов, как можно было бы подумать изначально, а в честь французского богослова Жана Кальвина (Jean Calvin), считавшего, что все события человеческой жизни предопределены Богом. Ведь если журнал сформирован заранее, то и результат исполнения транзакций из этого журнала предопределён.

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

Таким образом можно обозначить следующие особенности подхода:

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

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

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

Резонный вопрос: есть ли практические реализации и опыт использования этого подхода? Да, есть. Например, разработчики Apache Cassandra разрабатывают совместимый продукт под названием Accord. Он должен позволить выполнять запросы к Cassandra, объединяя их в ACID-транзакции. Однако гораздо бо́льших успехов добились разработчики YDB, о чём можно почитать в их официальном блоге.