GoSudaRandflake ID: Distribuované generovanie 64-bitových jedinečných ID so šifrou Sparx64 Block Cipher
Zvážte situáciu, v ktorej potrebujeme generovať jedinečné 64-bitové náhodné čísla a externé strany nesmú byť schopné predpovedať nasledujúce ani predchádzajúce číslo.
Tu 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. Každé vygenerované číslo musíme ukladať do databázy, aby sme zabezpečili jedinečnosť. Požiadavka na aspoň jednu komunikáciu s databázou (round trip) spôsobuje problémy s latenciou, najmä v distribuovanom prostredí, kde je škálovateľnosť kľúčová.
Na riešenie týchto problémov predstavujeme Randflake ID: distribuovaný, rovnomerný, nepredvídateľný a jedinečný generátor náhodných identifikátorov.
Ako funguje Randflake ID?
Randflake ID je inšpirované Snowflake ID, široko používaným mechanizmom generovania k-usporiadaných identifikátorov, ktorý vyvinula spoločnosť X (predtým Twitter).
Snowflake ID používa aktuálnu časovú značku, identifikátor uzla a lokálny počítadlo na vygenerovanie identifikátora.
Tento prístup sme ďalej rozšírili pre generovanie náhodných jedinečných identifikátorov a pridali nový prvok tajného kľúča.
Kľúčovou myšlienkou je pridanie vrstvy blokovej šifry k existujúcemu generátoru jedinečných identifikátorov, aby sa dosiahla nemožnosť predpovedať vzťah medzi číslami.
Bloková šifra je základná kryptografická funkcia, ktorá transformuje blok otvoreného textu pevnej dĺžky na šifrovaný blok rovnakej dĺžky. Táto transformácia je riadená kryptografickým kľúčom. Charakteristickou vlastnosťou blokovej šifry je jej reverzibilita: musí ísť o jednoznačné (bijektívne) zobrazenie, ktoré zabezpečuje, že každému jedinečnému vstupu zodpovedá jedinečný výstup a naopak. Táto vlastnosť je kľúčová pre dešifrovanie, pretože umožňuje obnoviť pôvodný otvorený text zo šifrovaného textu pri použití správneho kľúča.
Použitím blokovej šifry ako jednoznačného zobrazenia môžeme zaručiť, že každý jedinečný vstup vytvorí zodpovedajúci jedinečný výstup v definovanom rozsahu.
Štruktúra a konštrukčné úvahy
Na základe týchto základných pojmov sa pozrime na to, ako Randflake ID tieto myšlienky implementuje v praxi.
Štruktúra Randflake ID obsahuje 30-bitovú unixovú časovú značku 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é konštrukčné rozhodnutia:
Niektoré virtuálne stroje v Google Cloud Platform dokážu synchronizovať hodiny s presnosťou 0,2 ms, táto úroveň presnosti však nie je dostupná na verejnom internete ani u iných poskytovateľov cloudových služieb.
Zvolili sme presnosť na sekundy, pretože hodiny medzi uzlami dokážeme efektívne synchronizovať iba v rozlíšení na niekoľko milisekúnd.
17-bitový identifikátor uzla umožňuje 131 072 jednotlivých generátorov v rovnakom okamihu, ktoré je možné priradiť na úrovni procesu, jadra alebo vlákna.
Vo vysokovýkonných systémoch môže byť 17-bitové lokálne počítadlo nedostatočné. Aby sme zodpovedali priepustnosti, môžeme priradiť viacero generátorov, každý s odlišným identifikátorom uzla, ktoré budú pracovať v jednom procese alebo vlákne.
Ako 64-bitovú blokovú šifru sme použili sparx64, modernú ľahkú blokovú šifru založenú na operáciách ARX.
Randflake ID ponúkajú interné sledovateľnosť, pričom pôvodný identifikátor uzla a časovú značku odhalia 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 aplikácií globálneho rozsahu.
Pseudokód generovania Randflake ID
Na ďalšie objasnenie procesu generovania Randflake ID poskytuje nasledujúci pseudokód v jazyku Python zjednodušenú implementáciu:
1import time
2import struct
3from .sparx64 import Sparx64
4
5# Konštanty
6RANDFLAKE_EPOCH_OFFSET = 1730000000 # Nedeľa, 27. október 2024 3:33:20 UTC
7
8# Alokácia bitov
9RANDFLAKE_TIMESTAMP_BITS = 30 # 30 bitov pre časovú značku (životnosť 34 rokov)
10RANDFLAKE_NODE_BITS = 17 # 17 bitov pre identifikátor uzla (max. 131072 uzlov)
11RANDFLAKE_SEQUENCE_BITS = 17 # 17 bitov pre sekvenciu (max. 131072 sekvencií)
12
13# Odvodené konštanty
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čne pripravená implementácia Randflake, ktorá obsahuje mechanizmus prenájmu identifikátorov uzlov (node ID lease), je dostupná na GitHub.
Ďalšie úvahy
V tejto časti si rozoberieme niektoré ďalšie úvahy pri implementácii Randflake ID.
Koordinácia identifikátorov uzlov
Navrhujeme koordináciu identifikátorov uzlov na báze prenájmu (lease-based).
V tomto prístupe centrálna koordinačná služba priradí každému generátoru jedinečný identifikátor uzla.
Tento identifikátor uzla sa počas obdobia prenájmu nepriraďuje znova, aby sa zabezpečila jedinečnosť, čím sa znižuje potreba častej komunikácie s koordinačnou službou.
Generátor, ktorý drží prenájom, môže požiadať koordinačnú službu o jeho obnovenie, ak je splnená podmienka obnovy.
Podmienka obnovy označuje súbor kritérií, ktoré musia byť splnené, aby mohol byť prenájom obnovený, napríklad to, že generátor je stále aktívny a stále potrebuje identifikátor uzla.
Držiteľ prenájmu je aktuálnym držiteľom rozsahu identifikátorov uzlov.
Prenájom je považovaný za aktívny a nevypršaný, ak sa nachádza vo svojom platnom časovom období.
Týmto spôsobom môžeme znížiť počet komunikácií na jednu za obdobie obnovy prenájmu, čím sa minimalizuje latencia a zvyšuje efektivita v distribuovaných systémoch.
Ochrana proti chybným hodinám
Služba prenájmu musí pri prideľovaní prenájmu kontrolovať konzistenciu časových značiek. Začiatok priradeného prenájmu musí byť väčší alebo rovný začiatku predchádzajúceho prenájmu.
Generátor by mal požiadavku odmietnuť, ak je aktuálna časová značka menšia ako začiatok prenájmu alebo väčšia ako koniec prenájmu.
Tento postup je dôležitý na ochranu jedinečnosti generovaných identifikátorov v prípade, že hodiny skočia dozadu. Napríklad ak hodiny skočia dozadu, nový prenájom by mohol byť pridelený s časom začiatku skorším ako pri predchádzajúcom prenájme, čo môže viesť k vygenerovaniu duplicitných identifikátorov. Odmietnutím požiadaviek s časovými značkami v rámci existujúceho obdobia prenájmu tomuto scenáru zabraňujeme a zachovávame jedinečnosť identifikátorov.
Rovnomernosť distribúcie identifikátorov
Na základe vyššie uvedeného histogramu vidíme, že distribúcia generovaných Randflake ID je veľmi rovnomerná. To naznačuje, že distribúciu identifikátorov možno použiť priamo ako kľúč pre sharding.
Záver
V tomto článku sme predstavili Randflake, nový algoritmus generovania identifikátorov, ktorý kombinuje výhody Snowflake a Sparx64.
Dúfame, že vám tento článok poskytol komplexné porozumenie Randflake a jeho implementácie.
Úplný zdrojový kód 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 zlepšiť Randflake a implementovať ho v iných programovacích jazykoch.
Plánujeme vydať produkčne pripravenú koordinačnú službu pre Randflake a Snowflake, ktorá bude open-source na GitHube. Sledujte aktualizácie!