Esittelyssä Randflake ID: hajautettu, yhtenäinen, ennakoimaton, uniikki satunnaistunnisteen luoja.

Kuvitellaan tilanne, 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 tietokannassa, ja sitten tallentaa sen, jos se on yksilöllinen.

Tällä menetelmällä on kuitenkin useita haittapuolia. Meidän on tallennettava kaikki luodut numerot tietokantaan yksilöllisyyden varmistamiseksi. Vaatimus vähintään yhdestä edestakaisesta tietokantakäynnistä aiheuttaa latenssiongelmia, erityisesti hajautetussa ympäristössä, jossa skaalautuvuus on ratkaisevaa.

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

Miten Randflake ID toimii?

Randflake ID on saanut inspiraationsa Snowflake ID:stä, laajalti käytetystä k-järjestetystä tunnisteen luontimekanismista, 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 satunnaisten yksilöllisten tunnisteiden luomiseen ja lisäsimme uuden salaisen avainelementin.

Keskeinen ajatus on lisätä lohkosalauskerros olemassa olevaan yksilölliseen tunnisteen generaattoriin, jotta numeroiden välisen suhteen ennustaminen olisi mahdotonta.

Lohkosalaus on perustavanlaatuinen kryptografinen funktio, joka muuntaa kiinteäpituisen selväkielilohkon samapituiseksi salakirjoituslohkoksi. Tätä muunnosta ohjaa kryptografinen avain. Lohkosalauksen erottava ominaisuus on sen palautuvuus: 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, mahdollistaen alkuperäisen selväkielisen tekstin palauttamisen salakirjoituksesta, 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 timestampin sekunnin tarkkuudella, 17-bittisen solmun tunnisteen, 17-bittisen paikallisen laskurin ja 64-bittisen lohkosalauksen, joka perustuu sparx64-algoritmiin.

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

Jotkin Google Cloud Platformin VM-instanssit voivat synkronoida kellon 0,2 ms:n tarkkuudella, mutta tätä tarkkuustasoa ei ole saatavilla julkisessa internetissä tai muissa pilvipalveluissa.
Valitsimme sekunnin tarkkuuden, koska voimme synkronoida kellon tehokkaasti solmujen välillä vain muutaman millisekunnin resoluutiolla.
17-bittinen solmun tunniste mahdollistaa 131072 yksittäistä generaattoria samanaikaisesti, jotka voidaan määrittää prosessikohtaisesti, ydinkohtaisesti 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 solmun ID, toimimaan yhdessä prosessissa tai säikeessä.
Otamme 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 solmun ID:n ja aikaleiman vain niille, joilla on salainen avain.
Teoreettinen maksimisuorituskyky on 17 179 869 184 ID/s, mikä riittää useimpiin globaaleihin sovelluksiin.

Randflake ID:n luomisen pseudokoodi

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

 1import time
 2import struct
 3from .sparx64 import Sparx64
 4
 5# Constants
 6RANDFLAKE_EPOCH_OFFSET = 1730000000  # Sunnuntai, lokakuu 27, 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ä solmun 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]

Tuotantovalmis toteutus Randflake-tunnisteelle, jossa on solmun ID-vuokrausmekanismi, on saatavilla GitHubista.

Muita huomioitavia asioita

Tässä osiossa käsitellään joitakin lisähuomioita Randflake ID:n toteutuksessa.

Solmun ID-koordinaatio

Ehdotamme vuokraukseen perustuvaa solmun ID-koordinaatiota.

Tässä lähestymistavassa keskitetty koordinaatiopalvelu määrittää jokaiselle generaattorille yksilöllisen solmun ID:n.

Tätä solmun ID:tä ei määritetä uudelleen vuokra-aikana yksilöllisyyden varmistamiseksi, mikä vähentää tarvetta usein tapahtuvaan kommunikointiin koordinaatiopalvelun kanssa.

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

Uusimisen ehto viittaa kriteeristöön, joka on täytettävä vuokrauksen uusimiseksi, kuten generaattorin aktiivisuus ja solmun ID:n tarve.

Vuokraaja on solmun ID-alueen nykyinen haltija.

Vuokraus katsotaan aktiiviseksi ja vanhentumattomaksi, jos se on voimassaoloaikansa sisällä.

Tällä tavoin voimme vähentää edestakaisia käyntejä yhteen vuokrauksen uusimisjaksolla, minimoiden latenssin ja parantaen tehokkuutta hajautetuissa järjestelmissä.

Suojaus virheellistä kelloa vastaan

Vuokrauspalvelun on tarkistettava aikaleiman johdonmukaisuus vuokraa myönnettäessä. Määritetyn vuokrauksen alkamisajan on oltava suurempi tai yhtä suuri kuin edellisen 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ä luotujen tunnisteiden yksilöllisyyden suojaamiseksi, 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ä voi johtaa päällekkäisten tunnisteiden luomiseen. Hylkäämällä pyynnöt, joiden aikaleimat ovat olemassa olevan vuokrausjakson sisällä, estämme tämän skenaarion ja säilytämme tunnisteiden yksilöllisyyden.

Tunnisteen jakautumisen yhtenäisyys

ID-jakautumisen histogrammi

Yllä olevan histogrammin perusteella voimme nähdä, että luotujen Randflake ID:iden jakauma on erittäin tasainen. Tämä viittaa siihen, että ID-jakaumaa voidaan käyttää suoraan sharding-avaimena.

Johtopäätös

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

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

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

Jos sinulla on kysyttävää tai ehdotuksia, älä epäröi ottaa yhteyttä. Etsimme myös avustajia auttamaan Randflaken parantamisessa ja sen toteuttamisessa muilla ohjelmointikielillä.

Suunnittelemme julkaisevamme tuotantovalmiin koordinaatiopalvelun Randflakelle ja Snowflake-tunnisteelle, joka avataan lähdekoodiksi GitHubissa. Pysy kuulolla päivityksistä!