Wprowadzenie Randflake ID: rozproszony, jednolity, nieprzewidywalny, unikalny generator losowych ID.

Rozważmy sytuację, w której musimy generować unikalne 64-bitowe liczby losowe, a strony zewnętrzne nie powinny być w stanie przewidzieć kolejnej ani poprzedniej liczby.

W takiej sytuacji możemy wygenerować 8-bajtową wartość losową, sprawdzić, czy już istnieje w bazie danych, a następnie zapisać ją, jeśli jest unikalna.

Jednakże, ta metoda ma kilka wad. Musimy przechowywać każdą wygenerowaną liczbę w bazie danych, aby zapewnić unikalność. Wymóg co najmniej jednej podróży w obie strony do bazy danych generuje problemy z opóźnieniem (latency), szczególnie w środowisku rozproszonym, gdzie skalowalność jest kluczowa.

Aby rozwiązać te problemy, wprowadzamy Randflake ID: rozproszony, jednolity, nieprzewidywalny, unikalny generator losowych ID.

Jak działa Randflake ID?

Randflake ID jest inspirowany Snowflake ID, szeroko stosowanym mechanizmem generowania identyfikatorów k-sorted, opracowanym przez X (dawniej twitter).

Snowflake ID używa bieżącego znacznika czasu (timestamp), ID węzła (node ID) i lokalnego licznika do wygenerowania identyfikatora.

Rozszerzyliśmy to podejście w celu generowania losowych unikalnych ID i dodaliśmy nowy element w postaci tajnego klucza (secret key).

Kluczową ideą jest dodanie warstwy szyfru blokowego (block cipher) do istniejącego generatora unikalnych ID, aby osiągnąć niewykrywalność w przewidywaniu relacji między liczbami.

Szyfr blokowy to fundamentalna funkcja kryptograficzna, która przekształca blok tekstu jawnego (plaintext) o stałej długości w blok tekstu zaszyfrowanego (ciphertext) o tej samej długości. To przekształcenie jest kontrolowane przez klucz kryptograficzny. Cechą wyróżniającą szyfru blokowego jest jego odwracalność: musi to być funkcja jeden do jednego (bijektywna), zapewniająca, że każdy unikalny wejściowy blok odpowiada unikalnemu wyjściowemu blokowi i odwrotnie. Ta właściwość jest kluczowa dla deszyfrowania, umożliwiając odzyskanie oryginalnego tekstu jawnego z tekstu zaszyfrowanego po zastosowaniu poprawnego klucza.

Stosując szyfr blokowy jako funkcję jeden do jednego, możemy zagwarantować, że każde unikalne wejście generuje odpowiadające mu unikalne wyjście w zdefiniowanym zakresie.

Struktura i rozważania projektowe

Opierając się na tych fundamentalnych koncepcjach, przeanalizujmy, jak Randflake ID implementuje te idee w praktyce.

Struktura Randflake ID obejmuje 30-bitowy znacznik czasu unix z precyzją co do sekundy, 17-bitowy identyfikator węzła oraz 17-bitowy licznik lokalny, a także 64-bitowy szyfr blokowy oparty na algorytmie sparx64.

Oto kilka decyzji projektowych:

Niektóre instancje VM w Google Cloud Platform mogą synchronizować zegar z precyzją do 0,2 ms, ale ten poziom dokładności nie jest dostępny w publicznym Internecie ani u innych dostawców chmury.
Wybraliśmy precyzję co do sekundy, ponieważ możemy efektywnie synchronizować zegar między węzłami tylko z rozdzielczością kilku milisekund.
17-bitowy identyfikator węzła pozwala na 131072 indywidualnych generatorów w tym samym momencie, które mogą być przypisane na proces (per-process), na rdzeń (per-core) lub na wątek (per-thread).
W systemach o wysokiej przepustowości 17-bitowy licznik lokalny może być niewystarczający. Aby sprostać przepustowości, możemy przypisać wiele generatorów, każdy z odrębnym ID węzła, do pracy w jednym procesie lub wątku.
Przyjęliśmy sparx64 jako 64-bitowy szyfr blokowy, nowoczesny, lekki szyfr blokowy oparty na ARX.
Randflake ID oferuje wewnętrzną identyfikowalność, ujawniając swój pierwotny ID węzła i znacznik czasu tylko tym, którzy posiadają tajny klucz.
Teoretyczna maksymalna przepustowość wynosi 17 179 869 184 ID/s, co jest wystarczające dla większości aplikacji o globalnej skali.

Pseudokod generowania Randflake ID

Aby dokładniej zilustrować proces generowania Randflake ID, poniższy pseudokod w Pythonie przedstawia uproszczoną implementację:

 1import time
 2import struct
 3from .sparx64 import Sparx64
 4
 5# Constants
 6RANDFLAKE_EPOCH_OFFSET = 1730000000  # Sunday, October 27, 2024 3:33:20 AM UTC
 7# Stałe
 8# RANDFLAKE_EPOCH_OFFSET = 1730000000  # Niedziela, 27 października 2024 3:33:20 AM UTC
 9
10# Bits allocation
11RANDFLAKE_TIMESTAMP_BITS = 30  # 30 bits for timestamp (lifetime of 34 years)
12RANDFLAKE_NODE_BITS = 17  # 17 bits for node id (max 131072 nodes)
13RANDFLAKE_SEQUENCE_BITS = 17  # 17 bits for sequence (max 131072 sequences)
14# Alokacja bitów
15# RANDFLAKE_TIMESTAMP_BITS = 30  # 30 bitów na znacznik czasu (żywotność 34 lata)
16# RANDFLAKE_NODE_BITS = 17  # 17 bitów na ID węzła (maks. 131072 węzłów)
17# RANDFLAKE_SEQUENCE_BITS = 17  # 17 bitów na sekwencję (maks. 131072 sekwencji)
18
19# Derived constants
20RANDFLAKE_MAX_TIMESTAMP = RANDFLAKE_EPOCH_OFFSET + (1 << RANDFLAKE_TIMESTAMP_BITS) - 1
21RANDFLAKE_MAX_NODE = (1 << RANDFLAKE_NODE_BITS) - 1
22RANDFLAKE_MAX_SEQUENCE = (1 << RANDFLAKE_SEQUENCE_BITS) - 1
23# Stałe pochodne
24# RANDFLAKE_MAX_TIMESTAMP = RANDFLAKE_EPOCH_OFFSET + (1 << RANDFLAKE_TIMESTAMP_BITS) - 1
25# RANDFLAKE_MAX_NODE = (1 << RANDFLAKE_NODE_BITS) - 1
26# RANDFLAKE_MAX_SEQUENCE = (1 << RANDFLAKE_SEQUENCE_BITS) - 1
27
28class Randflake:
29    def __init__(self, node_id: int, secret: bytes):
30        self.node_id = int(node_id)
31        self.sequence = int(0)
32        self.rollover = int(time.time())
33        self.sbox = Sparx64(secret)
34
35    def _new_raw(self) -> int:
36        while True:
37            now = int(time.time())
38
39            self.sequence += 1
40            sequence = self.sequence
41
42            if sequence > RANDFLAKE_MAX_SEQUENCE:
43                if now > self.rollover:
44                    self.sequence = 0
45                    self.rollover = now
46                    sequence = 0
47                else:
48                    continue
49
50            timestamp = now - RANDFLAKE_EPOCH_OFFSET
51            return (timestamp << 34) | (self.node_id << 17) | sequence
52
53    def generate(self) -> int:
54        id_raw = self._new_raw()
55        src = struct.pack("<q", id_raw)
56        dst = bytearray(8)
57        self.sbox.encrypt(dst, src)
58        return struct.unpack("<q", dst)[0]

Gotowa do produkcji implementacja Randflake, zawierająca mechanizm dzierżawy (lease) ID węzła, jest dostępna na GitHubie.

Inne rozważania

W tej sekcji omówimy dodatkowe kwestie dotyczące implementacji Randflake ID.

Koordynacja ID węzła

Sugerujemy koordynację ID węzła opartą na dzierżawie.

W tym podejściu centralna usługa koordynacyjna przydziela unikalny ID węzła każdemu generatorowi.

Ten ID węzła nie jest ponownie przydzielany w okresie dzierżawy, aby zapewnić unikalność, co zmniejsza potrzebę częstej komunikacji z usługą koordynacyjną.

Generator posiadający dzierżawę może zażądać odnowienia dzierżawy od usługi koordynacyjnej, jeśli spełniony jest warunek odnowienia.

Warunek odnowienia odnosi się do zestawu kryteriów, które muszą być spełnione, aby dzierżawa została odnowiona, takich jak to, że generator jest nadal aktywny i wymaga ID węzła.

Dzierżawca (leaseholder) jest obecnym posiadaczem zakresu ID węzła.

Dzierżawa jest uważana za aktywną i nie wygasłą, jeśli mieści się w jej ważnym okresie czasowym.

W ten sposób możemy zredukować podróże w obie strony do jednej na okres odnowienia dzierżawy, minimalizując opóźnienia i poprawiając wydajność w systemach rozproszonych.

Łagodzenie skutków wadliwego zegara

Usługa dzierżawy musi sprawdzać spójność znacznika czasu podczas alokacji dzierżawy. Przypisany czas rozpoczęcia dzierżawy musi być większy lub równy czasowi rozpoczęcia ostatniej dzierżawy.

Generator powinien odrzucić żądanie, jeśli bieżący znacznik czasu jest mniejszy niż czas rozpoczęcia dzierżawy lub większy niż czas zakończenia dzierżawy.

Ta procedura jest ważna dla ochrony unikalności generowanych ID, gdy zegar cofa się w czasie. Na przykład, jeśli zegar się cofnie, nowa dzierżawa może zostać przydzielona z czasem rozpoczęcia wcześniejszym niż wcześniej przydzielona dzierżawa, co potencjalnie prowadzi do generowania duplikatów ID. Odrzucając żądania ze znacznikami czasu w ramach istniejącego okresu dzierżawy, zapobiegamy temu scenariuszowi i utrzymujemy unikalność ID.

Jednolitość dystrybucji ID

Histogram of ID distribution

Na podstawie powyższego histogramu możemy zauważyć, że dystrybucja generowanych Randflake ID jest bardzo jednolita. Sugeruje to, że dystrybucja ID może być bezpośrednio używana jako klucz do shardingu (sharding key).

Podsumowanie

W tym artykule przedstawiliśmy Randflake, nowatorski algorytm generowania ID, który łączy zalety Snowflake i Sparx64.

Mamy nadzieję, że ten artykuł zapewnił Państwu kompleksowe zrozumienie Randflake i jego implementacji.

Pełny kod źródłowy Randflake można znaleźć na GitHubie.

Jeśli mają Państwo jakiekolwiek pytania lub sugestie, prosimy o kontakt. Poszukujemy również współtwórców, którzy pomogą ulepszyć Randflake i zaimplementować go w innych językach programowania.

Planujemy wydać gotową do produkcji usługę koordynacyjną dla Randflake i Snowflake, która zostanie udostępniona jako open-source na GitHubie. Bądźcie Państwo na bieżąco z aktualizacjami!