Randflake ID: Distribuert generering av 64-bits unike ID-er med blokkchifferet Sparx64

Tenk deg en situasjon der vi må generere unike 64-biters tilfeldige tall, og eksterne parter skal ikke kunne forutsi det neste eller forrige tallet.

Her kan vi generere en 8-byte tilfeldig verdi, sjekke om den allerede finnes i databasen, og deretter lagre den hvis den er unik.

Denne metoden har imidlertid flere ulemper. Vi må lagre hvert generert tall i en database for å sikre unikhet. Kravet om minst én rundtur til databasen skaper forsinkelsesproblemer, særlig i et distribuert miljø der skalerbarhet er avgjørende.

For å løse disse problemene introduserer vi Randflake ID: en distribuert, uniform, uforutsigbar og unik generator for tilfeldige ID-er.

Hvordan fungerer Randflake ID?

Randflake ID er inspirert av Snowflake ID, den mye brukte k-sorterte ID-genereringsmekanismen utviklet av X (tidligere Twitter).

Snowflake ID bruker det nåværende tidsstempelet, en node-ID og en lokal teller for å generere en identifikator.

Vi utvidet denne tilnærmingen ytterligere for generering av unike tilfeldige ID-er og la til et nytt element: en hemmelig nøkkel.

Hovedideen er å legge et blokkchifferlag til den eksisterende generatoren for unike ID-er for å oppnå umulighet i å forutsi sammenhengen mellom tall.

En blokkchiffer er en grunnleggende kryptografisk funksjon som transformerer en blokk med fast lengde av klartekst til en chifferblokk av samme lengde. Denne transformasjonen styres av en kryptografisk nøkkel. Det særegne kjennetegnet ved en blokkchiffer er reversibilitet: den må være en én-til-én (bijektiv) funksjon, som sikrer at hver unik inndata tilsvarer en unik utdata, og omvendt. Denne egenskapen er avgjørende for dekryptering, slik at den opprinnelige klarteksten kan gjenvinnes fra chifferteksten når riktig nøkkel benyttes.

Ved å bruke en blokkchiffer som en én-til-én funksjon kan vi garantere at hver unik inndata gir en tilsvarende unik utdata innenfor det definerte området.

Strukturen og designhensyn

Basert på disse grunnleggende konseptene skal vi se nærmere på hvordan Randflake ID implementerer disse ideene i praksis.

Randflake ID-strukturen inkluderer et 30-biters unix-tidsstempel med sekundpresisjon, en 17-biters node-identifikator, en 17-biters lokal teller og en 64-biters blokkchiffer basert på sparx64-algoritmen.

Her er noen designbeslutninger:

• Noen VM-instanser i Google Cloud Platform kan synkronisere klokken med 0,2 ms presisjon, men et slikt nivå av nøyaktighet er ikke tilgjengelig på det åpne internett eller hos andre skyleverandører.

• Vi valgte sekundpresisjon fordi vi bare effektivt kan synkronisere klokken mellom noder innenfor en oppløsning på noen få millisekunder.

• En 17-biters node-identifikator gir plass til 131072 individuelle generatorer samtidig, som kan tilordnes på prosessnivå, kjerne-nivå eller tråd-nivå.

• I systemer med høy gjennomstrømning kan en 17-biters lokal teller være utilstrekkelig. For å møte gjennomstrømningen kan vi tilordne flere generatorer, hver med en egen node-ID, til å arbeide i én og samme prosess eller tråd.

• Vi tok i bruk sparx64 som en 64-biters blokkchiffer, en moderne lettvektsblokkchiffer basert på ARX-konstruksjon.

• Randflake-ID-er gir intern sporbarhet, og avslører opprinnelig node-ID og tidsstempel kun for dem som har den hemmelige nøkkelen.

• Teoretisk maksimal gjennomstrømning er 17 179 869 184 ID/s, noe som er tilstrekkelig for de fleste globale applikasjoner.

Pseudokode for generering av Randflake ID

For ytterligere å illustrere genereringsprosessen for Randflake ID gir følgende Python-pseudokode en forenklet implementasjon:

 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# Bitfordeling
 9RANDFLAKE_TIMESTAMP_BITS = 30  # 30 biter for tidsstempel (levetid på 34 år)
10RANDFLAKE_NODE_BITS = 17  # 17 biter for node-ID (maks 131072 noder)
11RANDFLAKE_SEQUENCE_BITS = 17  # 17 biter for sekvens (maks 131072 sekvenser)
12
13# Avledede 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 produksjonsklar implementasjon av Randflake, med en mekanisme for leasing av node-ID, er tilgjengelig på GitHub.

Andre hensyn

I denne delen drøfter vi noen tilleggshensyn for implementering av Randflake ID.

Koordinering av node-ID

Vi foreslår leasingbasert koordinering av node-ID.

I denne tilnærmingen tildeler en sentral koordineringstjeneste en unik node-ID til hver generator.

Denne node-ID-en blir ikke tildelt på nytt i leieperioden for å sikre unikhet, noe som reduserer behovet for hyppig kommunikasjon med koordineringstjenesten.

Generatoren som har leieavtalen kan be koordineringstjenesten om fornyelse av leieavtalen dersom fornyelsesvilkårene er oppfylt.

Fornyelsesvilkårene viser til et sett med kriterier som må være oppfylt for at leieavtalen skal fornyes, for eksempel at generatoren fortsatt er aktiv og har behov for node-ID-en.

Leietakeren er den nåværende innehaveren av node-ID-området.

Leieavtalen anses som aktiv og ikke utløpt dersom den er innenfor sin gyldige tidsperiode.

På denne måten kan vi redusere rundturer til én per leieperiode, noe som minimerer forsinkelser og forbedrer effektiviteten i distribuerte systemer.

Beskyttelse mot feilaktig klokke

Leasetjenesten må kontrollere tidsstempelkonsistens når den tildeler en leieavtale. Den tildelte starttiden for leieavtalen må være større than eller lik den siste starttiden for leieavtale.

Generatoren skal avvise forespørselen dersom det nåværende tidsstempelet er mindre enn starttiden for leieavtalen eller større enn sluttiden for leieavtalen.

Denne prosedyren er viktig for å beskytte unikheten til de genererte ID-ene når klokken hopper bakover. For eksempel, dersom en klokke hopper bakover, kan en ny leieavtale tildeles med en starttid tidligere enn en tidligere tildelt leieavtale, noe som potensielt kan føre til at dupliserte ID-er genereres. Ved å avvise forespørsler med tidsstempler innenfor en eksisterende leieperiode forhindrer vi dette scenariet og opprettholder unikheten til ID-ene.

Uniformitet i ID-fordelingen

Basert på histogrammet ovenfor ser vi at fordelingen av genererte Randflake-ID-er er svært uniform. Dette tyder på at ID-fordelingen kan brukes direkte som en shardingnøkkel.

Konklusjon

I denne artikkelen introduserte vi Randflake, en ny ID-genereringsalgoritme som kombinerer fordelene ved Snowflake og Sparx64.

Vi håper at denne artikkelen har gitt deg en omfattende forståelse av Randflake og dens implementering.

Du finner hele kildekoden til Randflake på GitHub.

Dersom du har spørsmål eller forslag, ikke nøl med å ta kontakt. Vi søker også bidragsytere som kan hjelpe til med å forbedre Randflake og implementere den i andre programmeringsspråk.

Vi planlegger å gi ut en produksjonsklar koordineringstjeneste for Randflake og Snowflake, som vil bli open source på GitHub. Følg med for oppdateringer!