Представяме Randflake ID: разпределен, униформен, непредвидим, уникален генератор на случайни ID.

Да разгледаме ситуация, при която трябва да генерираме уникални 64-битови случайни числа и външни страни да не могат да предскажат следващото или предишното число.

Тук можем да генерираме 8-байтова случайна стойност, да проверим дали тя вече съществува в базата данни и след това да я съхраним, ако е уникална.

Въпреки това, този метод има няколко недостатъка. Трябва да съхраняваме всяко генерирано число в база данни, за да гарантираме уникалност. Изискването за поне едно двупосочно пътуване до базата данни създава проблеми с латентността, особено в разпределена среда, където мащабируемостта е от решаващо значение.

За да решим тези проблеми, въвеждаме Randflake ID: разпределен, еднороден, непредсказуем, уникален генератор на случайни ID.

Как работи Randflake ID?

Randflake ID е вдъхновен от Snowflake ID, широко използвания механизъм за генериране на k-сортирани ID, разработен от X (преди twitter).

Snowflake ID използва текущия timestamp, ID на възел и локален брояч за генериране на идентификатор.

Разширихме този подход по-нататък за генериране на случайни уникални ID и добавихме нов елемент – таен ключ.

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

Блоковият шифър е фундаментална криптографска функция, която трансформира блок от открит текст с фиксирана дължина в блок от шифрован текст със същата дължина. Тази трансформация се управлява от криптографски ключ. Отличителната характеристика на блоковия шифър е неговата обратимост: той трябва да бъде едно-към-едно (биективна) функция, гарантираща, че всеки уникален вход съответства на уникален изход и обратно. Това свойство е от решаващо значение за дешифрирането, позволявайки възстановяването на оригиналния открит текст от шифрования текст, когато се приложи правилният ключ.

Чрез използването на блоков шифър като едно-към-едно функция, можем да гарантираме, че всеки уникален вход произвежда съответен уникален изход в рамките на определения диапазон.

Структурата и съображенията за дизайн

Надграждайки тези фундаментални концепции, нека разгледаме как Randflake ID прилага тези идеи на практика.

Структурата на Randflake ID включва 30-битов Unix timestamp с точност до секунда, 17-битов идентификатор на възел, 17-битов локален брояч и 64-битов блоков шифър, базиран на алгоритъма sparx64.

Ето някои дизайнерски решения:

• Някои VM инстанции в Google Cloud Platform могат да синхронизират часовника с точност до 0,2 ms, но това ниво на точност не е налично в публичния интернет или други доставчици на облачни услуги.

• Избрахме секундна точност, защото можем ефективно да синхронизираме часовника между възлите само в рамките на няколко милисекунди.

• 17-битовият идентификатор на възел позволява 131072 индивидуални генератора едновременно, които могат да бъдат присвоени на процес, на ядро, на нишка.

• В системи с висока пропускателна способност 17-битовият локален брояч може да е недостатъчен. За да съответстваме на пропускателната способност, можем да присвоим множество генератори, всеки с различен ID на възел, за да работят в един процес или нишка.

• Приехме sparx64 като 64-битов блоков шифър, модерен лек ARX-базиран блоков шифър.

• Randflake ID предлагат вътрешна проследяемост, разкривайки своя произхождащ ID на възел и timestamp само на тези, които притежават тайния ключ.

• Теоретичната максимална пропускателна способност е 17 179 869 184 ID/s, което е достатъчно за повечето глобални приложения.

Псевдокод за генериране на Randflake ID

За по-нататъшно илюстриране на процеса на генериране на Randflake ID, следващият Python псевдокод предоставя опростена имплементация:

 1import time
 2import struct
 3from .sparx64 import Sparx64
 4
 5# Constants
 6RANDFLAKE_EPOCH_OFFSET = 1730000000  # Неделя, 27 октомври 2024 г., 3:33:20 AM UTC
 7
 8# Bits allocation
 9RANDFLAKE_TIMESTAMP_BITS = 30  # 30 бита за timestamp (живот от 34 години)
10RANDFLAKE_NODE_BITS = 17  # 17 бита за ID на възел (макс. 131072 възела)
11RANDFLAKE_SEQUENCE_BITS = 17  # 17 бита за поредица (макс. 131072 поредици)
12
13# Derived constants
14RANDFLAKE_MAX_TIMESTAMP = RANDFLAKE_EPOCH_OFFSET + (1 << RANDFLAKE_TIMESTAMP_BITS) - 1
15RANDFLAKE_MAX_NODE = (1 << RANDFLAKE_NODE_BITS) - 1
16RANDFLAKE_MAX_SEQUENCE = (1 << RANDFLAKE_SEQUENCE_BITS) - 1
17
18class Randflake:
19    def __init__(self, node_id: int, secret: bytes):
20        self.node_id = int(node_id)
21        self.sequence = int(0)
22        self.rollover = int(time.time())
23        self.sbox = Sparx64(secret)
24
25    def _new_raw(self) -> int:
26        while True:
27            now = int(time.time())
28
29            self.sequence += 1
30            sequence = self.sequence
31
32            if sequence > RANDFLAKE_MAX_SEQUENCE:
33                if now > self.rollover:
34                    self.sequence = 0
35                    self.rollover = now
36                    sequence = 0
37                else:
38                    continue
39
40            timestamp = now - RANDFLAKE_EPOCH_OFFSET
41            return (timestamp << 34) | (self.node_id << 17) | sequence
42
43    def generate(self) -> int:
44        id_raw = self._new_raw()
45        src = struct.pack("<q", id_raw)
46        dst = bytearray(8)
47        self.sbox.encrypt(dst, src)
48        return struct.unpack("<q", dst)[0]

Готова за производство имплементация на Randflake, включваща механизъм за отдаване под наем на ID на възел, е достъпна в GitHub.

Други съображения

В този раздел ще обсъдим някои допълнителни съображения за имплементиране на Randflake ID.

Координация на ID на възел

Предлагаме координация на ID на възел, базирана на отдаване под наем.

При този подход централна координационна услуга присвоява уникален ID на възел на всеки генератор.

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

Генераторът, който държи наема, може да поиска подновяване на наема от координационната услуга, ако условието за подновяване е изпълнено.

Условието за подновяване се отнася до набор от критерии, които трябва да бъдат изпълнени, за да бъде подновен наемът, като например генераторът все още да е активен и да изисква ID на възел.

Наемателят е текущият държател на обхвата на ID на възел.

Наемът се счита за активен и не е изтекъл, ако е в рамките на валидния си период.

По този начин можем да намалим двупосочните пътувания до едно на период на подновяване на наема, минимизирайки латентността и подобрявайки ефективността в разпределени системи.

Смекчаване на неизправности в часовника

Услугата за наем трябва да проверява съгласуваността на timestamp при разпределяне на наем. Присвоеното начално време на наема трябва да бъде по-голямо или равно на последното начално време на наема.

Генераторът трябва да отхвърли заявката, ако текущият timestamp е по-малък от началното време на наема или по-голям от крайното време на наема.

Тази процедура е важна за защита на уникалността на генерираните ID, когато часовникът се върне назад. Например, ако часовникът се върне назад, може да бъде присвоен нов наем с начално време, по-ранно от предишен присвоен наем, което потенциално може да доведе до генериране на дублиращи се ID. Чрез отхвърляне на заявки с timestamp в рамките на съществуващ период на наем, предотвратяваме този сценарий и поддържаме уникалността на ID.

Еднородност на разпределението на ID

Въз основа на хистограмата по-горе, можем да видим, че разпределението на генерираните Randflake ID е много еднородно. Това предполага, че разпределението на ID може да се използва директно като ключ за sharding.

Заключение

В тази статия представихме Randflake, нов алгоритъм за генериране на ID, който съчетава предимствата на Snowflake и Sparx64.

Надяваме се, че тази статия ви е предоставила цялостно разбиране за Randflake и неговата имплементация.

Пълният изходен код за Randflake можете да намерите в GitHub.

Ако имате въпроси или предложения, моля, не се колебайте да се свържете с нас. Също така търсим сътрудници, които да помогнат за подобряването на Randflake и неговата имплементация на други езици за програмиране.

Планираме да пуснем готова за производство координационна услуга за Randflake и Snowflake, която ще бъде с отворен код в GitHub. Следете за актуализации!