Esittelyssä Randflake ID: hajautettu, yhtenäinen, ennakoimaton ja uniikki satunnainen tunnisteen generaattori.

Tarkastellaan tilannetta, jossa meidän on luotava yksilöllisiä 64-bittisiä satunnaislukuja, ja ulkopuoliset tahot eivät saisi pystyä ennustamaan seuraavaa tai edellistä lukua.

Tässä tapauksessa voimme luoda 8-tavun satunnaisarvon, tarkistaa, onko se jo olemassa tietokannassa, ja sitten tallentaa sen, jos se on yksilöllinen.

Tällä menetelmällä on kuitenkin useita haittoja. Meidän on tallennettava jokainen luotu luku tietokantaan yksilöllisyyden varmistamiseksi. Vaatimus vähintään yhdestä edestakaisesta tietokantakäynnistä aiheuttaa latenssiongelmia, erityisesti hajautetussa ympäristössä, jossa skaalautuvuus on ratkaisevan tärkeää.

Näiden ongelmien ratkaisemiseksi esittelemme Randflake ID:n: hajautetun, yhtenäisen, ennustamattoman, yksilöllisen satunnaisen ID-generaattorin.

Miten Randflake ID toimii?

Randflake ID on saanut inspiraationsa Snowflake ID:stä, laajalti käytetystä k-järjestetystä ID:n generointimekanismista, jonka on kehittänyt X (entinen Twitter).

Snowflake ID käyttää nykyistä aikaleimaa, solmun ID:tä ja paikallista laskuria tunnisteen luomiseen.

Laajensimme tätä lähestymistapaa edelleen satunnaisen yksilöllisen ID:n generointia varten ja lisäsimme uuden salaisen avainelementin.

Keskeinen ajatus on lisätä lohkosalauskerros olemassa olevaan yksilölliseen ID-generaattoriin, jotta numeroiden välisten suhteiden ennustaminen olisi mahdotonta.

Lohkosalaus on perustavanlaatuinen kryptografinen funktio, joka muuntaa kiinteäpituisen selväkielilohkon samapituiseksi salakielilohkoksi. Tätä muunnosta ohjaa kryptografinen avain. Lohkosalauksen erottava ominaisuus on sen palautettavuus: sen on oltava yksi-yhteen (bijektiivinen) funktio, joka varmistaa, että jokainen yksilöllinen syöte vastaa yksilöllistä tulostetta ja päinvastoin. Tämä ominaisuus on ratkaisevan tärkeä salauksen purkamisessa, sillä se mahdollistaa alkuperäisen selväkielitekstin palauttamisen salakielitekstistä, kun oikea avain on käytössä.

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

Rakenne ja suunnittelunäkökohdat

Näiden peruskäsitteiden pohjalta tarkastellaan, miten Randflake ID toteuttaa nämä ideat käytännössä.

Randflake ID:n rakenne sisältää 30-bittisen unix-aikaleiman sekunnin tarkkuudella, 17-bittisen solmutunnisteen, 17-bittisen paikallisen laskurin ja 64-bittisen lohkosalauksen, joka perustuu sparx64-algoritmiin.

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

Jotkin VM-instanssit Google Cloud Platformissa voivat synkronoida kellon 0,2 ms:n tarkkuudella, mutta tämä tarkkuustaso ei ole saatavilla julkisessa internetissä tai muissa pilvipalveluntarjoajissa.
Valitsimme sekunnin tarkkuuden, koska voimme synkronoida kellon tehokkaasti solmujen välillä vain muutaman millisekunnin tarkkuudella.
17-bittinen solmutunniste mahdollistaa 131072 yksittäistä generaattoria samanaikaisesti, jotka voidaan määrittää prosessikohtaisesti, ytimen mukaan tai säikeittäin.
Suuren suorituskyvyn järjestelmissä 17-bittinen paikallinen laskuri voi olla riittämätön. Suorituskyvyn vastaamiseksi voimme määrittää useita generaattoreita, joilla kullakin on oma solmu-ID, toimimaan yhdessä prosessissa tai säikeessä.
Otimme käyttöön sparx64:n 64-bittisenä lohkosalauksena, joka on moderni kevyt ARX-pohjainen lohkosalaus.
Randflake ID:t tarjoavat sisäisen jäljitettävyyden, paljastaen niiden alkuperäisen solmu-ID:n ja aikaleiman vain niille, joilla on salainen avain.
Teoreettinen maksimisuorituskyky on 17 179 869 184 ID/s, 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# Constants
 6RANDFLAKE_EPOCH_OFFSET = 1730000000  # Sunnuntai, 27. lokakuuta 2024 3:33:20 AM UTC
 7
 8# Bits allocation
 9RANDFLAKE_TIMESTAMP_BITS = 30  # 30 bittiä aikaleimalle (elinkaari 34 vuotta)
10RANDFLAKE_NODE_BITS = 17  # 17 bittiä solmu-ID:lle (max 131072 solmua)
11RANDFLAKE_SEQUENCE_BITS = 17  # 17 bittiä sekvenssille (max 131072 sekvenssiä)
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]

Randflaken tuotantovalmis toteutus, jossa on solmu-ID:n vuokrausmekanismi, on saatavilla GitHubissa.

Muita huomioitavia asioita

Tässä osiossa käsittelemme joitakin lisähuomioita Randflake ID:n toteuttamisessa.

Solmu-ID:n koordinointi

Ehdotamme vuokraukseen perustuvaa solmu-ID:n koordinointia.

Tässä lähestymistavassa keskitetty koordinointipalvelu määrittää yksilöllisen solmu-ID:n jokaiselle generaattorille.

Tätä solmu-ID:tä ei uudelleenmääritetä vuokrausjakson aikana yksilöllisyyden varmistamiseksi, mikä vähentää tarvetta usein toistuvalle kommunikaatiolle koordinointipalvelun kanssa.

Vuokrausta hallussaan pitävä generaattori voi pyytää vuokrauksen uusimista koordinointipalvelulta, jos uusimisen ehto täyttyy.

Uusimisen ehto viittaa kriteereihin, jotka on täytettävä vuokrauksen uusimiseksi, kuten generaattorin aktiivisuuden ja solmu-ID:n tarpeen.

Vuokraaja on solmu-ID-alueen nykyinen haltija.

Vuokrausta pidetään aktiivisena ja vanhentumattomana, jos se on voimassaoloajallaan.

Tällä tavoin voimme vähentää edestakaiset matkat yhteen vuokrauksen uusimisjaksoa kohti, minimoiden latenssin ja parantaen tehokkuutta hajautetuissa järjestelmissä.

Virheellisen kellon lieventäminen

Vuokrauspalvelun on tarkistettava aikaleiman johdonmukaisuus vuokraa myönnettäessä. Määrätyn vuokrauksen alkamisajan on oltava suurempi tai yhtä suuri kuin viimeisimmän vuokrauksen alkamisajan.

Generaattorin tulee hylätä pyyntö, jos nykyinen aikaleima on pienempi kuin vuokrauksen alkamisaika tai suurempi kuin vuokrauksen päättymisaika.

Tämä menettely on tärkeä suojata luotujen ID:iden yksilöllisyyttä, kun kello hyppää taaksepäin. Esimerkiksi, jos kello hyppää taaksepäin, uusi vuokraus voitaisiin määrätä alkamisajalla, joka on aikaisempi kuin aiemmin määrätty vuokraus, mikä saattaa johtaa päällekkäisten ID:iden luomiseen. Hylkäämällä pyynnöt, joiden aikaleimat ovat olemassa olevan vuokrausjakson sisällä, estämme tämän skenaarion ja säilytämme ID:iden yksilöllisyyden.

ID-jakautumisen tasaisuus

Histogram of ID distribution

Yllä olevan histogrammin perusteella voimme nähdä, että luotujen Randflake ID:iden jakautuminen on erittäin tasaista. Tämä viittaa siihen, että ID-jakautumista voidaan käyttää suoraan sharding keynä.

Johtopäätös

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

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

Randflaken koko lähdekoodi löytyy GitHubista.

Jos sinulla on kysyttävää tai ehdotuksia, älä epäröi ottaa yhteyttä. Etsimme myös avustajia parantamaan Randflakea ja toteuttamaan sen muilla ohjelmointikielillä.

Suunnittelemme julkaisevamme tuotantovalmiin koordinointipalvelun Randflakelle ja Snowflakelle, joka avataan avoimen lähdekoodin periaatteella GitHubissa. Pysy kuulolla päivityksistä!