Vi presenterar Randflake ID: en distribuerad, enhetlig, oförutsägbar, unik slumpmässig ID-generator.

Betrakta en situation där vi behöver generera unika 64-bitars slumptal, och externa parter inte ska kunna förutsäga nästa eller föregående nummer.

Här kan vi generera ett 8-byte slumpvärde, kontrollera om det redan existerar i databasen och sedan lagra det om det är unikt.

Denna metod har dock flera nackdelar. Vi måste lagra varje genererat nummer i en databas för att säkerställa unikhet. Kravet på minst en tur-och-returresa till databasen skapar latensproblem, särskilt i en distribuerad miljö där skalbarhet är avgörande.

För att lösa dessa problem introducerar vi Randflake ID: en distribuerad, uniform, oförutsägbar, unik slumpmässig ID-generator.

Hur fungerar Randflake ID?

Randflake ID är inspirerad av Snowflake ID, den allmänt använda k-sorterade ID-genereringsmekanismen utvecklad av X (tidigare twitter).

Snowflake ID använder aktuell tidsstämpel, ett node ID och en lokal räknare för att generera en identifierare.

Vi utökade denna metod ytterligare för generering av slumpmässiga unika ID:n och lade till ett nytt hemligt nyckelelement.

Huvudidén är att lägga till ett block cipher-lager till den befintliga unika ID-generatorn för att uppnå omöjligheten att förutsäga sambandet mellan nummer.

En block cipher är en grundläggande kryptografisk funktion som omvandlar ett block av klartext med fast längd till ett block av chiffertext av samma längd. Denna omvandling styrs av en kryptografisk nyckel. Den utmärkande egenskapen hos en block cipher är dess reversibilitet: den måste vara en en-till-en (bijektiv) funktion, vilket säkerställer att varje unik indata motsvarar en unik utdata, och vice versa. Denna egenskap är avgörande för dekryptering, vilket möjliggör att den ursprungliga klartexten kan återställas från chiffertexten när den korrekta nyckeln appliceras.

Genom att använda en block cipher som en en-till-en-funktion kan vi garantera att varje unik indata producerar en motsvarande unik utdata inom det definierade området.

Struktur och designöverväganden

Med utgångspunkt i dessa grundläggande koncept, låt oss undersöka hur Randflake ID implementerar dessa idéer i praktiken.

Randflake ID-strukturen inkluderar en 30-bitars Unix-tidsstämpel med sekundprecision, en 17-bitars nodidentifierare, en 17-bitars lokal räknare och en 64-bitars block cipher baserad på sparx64-algoritmen.

Här är några designbeslut:

• Vissa VM-instanser i Google Cloud Platform kan synkronisera klockan med 0,2 ms precision, men den nivån av noggrannhet är inte tillgänglig på offentligt internet eller andra molnleverantörer.

• Vi valde sekundprecision eftersom vi effektivt kan synkronisera klockan mellan noder endast inom några millisekunders upplösning.

• 17-bitars nodidentifierare tillåter 131072 individuella generatorer samtidigt, vilka kan tilldelas per-process, per-core, per-thread.

• I system med hög genomströmning kan en 17-bitars lokal räknare vara otillräcklig. För att matcha genomströmningen kan vi tilldela flera generatorer, var och en med ett distinkt node ID, att arbeta i en enda process eller tråd.

• Vi antog sparx64 som en 64-bitars block cipher, en modern lättviktig ARX-baserad block cipher.

• Randflake ID:n erbjuder intern spårbarhet, som avslöjar deras ursprungliga node ID och tidsstämpel endast för dem som besitter den hemliga nyckeln.

• Teoretisk maximal genomströmning är 17 179 869 184 ID/s, vilket är tillräckligt för de flesta applikationer i global skala.

Pseudokod för Randflake ID-generering

För att ytterligare illustrera Randflake ID-genereringsprocessen, tillhandahåller följande Python-pseudokod en förenklad implementation:

 1import time
 2import struct
 3from .sparx64 import Sparx64
 4
 5# Constants
 6RANDFLAKE_EPOCH_OFFSET = 1730000000  # Söndag, 27 oktober 2024 03:33:20 AM UTC
 7
 8# Bits allocation
 9RANDFLAKE_TIMESTAMP_BITS = 30  # 30 bitar för tidsstämpel (livslängd på 34 år)
10RANDFLAKE_NODE_BITS = 17  # 17 bitar för node id (max 131072 noder)
11RANDFLAKE_SEQUENCE_BITS = 17  # 17 bitar för sekvens (max 131072 sekvenser)
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 produktionsklar implementering av Randflake, med en node ID lease-mekanism, finns tillgänglig på GitHub.

Andra överväganden

I detta avsnitt kommer vi att diskutera några ytterligare överväganden för implementering av Randflake ID.

Node ID-koordinering

Vi föreslår lease-baserad node ID-koordinering.

I detta tillvägagångssätt tilldelar en central koordinationstjänst ett unikt node ID till varje generator.

Detta node ID omtilldelas inte under lease-perioden för att säkerställa unikhet, vilket minskar behovet av frekvent kommunikation med koordinationstjänsten.

Generatorn som innehar leasen kan begära en förnyelse av leasen från koordinationstjänsten om förnyelsevillkoret är uppfyllt.

Förnyelsevillkoret avser en uppsättning kriterier som måste uppfyllas för att leasen ska förnyas, såsom att generatorn fortfarande är aktiv och behöver node ID:t.

Leasehållaren är den nuvarande innehavaren av node ID-intervallet.

Leasen anses vara aktiv och inte utgången om den ligger inom sin giltiga tidsperiod.

På detta sätt kan vi minska tur-och-returresor till en per lease-förnyelseperiod, vilket minimerar latens och förbättrar effektiviteten i distribuerade system.

Mildring mot felaktig klocka

Lease-tjänsten måste kontrollera tidsstämpelns konsistens vid tilldelning av en lease. Den tilldelade lease-starttiden måste vara större än eller lika med den senaste lease-starttiden.

Generatorn bör avvisa begäran om den aktuella tidsstämpeln är mindre än lease-starttiden eller större än lease-slutstiden.

Denna procedur är viktig för att skydda unikheten hos genererade ID:n när klockan hoppar bakåt. Om klockan till exempel hoppar bakåt, kan en ny lease tilldelas med en starttid tidigare än en tidigare tilldelad lease, vilket potentiellt kan leda till att dubbletter av ID:n genereras. Genom att avvisa förfrågningar med tidsstämplar inom en befintlig lease-period förhindrar vi detta scenario och bibehåller ID:ns unikhet.

Uniformitet i ID-distributionen

Baserat på histogrammet ovan kan vi se att fördelningen av genererade Randflake ID:n är mycket uniform. Detta tyder på att ID-distributionen kan användas direkt som en sharding key.

Slutsats

I denna artikel introducerade vi Randflake, en ny ID-genereringsalgoritm som kombinerar fördelarna med Snowflake och Sparx64.

Vi hoppas att denna artikel har gett dig en omfattande förståelse för Randflake och dess implementering.

Du kan hitta hela källkoden för Randflake på GitHub.

Om du har några frågor eller förslag, tveka inte att kontakta oss. Vi söker också bidragsgivare som kan hjälpa till att förbättra Randflake och implementera det i andra programmeringsspråk.

Vi planerar att släppa en produktionsklar koordinationstjänst för Randflake och Snowflake, som kommer att vara open-source på GitHub. Håll utkik efter uppdateringar!