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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• 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  # Sunday, October 27, 2024 3:33:20 AM UTC
 7
 8# Bits allocation
 9RANDFLAKE_TIMESTAMP_BITS = 30  # 30 bits for timestamp (lifetime of 34 years)
10RANDFLAKE_NODE_BITS = 17  # 17 bits for node id (max 131072 nodes)
11RANDFLAKE_SEQUENCE_BITS = 17  # 17 bits for sequence (max 131072 sequences)
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 може да се използва директно като ключ за шардинг.

Заключение

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

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

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

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

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