Predstavujeme Randflake ID: distribuovaný, jednotný, nepredvídateľný, unikátny generátor náhodných ID.

Zvážte situáciu, keď potrebujeme generovať jedinečné 64-bitové náhodné čísla a externé strany by nemali byť schopné predpovedať nasledujúce alebo predchádzajúce číslo.

V tomto prípade môžeme vygenerovať 8-bajtovú náhodnú hodnotu, skontrolovať, či už existuje v databáze, a potom ju uložiť, ak je jedinečná.

Táto metóda má však niekoľko nevýhod. Musíme ukladať každé vygenerované číslo do databázy, aby sme zabezpečili jedinečnosť. Požiadavka na aspoň jednu okružnú cestu do databázy vytvára problémy s latenciou, najmä v distribuovanom prostredí, kde je škálovateľnosť kľúčová.

Na vyriešenie týchto problémov predstavujeme Randflake ID: distribuovaný, uniformný, nepredvídateľný, jedinečný generátor náhodných ID.

Ako funguje Randflake ID?

Randflake ID je inšpirovaný Snowflake ID, široko používaným mechanizmom generovania k-zoradených ID vyvinutým spoločnosťou X (predtým Twitter).

Snowflake ID používa aktuálnu časovú známku, ID uzla a lokálny počítadlo na generovanie identifikátora.

Tento prístup sme ďalej rozšírili pre generovanie náhodných jedinečných ID a pridali sme nový prvok tajného kľúča.

Kľúčovou myšlienkou je pridanie vrstvy blokovej šifry k existujúcemu generátoru jedinečných ID na dosiahnutie neuskutočniteľnosti predpovedania vzťahu medzi číslami.

Bloková šifra je základná kryptografická funkcia, ktorá transformuje blok obyčajného textu s pevnou dĺžkou na blok šifrovaného textu rovnakej dĺžky. Táto transformácia sa riadi kryptografickým kľúčom. Rozlišovacou charakteristikou blokovej šifry je jej reverzibilita: musí to byť jednoznačná (bijektívna) funkcia, ktorá zaisťuje, že každý jedinečný vstup zodpovedá jedinečnému výstupu a naopak. Táto vlastnosť je kľúčová pre dešifrovanie, čo umožňuje obnovenie pôvodného obyčajného textu zo šifrovaného textu, keď sa použije správny kľúč.

Použitím blokovej šifry ako jednoznačnej funkcie môžeme zaručiť, že každý jedinečný vstup generuje zodpovedajúci jedinečný výstup v rámci definovaného rozsahu.

Štruktúra a úvahy o návrhu

Na základe týchto základných konceptov si pozrime, ako Randflake ID implementuje tieto myšlienky v praxi.

Štruktúra Randflake ID zahŕňa 30-bitovú unixovú časovú známku s presnosťou na sekundy, 17-bitový identifikátor uzla, 17-bitový lokálny počítadlo a 64-bitovú blokovú šifru založenú na algoritme sparx64.

Tu sú niektoré rozhodnutia o návrhu:

• Niektoré inštancie VM v Google Cloud Platform dokážu synchronizovať hodiny s presnosťou 0,2 ms, ale táto úroveň presnosti nie je dostupná na verejnom internete ani u iných poskytovateľov cloudu.

• Zvolili sme presnosť na sekundu, pretože hodiny medzi uzlami dokážeme efektívne synchronizovať len s rozlíšením niekoľkých milisekúnd.

• 17-bitový identifikátor uzla umožňuje 131072 individuálnych generátorov v rovnakom okamihu, ktoré môžu byť priradené na základe procesu, jadra alebo vlákna.

• V systémoch s vysokou priepustnosťou môže byť 17-bitový lokálny počítadlo nedostatočný. Na dosiahnutie priepustnosti môžeme priradiť viacero generátorov, každý s odlišným ID uzla, aby pracovali v jednom procese alebo vlákne.

• Prijali sme sparx64 ako 64-bitovú blokovú šifru, modernú ľahkú ARX-založenú blokovú šifru.

• Randflake ID ponúkajú internú sledovateľnosť, odhaľujúcu ich pôvodné ID uzla a časovú známku iba tým, ktorí vlastnia tajný kľúč.

• Teoretická maximálna priepustnosť je 17 179 869 184 ID/s, čo je dostatočné pre väčšinu globálnych aplikácií.

Pseudokód generovania Randflake ID

Na ďalšie ilustrovanie procesu generovania Randflake ID, nasledujúci Python pseudokód poskytuje zjednodušenú implementáciu:

 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]

Produkčná implementácia Randflake, s mechanizmom prenájmu ID uzla, je dostupná na GitHub.

Ďalšie úvahy

V tejto sekcii prediskutujeme niektoré ďalšie úvahy pre implementáciu Randflake ID.

Koordinácia ID uzla

Navrhujeme koordináciu ID uzla založenú na prenájme.

V tomto prístupe centrálna koordinačná služba prideľuje každému generátoru jedinečné ID uzla.

Toto ID uzla sa počas doby prenájmu neprideľuje opätovne, aby sa zabezpečila jedinečnosť, čím sa znižuje potreba častého komunikovania s koordinačnou službou.

Generátor, ktorý drží prenájom, môže požiadať o obnovenie prenájmu od koordinačnej služby, ak je splnená podmienka obnovenia.

Podmienka obnovenia sa týka súboru kritérií, ktoré musia byť splnené pre obnovenie prenájmu, ako napríklad to, že generátor je stále aktívny a vyžaduje ID uzla.

Držiteľ prenájmu je aktuálny držiteľ rozsahu ID uzla.

Prenájom sa považuje za aktívny a nevypršaný, ak je v rámci svojho platného časového obdobia.

Týmto spôsobom môžeme znížiť počet okružných ciest na jednu za obdobie obnovenia prenájmu, čím sa minimalizuje latencia a zlepšuje sa účinnosť v distribuovaných systémoch.

Zmiernenie proti chybnému času

Služba prenájmu musí skontrolovať konzistenciu časových známok pri prideľovaní prenájmu. Priradený čas začiatku prenájmu musí byť väčší alebo rovný času začiatku posledného prenájmu.

Generátor by mal odmietnuť požiadavku, ak je aktuálna časová známka menšia ako čas začiatku prenájmu alebo väčšia ako čas konca prenájmu.

Tento postup je dôležitý na ochranu jedinečnosti generovaných ID, keď sa hodiny posunú dozadu. Napríklad, ak sa hodiny posunú dozadu, nový prenájom by mohol byť pridelený s časom začiatku skôr, ako bol predtým pridelený prenájom, čo by mohlo potenciálne viesť k generovaniu duplicitných ID. Odmietnutím požiadaviek s časovými známkami v rámci existujúceho obdobia prenájmu predchádzame tomuto scenáru a udržiavame jedinečnosť ID.

Rovnomernosť distribúcie ID

Na základe vyššie uvedeného histogramu môžeme vidieť, že distribúcia generovaných Randflake ID je veľmi rovnomerná. To naznačuje, že distribúcia ID môže byť priamo použitá ako sharding key.

Záver

V tomto článku sme predstavili Randflake, nový algoritmus na generovanie ID, ktorý kombinuje výhody Snowflake a Sparx64.

Dúfame, že tento článok vám poskytol komplexné pochopenie Randflake a jeho implementácie.

Kompletný zdrojový kód pre Randflake nájdete na GitHub.

Ak máte akékoľvek otázky alebo návrhy, neváhajte nás kontaktovať. Hľadáme tiež prispievateľov, ktorí by pomohli vylepšiť Randflake a implementovať ho v iných programovacích jazykoch.

Plánujeme vydať produkčnú koordinačnú službu pre Randflake a Snowflake, ktorá bude open-source na GitHub. Sledujte novinky!