Randflake ID: Distribueret generering af 64-bit unikke ID'er med Sparx64-blokchiffer

Overvej en situation, hvor vi skal generere unikke 64-bit tilfældige tal, og eksterne parter ikke må kunne forudsige det næste eller forrige tal.

Her kan vi generere en 8-byte tilfældig værdi, kontrollere, om den allerede findes i databasen, og derefter gemme den, hvis den er unik.

Denne metode har dog flere ulemper. Vi er nødt til at gemme hvert genereret tal i en database for at sikre unikhed. Kravet om mindst én rundrejse til databasen skaber latenstidsproblemer, især i et distribueret miljø, hvor skalerbarhed er afgørende.

For at løse disse problemer introducerer vi Randflake ID: en distribueret, uniform, uforudsigelig og unik generator af tilfældige ID'er.

Hvordan fungerer Randflake ID?

Randflake ID er inspireret af Snowflake ID, den udbredte k-sorterede ID-genereringsmekanisme udviklet af X (tidligere Twitter).

Snowflake ID bruger det aktuelle tidsstempel, et node-ID og en lokal tæller til at generere en identifikator.

Vi udvidede denne tilgang yderligere til generering af tilfældige unikke ID'er og tilføjede et nyt element i form af en hemmelig nøgle.

Den centrale idé er at tilføje et blokchiffer-lag til den eksisterende generator af unikke ID'er for at opnå umulighed ved at forudsige sammenhængen mellem tal.

En blokchiffer er en grundlæggende kryptografisk funktion, der transformerer en blok af klartekst med fast længde til en chifferblok af samme længde. Denne transformation styres af en kryptografisk nøgle. Blokchifferens særlige kendetegn er dens reversibilitet: den skal være en en-til-en (bijektiv) funktion, hvilket sikrer, at hvert unikt input svarer til et unikt output, og omvendt. Denne egenskab er afgørende for dekryptering, idet den gør det muligt at genskabe den oprindelige klartekst fra chifferteksten, når den korrekte nøgle anvendes.

Ved at anvende en blokchiffer som en en-til-en-funktion kan vi garantere, at hvert unikt input frembringer et tilsvarende unikt output inden for det definerede interval.

Strukturen og designovervejelser

Med udgangspunkt i disse grundlæggende begreber undersøger vi nu, hvordan Randflake ID implementerer disse idéer i praksis.

Randflake ID-strukturen omfatter et 30-bit unix-tidsstempel med sekundpræcision, et 17-bit node-identifikator, en 17-bit lokal tæller og en 64-bit blokchiffer baseret på algoritmen sparx64.

Her er nogle designbeslutninger:

• Nogle VM-instanser i Google Cloud Platform kan synkronisere uret med en præcision på 0,2 ms, men dette niveau af nøjagtighed er ikke tilgængeligt på det offentlige internet eller hos andre cloududbydere.

• Vi valgte sekundpræcision, fordi vi effektivt kun kan synkronisere uret mellem noder med opløsning på et par millisekunder.

• Et 17-bit node-identifikator tillader 131072 individuelle generatorer samtidigt, som kan tildeles på en per-proces-, per-kerne- eller per-tråd-basis.

• I systemer med høj gennemstrømning kan en 17-bit lokal tæller være utilstrækkelig. For at matche gennemstrømningen kan vi tildele flere generatorer, hver med et særskilt node-ID, til at arbejde i samme proces eller tråd.

• Vi valgte sparx64 som 64-bit blokchiffer, en moderne letvægts blokchiffer baseret på ARX-konstruktionen.

• Randflake ID'er tilbyder intern sporbarhed, idet de kun afslører deres oprindelige node-ID og tidsstempel over for dem, der er i besiddelse af den hemmelige nøgle.

• Den teoretiske maksimale gennemstrømning er 17.179.869.184 ID'er/s, hvilket er tilstrækkeligt til de fleste applikationer i global skala.

Pseudokode for generering af Randflake ID

For yderligere at illustrere genereringsprocessen for Randflake ID giver følgende Python-pseudokode en forenklet implementering:

 1import time
 2import struct
 3from .sparx64 import Sparx64
 4
 5# Konstanter
 6RANDFLAKE_EPOCH_OFFSET = 1730000000  # Søndag, 27. oktober 2024 kl. 03:33:20 UTC
 7
 8# Allokering af bits
 9RANDFLAKE_TIMESTAMP_BITS = 30  # 30 bits til tidsstempel (levetid på 34 år)
10RANDFLAKE_NODE_BITS = 17  # 17 bits til node-id (maks. 131072 noder)
11RANDFLAKE_SEQUENCE_BITS = 17  # 17 bits til sekvens (maks. 131072 sekvenser)
12
13# Afledte konstanter
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]

En produktionsklar implementering af Randflake, der indeholder en mekanisme til leasing af node-ID'er, er tilgængelig på GitHub.

Andre overvejelser

I dette afsnit diskuterer vi nogle yderligere overvejelser ved implementeringen af Randflake ID.

Koordinering af node-ID'er

Vi foreslår leasingbaseret koordinering af node-ID'er.

I denne tilgang tildeler en central koordineringstjeneste et unikt node-ID til hver generator.

Dette node-ID tildeles ikke igen i leasingperioden for at sikre unikhed, hvilket reducerer behovet for hyppig kommunikation med koordineringstjenesten.

Generatoren, der har leasingen, kan anmode koordineringstjenesten om en fornyelse af leasingen, hvis fornyelsesbetingelsen er opfyldt.

Fornyelsesbetingelsen henviser til et sæt kriterier, der skal være opfyldt, for at leasingen kan fornyes, såsom at generatoren stadig er aktiv og har brug for node-ID'et.

Leasingholderen er den nuværende indehaver af node-ID-intervallet.

Leasingen anses for at være aktiv og ikke udløbet, hvis den befinder sig inden for sin gyldige tidsperiode.

På denne måde kan vi reducere rundrejserne til én pr. leasingfornyelsesperiode, hvilket minimerer latenstid og forbedrer effektiviteten i distribuerede systemer.

Afbødning mod defekt ur

Leasingtjenesten skal kontrollere tidsstempelkonsistens, når en leasing tildeles. Leasingens starttidspunkt skal være større end eller lig med det sidste leasings starttidspunkt.

Generatoren bør afvise anmodningen, hvis det aktuelle tidsstempel er mindre end leasingens starttidspunkt eller større end leasingens sluttidspunkt.

Denne procedure er vigtig for at beskytte unikheden af de genererede ID'er, når uret springer baglæns. Hvis uret for eksempel springer baglæns, kan en ny leasing tildeles med et starttidspunkt, der er tidligere end en tidligere tildelt leasing, hvilket potentielt kan føre til, at dubletter af ID'er genereres. Ved at afvise anmodninger med tidsstempler inden for en eksisterende leasingperiode forhindrer vi dette scenario og opretholder unikheden af ID'erne.

Uniformitet i ID-fordelingen

Baseret på histogrammet ovenfor kan vi se, at fordelingen af de genererede Randflake ID'er er meget uniform. Dette tyder på, at ID-fordelingen direkte kan anvendes som sharding-nøgle.

Konklusion

I denne artikel introducerede vi Randflake, en ny ID-genereringsalgoritme, der kombinerer fordelene ved Snowflake og Sparx64.

Vi håber, at denne artikel har givet dig en omfattende forståelse af Randflake og dets implementering.

Du kan finde den fulde kildekode til Randflake på GitHub.

Hvis du har spørgsmål eller forslag, er du velkommen til at kontakte os. Vi søger også bidragydere, der kan hjælpe med at forbedre Randflake og implementere det i andre programmeringssprog.

Vi planlægger at udgive en produktionsklar koordineringstjeneste til Randflake og Snowflake, som vil blive open source på GitHub. Hold øje med opdateringer!