Představujeme Randflake ID: distribuovaný, jednotný, nepředvídatelný, unikátní generátor náhodných ID.

Zvažme situaci, kdy potřebujeme generovat unikátní 64bitová náhodná čísla a externí strany by neměly být schopny předpovědět další nebo předchozí číslo.

Zde můžeme vygenerovat 8bajtovou náhodnou hodnotu, zkontrolovat, zda již existuje v databázi, a poté ji uložit, pokud je unikátní.

Tato metoda má však několik nevýhod. Musíme ukládat každé vygenerované číslo do databáze, abychom zajistili jeho unikátnost. Požadavek na alespoň jednu cestu tam a zpět do databáze vytváří problémy s latencí, zejména v distribuovaném prostředí, kde je klíčová škálovatelnost.

K řešení těchto problémů představujeme Randflake ID: distribuovaný, uniformní, nepředvídatelný, unikátní generátor náhodných ID.

Jak Randflake ID funguje?

Randflake ID je inspirován Snowflake ID, široce používaným k-sortovaným mechanismem generování ID vyvinutým společností X (dříve Twitter).

Snowflake ID používá aktuální časové razítko, ID uzlu a lokální čítač k vygenerování identifikátoru.

Tento přístup jsme dále rozšířili pro generování náhodných unikátních ID a přidali jsme nový prvek tajného klíče.

Klíčovou myšlenkou je přidání vrstvy blokové šifry k existujícímu generátoru unikátních ID, aby se dosáhlo neproveditelnosti v předpovídání vztahu mezi čísly.

Bloková šifra je základní kryptografická funkce, která transformuje blok prostého textu s pevnou délkou na blok šifrovaného textu stejné délky. Tato transformace je řízena kryptografickým klíčem. Rozlišující charakteristikou blokové šifry je její reverzibilita: musí to být jednoznačná (bijektivní) funkce, zajišťující, že každý unikátní vstup odpovídá unikátnímu výstupu a naopak. Tato vlastnost je klíčová pro dešifrování, umožňující obnovení původního prostého textu ze šifrovaného textu, je-li použit správný klíč.

Použitím blokové šifry jako jednoznačné funkce můžeme zaručit, že každý unikátní vstup produkuje odpovídající unikátní výstup v definovaném rozsahu.

Struktura a úvahy o návrhu

Na základě těchto základních konceptů se podívejme, jak Randflake ID implementuje tyto myšlenky v praxi.

Struktura Randflake ID zahrnuje 30bitové unixové časové razítko s přesností na sekundy, 17bitový identifikátor uzlu, 17bitový lokální čítač a 64bitovou blokovou šifru založenou na algoritmu sparx64.

Zde jsou některá rozhodnutí o návrhu:

Některé instance VM v Google Cloud Platform mohou synchronizovat hodiny s přesností 0,2 ms, ale tato úroveň přesnosti není dostupná na veřejném internetu nebo u jiných poskytovatelů cloudu.
Zvolili jsme sekundovou přesnost, protože můžeme efektivně synchronizovat hodiny mezi uzly pouze s rozlišením několika milisekund.
17bitový identifikátor uzlu umožňuje 131072 jednotlivých generátorů ve stejném okamžiku, které mohou být přiřazeny na bázi procesu, jádra nebo vlákna.
V systémech s vysokou propustností může být 17bitový lokální čítač nedostatečný. Abychom dosáhli požadované propustnosti, můžeme přiřadit více generátorů, každý s odlišným ID uzlu, aby pracovaly v jednom procesu nebo vlákně.
Jako 64bitovou blokovou šifru jsme přijali sparx64, moderní lehkou blokovou šifru založenou na ARX.
Randflake ID nabízí interní sledovatelnost, odhalující původní ID uzlu a časové razítko pouze těm, kdo vlastní tajný klíč.
Teoretická maximální propustnost je 17 179 869 184 ID/s, což je dostatečné pro většinu globálních aplikací.

Pseudokód generování Randflake ID

Pro další ilustraci procesu generování Randflake ID, následující Python pseudokód poskytuje zjednodušenou implementaci:

 1import time
 2import struct
 3from .sparx64 import Sparx64
 4
 5# Constants
 6RANDFLAKE_EPOCH_OFFSET = 1730000000  # Neděle, 27. října 2024 3:33:20 AM UTC
 7
 8# Bits allocation
 9RANDFLAKE_TIMESTAMP_BITS = 30  # 30 bitů pro časové razítko (životnost 34 let)
10RANDFLAKE_NODE_BITS = 17  # 17 bitů pro ID uzlu (max. 131072 uzlů)
11RANDFLAKE_SEQUENCE_BITS = 17  # 17 bitů pro sekvenci (max. 131072 sekvencí)
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]

Implementace Randflake připravená pro produkci, zahrnující mechanismus pronájmu ID uzlu, je k dispozici na GitHubu.

Další úvahy

V této sekci probereme některé další úvahy pro implementaci Randflake ID.

Koordinace ID uzlů

Navrhujeme koordinaci ID uzlů založenou na pronájmu.

Při tomto přístupu centrální koordinační služba přiřazuje každému generátoru unikátní ID uzlu.

Toto ID uzlu není během doby pronájmu znovu přiřazováno, aby se zajistila unikátnost, což snižuje potřebu časté komunikace s koordinační službou.

Generátor držící pronájem může požádat o obnovení pronájmu od koordinační služby, pokud jsou splněny podmínky pro obnovení.

Podmínka obnovení se týká souboru kritérií, která musí být splněna pro obnovení pronájmu, jako je například to, že generátor je stále aktivní a vyžaduje ID uzlu.

Držitel pronájmu je aktuálním držitelem rozsahu ID uzlů.

Pronájem je považován za aktivní a nevypršelý, pokud je v rámci svého platného časového období.

Tímto způsobem můžeme snížit počet cest tam a zpět na jednu za období obnovy pronájmu, čímž minimalizujeme latenci a zlepšujeme efektivitu v distribuovaných systémech.

Zmírnění proti chybnému časování

Lease service musí při přidělování lease kontrolovat konzistenci časového razítka. Přiřazený čas zahájení lease musí být větší nebo roven času zahájení posledního lease.

Generátor by měl odmítnout požadavek, pokud je aktuální časové razítko menší než čas zahájení lease nebo větší než čas ukončení lease.

Tento postup je důležitý pro ochranu unikátnosti generovaných ID v případě, že se hodiny posunou zpět. Například, pokud se hodiny posunou zpět, může být přidělen nový lease s časem zahájení dřívějším než dříve přidělený lease, což by potenciálně vedlo k generování duplicitních ID. Odmítáním požadavků s časovými razítky v rámci existujícího období lease zabraňujeme tomuto scénáři a udržujeme unikátnost ID.

Uniformita distribuce ID

Histogram of ID distribution

Na základě výše uvedeného histogramu můžeme vidět, že distribuce generovaných Randflake ID je velmi uniformní. To naznačuje, že distribuce ID může být použita přímo jako sharding key.

Závěr

V tomto článku jsme představili Randflake, nový algoritmus generování ID, který kombinuje výhody Snowflake a Sparx64.

Doufáme, že vám tento článek poskytl komplexní pochopení Randflake a jeho implementace.

Úplný zdrojový kód pro Randflake naleznete na GitHubu.

Máte-li jakékoli dotazy nebo návrhy, neváhejte se na nás obrátit. Hledáme také přispěvatele, kteří by pomohli vylepšit Randflake a implementovat jej v jiných programovacích jazycích.

Plánujeme vydat koordinační službu pro Randflake a Snowflake připravenou pro produkci, která bude open-source na GitHubu. Sledujte nás pro aktualizace!