Bemutatkozik a Randflake ID: egy elosztott, egységes, kiszámíthatatlan, egyedi véletlenszerű azonosító generátor.

Vegyünk egy olyan helyzetet, amikor egyedi 64-bites véletlenszámokat kell generálnunk, és külső felek nem képesek előre jelezni a következő vagy az előző számot.

Itt generálhatunk egy 8-bájtos véletlenszerű értéket, ellenőrizhetjük, hogy az már létezik-e az adatbázisban, majd eltárolhatjuk, ha egyedi.

Ez a módszer azonban számos hátránnyal jár. Az egyediség biztosításához minden generált számot adatbázisban kell tárolnunk. Az adatbázishoz legalább egy oda-vissza út szükségessége késleltetési problémákat okoz, különösen olyan elosztott környezetben, ahol a skálázhatóság kulcsfontosságú.

E problémák megoldására vezetjük be a Randflake ID-t: egy elosztott, egységes, előre nem jelezhető, egyedi véletlenszerű ID generátort.

Hogyan működik a Randflake ID?

A Randflake ID-t a Snowflake ID inspirálta, amely az X (korábban Twitter) által fejlesztett széles körben használt k-rendezett ID generálási mechanizmus.

A Snowflake ID az aktuális időbélyeget, egy csomópont-azonosítót és egy helyi számlálót használ az azonosító generálásához.

Ezt a megközelítést tovább bővítettük a véletlenszerű egyedi ID generáláshoz, és hozzáadtunk egy új titkos kulcs elemet.

A kulcsfontosságú ötlet egy blokk titkosítási réteg hozzáadása a meglévő egyedi ID generátorhoz, hogy a számok közötti kapcsolat előrejelzése lehetetlenné váljon.

A blokk titkosítás egy alapvető kriptográfiai funkció, amely egy rögzített hosszúságú nyílt szöveg blokkot azonos hosszúságú titkosított szöveg blokká alakít át. Ezt az átalakítást egy kriptográfiai kulcs irányítja. A blokk titkosítás megkülönböztető jellemzője a visszafordíthatósága: egy-az-egyhez (bijektív) függvénynek kell lennie, biztosítva, hogy minden egyedi bemenet egyedi kimenetnek felel meg, és fordítva. Ez a tulajdonság kulcsfontosságú a visszafejtéshez, lehetővé téve az eredeti nyílt szöveg visszaállítását a titkosított szövegből, ha a megfelelő kulcsot alkalmazzák.

Egy blokk titkosítás egy-az-egyhez függvényként történő alkalmazásával garantálhatjuk, hogy minden egyedi bemenetnek megfelelő egyedi kimenet keletkezik a meghatározott tartományon belül.

A szerkezet és a tervezési szempontok

Ezen alapvető koncepciókra építve vizsgáljuk meg, hogyan valósítja meg a Randflake ID ezeket az ötleteket a gyakorlatban.

A Randflake ID struktúra tartalmaz egy 30 bites unix időbélyeget másodperc pontossággal, egy 17 bites csomópont-azonosítót, egy 17 bites helyi számlálót és egy 64 bites blokk titkosítást, amely a sparx64 algoritmuson alapul.

Íme néhány tervezési döntés:

• A Google Cloud Platform egyes VM-példányai 0,2 ms pontossággal tudják szinkronizálni az órát, de ez a pontossági szint nem érhető el nyilvános interneten vagy más felhőszolgáltatóknál.

• A másodperc pontosságot választottuk, mert az órát a csomópontok között csak néhány milliszekundumos felbontással tudjuk hatékonyan szinkronizálni.

• A 17 bites csomópont-azonosító 131072 egyedi generátort tesz lehetővé ugyanabban a pillanatban, amelyek folyamatonként, magonként, szálanként hozzárendelhetők.

• Nagy átviteli sebességű rendszerekben a 17 bites helyi számláló elégtelen lehet. Az átviteli sebesség illesztéséhez több generátort is hozzárendelhetünk, mindegyiket különálló csomópont-azonosítóval, hogy egyetlen folyamatban vagy szálban dolgozzanak.

• A sparx64-et egy 64 bites blokk titkosításként fogadtuk el, amely egy modern, könnyű ARX-alapú blokk titkosítás.

• A Randflake ID-k belső nyomon követhetőséget biztosítanak, felfedve eredeti csomópont-azonosítójukat és időbélyegüket csak azoknak, akik rendelkeznek a titkos kulccsal.

• Az elméleti maximális átviteli sebesség 17 179 869 184 ID/s, ami elegendő a legtöbb globális méretű alkalmazáshoz.

A Randflake ID generálás pszeudokódja

A Randflake ID generálási folyamat további szemléltetésére a következő Python pszeudokód egy egyszerűsített implementációt biztosít:

 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 bit az időbélyeghez (34 év élettartam)
10RANDFLAKE_NODE_BITS = 17  # 17 bit a csomópont azonosítóhoz (max 131072 csomópont)
11RANDFLAKE_SEQUENCE_BITS = 17  # 17 bit a szekvenciához (max 131072 szekvencia)
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]

A Randflake gyártásra kész implementációja, amely csomópont-azonosító bérleti mechanizmust tartalmaz, elérhető a GitHub oldalon.

Egyéb megfontolások

Ebben a szakaszban a Randflake ID implementálásával kapcsolatos további szempontokat tárgyalunk.

Csomópont azonosító koordináció

Javasoljuk a bérlet alapú csomópont azonosító koordinációt.

Ebben a megközelítésben egy központi koordinációs szolgáltatás egyedi csomópont-azonosítót rendel minden generátorhoz.

Ez a csomópont-azonosító a bérleti időszak alatt nem kerül újra kiosztásra az egyediség biztosítása érdekében, csökkentve a koordinációs szolgáltatással való gyakori kommunikáció szükségességét.

A bérlettel rendelkező generátor kérheti a bérlet megújítását a koordinációs szolgáltatástól, ha a megújítási feltétel teljesül.

A megújítási feltétel olyan kritériumokra vonatkozik, amelyeknek teljesülniük kell a bérlet megújításához, például a generátor továbbra is aktív és igényli a csomópont-azonosítót.

A bérlet birtokosa a csomópont-azonosító tartomány aktuális birtokosa.

A bérlet aktívnak és lejártnak nem tekintendő, ha érvényes időszakán belül van.

Ily módon a körutak számát bérlet megújítási időszakonként egyre csökkenthetjük, minimalizálva a késleltetést és javítva a hatékonyságot az elosztott rendszerekben.

Hibás óra elleni védelem

A bérleti szolgáltatásnak ellenőriznie kell az időbélyeg konzisztenciáját a bérlet kiosztásakor. A kiosztott bérlet kezdő idejének nagyobbnak vagy egyenlőnek kell lennie az utolsó bérlet kezdő idejével.

A generátornak el kell utasítania a kérést, ha az aktuális időbélyeg kisebb, mint a bérlet kezdő ideje, vagy nagyobb, mint a bérlet befejezési ideje.

Ez az eljárás fontos a generált azonosítók egyediségének védelmében, amikor az óra visszaugrik. Például, ha az óra visszaugrik, egy új bérlet kiosztható egy korábban kiosztott bérletnél korábbi kezdő idővel, ami potenciálisan duplikált azonosítók generálásához vezethet. Azáltal, hogy elutasítjuk azokat a kéréseket, amelyek időbélyegei egy meglévő bérleti időszakon belül vannak, megakadályozzuk ezt a forgatókönyvet, és fenntartjuk az azonosítók egyediségét.

Az azonosító elosztásának egyenletessége

A fenti hisztogram alapján láthatjuk, hogy a generált Randflake ID-k eloszlása nagyon egyenletes. Ez azt sugallja, hogy az ID eloszlás közvetlenül felhasználható sharding kulcsként.

Összefoglalás

Ebben a cikkben bemutattuk a Randflake-et, egy új ID generálási algoritmust, amely egyesíti a Snowflake és a Sparx64 előnyeit.

Reméljük, hogy ez a cikk átfogó képet adott a Randflake-ről és annak implementációjáról.

A Randflake teljes forráskódja megtalálható a GitHub oldalon.

Ha bármilyen kérdése vagy javaslata van, kérjük, ne habozzon felvenni velünk a kapcsolatot. Keresünk közreműködőket is, akik segítenek a Randflake fejlesztésében és más programozási nyelveken történő implementálásában.

Tervezzük, hogy kiadunk egy gyártásra kész koordinációs szolgáltatást a Randflake és a Snowflake számára, amelyet nyílt forráskódúként teszünk közzé a GitHubon. Kövesse figyelemmel a frissítéseket!