GoSudaRandflake ID: elosztott, 64 bites egyedi azonosító-generálás Sparx64 blokk-titkosítóval
Tekintsünk egy olyan helyzetet, amikor egyedi, 64 bites véletlen számokat kell generálnunk, és külső felek ne tudják megjósolni a következő vagy az előző számot.
Ebben az esetben generálhatunk egy 8 bájtos véletlen értéket, ellenőrizhetjük, hogy az már létezik-e az adatbázisban, majd tárolhatjuk, ha egyedi.
Ennek a módszernek azonban számos hátránya van. Minden generált számot adatbázisban kell tárolnunk az egyediség biztosításához. Az, hogy legalább egy adatbázis-kéréssel kell körbejárnunk, késleltetési problémákat okoz, különösen elosztott környezetben, ahol a skálázhatóság kulcsfontosságú.
Ezen problémák megoldására vezetjük be a Randflake ID-t: egy elosztott, egyenletes, kiszámíthatatlan és egyedi véletlen azonosító-generátort.
Hogyan működik a Randflake ID?
A Randflake ID a Snowflake ID-ból indul ki, amely az X (korábban Twitter) által kifejlesztett, széles körben használt, k-rendezett azonosító-generálási mechanizmus.
A Snowflake ID az aktuális időbélyeget, egy csomóponti azonosítót (node ID) és egy helyi számlálót használ az azonosító előállítására.
Ezt a megközelítést tovább bővítettük véletlen egyedi azonosítók generálására, és egy új titkos kulcs elemmel egészítettük ki.
A kulcsgondolat az, hogy a meglévő egyedi azonosító-generátorhoz blokk-titkosító réteget adunk, hogy a számok közötti összefüggés megjóslása megvalósíthatatlan legyen.
A blokk-titkosító egy alapvető kriptográfiai függvény, amely a rögzített hosszúságú nyílt szöveg blokkját azonos hosszúságú titkosszöveg-blokká alakítja. Ezt az átalakítást egy kriptográfiai kulcs szabályozza. A blokk-titkosító megkülönböztető jellemzője a visszafordíthatósága: egy-egyértelmű (bijektív) függvénynek kell lennie, amely biztosítja, hogy minden egyedi bemenet egyedi kimenetnek felel meg, és fordítva. Ez a tulajdonság alapvető fontosságú a visszafejtéshez, mivel a helyes kulcs alkalmazásakor az eredeti nyílt szöveg visszanyerhető a titkosszövegből.
Ha a blokk-titkosítót egy-egyértelmű függvényként alkalmazzuk, garantálhatjuk, hogy minden egyedi bemenet a definiált tartományon belül egy megfelelő egyedi kimenetet állít elő.
A szerkezet és a tervezési szempontok
Ezekre az alapfogalmakra építve vizsgáljuk meg, hogyan valósítja meg a Randflake ID ezeket az elveket a gyakorlatban.
A Randflake ID szerkezete egy 30 bites, másodperc pontosságú unix időbélyeget, egy 17 bites csomópont-azonosítót, egy 17 bites helyi számlálót és a sparx64 algoritmuson alapuló 64 bites blokk-titkosítót tartalmaz.
Néhány tervezési döntés:
A Google Cloud Platform egyes virtuális géppéldányai 0,2 ms pontossággal tudják szinkronizálni az órát, de ez a pontosság nem érhető el a nyilvános internetenvagy más felhőszolgáltatóknál.
Másodperc pontosságot választottunk, mert a csomópontok közötti óraszinkronizálást csak néhány milliszekundumos felbontáson tudjuk hatékonyan megvalósítani.
A 17 bites csomópont-azonosító egyidejűleg 131072 egyedi generátort tesz lehetővé, amelyek folyamatonként, magonként vagy szálanként rendelhetők hozzá.
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 rendelhetünk hozzá, mindegyiket egyedi csomópont-azonosítóval, hogy egyetlen folyamatban vagy szálon működjenek.
A 64 bites blokk-titkosítóként a sparx64 algoritmust alkalmaztuk, amely egy modern, könnyűsúlyú, ARX-alapú blokk-titkosító.
A Randflake azonosítók belső nyomonkövethetőséget biztosítanak: eredeti csomópont-azonosítójukat és időbélyegüket csak a titkos kulccsal rendelkezők láthatják.
Az elméleti maximális átviteli sebesség 17 179 869 184 azonosító/s, ami a legtöbb globális méretű alkalmazás számára elegendő.
A Randflake ID generálás álkódja
A Randflake ID generálási folyamatának további szemléltetésére a következő Python-álkód egyszerűsített megvalósítást nyújt:
1import time
2import struct
3from .sparx64 import Sparx64
4
5# Konstansok
6RANDFLAKE_EPOCH_OFFSET = 1730000000 # Vasárnap, 2024. október 27., 3:33:20 UTC
7
8# Bitkiosztás
9RANDFLAKE_TIMESTAMP_BITS = 30 # 30 bit az időbélyegnek (34 éves élettartam)
10RANDFLAKE_NODE_BITS = 17 # 17 bit a csomópont-azonosítónak (legfeljebb 131072 csomópont)
11RANDFLAKE_SEQUENCE_BITS = 17 # 17 bit a sorszámnak (legfeljebb 131072 sorszám)
12
13# Származtatott konstansok
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]
Egy éles használatra kész, csomópont-azonosító bérleti mechanizmust tartalmazó Randflake-implementáció a GitHubon érhető el.
Egyéb szempontok
Ebben a szakaszban a Randflake ID megvalósításának néhány további szempontját tárgyaljuk.
Csomópont-azonosítók koordinálása
Bérleten alapuló csomópont-azonosító koordinálást javasolunk.
Ebben a megközelítésben egy központi koordinációs szolgáltatás minden generátornak egyedi csomópont-azonosítót rendel.
Ezt a csomópont-azonosítót a bérleti időszak alatt nem osztják ki újra, hogy biztosítsák az egyediséget, ami csökkenti a koordinációs szolgáltatással való gyakori kommunikáció szükségességét.
A bérletet birtokoló 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ériumok összességét jelenti, amelyeknek teljesülniük kell ahhoz, hogy a bérlet megújítható legyen, például hogy a generátor még aktív, és továbbra is szüksége van a csomópont-azonosítóra.
A bérletes (leaseholder) a csomópont-azonosító tartomány aktuális birtokosa.
A bérlet akkor tekinthető aktívnak és nem lejártnak, ha érvényes időszakán belül van.
Így a bérlet megújítási időszakonként legfeljebb egy körutazásra csökkenthető, ami minimalizálja a késleltetést és javítja a hatékonyságot az elosztott rendszerekben.
Védelem hibás óra ellen
A bérletszolgáltatásnak ellenőriznie kell az időbélyegek konzisztenciáját a bérlet kiosztásakor. A kiosztott bérlet kezdési idejének nagyobbnak vagy egyenlőnek kell lennie az utolsó bérlet kezdési idejével.
A generátornak el kell utasítania a kérést, ha az aktuális időbélyeg kisebb a bérlet kezdési idejénél, vagy nagyobb a bérlet befejezési idejénél.
Ez az eljárás fontos a generált azonosítók egyediségének védelmében, amikor az óra visszafelé ugrik. Például, ha az óra visszafelé ugrik, előfordulhat, hogy egy új bérletet a korábban kiosztott bérletnél korábbi kezdési idővel osztanak ki, ami duplikált azonosítók generálásához vezethet. A létező bérleti időszakon belüli időbélyegű kérések elutasításával megakadályozzuk ezt a helyzetet, és fenntartjuk az azonosítók egyediségét.
Azonosítóeloszlás egyenletessége
A fenti hisztogram alapján láthatjuk, hogy a generált Randflake azonosítók eloszlása nagyon egyenletes. Ez arra utal, hogy az azonosítóeloszlás közvetlenül használható shardolási kulcsként.
Következtetés
Ebben a cikkben a Randflake-et mutattuk be, egy újszerű azonosító-generálási algoritmust, amely ötvözi a Snowflake és a Sparx64 előnyeit.
Reméljük, hogy ez a cikk átfogó képet adott a Randflake-ről és megvalósításáról.
A Randflake teljes forráskódja a GitHubon érhető el.
Ha kérdése vagy javaslata van, nyugodtan lépjen velünk kapcsolatba. Emellett olyan közreműködőket keresünk, akik segítenek a Randflake fejlesztésében és más programozási nyelvekben történő megvalósításában.
Egy éles használatra kész koordinációs szolgáltatást tervezünk kiadni a Randflake és a Snowflake számára, amely nyílt forráskódú lesz a GitHubon. Figyelje a frissítéseket!