Rozproszone generowanie numerów sekwencyjnych?

103

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?

Jon
źródło
To pytanie jest stare, ale proszę zobaczyć moją nową odpowiedź stackoverflow.com/questions/2671858/ ...
Jesper M
Jak korzystasz z nextval.org? Strona jest trochę dziwna i nie wiem, o co chodzi. Czy to jakieś polecenie Unix? A może usługa w chmurze?
diegosasw

Odpowiedzi:

116

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 .

Jesper M
źródło
Cassandra obsługuje liczniki ( cassandra.apache.org/doc/cql3/CQL.html#counters ), istnieją jednak pewne ograniczenia.
Piyush Kansal
numery sekwencji są łatwe do ustawienia pozycji dla indeksu bitmapy, ale unikalny identyfikator czasami jest zbyt długi (64-bitowy lub 128-bitowy), w jaki sposób można mapować unikalne ID na pozycję indeksu mapy bitowej? Dzięki.
brucenan
2
Naprawdę podobał opcja #b ..... może to pozwolić na dużą skalę, a nie przyczyną wiele kwestii współbieżności
Puneet
2
twitter/snowflakenie jest już obsługiwany
Navin
Jeśli chcesz mieć licencjonowaną implementację opcji B Apache2, sprawdź bitbucket.org/pythagorasio/common-libraries/src/master/… Możesz ją również pobrać z maven io.pythagoras.common: rozproszona sekwencja id-generator: 1.0 .0
Wpigott
16

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

Paolo
źródło
3
Zookeeper to opcja, z której wybrałem, jest dobry opis i napisanie tego na liście mailingowej, którą założyłem - mail-archive.com/[email protected]/msg01967.html
Jon
Jon, dzięki za wskazanie tego wątku, właśnie o tym myślałem. BTW, czy stworzyłeś kod, aby pokonać ograniczenie MAX_INT?
Paolo
15

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

Steven Schlansker
źródło
1
Podoba mi się twój punkt widzenia dotyczący generowania identyfikatora partii, ale ogranicza to po prostu wszelkie możliwości obliczeń w czasie rzeczywistym.
ishan
Zaimplementowałem podobny mechanizm. W tym, oprócz klientów buforujących blok sekwencji, dodałem kilka serwerów-hostów, które buforują bloki sekwencji. (Pojedynczy) główny generator jest utrzymywany w pewnej wysoce dostępnej pamięci masowej lub na hoście z jednym głównym, dostępnym tylko dla floty serwerów-hostów. Buforowanie serwera pomogłoby nam również w dłuższym czasie działania, nawet jeśli pojedynczy serwer główny nie działa na chwilę.
Janakiram,
11

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();
Nikita Koksharov
źródło
8

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?

wsorenson
źródło
3
... a co się stanie, gdy serwer z tą usługą przestanie działać?
Navin
Masz alert, który każe komuś rozpocząć kolejny? Czasami to wystarczy. Myślę, że odpowiedzią jest próba stwierdzenia „patrz na to z perspektywy”. Idealne rozwiązanie rozproszone ma swoje wady i czasami prostsze jest lepsze.
nic ferrier
6

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

Javier
źródło
5

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

Phil
źródło
1
Chociaż identyfikatory UUID działają, problem z nimi polega na tym, że musisz zachować ostrożność podczas ich przechowywania, jeśli ostatecznie musisz zindeksować wygenerowane klucze. Zwykle zajmują znacznie więcej miejsca niż sekwencja o monotonnym wzroście. Zobacz percona.com/blog/2014/12/19/store-uuid-optimized-way, aby zapoznać się z dyskusją na temat przechowywania ich w MySQL.
Pavel
2

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.

SANN3
źródło
2

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

Zohair
źródło
0

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

Majid Azimi
źródło
0

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!

user2108278
źródło
0

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.

user1860223
źródło
1
proszę dodać więcej szczegółów
Ved Prakash
0

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

odmówić
źródło