--- id: c6fb06cc6cc2bcfd669fca4de7868882 author: Lemon Mint title: 'Randflake ID: Generarea distribuită a identificatorilor unici pe 64 de biți cu ajutorul cifrului bloc Sparx64' description: Generator distribuit de identificatori unici pe 64 de biți, care combină un marcaj temporal pe 30 de biți, un identificator de nod pe 17 biți, un contor local pe 17 biți și algoritmul de cifrare bloc Sparx64 ARX, pentru a produce identificatori imprevizibili. language: ro date: 2024-12-09T14:50:44.030047Z path: /randflake go_package: gosuda.org/randflake go_repourl: https://github.com/gosuda/randflake.git category: security --- Luați în considerare o situație în care trebuie să generăm numere aleatoare unice pe 64 de biți, iar entitățile externe nu ar trebui să poată prezice numărul următor sau pe cel anterior. Aici, putem genera o valoare aleatoare de 8 octeți, verifica dacă aceasta există deja în baza de date și apoi o stoca dacă este unică. Totuși, această metodă prezintă mai multe dezavantaje. Trebuie să stocăm fiecare număr generat într-o bază de date pentru a asigura unicitatea. Necesitatea a cel puțin o călătorie dus-întors către baza de date generează probleme de latență, mai ales într-un mediu distribuit, unde scalabilitatea este esențială. Pentru a rezolva aceste probleme, introducem Randflake ID: un generator distribuit, uniform, imprevizibil și unic de identificatori aleatori. ## Cum funcționează Randflake ID? Randflake ID este inspirat de Snowflake ID, mecanismul k-sortabil de generare a identificatorilor utilizat pe scară largă, dezvoltat de X (fost Twitter). Snowflake ID utilizează marca temporală curentă, un identificator de nod și un contor local pentru a genera un identificator. Am extins această abordare în continuare pentru generarea identificatorilor aleatori unici și am adăugat un nou element, o cheie secretă. Ideea centrală este adăugarea unui strat de cifru bloc la generatorul existent de identificatori unici, pentru a obține imposibilitatea practică de a prezice relația dintre numere. Un cifru bloc este o funcție criptografică fundamentală care transformă un bloc de text clar de lungime fixă într-un bloc de text cifrat de aceeași lungime. Această transformare este guvernată de o cheie criptografică. Caracteristica distinctivă a unui cifru bloc este reversibilitatea sa: acesta trebuie să fie o funcție biunivocă (bijectivă), asigurând că fiecărei intrări unice îi corespunde o ieșire unică și invers. Această proprietate este esențială pentru decriptare, permițând recuperarea textului clar original din textul cifrat atunci când se aplică cheia corectă. Prin utilizarea unui cifru bloc ca funcție biunivocă, putem garanta că fiecare intrare unică produce o ieșire unică corespunzătoare în intervalul definit. ## Structura și considerentele de proiectare Pornind de la aceste concepte fundamentale, să examinăm modul în care Randflake ID implementează aceste idei în practică. Structura Randflake ID include o marcă temporală Unix de 30 de biți, cu precizie de secundă, un identificator de nod de 17 biți, un contor local de 17 biți și un cifru bloc de 64 de biți bazat pe algoritmul sparx64. Iată câteva decizii de proiectare: - Unele instanțe VM din Google Cloud Platform pot sincroniza ceasul cu o precizie de 0,2 ms, however această precizie nu este disponibilă pe internetul public sau la alți furnizori de cloud. - Am ales precizia de secundă deoarece putem sincroniza eficient ceasul între noduri doar la o rezoluție de câteva milisecunde. - Un identificator de nod de 17 biți permite 131072 de generatoare individuale în același moment, care pot fi atribuite în mod per-proces, per-nucleu sau per-fir de execuție. - În sistemele cu debit ridicat, un contor local de 17 biți poate fi insuficient. Pentru a se potrivi debitului, putem atribui mai multe generatoare, fiecare cu un identificator de nod distinct, care să lucreze într-un singur proces sau fir de execuție. - Am adoptat sparx64 ca cifru bloc pe 64 de biți, un cifru bloc modern și ușor, bazat pe operații ARX. - Identificatorii Randflake oferă trasabilitate internă, dezvăluind nodul de origine și marca temporală doar celor care posedă cheia secretă. - Debitul teoretic maxim este de 17.179.869.184 ID/s, ceea ce este suficient pentru majoritatea aplicațiilor la scară globală. ## Pseudocodul generării Randflake ID Pentru a ilustra în continuare procesul de generare Randflake ID, următorul pseudocod Python oferă o implementare simplificată: ```python import time import struct from .sparx64 import Sparx64 # Constante RANDFLAKE_EPOCH_OFFSET = 1730000000 # Duminică, 27 octombrie 2024, ora 03:33:20 UTC # Alocarea biților RANDFLAKE_TIMESTAMP_BITS = 30 # 30 de biți pentru marca temporală (durată de viață de 34 de ani) RANDFLAKE_NODE_BITS = 17 # 17 biți pentru identificatorul de nod (maximum 131072 de noduri) RANDFLAKE_SEQUENCE_BITS = 17 # 17 biți pentru secvență (maximum 131072 de secvențe) # Constante derivate RANDFLAKE_MAX_TIMESTAMP = RANDFLAKE_EPOCH_OFFSET + (1 << RANDFLAKE_TIMESTAMP_BITS) - 1 RANDFLAKE_MAX_NODE = (1 << RANDFLAKE_NODE_BITS) - 1 RANDFLAKE_MAX_SEQUENCE = (1 << RANDFLAKE_SEQUENCE_BITS) - 1 class Randflake: def __init__(self, node_id: int, secret: bytes): self.node_id = int(node_id) self.sequence = int(0) self.rollover = int(time.time()) self.sbox = Sparx64(secret) def _new_raw(self) -> int: while True: now = int(time.time()) self.sequence += 1 sequence = self.sequence if sequence > RANDFLAKE_MAX_SEQUENCE: if now > self.rollover: self.sequence = 0 self.rollover = now sequence = 0 else: continue timestamp = now - RANDFLAKE_EPOCH_OFFSET return (timestamp << 34) | (self.node_id << 17) | sequence def generate(self) -> int: id_raw = self._new_raw() src = struct.pack("