Presentazione di Randflake ID: un generatore di ID casuali distribuito, uniforme, imprevedibile e unico.

Si consideri una situazione in cui è necessario generare numeri casuali a 64 bit unici, e le parti esterne non dovrebbero essere in grado di prevedere il numero successivo o precedente.

In questo caso, possiamo generare un valore casuale di 8 byte, verificare se esiste già nel database, e quindi memorizzarlo se è unico.

Tuttavia, questo metodo presenta diversi svantaggi. Dobbiamo memorizzare ogni numero generato in un database per garantirne l'unicità. La necessità di almeno un round trip al database crea problemi di latenza, in particolare in un ambiente distribuito dove la scalabilità è cruciale.

Per risolvere questi problemi, stiamo introducendo Randflake ID: un generatore di ID casuali distribuito, uniforme, imprevedibile e unico.

Come Funziona Randflake ID?

Randflake ID si ispira a Snowflake ID, il meccanismo di generazione di ID k-ordinati ampiamente utilizzato e sviluppato da X (precedentemente twitter).

Snowflake ID utilizza il timestamp corrente, un ID del nodo e un contatore locale per generare un identificatore.

Abbiamo ulteriormente ampliato questo approccio per la generazione di ID casuali unici e abbiamo aggiunto un nuovo elemento di chiave segreta.

L'idea chiave è aggiungere un livello di cifratura a blocchi al generatore di ID unici esistente per rendere infattibile la previsione della relazione tra i numeri.

Una cifratura a blocchi è una funzione crittografica fondamentale che trasforma un blocco di testo in chiaro a lunghezza fissa in un blocco di testo cifrato della stessa lunghezza. Questa trasformazione è governata da una chiave crittografica. La caratteristica distintiva di una cifratura a blocchi è la sua reversibilità: deve essere una funzione uno-a-uno (biettiva), garantendo che ogni input unico corrisponda a un output unico, e viceversa. Questa proprietà è cruciale per la decrittazione, consentendo di recuperare il testo in chiaro originale dal testo cifrato quando viene applicata la chiave corretta.

Impiegando una cifratura a blocchi come funzione uno-a-uno, possiamo garantire che ogni input unico produca un output unico corrispondente all'interno dell'intervallo definito.

La struttura e le considerazioni di progettazione

Basandosi su questi concetti fondamentali, esaminiamo come Randflake ID implementa queste idee in pratica.

La struttura di Randflake ID include un timestamp unix a 30 bit con precisione al secondo, un identificatore di nodo a 17 bit, un contatore locale a 17 bit e una cifratura a blocchi a 64 bit basata sull'algoritmo sparx64.

Ecco alcune decisioni di progettazione:

• Alcune istanze VM in Google Cloud Platform possono sincronizzare l'orologio con una precisione di 0.2ms, ma tale livello di accuratezza non è disponibile su internet pubblico o altri provider di cloud.

• Abbiamo selezionato una precisione al secondo perché possiamo sincronizzare efficacemente l'orologio tra i nodi solo con risoluzioni di pochi millisecondi.

• L'identificatore di nodo a 17 bit consente 131072 generatori individuali nello stesso momento, che possono essere assegnati per processo, per core, per thread.

• Nei sistemi ad alta produttività, un contatore locale a 17 bit potrebbe essere insufficiente. Per eguagliare la produttività, possiamo assegnare più generatori, ciascuno con un ID di nodo distinto, per lavorare in un singolo processo o thread.

• Abbiamo adottato sparx64 come cifratura a blocchi a 64 bit, una moderna cifratura a blocchi leggera basata su ARX.

• Gli ID Randflake offrono tracciabilità interna, rivelando il loro ID del nodo di origine e il timestamp solo a coloro che possiedono la chiave segreta.

• La produttività massima teorica è di 17.179.869.184 ID/s, che è sufficiente per la maggior parte delle applicazioni su scala globale.

Pseudocodice per la generazione di Randflake ID

Per illustrare ulteriormente il processo di generazione di Randflake ID, il seguente pseudocodice Python fornisce un'implementazione semplificata:

 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]

Un'implementazione di Randflake pronta per la produzione, che include un meccanismo di lease dell'ID del nodo, è disponibile su GitHub.

Altre considerazioni

In questa sezione, discuteremo alcune considerazioni aggiuntive per l'implementazione di Randflake ID.

Coordinamento dell'ID del nodo

Suggeriamo un coordinamento dell'ID del nodo basato su lease.

In questo approccio, un servizio di coordinamento centrale assegna un ID di nodo unico a ciascun generatore.

Questo ID di nodo non viene riassegnato durante il periodo di lease per garantire l'unicità, riducendo la necessità di comunicazioni frequenti con il servizio di coordinamento.

Il generatore che detiene il lease può richiedere un rinnovo del lease al servizio di coordinamento se la condizione di rinnovo è soddisfatta.

La condizione di rinnovo si riferisce a un insieme di criteri che devono essere soddisfatti affinché il lease venga rinnovato, come il generatore che è ancora attivo e che richiede l'ID del nodo.

Il leaseholder è l'attuale detentore dell'intervallo di ID del nodo.

Il lease è considerato attivo e non scaduto se rientra nel suo periodo di validità.

In questo modo, possiamo ridurre i round trip a uno per periodo di rinnovo del lease, minimizzando la latenza e migliorando l'efficienza nei sistemi distribuiti.

Mitigazione contro l'orologio difettoso

Il servizio di lease deve verificare la coerenza del timestamp durante l'assegnazione di un lease. L'ora di inizio del lease assegnato deve essere maggiore o uguale all'ora di inizio dell'ultimo lease.

Il generatore dovrebbe rifiutare la richiesta se il timestamp corrente è inferiore all'ora di inizio del lease o maggiore dell'ora di fine del lease.

Questa procedura è importante per proteggere l'unicità degli ID generati quando l'orologio torna indietro. Ad esempio, se un orologio torna indietro, un nuovo lease potrebbe essere assegnato con un'ora di inizio precedente a un lease precedentemente assegnato, portando potenzialmente alla generazione di ID duplicati. Rifiutando le richieste con timestamp all'interno di un periodo di lease esistente, preveniamo questo scenario e manteniamo l'unicità degli ID.

Uniformità della distribuzione degli ID

Basandosi sull'istogramma sopra, possiamo osservare che la distribuzione degli ID Randflake generati è molto uniforme. Ciò suggerisce che la distribuzione degli ID può essere utilizzata direttamente come chiave di sharding.

Conclusione

In questo articolo, abbiamo introdotto Randflake, un nuovo algoritmo di generazione di ID che combina i vantaggi di Snowflake e Sparx64.

Ci auguriamo che questo articolo vi abbia fornito una comprensione completa di Randflake e della sua implementazione.

Potete trovare il codice sorgente completo per Randflake su GitHub.

Se avete domande o suggerimenti, non esitate a contattarci. Siamo anche alla ricerca di collaboratori per contribuire a migliorare Randflake e implementarlo in altri linguaggi di programmazione.

Stiamo pianificando di rilasciare un servizio di coordinamento pronto per la produzione per Randflake e Snowflake, che sarà open-source su GitHub. Restate sintonizzati per gli aggiornamenti!