Snowflake ID

Snowflake ID — это формат уникального идентификатора, используемый в распределённых системах для генерации уникальных, упорядодоченных по времени 64-битных целых чисел. Разработан компанией Twitter (социальная сеть, заблокирована на территории РФ) для внутреннего использования в сервисе микроблогов. Основное назначение Snowflake ID — обеспечение глобальной уникальности идентификаторов в масштабируемых системах без необходимости координации между узлами, а также поддержка естественной сортировки по времени создания.

История

Необходимость в создании собственного формата идентификаторов возникла в Twitter (социальная сеть, заблокирована на территории РФ) в начале 2010-х годов. Изначально сервис использовал для идентификации твитов последовательные 64-битные числа, генерируемые централизованно. Однако с ростом нагрузки и переходом к распределённой архитектуре такой подход стал узким местом: централизованный генератор не справлялся с потоком запросов, а его отказ мог парализовать работу всей системы.

В 2010 году инженеры Twitter (социальная сеть, заблокирована на территории РФ) представили решение — алгоритм Snowflake. Он позволял каждому узлу системы генерировать уникальные идентификаторы локально, без обращения к общему серверу. Формат был впервые описан в блоге компании в июне 2010 года. Впоследствии алгоритм лёг в основу многих аналогичных решений в других компаниях и открытых проектах, став де-факто стандартом для генерации распределённых идентификаторов.

Структура

Snowflake ID представляет собой 64-битное целое число без знака. Структура битового поля разбита на несколько частей, каждая из которых несёт определённую информацию. Классическая схема, используемая в Twitter (социальная сеть, заблокирована на территории РФ), включает четыре поля:

1. Знаковый бит (1 бит): Всегда равен 0. Зарезервирован для будущих расширений или для совместимости с системами, использующими знаковые целые числа. В большинстве реализаций не используется.
2. Метка времени (41 бит): Хранит количество миллисекунд, прошедших с заданной эпохи (например, с 1 января 2010 года 00:00:00 UTC). Это позволяет охватить период около 69 лет (2^41 миллисекунд). Именно эта часть обеспечивает упорядоченность идентификаторов по времени.
3. Идентификатор узла (10 бит): Уникальный номер сервера или процесса, генерирующего идентификатор. Обычно делится на две части: идентификатор дата-центра (5 бит, до 32 центров) и идентификатор рабочей машины внутри дата-центра (5 бит, до 32 машин). Это гарантирует уникальность идентификаторов, генерируемых одновременно на разных узлах.
4. Счётчик (12 бит): Последовательный номер, который увеличивается на 1 для каждого нового идентификатора, созданного в пределах одной миллисекунды на одном узле. Позволяет генерировать до 4096 (2^12) уникальных идентификаторов в миллисекунду на один узел.

Таблица структуры Snowflake ID

Принцип работы

Генерация Snowflake ID происходит на каждом узле системы независимо. Алгоритм работает следующим образом:

1. При получении запроса на создание идентификатора узел фиксирует текущее время в миллисекундах.
2. Если текущая миллисекунда совпадает с предыдущей, счётчик увеличивается на 1. Если счётчик достигает максимального значения (4095), узел ожидает наступления следующей миллисекунды.
3. Если текущая миллисекунда больше предыдущей, счётчик сбрасывается в 0.
4. Из полученных значений (метка времени, идентификатор узла, счётчик) формируется 64-битное число путём битового сдвига и логического сложения.
5. Сгенерированный идентификатор возвращается вызывающему коду.

Важной особенностью является то, что метка времени монотонно возрастает. Если системные часы на узле были переведены назад (например, из-за синхронизации времени по NTP), алгоритм может приостановить генерацию до тех пор, пока время не «догонит» последнее сохранённое значение, чтобы избежать дублирования идентификаторов.

Преимущества и недостатки

Преимущества

• Децентрализация: Каждый узел генерирует идентификаторы независимо, что устраняет единую точку отказа и повышает производительность.
• Упорядоченность по времени: Идентификаторы можно сортировать по времени создания, что удобно для индексации в базах данных (например, в B-деревьях).
• Компактность: 64-битный размер позволяет эффективно хранить и передавать идентификаторы, а также использовать их в качестве первичных ключей в большинстве СУБД.
• Простота реализации: Алгоритм не требует сложных вычислений или внешних сервисов.

Недостатки

• Зависимость от точности часов: Если системные часы на узле дают сбой или переводятся назад, это может привести к дублированию идентификаторов или остановке генерации.
• Ограниченная пропускная способность: Максимальная производительность одного узла составляет 4096 идентификаторов в миллисекунду. Для большинства приложений этого достаточно, но для высоконагруженных систем может потребоваться больше узлов.
• Предсказуемость: Поскольку идентификаторы содержат метку времени, злоумышленник может оценить время создания объекта, что в некоторых сценариях может быть нежелательным.
• Сложность управления узлами: Необходимо вести реестр идентификаторов узлов, чтобы избежать конфликтов.

Применение

Snowflake ID и его модификации широко применяются в распределённых системах, где требуется глобальная уникальность идентификаторов. Основные области использования:

• Социальные сети и мессенджеры: Генерация идентификаторов для сообщений, постов, комментариев, пользователей.
• Системы управления базами данных: В качестве первичных ключей для шардированных таблиц (например, в CockroachDB, YugabyteDB).
• Платформы электронной коммерции: Идентификация заказов, транзакций, товаров.
• Системы логирования и мониторинга: Присвоение уникальных номеров событиям и записям.
• Микросервисная архитектура: Создание идентификаторов для запросов и сообщений, передаваемых между сервисами.

Варианты и модификации

Оригинальный алгоритм Snowflake породил множество реализаций и адаптаций, как в виде открытых библиотек, так и в составе коммерческих продуктов. Некоторые из них:

• Sonyflake: Модификация от компании Sony, использующая 39 бит для метки времени и 16 бит для последовательного номера, что позволяет генерировать до 65536 идентификаторов в секунду.
• **Instagram (продукт Meta, признанной экстремистской и запрещённой в РФ) ID:** Алгоритм, используемый в Instagram (социальная сеть, принадлежит компании Meta, признанной экстремистской и запрещённой в РФ). Отличается распределением битов: 41 бит на метку времени, 13 бит на идентификатор шарда и 10 бит на счётчик.
• Discord Snowflake: Используется в мессенджере Discord. Имеет схожую структуру, но использует 42 бита для метки времени и 5 бит для идентификатора рабочего процесса.
• Boundary Flake: Вариант, в котором метка времени занимает 64 бита, а идентификатор узла и счётчик хранятся отдельно, что позволяет генерировать идентификаторы с более высокой точностью.

Источники

1. Twitter Engineering Blog, "Announcing Snowflake", June 2010.
2. Martin Kleppmann, "Designing Data-Intensive Applications", O'Reilly Media, 2017.
3. Instagram Engineering, "Sharding & IDs at Instagram", May 2012.
4. Discord Engineering, "How Discord Scaled to 100 Million Users", 2017.
5. Sony, "Sonyflake: A distributed unique ID generator", GitHub repository.