Introduktion af Randflake ID: en distribueret, uniform, uforudsigelig, unik tilfældig ID-generator.

Overvej en situation, hvor vi har brug for at generere unikke 64-bit tilfældige tal, og eksterne parter ikke bør være i stand til at forudsige det næste eller tidligere tal.

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

Denne metode har dog flere ulemper. Vi skal gemme hvert genereret tal i en database for at sikre unikhed. Kravet om mindst én retur til databasen skaber latenstider, 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, unik tilfældig ID-generator.

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 hemmeligt nøgleelement.

Hovedideen er at tilføje et blokchifferlag til den eksisterende unikke ID-generator for at opnå umuligheden af at forudsige forholdet mellem tal.

Et blokchiffer er en fundamental kryptografisk funktion, der omdanner en fastlængde blok af klartekst til en blok af chiffertekst af samme længde. Denne transformation styres af en kryptografisk nøgle. Den særprægede egenskab ved et blokchiffer er dets reversibilitet: det skal være en én-til-én (bijektiv) funktion, der sikrer, at hver unik input svarer til en unik output og omvendt. Denne egenskab er afgørende for dekryptering, da den gør det muligt at genoprette den originale klartekst fra chifferteksten, når den korrekte nøgle anvendes.

Ved at anvende et blokchiffer som en én-til-én funktion kan vi garantere, at hvert unikt input producerer en tilsvarende unik output inden for det definerede område.

Struktur og designovervejelser

Med udgangspunkt i disse grundlæggende koncepter, lad os undersøge, hvordan Randflake ID implementerer disse ideer i praksis.

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

Her er nogle designbeslutninger:

• Nogle VM-instanser i Google Cloud Platform kan synkronisere uret inden for 0,2ms præcision, men dette niveau af nøjagtighed er ikke tilgængeligt på offentligt internet eller andre cloud-udbydere.

• Vi valgte en sekundpræcision, fordi vi effektivt kan synkronisere uret mellem noder kun inden for få millisekund-opløsninger.

• 17-bit nodeidentifikator tillader 131072 individuelle generatorer på samme tid, som kan tildeles per-proces, per-kerne, per-tråd.

• 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 en enkelt proces eller tråd.

• Vi adopterede sparx64 som et 64-bit blokchiffer, et moderne letvægts ARX-baseret blokchiffer.

• Randflake ID'er tilbyder intern sporbarhed, der kun afslører deres oprindelige node-ID og tidsstempel til dem, der besidder den hemmelige nøgle.

• Teoretisk maksimal gennemstrømning er 17.179.869.184 ID/s, hvilket er tilstrækkeligt til de fleste globale applikationer.

Pseudokode for Randflake ID-generering

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

 1import time
 2import struct
 3from .sparx64 import Sparx64
 4
 5# Constants
 6RANDFLAKE_EPOCH_OFFSET = 1730000000  # Søndag, 27. oktober 2024 3:33:20 AM UTC
 7
 8# Bits allokering
 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, med en node ID lease-mekanisme, er tilgængelig på GitHub.

Andre overvejelser

I dette afsnit vil vi diskutere nogle yderligere overvejelser for implementering af Randflake ID.

Node ID-koordination

Vi foreslår lease-baseret node ID-koordination.

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

Dette node-ID tildeles ikke igen i løbet af lease-perioden for at sikre unikhed, hvilket reducerer behovet for hyppig kommunikation med koordineringstjenesten.

Generatoren, der holder leasen, kan anmode om en fornyelse af leasen fra koordineringstjenesten, hvis fornyelsesbetingelsen er opfyldt.

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

Leaseholderen er den nuværende indehaver af node-ID-området.

Leasen anses for aktiv og ikke udløbet, hvis den er inden for dens gyldige tidsperiode.

På denne måde kan vi reducere round trips til én per leasefornyelsesperiode, hvilket minimerer latenstiden og forbedrer effektiviteten i distribuerede systemer.

Afbødning mod fejlbehæftet ur

Lease-tjenesten skal kontrollere tidsstempelkonsistensen ved tildeling af en lease. Det tildelte lease-starttidspunkt skal være større end eller lig med det sidste lease-starttidspunkt.

Generatoren bør afvise anmodningen, hvis det aktuelle tidsstempel er mindre end lease-starttidspunktet eller større end lease-sluttidspunktet.

Denne procedure er vigtig for at beskytte unikheden af genererede ID'er, når uret springer tilbage. For eksempel, hvis et ur springer tilbage, kan en ny lease tildeles med et starttidspunkt, der er tidligere end en tidligere tildelt lease, hvilket potentielt kan føre til generering af duplikate ID'er. Ved at afvise anmodninger med tidsstempler inden for en eksisterende lease-periode forhindrer vi dette scenarie og opretholder unikheden af ID'erne.

Ensartethed i ID-distribution

Baseret på histogrammet ovenfor kan vi se, at distributionen af genererede Randflake ID'er er meget ensartet. Dette antyder, at ID-distributionen kan bruges direkte som en sharding key.

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 dens 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 til at hjælpe med at forbedre Randflake og implementere den på andre programmeringssprog.

Vi planlægger at frigive en produktionsklar koordineringstjeneste for Randflake og Snowflake, som vil blive open-sourced på GitHub. Følg med for opdateringer!