Prezentăm Randflake ID: un generator distribuit, uniform, impredictibil și unic de ID-uri aleatorii.

Să luăm în considerare o situație în care trebuie să generăm numere aleatoare unice pe 64 de biți, iar părțile externe nu ar trebui să poată prezice numărul următor sau anterior.

Aici, putem genera o valoare aleatoare de 8 octeți, să verificăm dacă există deja în baza de date și apoi să o stocăm dacă este unică.

Cu toate acestea, această metodă are mai multe dezavantaje. Trebuie să stocăm fiecare număr generat într-o bază de date pentru a asigura unicitatea. Necesitatea a cel puțin unei călătorii dus-întors către baza de date creează probleme de latență, în special într-un mediu distribuit unde scalabilitatea este crucială.

Pentru a rezolva aceste probleme, introducem Randflake ID: un generator de ID-uri aleatoare distribuit, uniform, impredictibil și unic.

Cum funcționează Randflake ID?

Randflake ID este inspirat de Snowflake ID, mecanismul de generare a ID-urilor sortate k, utilizat pe scară largă și dezvoltat de X (fostul Twitter).

Snowflake ID utilizează timestamp-ul curent, un ID de nod și un contor local pentru a genera un identificator.

Am extins această abordare pentru generarea de ID-uri unice aleatoare și am adăugat un nou element secret: cheia.

Ideea cheie este adăugarea unui strat de cifru bloc la generatorul de ID-uri unice existent pentru a obține o imposibilitate în prezicerea relației dintre numere.

Un cifru bloc este o funcție criptografică fundamentală care transformă un bloc de text clar de lungime fixă într-un bloc de text cifrat de aceeași lungime. Această transformare este guvernată de o cheie criptografică. Caracteristica distinctivă a unui cifru bloc este reversibilitatea sa: trebuie să fie o funcție unu-la-unu (bijectivă), asigurând că fiecare intrare unică corespunde unei ieșiri unice și invers. Această proprietate este crucială pentru decriptare, permițând recuperarea textului clar original din textul cifrat atunci când este aplicată cheia corectă.

Prin utilizarea unui cifru bloc ca funcție unu-la-unu, putem garanta că fiecare intrare unică produce o ieșire unică corespunzătoare în intervalul definit.

Structura și considerentele de proiectare

Bazându-ne pe aceste concepte fundamentale, să examinăm modul în care Randflake ID implementează aceste idei în practică.

Structura Randflake ID include un timestamp Unix pe 30 de biți cu precizie la secundă, un identificator de nod pe 17 biți, un contor local pe 17 biți și un cifru bloc pe 64 de biți bazat pe algoritmul sparx64.

Iată câteva decizii de proiectare:

• Unele instanțe VM din Google Cloud Platform pot sincroniza ceasul cu o precizie de 0,2 ms, dar acest nivel de precizie nu este disponibil pe internetul public sau la alți furnizori de cloud.

• Am selectat o precizie la secundă deoarece putem sincroniza eficient ceasul între noduri doar cu rezoluții de câteva milisecunde.

• Identificatorul de nod pe 17 biți permite 131072 de generatoare individuale în același moment, care pot fi atribuite per-proces, per-nucleu, per-fir de execuție.

• În sistemele cu un debit ridicat, contorul local pe 17 biți poate fi insuficient. Pentru a se potrivi cu debitul, putem atribui mai multe generatoare, fiecare cu un ID de nod distinct, să lucreze într-un singur proces sau fir de execuție.

• Am adoptat sparx64 ca cifru bloc pe 64 de biți, un cifru bloc modern, ușor, bazat pe ARX.

• ID-urile Randflake oferă trasabilitate internă, dezvăluind ID-ul nodului de origine și timestamp-ul numai celor care dețin cheia secretă.

• Debitul maxim teoretic este de 17.179.869.184 ID/s, ceea ce este suficient pentru majoritatea aplicațiilor la scară globală.

Pseudocodul generării Randflake ID

Pentru a ilustra în continuare procesul de generare a Randflake ID, următorul pseudocod Python oferă o implementare simplificată:

 1import time
 2import struct
 3from .sparx64 import Sparx64
 4
 5# Constants
 6RANDFLAKE_EPOCH_OFFSET = 1730000000  # Duminică, 27 octombrie 2024 3:33:20 AM UTC
 7
 8# Alocarea biților
 9RANDFLAKE_TIMESTAMP_BITS = 30  # 30 de biți pentru timestamp (durată de viață de 34 de ani)
10RANDFLAKE_NODE_BITS = 17  # 17 biți pentru ID-ul nodului (max 131072 noduri)
11RANDFLAKE_SEQUENCE_BITS = 17  # 17 biți pentru secvență (max 131072 secvențe)
12
13# Constante derivate
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]

O implementare Randflake pregătită pentru producție, cu un mecanism de închiriere a ID-ului de nod, este disponibilă pe GitHub.

Alte considerații

În această secțiune, vom discuta câteva considerații suplimentare pentru implementarea Randflake ID.

Coordonarea ID-ului de nod

Sugem coordonarea ID-ului de nod bazată pe închiriere.

În această abordare, un serviciu central de coordonare atribuie un ID de nod unic fiecărui generator.

Acest ID de nod nu este realocat pe durata perioadei de închiriere pentru a asigura unicitatea, reducând necesitatea unei comunicări frecvente cu serviciul de coordonare.

Generatorul care deține închirierea poate solicita o reînnoire a închirierii de la serviciul de coordonare dacă este îndeplinită condiția de reînnoire.

Condiția de reînnoire se referă la un set de criterii care trebuie îndeplinite pentru ca închirierea să fie reînnoită, cum ar fi faptul că generatorul este încă activ și necesită ID-ul de nod.

Deținătorul închirierii este deținătorul actual al intervalului ID-ului de nod.

Închirierea este considerată activă și neexpirată dacă se află în perioada sa de valabilitate.

În acest fel, putem reduce călătoriile dus-întors la una per perioadă de reînnoire a închirierii, minimizând latența și îmbunătățind eficiența în sistemele distribuite.

Atenuarea împotriva ceasului defect

Serviciul de închiriere trebuie să verifice consistența timestamp-ului la alocarea unei închirieri. Ora de început a închirierii alocate trebuie să fie mai mare sau egală cu ora de început a ultimei închirieri.

Generatorul ar trebui să respingă cererea dacă timestamp-ul curent este mai mic decât ora de început a închirierii sau mai mare decât ora de sfârșit a închirierii.

Această procedură este importantă pentru a proteja unicitatea ID-urilor generate atunci când ceasul sare înapoi. De exemplu, dacă un ceas sare înapoi, o nouă închiriere ar putea fi atribuită cu o oră de început anterioară unei închirieri atribuite anterior, ceea ce ar putea duce la generarea de ID-uri duplicate. Prin respingerea cererilor cu timestamp-uri în cadrul unei perioade de închiriere existente, prevenim acest scenariu și menținem unicitatea ID-urilor.

Uniformitatea distribuției ID-urilor

Pe baza histogramei de mai sus, putem observa că distribuția ID-urilor Randflake generate este foarte uniformă. Acest lucru sugerează că distribuția ID-urilor poate fi utilizată direct ca cheie de sharding.

Concluzie

În acest articol, am introdus Randflake, un nou algoritm de generare a ID-urilor care combină avantajele Snowflake și Sparx64.

Sperăm că acest articol v-a oferit o înțelegere cuprinzătoare a Randflake și a implementării sale.

Puteți găsi codul sursă complet pentru Randflake pe GitHub.

Dacă aveți întrebări sau sugestii, nu ezitați să ne contactați. Căutăm, de asemenea, contribuitori care să ajute la îmbunătățirea Randflake și la implementarea acestuia în alte limbaje de programare.

Intenționăm să lansăm un serviciu de coordonare pregătit pentru producție pentru Randflake și Snowflake, care va fi open-source pe GitHub. Rămâneți la curent pentru actualizări!