Co to jest algorytm Hi / Lo?

Co to jest algorytm Hi / Lo?

Znalazłem to w dokumentacji NHibernate (jest to jedna metoda generowania unikalnych kluczy, sekcja 5.1.4.2), ale nie znalazłem dobrego wyjaśnienia, jak to działa.

Wiem, że Nhibernate sobie z tym poradzi i nie muszę znać wnętrza, ale jestem po prostu ciekawa.

Podstawową ideą jest to, że masz dwie liczby, które składają się na klucz podstawowy - „wysoką” i „niską” liczbę. Klient może w zasadzie zwiększyć sekwencję „wysoką”, wiedząc, że może bezpiecznie wygenerować klucze z całego zakresu poprzedniej „wysokiej” wartości z różnorodnością „niskich” wartości.

Załóżmy na przykład, że masz „wysoką” sekwencję o bieżącej wartości 35, a „niska” liczba mieści się w zakresie 0–1023. Następnie klient może zwiększyć sekwencję do 36 (aby inni klienci mogli generować klucze podczas korzystania z 35) i wiedzieć, że klucze 35/0, 35/1, 35/2, 35/3 ... 35/1023 wszystkie dostępne.

Może być bardzo przydatne (szczególnie w przypadku ORM), aby móc ustawić klucze podstawowe po stronie klienta, zamiast wstawiać wartości bez kluczy podstawowych, a następnie pobierać je z powrotem do klienta. Pomijając wszystko inne, to znaczy można łatwo relacji rodzic / dziecko i mam klucze wszystko na swoim miejscu, zanim zrobisz żadnych wkładek, co czyni je dozujący prostsze.

Oprócz odpowiedzi Jona:

Służy do pracy bez połączenia. Klient może następnie poprosić serwer o numer hi i utworzyć obiekty zwiększające sam numer lo. Nie musi kontaktować się z serwerem, dopóki zakres lo nie zostanie wyczerpany.

Ponieważ jest to bardzo częste pytanie, napisałem ten artykuł , na którym opiera się ta odpowiedź.

Algorytmy hi / lo dzielą domenę sekwencji na grupy „hi”. Wartość „hi” jest przypisywana synchronicznie. Każda grupa „cześć” otrzymuje maksymalną liczbę „lo” wpisów, które można przypisać offline, nie martwiąc się o współbieżne duplikaty wpisów.

1. Token „cześć” jest przypisywany przez bazę danych, a dwa równoczesne wywołania gwarantują unikalne kolejne wartości
2. Po pobraniu tokenu „cześć” potrzebujemy tylko „incrementSize” (liczba wpisów „lo”)

3. Zakres identyfikatorów określa następujący wzór:

   [(hi -1) * incrementSize) + 1, (hi * incrementSize) + 1)

   a wartość „lo” będzie w zakresie:

   [0, incrementSize)

   stosowane od wartości początkowej:

   [(hi -1) * incrementSize) + 1)

4. Po zastosowaniu wszystkich wartości „lo”, pobierana jest nowa wartość „hi” i cykl jest kontynuowany

Bardziej szczegółowe wyjaśnienie można znaleźć w tym artykule :

Ta wizualna prezentacja jest łatwa do naśladowania:

Podczas gdy optymalizator hi / lo nadaje się do optymalizacji generowania identyfikatorów, nie działa dobrze z innymi systemami wstawiającymi wiersze do naszej bazy danych, nie wiedząc nic o naszej strategii identyfikatorów.

Hibernate oferuje optymalizator pooled-lo , który oferuje zalety strategii generatora hi / lo, jednocześnie zapewniając interoperacyjność z innymi klientami zewnętrznymi, którzy nie są świadomi tej strategii alokacji sekwencji.

Optymalizator pooled-lo jest zarówno wydajny, jak i współpracuje z innymi systemami, jest znacznie lepszym kandydatem niż starsza strategia identyfikatora hi / lo.

Lo to buforowany rozdzielacz, który dzieli przestrzeń klawiszy na duże fragmenty, zwykle oparte na pewnym rozmiarze słowa maszynowego, a nie na znacznych zakresach (np. Uzyskiwanie 200 kluczy jednocześnie), które człowiek mógłby rozsądnie wybrać.

Użycie Hi-Lo powoduje marnowanie dużej liczby kluczy przy ponownym uruchomieniu serwera i generowanie dużych wartości kluczy nieprzyjaznych dla człowieka.

Lepszym niż alokatorem Hi-Lo jest alokator „Linear Chunk”. Korzysta z podobnej zasady opartej na tabeli, ale przydziela małe porcje o dogodnej wielkości i generuje ładne wartości przyjazne dla człowieka.

create table KEY_ALLOC (
    SEQ varchar(32) not null,
    NEXT bigint not null,
    primary key (SEQ)
);

Aby przydzielić kolejne, powiedzmy, 200 kluczy (które są następnie przechowywane na serwerze i używane w razie potrzeby):

select NEXT from KEY_ALLOC where SEQ=?;
update KEY_ALLOC set NEXT=(old value+200) where SEQ=? and NEXT=(old value);

Pod warunkiem, że możesz zatwierdzić tę transakcję (użyj ponownych prób, aby obsłużyć spór), przydzieliłeś 200 kluczy i możesz wydać je w razie potrzeby.

Przy wielkości fragmentu wynoszącej zaledwie 20, ten schemat jest 10 razy szybszy niż przydział z sekwencji Oracle i jest w 100% przenośny we wszystkich bazach danych. Wydajność alokacji jest równoważna z hi-lo.

W przeciwieństwie do pomysłu Amblera, traktuje przestrzeń klawiszy jako ciągłą liniową linię numeryczną.

Pozwala to uniknąć impulsu dla kluczy kompozytowych (które nigdy nie były tak naprawdę dobrym pomysłem) i pozwala uniknąć marnowania całych słów po ponownym uruchomieniu serwera. Generuje „przyjazne” kluczowe wartości na skalę ludzką.

Dla porównania pomysł Amblera przydziela wysokie 16- lub 32-bitowe i generuje duże nieprzyjazne człowiekowi kluczowe wartości jako przyrostowe słowa.

Porównanie przydzielonych kluczy:

Linear_Chunk       Hi_Lo
100                65536
101                65537
102                65538
.. server restart
120                131072
121                131073
122                131073
.. server restart
140                196608

Pod względem projektowym jego rozwiązanie jest zasadniczo bardziej złożone na linii liczbowej (klucze złożone, duże produkty hi_word) niż Linear_Chunk, nie osiągając przy tym żadnych korzyści porównawczych.

Projekt Hi-Lo powstał na wczesnym etapie mapowania i trwałości OO. Obecnie systemy utrwalania, takie jak Hibernacja, oferują domyślnie prostsze i lepsze alokatory.

Odkryłem, że algorytm Hi / Lo jest idealny dla wielu baz danych ze scenariuszami replikacji opartymi na moim doświadczeniu. Wyobraź to sobie. masz serwer w Nowym Jorku (alias 01) i inny serwer w Los Angeles (alias 02), a następnie masz tabelę PERSON ... więc w Nowym Jorku, gdy osoba jest tworzona ... zawsze używasz 01 jako wartości HI a wartość LO jest następną sekwencją. przykład por.

• 010000010 Jason
• 010000011 David
• 010000012 Theo

w Los Angeles zawsze używasz HI 02. na przykład:

• 020000045 Rupert
• 020000046 Oswald
• 020000047 Mario

Kiedy więc korzystasz z replikacji bazy danych (bez względu na markę), wszystkie klucze podstawowe i dane łączą się łatwo i naturalnie, nie martwiąc się o duplikaty kluczy podstawowych, kolizje itp.

To najlepszy sposób na przejście w tym scenariuszu.