Недавно в хабе Serverless вышла статья Бессерверная альтернатива традиционным базам данных от @olalala. В комментариях к статье пользователи просили рассказать о Calvin — подходе, который используется внутри Yandex Database. Нам понравилась эта идея и я решил коротенько рассказать об этом.

Calvin — это подход к фиксации транзакций, который позволяет сохранить принципы ACID в распределенных системах без потери производительности. Впервые он был упомянут в работе Йельского университета в 2012 году. Calvin хорошо вписывается в целый класс бессерверных СУБД. Мы знаем как минимум две системы, в которых он используется: Yandex Database и FaunaDB, но, возможно, есть и другие.

Двухфазный коммит — основная проблема традиционных распределенных СУБД

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

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

2. Если все узлы выполнили транзакцию, координатор отправляет им команду зафиксировать изменения, то есть сделать их постоянными.

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

С точки зрения распределенных систем, в таком подходе есть две большие проблемы:

• Очень много «общения» между координатором и узлами. Распределенные СУБД, как правило, находятся в нескольких ЦОД, которые расположены в разных регионах или странах. Поэтому, чем больше узлы «общаются» между собой, тем больше сетевые задержки.

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

Тут можно вспомнить про системы NoSQL, которые решают проблему низкой производительности, но жертвуют всеми или многими принципами ACID.

Принципы Calvin и детерминированные базы данных

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

Но чтобы это сработало, планы транзакций должны быть детерминированными. Это означает, что система должна быть «уверена» в том, что один и тот же план на разных узлах приведет к одинаковому результату, и в конечном итоге реплики будут находиться в одинаковом состоянии. Calvin достигает такого состояния с помощью двух подходов:

• Соглашение о том, какие транзакции и в каком порядке выполнять. Это своего рода глобальная очередь, которая формируется до того, как узлы начнут обрабатывать транзакции.

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

Но что будет, если во время выполнения транзакции один из узлов не сможет зафиксировать изменения? Это может произойти по следующим причинам:

• Недетерминированные причины. События, которые не зависят от логики транзакции: выход узла из строя на аппаратном или программном уровне или проблемы с сетью.

• Детерминированные причины. Проблемы в логике транзакции, например повтор первичного ключа, нарушение ссылочной целостности или уникальности.

В традиционных СУБД любая из этих причин приведет к отмене всей транзакции. При этом все остальные узлы, которые отработали корректно, тоже должны будут отменить транзакцию. На этот сеанс «общения» уходит дополнительное время.

В случае с Calvin и детерминированными системами, недетерминированное событие не отменяет транзакцию целиком. Все узлы, кроме отказавшего, выполняют команды по утвержденному плану. А проблемный узел после восстановления «накатит» изменения по своему же плану или по логам другого узла.

Архитектура Calvin

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

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

2. Уровень планирования (scheduler). Система использует детерминированный протокол блокировки для управления выполнением транзакции. Это гарантирует, что транзакции будут выполнены строго в том порядке, в котором они были запланированы на уровне упорядочивания.

3. Уровень хранения (storage). Система обрабатывает всю физическую структуру данных. К Calvin можно подключить любой механизм хранения с базовым интерфейсом CRUD.

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

Параллелизм, блокировки и ожидание диска

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

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

Чтобы избавиться от этой задержки, Calvin старается убедиться, что транзакции не удерживают блокировки и не ожидают дискового ввода-вывода. Для этого каждый раз, когда sequencer получает запрос на транзакцию, которая может вызвать остановку диска, он:

• создает искусственную задержку перед отправкой запроса на уровень планирования;

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

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

В заключение

В заключение стоит добавить, что подход Calvin хорошо вписывается в распределенные высоконагруженные системы. Мы уже говорили, что используем его в нашей бессерверной СУБД Yandex Database. Вы можете бесплатно попробовать ее на нашей платформе. В рамках free tier вы каждый месяц получаете первый миллион операций (в единицах Request Unit) и первый гигабайт хранения данных бесплатно. Этого вполне достаточно, чтобы протестировать технологию или даже запустить пет-проект.

Кроме того, если вам интересна экосистема Serverless-сервисов и все, что с этим связано, заходите в наше сообщество в Telegram, где можно обсудить serverless в целом.

П.С. Кстати, новый сервис экосистемы Serverless Yandex Data Streams вышел в стадии Preview. С помощью Data Streams вы можете настраивать потоки данных, их обработку и поставку данных в системы хранения Yandex.Cloud без написания кода. Подробнее можно почитать тут.