Vi introduserer Randflake ID: en distribuert, uniform, uforutsigbar, unik tilfeldig ID-generator.

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

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

Denne metoden har imidlertid flere ulemper. Vi må lagre hvert genererte tall i en database for å sikre unikhet. Kravet om minst én tur-retur til databasen skaper latensproblemer, spesielt i et distribuert miljø der skalerbarhet er avgjørende.

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

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 gjeldende tidsstempel, en node ID og en lokal teller for å generere en identifikator.

Vi utvidet denne tilnærmingen ytterligere for tilfeldig unik ID-generering og la til et nytt secret key-element.

Hovedideen er å legge til et block cipher-lag til den eksisterende unike ID-generatoren for å oppnå uforutsigbarhet i forholdet mellom tallene.

En block cipher er en fundamental kryptografisk funksjon som transformerer en blokk med klartekst av fast lengde til en blokk med chiffertekst av samme lengde. Denne transformasjonen styres av en kryptografisk nøkkel. Den fremtredende egenskapen til en block cipher er dens reversibilitet: den må være en en-til-en (bijektiv) funksjon, som sikrer at hver unike inngang tilsvarer en unik utgang, og omvendt. Denne egenskapen er avgjørende for dekryptering, da den tillater at den opprinnelige klarteksten gjenopprettes fra chifferteksten når den korrekte nøkkelen brukes.

Ved å benytte en block cipher som en en-til-en-funksjon, kan vi garantere at hver unike inngang produserer en korresponderende unik utgang innenfor det definerte området.

Struktur og designhensyn

Basert på disse grunnleggende konseptene, la oss undersøke 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 block cipher basert på sparx64-algoritmen.

Her er noen designbeslutninger:

• Noen VM-instanser i Google Cloud Platform kan synkronisere klokken med 0.2ms presisjon, men dette nøyaktighetsnivået er ikke tilgjengelig på offentlig internett eller andre skyleverandører.

• Vi valgte en sekundpresisjon fordi vi effektivt kan synkronisere klokken mellom noder kun innenfor få millisekunders oppløsning.

• 17-biters node-identifikator tillater 131072 individuelle generatorer samtidig, som kan tildeles per-prosess, per-kjerne, per-tråd.

• I systemer med høy gjennomstrømning kan en 17-biters lokal teller være utilstrekkelig. For å matche gjennomstrømningen kan vi tildele flere generatorer, hver med en distinkt node ID, til å arbeide i en enkelt prosess eller tråd.

• Vi adopterte sparx64 som en 64-biters block cipher, en moderne lettvekts ARX-basert block cipher.

• Randflake ID-er tilbyr intern sporbarhet, og avslører deres opprinnelige node ID og tidsstempel kun for dem som besitter secret key.

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

Pseudokode for Randflake ID-generering

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

 1import time
 2import struct
 3from .sparx64 import Sparx64
 4
 5# Constants
 6RANDFLAKE_EPOCH_OFFSET = 1730000000  # Sunday, October 27, 2024 3:33:20 AM UTC
 7
 8# Bits allocation
 9RANDFLAKE_TIMESTAMP_BITS = 30  # 30 bits for timestamp (lifetime of 34 years)
10RANDFLAKE_NODE_BITS = 17  # 17 bits for node id (max 131072 nodes)
11RANDFLAKE_SEQUENCE_BITS = 17  # 17 bits for sequence (max 131072 sequences)
12
13# Derived constants
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 node ID lease-mekanisme, er tilgjengelig på GitHub.

Andre hensyn

I denne seksjonen vil vi diskutere noen ytterligere hensyn for implementering av Randflake ID.

Node ID-koordinering

Vi foreslår lease-basert node ID-koordinering.

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

Denne node ID-en tildeles ikke på nytt i løpet av lease-perioden for å sikre unikhet, noe som reduserer behovet for hyppig kommunikasjon med koordineringstjenesten.

Generatoren som holder leasen kan be om en fornyelse av leasen fra koordineringstjenesten hvis fornyelsesbetingelsen er oppfylt.

Fornyelsesbetingelsen refererer til et sett med kriterier som må være oppfylt for at leasen skal fornyes, for eksempel at generatoren fortsatt er aktiv og trenger node ID-en.

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

Leasen anses som aktiv og ikke utløpt hvis den er innenfor sin gyldige tidsperiode.

På denne måten kan vi redusere tur-retur til én per lease-fornyelsesperiode, noe som minimerer latens og forbedrer effektiviteten i distribuerte systemer.

Avbøtning mot feilaktig klokke

Lease-tjenesten må sjekke tidsstempelkonsistensen ved tildeling av en lease. Den tildelte lease-starttiden må være større enn eller lik den siste lease-starttiden.

Generatoren skal avvise forespørselen hvis gjeldende tidsstempel er mindre enn lease-starttiden eller større enn lease-sluttiden.

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

Ensartethet i ID-distribusjon

Basert på histogrammet ovenfor kan vi se at distribusjonen av genererte Randflake ID-er er svært jevn. Dette indikerer at ID-distribusjonen kan brukes direkte som en sharding key.

Konklusjon

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

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

Du finner hele kildekoden for Randflake på GitHub.

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

Vi planlegger å lansere en produksjonsklar koordineringstjeneste for Randflake og Snowflake, som vil bli åpen kildekode på GitHub. Følg med for oppdateringer!