Randflake ID: генериране на разпределени 64-битови уникални идентификатори с блоковия шифър Sparx64

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

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

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

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

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

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

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

Ние разширихме този подход допълнително за генериране на уникални случайни идентификатори и добавихме нов елемент: таен ключ.

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

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

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

Структура и проектни съображения

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

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

Ето някои проектни решения:

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

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

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

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

• Възприехме sparx64 като 64-битов блоков шифър, съвременен лек блоков шифър, базиран на ARX конструкция.

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

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

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

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

 1import time
 2import struct
 3from .sparx64 import Sparx64
 4
 5# Константи
 6RANDFLAKE_EPOCH_OFFSET = 1730000000  # Неделя, 27 октомври 2024, 03:33:20 ч. UTC
 7
 8# Разпределение на битовете
 9RANDFLAKE_TIMESTAMP_BITS = 30  # 30 бита за времевата марка (живот от 34 години)
10RANDFLAKE_NODE_BITS = 17  # 17 бита за идентификатор на възел (максимум 131072 възела)
11RANDFLAKE_SEQUENCE_BITS = 17  # 17 бита за последователност (максимум 131072 последователности)
12
13# Производни константи
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, включваща механизъм за наемане на идентификатор на възел, е налична в GitHub.

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

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

Координиране на идентификаторите на възли

Предлагаме координиране на идентификаторите на възли, базирано на наеми.

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

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

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

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

Притежателят на наема е настоящият държател на диапазона от идентификатори на възли.

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

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

Защита срещу неизправен часовник

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

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

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

Равномерност на разпределението на идентификаторите

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

Заключение

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

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

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

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

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