Przedstawiamy Randflake ID: rozproszony, jednolity, nieprzewidywalny i unikalny generator losowych identyfikatorów.
Rozważmy sytuację, w której musimy wygenerować unikalne 64-bitowe liczby losowe, a strony zewnętrzne nie powinny być w stanie przewidzieć kolejnej ani poprzedniej liczby.
W tym przypadku 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 posiada kilka wad. Musimy przechowywać każdą wygenerowaną liczbę w bazie danych, aby zapewnić unikalność. Wymóg co najmniej jednej rundy komunikacji z bazą danych powoduje problemy z opóźnieniami, szczególnie w środowisku rozproszonym, gdzie skalowalność jest kluczowa.
Aby rozwiązać te problemy, wprowadzamy Randflake ID: rozproszony, jednolity, nieprzewidywalny, unikalny generator losowych identyfikatorów.
Jak działa Randflake ID?
Randflake ID jest inspirowany Snowflake ID, szeroko stosowanym mechanizmem generowania identyfikatorów k-sortowanych, opracowanym przez X (dawniej twitter).
Snowflake ID wykorzystuje bieżącą sygnaturę czasową, ID węzła oraz lokalny licznik do wygenerowania identyfikatora.
Rozszerzyliśmy to podejście dalej w celu generowania losowych unikalnych identyfikatorów i dodaliśmy nowy element tajnego klucza.
Kluczową ideą jest dodanie warstwy szyfru blokowego do istniejącego generatora unikalnych identyfikatorów, aby osiągnąć niewykonalność w przewidywaniu relacji między liczbami.
Szyfr blokowy to fundamentalna funkcja kryptograficzna, która przekształca blok tekstu jawnego o stałej długości w blok tekstu zaszyfrowanego o tej samej długości. Transformacja ta jest regulowana przez klucz kryptograficzny. Cechą wyróżniającą szyfr blokowy jest jego odwracalność: musi być funkcją jeden do jednego (bijektywną), zapewniającą, że każdy unikalny wejście odpowiada unikalnemu wyjściu i vice versa. Ta właściwość jest kluczowa dla deszyfrowania, umożliwiając odzyskanie oryginalnego tekstu jawnego z tekstu zaszyfrowanego po zastosowaniu prawidłowego 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
Bazując na tych podstawowych koncepcjach, przeanalizujmy, w jaki sposób Randflake ID implementuje te idee w praktyce.
Struktura Randflake ID obejmuje 30-bitową sygnaturę czasową Unix z precyzją do sekundy, 17-bitowy identyfikator węzła, 17-bitowy licznik lokalny oraz 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ę sekundową, ponieważ możemy skutecznie synchronizować zegar między węzłami jedynie 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 per-process, per-core, per-thread.
W systemach o wysokiej przepustowości 17-bitowy licznik lokalny może być niewystarczający. Aby dopasować przepustowość, możemy przypisać wiele generatorów, każdy z innym 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 swoje źródłowe ID węzła i sygnaturę czasową 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 dodatkowo zilustrować proces generowania Randflake ID, poniższy pseudokod w języku Python przedstawia uproszczoną implementację:
1import time
2import struct
3from .sparx64 import Sparx64
4
5# Constants
6RANDFLAKE_EPOCH_OFFSET = 1730000000 # Niedziela, 27 października 2024 3:33:20 AM UTC
7
8# Bits allocation
9RANDFLAKE_TIMESTAMP_BITS = 30 # 30 bitów dla sygnatury czasowej (żywotność 34 lata)
10RANDFLAKE_NODE_BITS = 17 # 17 bitów dla ID węzła (maks. 131072 węzły)
11RANDFLAKE_SEQUENCE_BITS = 17 # 17 bitów dla sekwencji (maks. 131072 sekwencje)
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]
Gotowa do produkcji implementacja Randflake, zawierająca mechanizm dzierżawy ID węzła, jest dostępna na GitHub.
Inne uwagi
W tej sekcji omówimy kilka dodatkowych kwestii dotyczących implementacji Randflake ID.
Koordynacja ID węzłów
Sugerujemy koordynację ID węzłów opartą na dzierżawie.
W tym podejściu centralna usługa koordynacji przypisuje unikalny ID węzła każdemu generatorowi.
Ten ID węzła nie jest ponownie przypisywany w okresie dzierżawy, aby zapewnić unikalność, zmniejszając potrzebę częstej komunikacji z usługą koordynacji.
Generator posiadający dzierżawę może zażądać odnowienia dzierżawy od usługi koordynacji, jeśli spełniony zostanie warunek odnowienia.
Warunek odnowienia odnosi się do zestawu kryteriów, które muszą być spełnione, aby dzierżawa została odnowiona, takich jak aktywność generatora i jego zapotrzebowanie na ID węzła.
Dzierżawca jest aktualnym posiadaczem zakresu ID węzłów.
Dzierżawa jest uważana za aktywną i nie wygasłą, jeśli mieści się w swoim ważnym okresie czasowym.
W ten sposób możemy ograniczyć liczbę rund komunikacji do jednej na okres odnowienia dzierżawy, minimalizując opóźnienia i poprawiając wydajność w systemach rozproszonych.
Łagodzenie skutków awarii zegara
Usługa dzierżawy musi sprawdzać spójność sygnatur czasowych podczas przydzielania dzierżawy. Przypisany czas rozpoczęcia dzierżawy musi być większy lub równy ostatniemu czasowi rozpoczęcia dzierżawy.
Generator powinien odrzucić żądanie, jeśli bieżąca sygnatura czasowa jest mniejsza niż czas rozpoczęcia dzierżawy lub większa niż czas zakończenia dzierżawy.
Ta procedura jest ważna dla ochrony unikalności generowanych ID, gdy zegar cofa się. Na przykład, jeśli zegar cofa się, nowa dzierżawa może zostać przypisana z czasem rozpoczęcia wcześniejszym niż wcześniej przypisana dzierżawa, co potencjalnie prowadzi do generowania zduplikowanych ID. Odrzucając żądania z sygnaturami czasowymi w istniejącym okresie dzierżawy, zapobiegamy temu scenariuszowi i utrzymujemy unikalność ID.
Jednolitość rozkładu ID
Na podstawie powyższego histogramu możemy zauważyć, że rozkład wygenerowanych Randflake ID jest bardzo jednolity. Sugeruje to, że rozkład ID może być bezpośrednio wykorzystywany jako klucz shardingowy.
Wnioski
W niniejszym artykule przedstawiliśmy Randflake, nowatorski algorytm generowania ID, który łączy zalety Snowflake i Sparx64.
Mamy nadzieję, że ten artykuł dostarczył Państwu kompleksowego zrozumienia Randflake i jego implementacji.
Pełny kod źródłowy Randflake można znaleźć na GitHub.
W przypadku pytań lub sugestii, prosimy o kontakt. Poszukujemy również współpracowników, którzy pomogą ulepszyć Randflake i zaimplementować go w innych językach programowania.
Planujemy wydać gotową do produkcji usługę koordynacji dla Randflake i Snowflake, która zostanie udostępniona jako open-source na GitHub. Bądźcie na bieżąco z aktualizacjami!