Bemutatkozik a Randflake ID: egy elosztott, egységes, kiszámíthatatlan, egyedi véletlenszerű ID 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.
Ilyenkor generálhatunk egy 8-bájtos véletlen értéket, ellenőrizhetjük, hogy létezik-e már az adatbázisban, majd eltárolhatjuk, ha egyedi.
Ez a módszer azonban számos hátránnyal jár. Minden generált számot tárolnunk kell egy adatbázisban az egyediség biztosításához. Az adatbázishoz legalább egy oda-vissza út szükségessége késleltetési problémákat okoz, különösen egy elosztott környezetben, ahol a skálázhatóság kulcsfontosságú.
Ezen problémák megoldására mutatjuk be a Randflake ID-t: egy elosztott, egységes, előre nem jelezhető, egyedi véletlen ID generátort.
Hogyan működik a Randflake ID?
A Randflake ID-t a Snowflake ID inspirálta, a széles körben használt k-rendezett ID generálási mechanizmus, amelyet az X (korábban Twitter) fejlesztett ki.
A Snowflake ID az aktuális időbélyeget, egy node ID-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 az egyedi véletlen ID generáláshoz, és hozzáadtunk egy új titkos kulcs elemet.
A kulcsfontosságú ötlet egy blokk-rejtjelező réteg hozzáadása a meglévő egyedi ID generátorhoz, hogy a számok közötti kapcsolat előrejelzését kivitelezhetetlenné tegyük.
A blokk-rejtjelező egy alapvető kriptográfiai függvény, 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-rejtjelező 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 egy 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, amikor a megfelelő kulcsot alkalmazzák.
Egy blokk-rejtjelező egy-az-egyhez függvényként történő alkalmazásával garantálhatjuk, hogy minden egyedi bemenet egy megfelelő egyedi kimenetet eredményez a meghatározott tartományon belül.
A struktúra é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 node azonosítót, egy 17 bites helyi számlálót és egy 64 bites blokk-rejtjelezőt, 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ónál.
Másodperc pontosságot választottunk, mert az órát a node-ok között csak néhány milliszekundum felbontáson belül tudjuk hatékonyan szinkronizálni.
A 17 bites node 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, mindegyiknek külön node ID-vel, hogy egyetlen folyamatban vagy szálban működjenek.
A sparx64-et 64 bites blokk-rejtjelezőként fogadtuk el, amely egy modern, könnyű, ARX-alapú blokk-rejtjelező.
A Randflake ID-k belső nyomon követhetőséget kínálnak, a származási node ID-t és az időbélyeget csak azoknak fedik fel, 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.
Randflake ID generálás pszeudokódja
A Randflake ID generálási folyamat további illusztrálására az alábbi Python pszeudokód egy egyszerűsített implementációt mutat be:
1import time
2import struct
3from .sparx64 import Sparx64
4
5# Konstansok
6RANDFLAKE_EPOCH_OFFSET = 1730000000 # Vasárnap, 2024. október 27., 3:33:20 AM UTC
7
8# Bit allokáció
9RANDFLAKE_TIMESTAMP_BITS = 30 # 30 bit időbélyeghez (34 év élettartam)
10RANDFLAKE_NODE_BITS = 17 # 17 bit node ID-hez (max 131072 node)
11RANDFLAKE_SEQUENCE_BITS = 17 # 17 bit szekvenciához (max 131072 szekvencia)
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]
A Randflake gyártásra kész implementációja, amely node ID bérleti mechanizmust is tartalmaz, elérhető a GitHubon.
Egyéb szempontok
Ebben a szakaszban a Randflake ID implementálásának további szempontjait tárgyaljuk.
Node ID koordináció
Javasoljuk a bérlet alapú node ID koordinációt.
Ebben a megközelítésben egy központi koordinációs szolgáltatás egyedi node ID-t rendel minden generátorhoz.
Ez a node ID a bérleti időszak alatt nem kerül újra kiosztásra az egyediség biztosítása érdekében, csökkentve a gyakori kommunikáció szükségességét a koordinációs szolgáltatással.
A bérletet birtokló 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 utal, amelyeknek teljesülniük kell a bérlet megújításához, például, hogy a generátor továbbra is aktív legyen és igényelje a node ID-t.
A bérlő a node ID tartomány jelenlegi birtokosa.
A bérlet aktívnak és lejártnak nem tekinthető, ha érvényes időtartamán belül van.
Így csökkenthetjük az oda-vissza utazások számát bérlet megújítási időszakonként egyre, minimalizálva a késleltetést és javítva a hatékonyságot az elosztott rendszerekben.
Védekezés a hibás óra ellen
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ési időpontjának nagyobbnak vagy egyenlőnek kell lennie az utolsó bérlet kezdési időpontjával.
A generátornak el kell utasítania a kérést, ha az aktuális időbélyeg kisebb, mint a bérlet kezdési időpontja, vagy nagyobb, mint a bérlet befejezési időpontja.
Ez az eljárás fontos a generált ID-k egyediségének védelméhez, amikor az óra visszaugrik. Például, ha egy óra visszaugrik, új bérletet lehetne kiosztani egy korábbi kezdési időponttal, mint egy korábban kiosztott bérlet, ami potenciálisan duplikált ID-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, megelőzzük ezt a forgatókönyvet és fenntartjuk az ID-k egyediségét.
Az ID eloszlás egységessége
A fenti hisztogram alapján láthatjuk, hogy a generált Randflake ID-k eloszlása nagyon egységes. Ez arra utal, hogy az ID eloszlás közvetlenül használható sharding key-ként.
Konklúzió
Ebben a cikkben bemutattuk a Randflake-et, egy új ID generáló algoritmust, amely egyesíti a Snowflake és a Sparx64 előnyeit.
Reméljük, hogy ez a cikk átfogó megértést nyújtott Önnek a Randflake-ről és annak implementációjáról.
A Randflake teljes forráskódja megtalálható a GitHubon.
Ha bármilyen kérdése vagy javaslata van, kérjük, ne habozzon kapcsolatba lépni velünk. Keresünk hozzájárulókat is, akik segítenek a Randflake fejlesztésében és más programozási nyelveken történő implementálásában.
Tervezzük egy gyártásra kész koordinációs szolgáltatás kiadását a Randflake és a Snowflake számára, amelyet nyílt forráskódúvá teszünk a GitHubon. Maradjon velünk a frissítésekért!