Генератор на Snowflake ID - Създаване на уникални разпределени идентификатори

Какво представлява генераторът на Snowflake ID?

Генераторът на Snowflake ID създава уникално число с дължина 64 бита от времеви печат, идентификатор на машина и пореден номер. Twitter създава формата през 2010 г., за да даде на всеки туит идентификатор, който много сървъри могат да генерират едновременно, без да се налага да се питат „използвано ли е вече това число?“. Този инструмент създава един Snowflake ID от въведените стойности и показва как тези стойности запълват 64-те бита.

Как работи този генератор на Snowflake ID

Генераторът приема четири входни стойности:

• Времеви печат: Unix времеви печат в милисекунди. Оставете полето празно, за да използвате текущото време.
• Идентификатор на машина: цяло число от 0 до 31 (5 бита). Това е оригиналният „worker ID“ на Twitter.
• Идентификатор на център за данни: цяло число от 0 до 31 (5 бита).
• Пореден номер: цяло число от 0 до 4095 (12 бита), използвано за разграничаване на идентификатори, създадени в една и съща милисекунда.

Инструментът комбинира четирите стойности в един ID с 64 бита. След това показва резултата като двоично число, разделено на сегменти за времевия печат, центъра за данни, машината и поредния номер.

Времевият печат се измерва от фиксирана начална точка, наречена епоха на Twitter: 4 ноември 2010 г., 1:42:54,657 UTC, или 1 288 834 974 657 милисекунди след Unix епохата. Този генератор не позволява тази начална точка да бъде променяна. Всеки създаден от него ID се измерва спрямо тази една фиксирана дата.

Структура на Snowflake ID

Snowflake ID е цяло число с 64 бита, разделено на четири части, които се прочитат от най-значимия бит надолу:

Началният бит винаги е 0, затова Snowflake ID винаги е положително число. Полето за времевия печат с 41 бита и полето за поредния номер с 12 бита са двете части, които правят Snowflake ID подходящ за сортиране: идентификаторите, създадени по-късно, имат по-голям сегмент за времевия печат и затова се подреждат след по-ранните.

Формула на Snowflake ID

Генераторът създава ID чрез следната формула:

$d = t - 1288834974657$

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

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

<< е побитово отместване наляво. Отместването на число наляво с 22 бита е равнозначно на умножаването му по 2²², или по 4 194 304. Величините на отместването (22, 17, 12) произтичат директно от ширините на полетата: полето за поредния номер е широко 12 бита, затова идентификаторът на машината се намира 12 бита по-високо; полето за машината е широко 5 бита, затова идентификаторът на центъра за данни се намира 17 бита по-високо (12 + 5); и така нататък.

Как се изчислява Snowflake ID: примерно изчисление

Да предположим, че някой въвежда:

• Времеви печат: 1 288 834 975 657 (точно 1 000 ms след епохата на 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 ID за тези входни данни. Изгледът с резултата разделя същия двоичен низ с 64 бита обратно на блок за времевия печат с 41 бита, блок за центъра за данни с 5 бита, блок за машината с 5 бита и блок за поредния номер с 12 бита, така че структурата на числото остава видима.

Къде се използват Snowflake ID

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

Ограничения на Snowflake ID

Работещият в производствена среда генератор на Snowflake обикновено поддържа собствен часовник: увеличава поредния номер за всеки ID, създаден в една и съща милисекунда, и изчаква следващата милисекунда, когато поредният номер достигне 4 095. Този инструмент не запазва състояние между изчисленията. Той създава един ID от въведените стойности, което го прави полезен за разглеждане на формата, но различен от работеща производствена услуга.

Проектът има фиксирани ограничения, независимо от услугата, която го реализира:

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

История на Snowflake ID

Twitter обявява формата Snowflake ID през 2010 г. като заместител на обикновените автоматично увеличаващи се идентификатори на бази данни, които не се мащабират при много независими сървъри за бази данни. Името произлиза от идеята, че подобно на истинските снежинки никои два генерирани идентификатора не са еднакви. По-късно проектът е публикуван като софтуер с отворен код и е копиран в изменен вид от други големи платформи, които се нуждаят от същото: уникални идентификатори, подлежащи на сортиране, генерирани от много машини едновременно.

Често задавани въпроси

Какво представлява Snowflake ID? Snowflake ID е число с 64 бита, съставено от времеви печат, идентификатор на машина и пореден номер, проектирано така, че много машини да могат да генерират уникални идентификатори, без да се координират помежду си.

Каква е формулата на Snowflake ID? id = ((timestamp − epoch) << 22) | (dataCenterId << 17) | (machineId << 12) | sequence, където епохата е фиксирана начална дата, а << е побитово отместване наляво.

Мога ли да променя епохата в този генератор? Не. Този инструмент винаги измерва времевия печат спрямо фиксираната епоха на Twitter от 4 ноември 2010 г.. Няма поле за задаване на друга начална дата.

Този инструмент декодира ли съществуващ Snowflake ID? Не. Той само създава нов ID от въведените времеви печат, идентификатор на машина, идентификатор на център за данни и пореден номер, след което показва разпределението на битовете в този нов ID.

Колко Snowflake ID може да генерира една машина за милисекунда? До 4 096, тъй като полето за поредния номер е широко 12 бита (стойности от 0 до 4 095).

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

Източници

1. „Представяме Snowflake.“ Блог на инженерния екип на Twitter, 2010 г.
2. "Snowflake ID." Wikipedia, https://en.wikipedia.org/wiki/Snowflake_ID