--- id: c6fb06cc6cc2bcfd669fca4de7868882 author: Lemon Mint title: 'Randflake ID: generování distribuovaných 64bitových unikátních identifikátorů pomocí blokové šifry Sparx64' description: Distribuovaný generátor unikátních 64bitových identifikátorů, který kombinuje 30bitovou časovou značku, 17bitový identifikátor uzlu, 17bitový lokální čítač a blokovou šifru Sparx64 ARX pro nepředvídatelné identifikátory. language: cs date: 2024-12-09T14:50:44.030047Z path: /randflake go_package: gosuda.org/randflake go_repourl: https://github.com/gosuda/randflake.git category: security --- Zvažte situaci, kdy potřebujeme generovat jedinečná 64bitová náhodná čísla a externí strany nesmějí být schopny předpovědět další ani 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 jedinečná. Tato metoda však má několik nevýhod. Musíme ukládat každé vygenerované číslo do databáze, abychom zajistili jedinečnost. Požadavek alespoň jedné round trip komunikace s databází způsobuje problémy s latencí, zejména v distribuovaném prostředí, kde je škálovatelnost zásadní. Abychom tyto problémy vyřešili, představujeme Randflake ID: distribuovaný, rovnoměrný, nepředvídatelný a jedinečný generátor náhodných ID. ## Jak funguje Randflake ID? Randflake ID je inspirováno Snowflake ID, široce používaným mechanismem generování k-seřazených identifikátorů, který vyvinula společnost X (dříve Twitter). Snowflake ID používá aktuální časové razítko, identifikátor uzlu a lokální čítač ke generování identifikátoru. Tento přístup jsme dále rozšířili pro generování náhodných jedinečných ID a přidali nový prvek tajného klíče. Klíčovou myšlenkou je přidání vrstvy blokové šifry k existujícímu generátoru jedinečných ID, aby bylo dosaženo nemožnosti předpovědět vztah mezi čísly. Bloková šifra je základní kryptografická funkce, která transformuje blok otevřeného textu pevné délky na blok šifrovaného textu stejné délky. Tato transformace je řízena kryptografickým klíčem. Rozlišovací vlastností blokové šifry je její reverzibilita: musí se jednat o jednoznačnou (bijektivní) funkci, která zajišťuje, že každý jedinečný vstup odpovídá jedinečnému výstupu a naopak. Tato vlastnost je klíčová pro dešifrování, které umožňuje obnovit původní otevřený text ze šifrovaného textu při použití správného klíče. Použitím blokové šifry jako jednoznačné funkce můžeme zaručit, že každý jedinečný vstup vytvoří odpovídající jedinečný výstup v definovaném rozsahu. ## Struktura a návrhová hlediska Na základě těchto základních konceptů se podívejme, jak Randflake ID tyto myšlenky implementuje 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á návrhová rozhodnutí: - Některé virtuální instance v Google Cloud Platform dokážou synchronizovat hodiny s přesností 0,2 ms, ale taková úroveň přesnosti není dostupná na veřejném internetu ani u jiných poskytovatelů cloudu. - Zvolili jsme přesnost na sekundy, protože hodiny mezi uzly dokážeme efektivně synchronizovat pouze s rozlišením na několik milisekund. - 17bitový identifikátor uzlu umožňuje 131072 jednotlivých generátorů ve stejný okamžik, které lze přiřazovat způsobem na proces, na jádro nebo na vlákno. - U systémů s vysokou propustností může být 17bitový lokální čítač nedostatečný. Abychom odpovídali propustnosti, můžeme přiřadit více generátorů, každý s odlišným identifikátorem uzlu, aby pracovaly v rámci jednoho procesu nebo vlákna. - Jako 64bitovou blokovou šifru jsme přijali sparx64, moderní lehkou blokovou šifru založenou na ARX. - Randflake ID nabízejí interní sledovatelnost, která odhaluje identifikátor uzlu, který je vygeneroval, a časové razítko pouze těm, kdo vlastní tajný klíč. - Teoretická maximální propustnost činí 17 179 869 184 ID/s, což je dostatečné pro většinu aplikací globálního rozsahu. ## Pseudokód generování Randflake ID Pro lepší ilustraci procesu generování Randflake ID poskytuje následující pseudokód v Pythonu zjednodušenou implementaci: ```python import time import struct from .sparx64 import Sparx64 # Konstanty RANDFLAKE_EPOCH_OFFSET = 1730000000 # Neděle, 27. října 2024 3:33:20 AM UTC # Alokace bitů RANDFLAKE_TIMESTAMP_BITS = 30 # 30 bitů pro časové razítko (životnost 34 let) RANDFLAKE_NODE_BITS = 17 # 17 bitů pro identifikátor uzlu (max. 131072 uzlů) RANDFLAKE_SEQUENCE_BITS = 17 # 17 bitů pro sekvenci (max. 131072 sekvencí) # Odvozené konstanty RANDFLAKE_MAX_TIMESTAMP = RANDFLAKE_EPOCH_OFFSET + (1 << RANDFLAKE_TIMESTAMP_BITS) - 1 RANDFLAKE_MAX_NODE = (1 << RANDFLAKE_NODE_BITS) - 1 RANDFLAKE_MAX_SEQUENCE = (1 << RANDFLAKE_SEQUENCE_BITS) - 1 class Randflake: def __init__(self, node_id: int, secret: bytes): self.node_id = int(node_id) self.sequence = int(0) self.rollover = int(time.time()) self.sbox = Sparx64(secret) def _new_raw(self) -> int: while True: now = int(time.time()) self.sequence += 1 sequence = self.sequence if sequence > RANDFLAKE_MAX_SEQUENCE: if now > self.rollover: self.sequence = 0 self.rollover = now sequence = 0 else: continue timestamp = now - RANDFLAKE_EPOCH_OFFSET return (timestamp << 34) | (self.node_id << 17) | sequence def generate(self) -> int: id_raw = self._new_raw() src = struct.pack("