Архитектоника в ИТ

Lamport Timestamp

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

Контекст

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

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

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

Проблема

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

Решение

🗂 Иллюстрация шагов алгоритма приведена в заголовке статьи. 🔼 Клиенты A и B пытаются последовательно увеличить на 1 значение счетчика c в базе, изначально полагая, что значение этого счетчика равно 0. При обращении к базе каждый из клиентов отправляет свой уникальный идентификатор n.

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

🕚

name — имя последовательности;

🕚

node — уникальный идентификатор клиента;

🕚

value — последнее использованное значение последовательности.

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

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

CREATE TABLE counters (
 name text PRIMARY KEY,
 node uuid,
 value bigint
)

1️⃣ Увеличение счётчика

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

UPDATE counters SET
 node = <client UUID>,
 value = <new value> -- <old value> + 1
WHERE name = <seq name>
IF value = <old value>

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

2️⃣ Проверка счётчика

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

SELECT node, value
FROM counters
WHERE name = <seq name>

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

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

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

Плюсы

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

Минусы

При запросе диапазонов значений возможны некоторые пропуски из-за перезапуска клиента.

〰️

P.s. Сталкивались ли вы с подобной проблемой на практике и как её решали? 😉

#tip #db

Please open Telegram to view this post