Randflake ID: hajautettu 64-bittisen yksilöllisen tunnisteen generointi Sparx64-lohkosalauksella

Harkitse tilannetta, jossa meidän on generoitava ainutlaatuisia 64-bittisiä satunnaislukuja, eikä ulkopuolisten osapuolten pitäisi pystyä ennustamaan seuraavaa tai edellistä lukua.

Tässä voimme generoida 8 tavun satunnaisarvon, tarkistaa, onko se jo tietokannassa, ja tallentaa sen, jos se on ainutlaatuinen.

Tällä menetelmällä on kuitenkin useita haittapuolia. Meidän on tallennettava jokainen generoitu luku tietokantaan uniikkiuden varmistamiseksi. Vaatimus vähintään yhdestä kierrosmatkasta tietokantaan aiheuttaa viiveongelmia, erityisesti hajautetussa ympäristössä, jossa skaalautuvuus on ratkaisevan tärkeää.

Näiden ongelmien ratkaisemiseksi esittelemme Randflake ID:n: hajautetun, tasaisesti jakautuvan, ennustamattoman ja ainutlaatuisen satunnaisen tunnisteen generaattorin.

Miten Randflake ID toimii?

Randflake ID on saanut inspiraationsa Snowflake ID:stä, laajalti käytetystä k-lajitellusta tunnisteiden generointimekanismista, jonka on kehittänyt X (aiemmin Twitter).

Snowflake ID käyttää nykyistä aikaleimaa, solmutunnusta ja paikallista laskuria tunnisteen generoimiseen.

Laajensimme tätä lähestymistapaa edelleen satunnaisten ainutlaatuisten tunnisteiden generointiin ja lisäsimme uuden salaisen avaimen elementin.

Keskeinen ajatus on lisätä lohkosalauskerros olemassa olevaan ainutlaatuisten tunnisteiden generaattoriin, jotta lukujen välisen suhteen ennustaminen on käytännössä mahdotonta.

Lohkosalain on perustavanlaatuinen kryptografinen funktio, joka muuntaa kiinteän pituisen selkotekstilohkon samanpituiseksi salatekstilohkoksi. Tätä muunnosta ohjaa kryptografinen avain. Lohkosalaimen erottava ominaisuus on sen käänteisyys: sen on oltava yksi-yhteen (bijektiivinen) funktio, joka varmistaa, että jokainen yksilöllinen syöte vastaa yksilöllistä tulosta ja päinvastoin. Tämä ominaisuus on ratkaiseva salauksen purkamisen kannalta, sillä se mahdollistaa alkuperäisen selkotekstin palauttamisen salatekstistä oikealla avaimella.

Käyttämällä lohkosalainta yksi-yhteen-funktiona voimme taata, että jokainen yksilöllinen syöte tuottaa vastaavan yksilöllisen tulosteen määritellyllä alueella.

Rakenne ja suunnittelunäkökohdat

Rakentuen näille perusperiaatteille tarkastellaan seuraavaksi, miten Randflake ID toteuttaa nämä ajatukset käytännössä.

Randflake ID:n rakenne sisältää 30-bittisen Unix-aikaleiman sekuntitarkkuudella, 17-bittisen solmutunnuksen, 17-bittisen paikallisen laskurin sekä 64-bittisen lohkosalaimen, joka perustuu sparx64-algoritmiin.

Tässä on joitakin suunnittelupäätöksiä:

• Jotkin Google Cloud Platformin virtuaalikoneinstanssit voivat synkronoida kellon 0,2 ms:n tarkkuudella, mutta tämä tarkkuustaso ei ole saatavilla julkisessa internetissä tai muilla pilvipalveluntarjoajilla.

• Valitsimme sekuntitarkkuuden, koska voimme tehokkaasti synkronoida kellot solmujen välillä vain muutaman millisekunnin resoluutiolla.

• 17-bittinen solmutunnus mahdollistaa 131 072 yksittäistä generaattoria samanaikaisesti, ja ne voidaan määrittää prosessikohtaisesti, ytimekohtaisesti tai säikeittäin.

• Suuren läpäisykyvyn järjestelmissä 17-bittinen paikallinen laskuri saattaa olla riittämätön. Läpäisykyvyn vastaamiseksi voimme määrittää useita generaattoreita, joilla kullakin on yksilöllinen solmutunnus, toimimaan yhdessä prosessissa tai säikeessä.

• Valitsimme sparx64:n 64-bittiseksi lohkosalaimeksi, joka on moderni kevyt ARX-pohjainen lohkosalain.

• Randflake ID:t tarjoavat sisäistä jäljitettävyyttä, ja ne paljastavat alkuperäisen solmutunnuksensa ja aikaleimansa ainoastaan niille, jotka hallitsevat salaista avainta.

• Teoreettinen enimmäisläpäisykyky on 17 179 869 184 tunnistetta sekunnissa, mikä riittää useimpiin globaalin mittakaavan sovelluksiin.

Randflake ID:n generoinnin pseudokoodi

Randflake ID:n generointiprosessin havainnollistamiseksi seuraava Python-pseudokoodi tarjoaa yksinkertaistetun toteutuksen:

 1import time
 2import struct
 3from .sparx64 import Sparx64
 4
 5# Vakiot
 6RANDFLAKE_EPOCH_OFFSET = 1730000000  # Sunnuntai, 27. lokakuuta 2024 klo 3.33.20 UTC
 7
 8# Bittien jakaminen
 9RANDFLAKE_TIMESTAMP_BITS = 30  # 30 bittiä aikaleimalle (elinikä 34 vuotta)
10RANDFLAKE_NODE_BITS = 17  # 17 bittiä solmutunnukselle (enintään 131072 solmua)
11RANDFLAKE_SEQUENCE_BITS = 17  # 17 bittiä sekvenssille (enintään 131072 sekvenssiä)
12
13# Johdetut vakiot
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]

Tuotantovalmis Randflake-toteutus, joka sisältää solmutunnuksen vuokrausmekanismin, on saatavilla GitHubissa.

Muut näkökohdat

Tässä osiossa käsittelemme joitakin lisänäkökohtia Randflake ID:n toteuttamiseen.

Solmutunnusten koordinointi

Ehdotamme vuokrapohjaista solmutunnusten koordinointia.

Tässä lähestymistavassa keskitetty koordinointipalvelu määrittää jokaiselle generaattorille yksilöllisen solmutunnuksen.

Tätä solmutunnusta ei uudelleenmääritetä vuokra-ajan aikana uniikkiuden varmistamiseksi, mikä vähentää tarvetta tiheään kommunikointiin koordinointipalvelun kanssa.

Vuokran haltuunottava generaattori voi pyytää vuokran uusimista koordinointipalvelulta, jos uusimisehto täyttyy.

Uusimisehto tarkoittaa joukkoa kriteerejä, joiden on täytyttävä, jotta vuokra voidaan uusia, kuten se, että generaattori on yhä aktiivinen ja tarvitsee solmutunnusta.

Vuokranhaltija on solmutunnusalueen nykyinen haltija.

Vuokra on voimassa ja ei vanhentunut, jos se on sen kelvollisella voimassaoloajanjaksolla.

Näin voimme vähentää kierrosmatkat yhteen per vuokran uusimisjakso, mikä minimoi viiveen ja parantaa tehokkuutta hajautetuissa järjestelmissä.

Suojautuminen virheellistä kelloa vastaan

Vuokrapalvelun on tarkistettava aikaleimojen johdonmukaisuus vuokraa myöntäessään. Myönnetyn vuokran alkuajan on oltava suurempi tai yhtä suuri kuin viimeksi myönnetyn vuokran alkuaika.

Generaattorin tulee hylätä pyyntö, jos nykyinen aikaleima on pienempi kuin vuokran alkuaika tai suurempi kuin vuokran loppuaika.

Tämä menettely on tärkeä Randflake-tunnisteiden uniikkiuden suojaamiseksi silloin, kun kello hyppää taaksepäin. Esimerkiksi jos kello hyppää taaksepäin, uusi vuokra voitaisiin myöntää alkuajalla, joka on aiemmin myönnetyn vuokran alkuaikaa aikaisempi, mikä voisi johtaa tuplatunnisteiden generoitumiseen. Hylkäämällä pyynnöt, joiden aikaleimat kuuluvat olemassa olevan vuokran voimassaoloajanjaksoon, estämme tämän tilanteen ja ylläpidämme tunnisteiden uniikkiutta.

Tunnisteiden jakauman tasaisuus

Yllä olevan histogrammin perusteella voimme todeta, että generoitujen Randflake-tunnisteiden jakauma on erittäin tasainen. Tämä viittaa siihen, että tunnisteiden jakaumaa voidaan käyttää suoraan shardausavaimena.

Yhteenveto

Tässä artikkelissa esittelimme Randflaken, uuden tunnisteiden generointialgoritmin, joka yhdistää Snowflaken ja Sparx64:n edut.

Toivomme, että tämä artikkeli on antanut sinulle kattavan käsityksen Randflakesta ja sen toteutuksesta.

Randflaken täyden lähdekoodin löydät GitHubista.

Jos sinulla on kysymyksiä tai ehdotuksia, älä epäröi ottaa yhteyttä. Etsimme myös avustajia, jotka auttavat kehittämään Randflakea ja toteuttamaan sen muilla ohjelmointikielillä.

Suunnittelemme julkaisevamme tuotantovalmiin koordinointipalvelun Randflakelle ja Snowflakelle, joka avataan GitHubissa. Pysy kuulolla päivitysten osalta!