Generalnie zaimplementowałem generowanie numerów sekwencji przy użyciu sekwencji bazy danych w przeszłości.
np. Używając Postgres SERIAL typu http://www.neilconway.org/docs/sequences/
Jestem jednak ciekawy, jak generować numery sekwencyjne dla dużych systemów rozproszonych, w których nie ma bazy danych. Czy ktoś ma jakieś doświadczenie lub sugestie dotyczące najlepszych praktyk w zakresie generowania numerów sekwencyjnych w sposób bezpieczny dla wątków dla wielu klientów?
Odpowiedzi:
OK, to bardzo stare pytanie, które teraz widzę po raz pierwszy.
Będziesz musiał rozróżnić numery sekwencyjne i unikalne identyfikatory , które (opcjonalnie) można luźno sortować według określonych kryteriów (zwykle czasu generacji). Prawdziwe liczby sekwencyjne implikują wiedzę o tym, co zrobili wszyscy inni pracownicy i jako takie wymagają wspólnego stanu. Nie ma łatwego sposobu na zrobienie tego w sposób rozproszony i na dużą skalę. Możesz przyjrzeć się takim rzeczom, jak emisje sieciowe, zakresy okienkowe dla każdego pracownika i rozproszone tabele skrótów dla unikalnych identyfikatorów pracowników , ale to dużo pracy.
Unikalne identyfikatory to inna sprawa, istnieje kilka dobrych sposobów generowania unikalnych identyfikatorów w sposób zdecentralizowany:
a) Możesz skorzystać z usługi sieciowej Twittera Snowflake ID . Płatek śniegu to:
b) Można wygenerować unikalne identyfikatory na samych klientach, korzystając z podejścia wywodzącego się ze sposobu tworzenia identyfikatorów UUID i Snowflake. Istnieje wiele opcji, ale coś w rodzaju:
Najistotniejsze około 40 bitów: znacznik czasu; czas wygenerowania identyfikatora. (Używamy najbardziej znaczących bitów dla sygnatury czasowej, aby umożliwić sortowanie identyfikatorów według czasu generacji).
Następne 14 bitów: licznik na generator, który każdy generator zwiększa o jeden dla każdego nowego wygenerowanego identyfikatora. Gwarantuje to, że identyfikatory wygenerowane w tym samym momencie (te same znaczniki czasu) nie nakładają się.
Ostatnie 10 bitów: unikalna wartość dla każdego generatora. Korzystając z tego, nie musimy wykonywać żadnej synchronizacji między generatorami (co jest niezwykle trudne), ponieważ wszystkie generatory wytwarzają nienakładające się identyfikatory z powodu tej wartości.
c) Możesz wygenerować identyfikatory klientów, używając tylko znacznika czasu i losowej wartości. Pozwala to uniknąć konieczności znajomości wszystkich generatorów i przypisywania każdemu z nich unikalnej wartości. Z drugiej strony, takie identyfikatory nie mają gwarancji, że będą unikalne w skali globalnej, a jest bardzo prawdopodobne, że będą unikalne. (Aby się zderzyć, jeden lub więcej generatorów musiałby stworzyć tę samą losową wartość dokładnie w tym samym czasie.) Coś w rodzaju:
d) Łatwe wyjście, użyj identyfikatorów UUID / GUID .
źródło
twitter/snowflake
nie jest już obsługiwanyTeraz jest więcej opcji.
Chociaż to pytanie jest „stare”, dotarłem tutaj, więc myślę, że warto pozostawić opcje, które znam (do tej pory):
Twoje zdrowie
źródło
Możesz mieć każdy węzeł mieć unikalny identyfikator (który i tak możesz mieć), a następnie dołączyć go do numeru sekwencyjnego.
Na przykład węzeł 1 generuje sekwencję 001-00001 001-00002 001-00003 itd., A węzeł 5 generuje 005-00001 005-00002
Wyjątkowy :-)
Alternatywnie, jeśli chcesz mieć scentralizowany system, możesz rozważyć podzielenie serwera sekwencji w blokach. Zmniejsza to znacznie koszty ogólne. Na przykład, zamiast żądać nowego identyfikatora z serwera centralnego dla każdego identyfikatora, który musi zostać przypisany, żądasz identyfikatorów w blokach po 10 000 z serwera centralnego, a następnie musisz wykonać kolejne żądanie sieciowe, gdy się skończą.
źródło
Można to zrobić za pomocą Redisson . Implementuje rozproszoną i skalowalną wersję
AtomicLong
. Oto przykład:źródło
Jeśli naprawdę ma być globalnie sekwencyjny, a nie po prostu wyjątkowy, rozważę stworzenie jednej, prostej usługi do wydawania tych liczb.
Systemy rozproszone opierają się na współdziałaniu wielu małych usług, a do tego prostego zadania naprawdę potrzebujesz, czy naprawdę skorzystasz z innego złożonego, rozproszonego rozwiązania?
źródło
Istnieje kilka strategii; ale żadne, które znam, nie może być naprawdę rozpowszechniane i dać prawdziwą sekwencję.
memcached
ma szybki licznik atomowy, w zdecydowanej większości przypadków jest wystarczająco szybki dla całego klastra.osobiście oparłbym się na UUID lub memcached, jeśli chcę mieć w większości ciągłą przestrzeń.
źródło
Dlaczego nie użyć generatora UUID (bezpiecznego wątkowo)?
Powinienem chyba to rozwinąć.
Gwarantujemy, że identyfikatory UUID będą unikalne w skali globalnej (jeśli unikniesz identyfikatorów opartych na liczbach losowych, gdzie niepowtarzalność jest po prostu wysoce prawdopodobna).
Bez względu na to, z ilu generatorów UUID korzystasz, Twoje „rozproszone” wymaganie jest spełnione dzięki globalnej unikatowości każdego UUID.
Twoje wymaganie „bezpieczne wątkowo” można spełnić, wybierając generatory UUID „bezpieczne wątkowo”.
Zakłada się, że wymóg „numeru sekwencyjnego” jest spełniony przez gwarantowaną globalną niepowtarzalność każdego UUID.
Należy zauważyć, że wiele implementacji numerów sekwencyjnych w bazie danych (np. Oracle) nie gwarantuje ani monotonicznie rosnących, ani (nawet) rosnących numerów sekwencyjnych (na podstawie każdego „połączenia”). Dzieje się tak, ponieważ kolejna partia numerów sekwencji jest przydzielana w blokach „buforowanych” dla każdego połączenia. Gwarantuje to globalną wyjątkowość i utrzymuje odpowiednią prędkość. Ale faktycznie przydzielone numery sekwencyjne (w czasie) mogą być pomieszane, gdy są przydzielane przez wiele połączeń!
źródło
Rozproszone generowanie identyfikatorów można archiwizować za pomocą Redis i Lua. Implementacja dostępna w Github . Tworzy rozproszone unikalne identyfikatory, które można sortować metodą k.
źródło
Wiem, że to stare pytanie, ale też mieliśmy taką samą potrzebę i nie mogliśmy znaleźć rozwiązania, które spełniałoby nasze potrzeby. Naszym wymaganiem było uzyskanie unikalnej sekwencji (0,1,2,3 ... n) identyfikatorów, a zatem płatek śniegu nie pomagał. Stworzyliśmy własny system do generowania identyfikatorów za pomocą Redis. Redis jest jednowątkowy, więc jego mechanizm listy / kolejki zawsze dawał nam 1 pop na raz.
Robimy to, tworzymy bufor identyfikatorów. Początkowo kolejka będzie miała od 0 do 20 identyfikatorów, które są gotowe do wysłania na żądanie. Wielu klientów może zażądać identyfikatora, a redis wyświetli 1 identyfikator naraz. Po każdym pop od lewej wstawiamy BUFFER + currentId po prawej stronie, co utrzymuje listę buforów. Wdrożenie tutaj
źródło
Napisałem prostą usługę, która może generować pół-unikatowe niesekwencyjne 64-bitowe liczby. Można go wdrożyć na wielu komputerach w celu zapewnienia nadmiarowości i skalowalności. Używa ZeroMQ do przesyłania wiadomości. Więcej informacji o tym, jak to działa, znajdziesz na stronie github: zUID
źródło
Korzystając z bazy danych, możesz osiągnąć ponad 1000 przyrostów na sekundę przy użyciu jednego rdzenia. To całkiem proste. Możesz użyć własnej bazy danych jako zaplecza do wygenerowania tego numeru (ponieważ powinien to być jego własny agregat, w terminach DDD).
Miałem podobny problem. Miałem kilka partycji i chciałem uzyskać licznik przesunięć dla każdej z nich. Zaimplementowałem coś takiego:
Następnie wykonałem następującą instrukcję:
Jeśli Twoja aplikacja na to pozwala, możesz od razu przydzielić blok (tak było w moim przypadku).
Jeśli potrzebujesz większej przepustowości i nie możesz wcześniej przydzielić przesunięć, możesz zaimplementować własną usługę za pomocą Flink do przetwarzania w czasie rzeczywistym. Udało mi się uzyskać około 100K przyrostów na partycję.
Mam nadzieję, że to pomoże!
źródło
Problem jest podobny do: W świecie iscsi, gdzie każdy lun / wolumin musi być jednoznacznie identyfikowalny przez inicjatory działające po stronie klienta. Standard iscsi mówi, że kilka pierwszych bitów musi reprezentować informacje o dostawcy / producencie pamięci masowej, a pozostałe monotonicznie rosną.
Podobnie, można użyć początkowych bitów w rozproszonym systemie węzłów do reprezentowania nodeID, a reszta może być monotonicznie zwiększana.
źródło
Jednym z przyzwoitych rozwiązań jest użycie generacji opartej na długim czasie. Można to zrobić przy wsparciu rozproszonej bazy danych.
źródło