Доказано, что каждая снежинка имеет уникальную структуру. Разработчики Twitter вдохновились этим феноменом и изобрели Snowflake ID — целочисленный глобально-уникальный идентификатор.
Контекст и проблема
Проблематика хорошо описана в моём предыдущем посте про Lamport Timestamp, поэтому здесь сразу перейдём к основной части.
Решение
Структура 64-битного идентификатора (от старшего бита к младшему):
- Sign (1 бит). Знаковый бит.
- Timestamp (41 бит). Количество миллисекунд от какой-либо даты. Такой размерности хватит на 69 лет. Например, если за начало отсчета взять Unit Time Epoch, генерация без переполнения будет до 2039 года. Однако правую границу можно сместить, сместив вправо точку отсчета времени.
- Datacenter ID (5 бит). Идентификатор ЦОД (до 32 ЦОД).
- Machine ID (5 бит). Идентификатор узла в каждом ЦОД (до 32 машин).
- Machine Sequence Number (12 бит). Счётчик генераций, который сбрасывается каждую миллисекунду (4096000 генераций в секунду на каждом узле).
В зависимости от потребностей размерность полей может варьироваться. Например, если требуется более длительное хранение данных (более 69 лет), можно увеличить размерность поля Timestamp. Изменение на 1 бит изменяет диапазон в 2 раза (42 бита — 139 лет, 43 бита — 278 лет и т.д.; аналогично в обратную сторону). Изменить размерность полей можно за счет размерности счётчика генераций. Если в системе генерации редкие (и нет значительных всплесков), то 12 разрядов слишком много.
Для закрепления материала приготовил рабочий пример на Java. Он очень простой, его можно портировать на любой другой язык. Забирайте, улучшайте, делитесь опытом и впечатлениями. ;-)
Плюсы
- Скорость генерации.
- Автономность генерации.
- Растущая по времени последовательность.
- Компактный глобально-уникальный идентификатор (в 2 раза меньше UUID).
Помимо прочего, всё это создаёт благоприятные условия для использования Snowflake ID в качестве ключа для B-Tree. Напомню, ранее я делал исследование на тему выбора оптимального ключа для B-Tree. Поведение Snowflake ID будет идентично целочисленному идентификатору.
Минусы
- Ошибки или задержки генерации при прыжках времени назад. Неявно предполагается, что часы на рабочем узле всегда двигаются только вперед. Мы все знаем, что это не всегда так. Во-первых, так называемый Clock Drift характерен для любых часов. Часы работают с непостоянной частотой, которая в том числе зависит от нагрузки на систему. Во-вторых, Multi-Core/Multi-Socket серверы могут иметь отдельный таймер на каждое ядро, и они не обязательно синхронизированы друг с другом (см. Time on Multi-Core, Multi-Socket Servers). Вполне возможны случаи, когда последовательные обращения к Monotonic Clock (например, с помощью System.nanotime()) будут приводить к прыжкам во времени из-за того, что код выполнялся на разных ядрах. В общем случае на уровне прикладного кода выходом может служить механизм привязки к процессору (Process Affinity). Наконец, часы типа Time-of-Day благодаря NTP регулярно совершают прыжки во времени.
- Генерируемое множество не является множеством натуральных чисел. Иначе говоря, отсчет начинается не с 0 и далее по порядку, а с гораздо большего числа, которое обязано должно быть 64-разрядным.
- Возможны коллизии. Если два одновременно работающих узла будут иметь одинаковые Datacenter ID и Machine ID. Такое возможно, если один узел постепенно выводится из работы и заменяется своим "клоном".
- Раскрытие особенностей. Из идентификатора можно получить представление об инфраструктуре (количество ЦОД и узлов).
Похожие решения
На самом деле никто не запрещает адаптировать данный алгоритм к своим условиям. Одной из таких адаптаций является алгоритм Sonyflake.
***
P.s. Посмею напомнить, что у меня есть Telegram-канал "Архитектоника в ИТ", где я публикую материал на похожие темы примерно раз в неделю. Подписчики меня мотивируют, но ещё больше мотивируют живые дискуссии, ведь именно в них рождается истина. Поэтому подписывайтесь на канал или на мой блог здесь. Будем обмениваться опытом и мнениями. ;-)