Rozproszone generowanie numerów sekwencyjnych?

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?

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:

• Usługa sieciowa, czyli nawiązanie połączenia sieciowego w celu uzyskania unikalnego identyfikatora;
• który generuje 64-bitowe unikalne identyfikatory uporządkowane według czasu generacji;
• a usługa jest wysoce skalowalna i (potencjalnie) wysoce dostępna; każda instancja może generować wiele tysięcy identyfikatorów na sekundę i możesz uruchomić wiele instancji w swojej sieci LAN / WAN;
• napisany w Scali, działa na JVM.

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:

• Najważniejsze 32 bity: znacznik czasu, czas wygenerowania identyfikatora.
• Najmniej znaczące 32 bity: 32 bity losowości, generowane od nowa dla każdego identyfikatora.

d) Łatwe wyjście, użyj identyfikatorów UUID / GUID .

Teraz 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):

• Możesz spróbować Hazelcast . W wersji 1.9 zawiera rozproszoną implementację java.util.concurrent.AtomicLong
• Możesz także użyć Zookeepera . Zapewnia metody tworzenia węzłów sekwencji (dołączanych do nazw znode, chociaż wolę używać numerów wersji węzłów). Uważaj jednak na to: jeśli nie chcesz pominąć liczb w swojej sekwencji, może nie być tym, czego chcesz.

Twoje zdrowie

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ą.

Można to zrobić za pomocą Redisson . Implementuje rozproszoną i skalowalną wersję AtomicLong. Oto przykład:

Config config = new Config();
config.addAddress("some.server.com:8291");

Redisson redisson = Redisson.create(config);
RAtomicLong atomicLong = redisson.getAtomicLong("anyAtomicLong");
atomicLong.incrementAndGet();

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?

Istnieje kilka strategii; ale żadne, które znam, nie może być naprawdę rozpowszechniane i dać prawdziwą sekwencję.

1. mieć centralny generator liczb. nie musi to być duża baza danych. memcachedma szybki licznik atomowy, w zdecydowanej większości przypadków jest wystarczająco szybki dla całego klastra.
2. oddziel zakres liczb całkowitych dla każdego węzła (jak odpowiedź Stevena Schlansktera )
3. użyj liczb losowych lub identyfikatorów UUID
4. użyj jakiejś części danych wraz z identyfikatorem węzła i zhaszuj to wszystko (lub hmac it)

osobiście oparłbym się na UUID lub memcached, jeśli chcę mieć w większości ciągłą przestrzeń.

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ń!

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.

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

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

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:

CREATE DATABASE example;
USE example;
CREATE TABLE offsets (partition INTEGER, offset LONG, PRIMARY KEY (partition));
INSERT offsets VALUES (1,0);

Następnie wykonałem następującą instrukcję:

SELECT @offset := offset from offsets WHERE partition=1 FOR UPDATE;
UPDATE offsets set offset=@offset+1 WHERE partition=1;

Jeśli Twoja aplikacja na to pozwala, możesz od razu przydzielić blok (tak było w moim przypadku).

SELECT @offset := offset from offsets WHERE partition=1 FOR UPDATE;
UPDATE offsets set offset=@offset+100 WHERE partition=1;

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!

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.

Jednym z przyzwoitych rozwiązań jest użycie generacji opartej na długim czasie. Można to zrobić przy wsparciu rozproszonej bazy danych.