Генератор ідентифікаторів Snowflake - Створення унікальних розподілених ідентифікаторів

Що таке генератор ідентифікаторів Snowflake?

Генератор ідентифікаторів Snowflake створює унікальне 64-бітове число з часової мітки, ідентифікатора машини та порядкового номера. Twitter створив цей формат у 2010 році, щоб кожен твіт мав ідентифікатор, який могли одночасно створювати багато серверів, не запитуючи одне одного: «Чи використовувалося вже це число?» Цей інструмент створює один ідентифікатор Snowflake із введених значень і показує, як ці значення заповнюють 64 біти.

Як працює цей генератор ідентифікаторів Snowflake

Генератор приймає чотири вхідні значення:

• Часова мітка: часова мітка Unix у мілісекундах. Залиште поле порожнім, щоб використати поточний час.
• Ідентифікатор машини: ціле число від 0 до 31 (5 бітів). Це оригінальний «ідентифікатор працівника» Twitter.
• Ідентифікатор центру обробки даних: ціле число від 0 до 31 (5 бітів).
• Порядковий номер: ціле число від 0 до 4095 (12 бітів), яке дає змогу розрізняти ідентифікатори, створені в межах однієї мілісекунди.

Інструмент об’єднує чотири значення в один 64-бітовий ідентифікатор. Потім він показує результат у двійковому вигляді, розділяючи його на сегменти часової мітки, центру обробки даних, машини та порядкового номера.

Часова мітка відлічується від фіксованої початкової точки, яка називається епохою Twitter: 4 листопада 2010 р., 1:42:54,657 UTC, або 1 288 834 974 657 мілісекунд після епохи Unix. Цей генератор не дає змоги змінити цю початкову точку. Кожен ідентифікатор, який він створює, відлічується від цієї єдиної фіксованої дати.

Структура ідентифікатора Snowflake

Ідентифікатор Snowflake — це 64-бітове ціле число, розділене на чотири частини, які читаються від найстаршого біта до наймолодшого:

Старший біт завжди дорівнює 0, тому ідентифікатор Snowflake завжди є додатним числом. 41-бітове поле часової мітки та 12-бітове поле порядкового номера — це дві частини, завдяки яким ідентифікатори Snowflake зручно сортувати: ідентифікатори, створені пізніше, мають більший сегмент часової мітки, тому розташовуються після раніших.

Формула ідентифікатора Snowflake

Генератор створює ідентифікатор за такою формулою:

$d = t - 1288834974657$

$I = (d << 22) \mathbin{|} (c << 17) \mathbin{|} (m << 12) \mathbin{|} s$

де d — дельта, t — введена часова мітка в мілісекундах, I — згенерований ідентифікатор, c — ідентифікатор центру обробки даних, m — ідентифікатор машини, а s — порядковий номер.

<< — це бітовий зсув ліворуч. Зсув числа ліворуч на 22 бітів еквівалентний множенню на 2²², або 4 194 304. Величини зсуву (22, 17, 12) безпосередньо випливають із ширини полів: поле порядкового номера має ширину 12 бітів, тому ідентифікатор машини розташований на 12 бітів вище; поле машини має ширину 5 бітів, тому ідентифікатор центру обробки даних розташований на 17 бітів вище (12 + 5); і так далі.

Як обчислити ідентифікатор Snowflake: приклад із розрахунком

Припустімо, хтось вводить:

• Часова мітка: 1 288 834 975 657 (рівно через 1 000 мс після епохи Twitter)
• Ідентифікатор центру обробки даних: 1
• Ідентифікатор машини: 1
• Порядковий номер: 0

Крок 1 — обчислення різниці. Відніміть епоху від часової мітки: 1 288 834 975 657 − 1 288 834 974 657 = 1 000.

Крок 2 — зсув кожного поля на потрібну позицію.

• Часова мітка: 1 000 << 22 = 4 194 304 000
• Ідентифікатор центру обробки даних: 1 << 17 = 131 072
• Ідентифікатор машини: 1 << 12 = 4 096
• Порядковий номер: 0

Крок 3 — об’єднання за допомогою побітового АБО. Оскільки жодне зі зміщених полів не перекривається, їх додавання дає той самий результат, що й операція АБО:

4 194 304 000 + 131 072 + 4 096 + 0 = 4 194 439 168

Це і є ідентифікатор Snowflake для такого введення. У вікні результату інструмент знову розділяє той самий 64-бітовий двійковий рядок на 41-бітовий блок часової мітки, 5-бітовий блок центру обробки даних, 5-бітовий блок машини та 12-бітовий блок порядкового номера, щоб структура числа залишалася видимою.

Де використовують ідентифікатори Snowflake

Twitter створив цей формат, щоб надавати унікальні, приблизно впорядковані за часом ідентифікатори твітам на тисячах машин баз даних без центрального лічильника, який мав би перевіряти кожен сервер. Пізніше Discord та Instagram прийняли подібні ідентифікатори завдовжки 64 бітів для повідомлень і дописів. Та сама ідея використовується у фрагментації баз даних, ідентифікаторах замовлень в електронній торгівлі та журналах подій у розподілених застосунках. Вона підходить для будь-якого середовища, де багато машин незалежно видають ідентифікатори, які все одно потрібно приблизно впорядковувати за часом.

Обмеження ідентифікаторів Snowflake

Робочий генератор Snowflake зазвичай підтримує власний поточний годинник: він збільшує порядковий номер для кожного ідентифікатора, створеного в межах тієї самої мілісекунди, і чекає наступної мілісекунди, коли порядковий номер досягає 4 095. Цей інструмент не зберігає стан між обчисленнями. Він створює один ідентифікатор із введених значень, тому корисний для вивчення формату, але відрізняється від сервісу, що працює в реальному часі.

Конструкція має фіксовані обмеження незалежно від того, який сервіс її реалізує:

• Фіксована епоха: цей генератор приймає лише часові мітки, що відповідають 4 листопада 2010 р. або пізнішому часу (епосі Twitter). Раніші дати закодувати неможливо.
• Верхня межа часової мітки: 41-бітове поле часової мітки вичерпується приблизно в липні 2080 року. Після цього різниця від епохи вже не вміщується в 41 бітів.
• Обмеження порядкового номера: одна машина може видати лише 4 096 різних ідентифікаторів (0–4095) за одну мілісекунду, перш ніж значення почнуть повторюватися.
• Простір машин: за 5 бітів для кожного з ідентифікаторів машини та центру обробки даних розгортання має 1 024 різних ідентифікаторів машин (32 × 32), які можна розподілити без колізій.
• Локальне, а не глобальне впорядкування: ідентифікатори правильно порівнюються між собою лише тоді, коли вони надійшли від машин із синхронізованими годинниками. Розбіжність годинників між машинами може порушити строгий порядок за часом.

Історія ідентифікатора Snowflake

Twitter представив формат ідентифікаторів Snowflake у 2010 році як заміну простим ідентифікаторам бази даних з автоматичним збільшенням, які не масштабуються на багато незалежних серверів баз даних. Назва походить від ідеї, що, подібно до справжніх сніжинок, жодні два створені ідентифікатори не є однаковими. Згодом конструкцію опублікували у відкритому коді, а інші великі платформи, яким було потрібно те саме — унікальні ідентифікатори, придатні для сортування та створювані багатьма машинами одночасно, — скопіювали її в модифікованому вигляді.

Поширені запитання

Що таке ідентифікатор Snowflake? Ідентифікатор Snowflake — це 64-бітове число, що складається з часової мітки, ідентифікатора машини та порядкового номера і дає змогу багатьом машинам створювати унікальні ідентифікатори без координації між собою.

Яка формула ідентифікатора Snowflake? id = ((timestamp − epoch) << 22) | (dataCenterId << 17) | (machineId << 12) | sequence, де епоха — це фіксована початкова дата, а << — бітовий зсув ліворуч.

Чи можна змінити епоху в цьому генераторі? Ні. Цей інструмент завжди відлічує часову мітку від фіксованої епохи Twitter — 4 листопада 2010 р.. Поля для встановлення іншої початкової дати немає.

Чи декодує цей інструмент наявний ідентифікатор Snowflake? Ні. Він лише створює новий ідентифікатор із введених часової мітки, ідентифікатора машини, ідентифікатора центру обробки даних та порядкового номера, а потім показує побітову структуру цього нового ідентифікатора.

Скільки ідентифікаторів Snowflake одна машина може створити за мілісекунду? До 4 096, оскільки поле порядкового номера має ширину 12 бітів (значення від 0 до 4 095).

До якого року цей генератор може створювати коректні часові мітки? Приблизно до липня 2080 року. 41-бітове поле часової мітки може містити щонайбільше приблизно 69,7 року від фіксованої епохи 2010, після чого значення переповнює поле.

Джерела

1. «Представляємо Snowflake». Інженерний блог Twitter, 2010.
2. "Snowflake ID." Вікіпедія, https://en.wikipedia.org/wiki/Snowflake_ID