Lamport Timestamp: генерация целочисленного идентификатора в распределённой БД без ACID-транзакций

В далёком 1978 году Leslie Lamport — американский учёный в области информатики и распределённых систем — предложил простой и эффективный способ определения порядка событий в распределённой системе. Позже этот алгоритм так и назвали: Lamport Timestamp. Давайте разберёмся, как данный алгоритм можно использовать на практике. В качестве примера рассмотрим прикладную задачу.

Существует таблица, где в качестве первичного ключа используется целочисленный идентификатор. Это типичная и привычная ситуация для монолитных баз данных (PostgreSQL, MySQL, MariaDB, Oracle, MS SQL и т.п.). Подобные базы имеют встроенный механизм автоматической генерации целочисленных идентификаторов, который можно подключить при создании таблицы. Те, кто впервые сталкивается с распределёнными базами, с удивлением обнаруживают, что многие из них не имеют подобной функциональности, также как и ACID-транзакций, а в качестве первичного ключа предлагают использовать UUID. Понятно, что такие ограничения имеют серьезные основания, связанные с производительностью и сложностью согласования изменений между репликами базы данных.

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

Один из вариантов решения — внешний генератор последовательности. Например, всё та же монолитная база (см. SEQUENCE); какой-либо координатор (ZooKeeper, etcd и т.п.); распределённые кэши (Redis, Hazelcast, Ignite и т.п.). Обычно используют то, что уже есть в окружении. Основной недостаток — счетчик может быть сброшен независимо от базы, в которой он используется. Например, в следствии восстановления базы из бэкапа.

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

В целевой базе данных создать таблицу counters с тремя колонками:

Таблица хранит именованные пары (node,value), которые и являются Lamport Timestamps.

В качестве примера будем использовать Apache Cassandra:

Каждый клиент знает имя последовательности, имеет уникальный идентификатор и хранит максимальное значение последовательности, о котором он знает. Для генерации нового значения выполняется UPDATE-запрос вида:

где <client UUID> — уникальный идентификатор клиента; <new value> — новое значение последовательности (например, полученное путем прибавления единицы к старому значению); <seq name> — имя последовательности; <old value> — старое значение последовательности, о котором знает клиент.

Пример конкретного UPDATE-запроса:

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

Для проверки успешности обновления счётчика выполняется SELECT-запрос:

Пример конкретного SELECT-запроса:

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

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

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

Наипростейшая реализация. База данных полностью самодостаточна и независима от внешних инструментов.

При запросе диапазонов значений возможны некоторые пропуски из-за остановки или перезапуска клиента. Например, два клиента запросили по 1000 значений. Один с 1 по 1000, другой с 1001 по 2000. Оба клиента создают записи в базе, но один из них был остановлен или перезапущен до того, как использовал все запрошенные значения. Неиспользованные значения будут потеряны навсегда, т.к. последовательность только увеличивается.

P.s. Если вам интересна данная тематика, присоединяйтесь к моей новостной ленте в Telegram или здесь. Буду рад поделиться опытом. ;-)