Ewolucja rozproszonego generowania identyfikatorów sięga scentralizowanych sekrecji baz danych, które stały się wąskim gardłem w architekturach mikroserwisów, do Twitter's Snowflake i wariantów UUID. Wczesne podejścia polegały w dużej mierze na zegarkach zsynchronizowanych NTP, które okazały się kruche podczas skoków sekundowych, dryfu zegarów i podziałów sieci. Nowoczesne wymagania dotyczące zbierania zdarzeń i globalnie spójnego logowania wymagały ściśle monotonicznych sekwencji, które szanują przyczynowość bez obciążenia koordynacją.
Tradycyjne podejścia stają w obliczu dylematu dryfu zegara między dostępnością a porządkiem. Czyste znaczniki czasowe wymagają ścisłej synchronizacji, naruszając tolerancję na podziały według teorii CAP, podczas gdy czyste zegary logiczne, takie jak znaczniki Lamporta lub zegary wektorowe, poświęcają lokalność czasową i wydajność kompresji baz danych. Wyzwanie staje się bardziej intensywne, gdy wymagana jest k-sortowalność dla wydajności indeksowania baz danych. Ta szorstka kolejność czasowa musi współistnieć z ściśle monotonicznymi ustawieniami, zapewniając, że nie ma ruchu wstecznego podczas scenariuszy awaryjnych. Dodatkowo, izolacja regionalna podczas przerw w kablach podmorskich nie może powodować kolizji identyfikatorów ani utraty dostępności.
Wdrożenie architektury Hybrd Logical Clock (HLC) łączącej czas fizyczny (składnik milisekundowy) z licznikami logicznymi, wzbogaconej o partycjonowanie ID węzłów. Każdy regionalny klaster otrzymuje ID węzła (10-16 bitów) z usługi konsensusu takiej jak etcd lub ZooKeeper tylko podczas uruchamiania lub zmiany członkostwa. W każdym węźle HLC inkrementuje swój składnik logiczny, gdy czas fizyczny się nie zmienił, zapewniając monotoniczność pomimo dostosowań zegara.
Struktura ID łączy: milisekundy epoki (41 bitów) + licznik logiczny (12 bitów) + ID węzła (10 bitów). Podczas podziałów węzły kontynuują przydzielanie z ich lokalnego obszaru licznika logicznego. Po naprawie podziału zasada łączenia max-plus-one HLC zapewnia zachowanie przyczynowości bez centralnej koordynacji.
Globalna giełda kryptowalut wymagała generowania identyfikatorów transakcji w ramach AWS us-east-1, eu-west-1 i ap-southeast-1. System musiał przetwarzać 8 milionów zamówień na sekundę podczas zmienności rynku, zachowując ściśle temporalne porządki dla audytów regulacyjnych. Podziały sieciowe podczas konserwacji kabli podmorskich wcześniej spowodowały ryzyko kolizji UUIDv4 w ich starszym systemie, co prowadziło do naruszeń ograniczeń unikalności bazy danych i wstrzymań handlowych.
Rozwiązanie 1: Scentralizowana sekwencja PostgreSQL z buforowaniem
Wdrażając sekwencję PostgreSQL z alokacją wsadową na poziomie aplikacji (pobieranie 10,000 identyfikatorów na raz) zmniejszono liczbę podróży do bazy danych. Jednak podczas podziału sieci azjatycko-pacyficznego węzły buforujące wyczerpały swoje przydzielone zakresy w ciągu 90 sekund, zmuszając do powrotu do generacji UUID, co złamało porządek audytu. Jedna instancja RDS stworzyła także opóźnienie rzędu 140 ms dla zapisów krzyżowo-regionalnych, naruszając wymóg generacji poniżej 50 ms.
Rozwiązanie 2: Algorytm inspirowany Snowflake od Twittera
Wdrożenie Snowflake z zarządzanymi przez ZooKeeper ID węzłów osiągnęło 22,000 ID/s na węzeł i doskonałą sortowalność z kompaktowymi 64-bitowymi ID. Jednak gdy demony NTP na europejskich węzłach doświadczyły rozmycia skoków sekundowych, podczas gdy węzły w USA używały natychmiastowego kroku, system generował zduplikowane znaczniki czasowe milisekund, co wymagało kosztownych kontroli ograniczeń bazy danych, które obniżały przezorność o 40%.
Rozwiązanie 3: Hybrydowy Zegar Logiczny z zbieżnością CRDT
Przyjmując wzór HLC z CockroachDB, każdy lider regionalny utrzymywał lokalny licznik logiczny umożliwiający 4096 ID na milisekundę na węzeł z ID węzła podzielonym według regionów. Podczas przerwy w kablu w Singapurze izolowane węzły kontynuowały generowanie ID z użyciem swoich liczników logicznych, a po ponownym połączeniu funkcja porównawcza HLC zapewniła brak duplikatów przy zachowaniu przyczynowości. To podejście poświęciło 128-bitową szerokość ID dla gwarancji poprawności i utrzymało dostępność podczas podziałów.
Wybrane rozwiązanie i wynik
Rozwiązanie 3 zostało wybrane ze względu na swoją tolerancję na podziały i gwarancje monotoniczności. System pomyślnie przetrwał 4-godzinny podział podczas konserwacji kabla w Morzu Południowochińskim, przetwarzając 12 milionów ID/s w izolowanym regionie Tokio bez duplikacji. Po zrekoncyliowaniu nie było potrzeby przepisywania ID dzięki śledzeniu happens-before HLC, a koszty magazynowania zmniejszyły się o 15% w porównaniu do UUID dzięki porządkowi leksykograficznemu, co zmniejszyło kompresje RocksDB.
Większość kandydatów zakłada, że NTP zawsze przesuwa czas do przodu. W rzeczywistości agresywna korekcja dryfu zegara może cofnąć czas o setki milisekund. Rozwiązanie wymaga utrzymania trwałego monotonicznego zegara (podobnego do "syntetycznego" czasu CockroachDB): gdy system operacyjny zgłasza znacznik czasu mniejszy niż składnik fizyczny ostatnio przydzielonego ID, system ignoruje regresję fizyczną i kontynuuje inkrementację tylko licznika logicznego, aż prawdziwy czas nadgoni.
Dodatkowo, wdrażaj propagację ograniczeń zegara, gdzie węzły przekazują swoje maksymalne przedziały pewności dryfu, odrzucając żądania generacji, jeśli lokalna niepewność przewyższa 10 ms. Ten mechanizm wykrywa niesynchronizowane węzły, zanim wydadzą ID. Zapobiega to anomaliom "cofania się", które naruszają spójność zewnętrzną.
Kandydaci często nie zauważają, że 10-bitowe identyfikatory węzłów pozwalają tylko na 1,024 unikalne generatory. W środowisku Kubernetes z częstymi ponownymi uruchomieniami podów, naiwny przydział ID wyczerpuje przestrzeń nazw w ciągu kilku tygodni. Rozwiązanie wprowadza recykling oparty na epoce: identyfikatory węzłów są wynajmowane z TTL (Czasem Życia) w etcd, a recyklingowane identyfikatory wchodzą w okres kwarantanny "nagrobka" przekraczający maksymalny dryf zegara (zwykle 24 godziny).
Podczas ponownego wdrażania system sprawdza HLC ostatnio wydanego ID przez ten identyfikator węzła. Jeśli bieżący globalny czas minus ten znacznik czasu przekracza kwarantannę, ID jest bezpieczne do ponownego przypisania. Wymaga to usługi cmentarza, która śledzi dane metadane wycofanych węzłów.
K-sortowalne identyfikatory (jak Snowflake) koncentrują zapisy na "gorącym końcu" struktury LSM-tree lub B-tree, przytłaczając najnowszą SSTable lub najbardziej prawą stronę strony liścia. Kandydaci często nie dostrzegają, że podczas gdy k-sortowalność poprawia lokalność odczytu, tworzy wzmocnienie zapisu w Cassandra lub TiKV. Łagodzenie wprowadza kodowanie entropii poprzez prefiksy rozdziałów: poprzedzanie 4-bitowym hashem identyfikatora węzła lub sesji klienta, rozprowadzając zapisy w 16 memtable RocksDB, zachowując jednocześnie przybliżony porządek czasowy.
Dla CockroachDB użyj indeksów podzielonych hashem na kolumnie ID. Alternatywnie, użyj deckingu zapisu, gdzie niedawne identyfikatory są buforowane w Strumieniach Redis przed wsadowym wstawieniem do zimnego magazynu. To oddziela wchłanianie od cykli kompresji.