Was ist der Hi / Lo-Algorithmus?

Was ist der Hi / Lo-Algorithmus?

Ich habe dies in der NHibernate- Dokumentation gefunden (es ist eine Methode zum Generieren eindeutiger Schlüssel, Abschnitt 5.1.4.2), aber ich habe keine gute Erklärung für die Funktionsweise gefunden.

Ich weiß, dass Nhibernate damit umgeht, und ich muss das Innere nicht kennen, aber ich bin nur neugierig.

Die Grundidee ist, dass Sie zwei Zahlen haben, um einen Primärschlüssel zu bilden - eine "hohe" und eine "niedrige" Zahl. Ein Client kann die "hohe" Sequenz grundsätzlich inkrementieren, da er weiß, dass er dann sicher Schlüssel aus dem gesamten Bereich des vorherigen "hohen" Werts mit der Vielzahl von "niedrigen" Werten generieren kann.

Angenommen, Sie haben eine "hohe" Sequenz mit einem aktuellen Wert von 35 und die "niedrige" Zahl liegt im Bereich von 0 bis 1023. Dann kann der Client die Sequenz auf 36 erhöhen (damit andere Clients Schlüssel generieren können, während er 35 verwendet) und wissen, dass die Schlüssel 35/0, 35/1, 35/2, 35/3 ... 35/1023 sind alles Verfügbar.

Es kann sehr nützlich sein (insbesondere bei ORMs), die Primärschlüssel auf der Clientseite festlegen zu können, anstatt Werte ohne Primärschlüssel einzufügen und sie dann wieder auf den Client abzurufen. Abgesehen von allem anderen, es heißt , Sie können leicht Eltern / Kind - Beziehungen machen und haben die alle Schlüssel vorhanden , bevor Sie tun alle Einsätze, die sie einfacher macht Dosieren.

Zusätzlich zu Jons Antwort:

Es wird verwendet, um getrennt arbeiten zu können. Ein Client kann dann den Server nach einer Hi-Nummer fragen und Objekte erstellen, die die Lo-Nummer selbst erhöhen. Der Server muss erst kontaktiert werden, wenn der Bereich lo aufgebraucht ist.

Da dies eine sehr häufige Frage ist, habe ich diesen Artikel geschrieben , auf dem diese Antwort basiert.

Die Hi / Lo-Algorithmen teilen die Sequenzdomäne in "Hi" -Gruppen auf. Ein "Hi" -Wert wird synchron zugewiesen. Jede "Hi" -Gruppe erhält eine maximale Anzahl von "Lo" -Einträgen, die offline zugewiesen werden können, ohne sich um gleichzeitige doppelte Einträge sorgen zu müssen.

1. Das "Hi" -Token wird von der Datenbank zugewiesen, und bei zwei gleichzeitigen Aufrufen werden garantiert eindeutige aufeinanderfolgende Werte angezeigt
2. Sobald ein "Hi" -Token abgerufen wurde, benötigen wir nur noch die "incrementSize" (die Anzahl der "lo" -Einträge).

3. Der Bezeichnerbereich wird durch die folgende Formel angegeben:

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

   und der "lo" -Wert liegt im Bereich:

   [0, incrementSize)

   wird ab dem Startwert angewendet von:

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

4. Wenn alle "lo" -Werte verwendet werden, wird ein neuer "hi" -Wert abgerufen und der Zyklus fortgesetzt

Eine ausführlichere Erklärung finden Sie in diesem Artikel :

Und diese visuelle Präsentation ist auch leicht zu verfolgen:

Der Hi / Lo-Optimierer eignet sich zwar gut zur Optimierung der Bezeichnergenerierung, funktioniert jedoch nicht gut mit anderen Systemen, die Zeilen in unsere Datenbank einfügen, ohne etwas über unsere Bezeichnerstrategie zu wissen.

Hibernate bietet das Pool-Lo Optimierer, der die Vorteile der Hi / Lo-Generatorstrategie bietet und gleichzeitig Interoperabilität mit anderen Drittanbieter-Clients bietet, die diese Sequenzzuweisungsstrategie nicht kennen.

Der Pooled-Lo-Optimierer ist sowohl effizient als auch interoperabel mit anderen Systemen und ein viel besserer Kandidat als die bisherige Hi / Lo-Identifizierungsstrategie.

Lo ist ein zwischengespeicherter Allokator, der den Schlüsselbereich in große Teile aufteilt, die normalerweise auf einer bestimmten Maschinenwortgröße basieren, und nicht auf den Bereichen mit sinnvoller Größe (z. B. 200 Schlüssel gleichzeitig), die ein Mensch möglicherweise sinnvoll auswählt.

Die Verwendung von Hi-Lo verschwendet beim Neustart des Servers in der Regel eine große Anzahl von Schlüsseln und generiert große, für den Menschen unfreundliche Schlüsselwerte.

Besser als der Hi-Lo-Allokator ist der Allokator "Linear Chunk". Dies verwendet ein ähnliches tabellenbasiertes Prinzip, weist jedoch kleine, zweckmäßig große Blöcke zu und generiert nette, menschenfreundliche Werte.

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

So weisen Sie beispielsweise die nächsten 200 Schlüssel zu (die dann als Bereich auf dem Server gespeichert und bei Bedarf verwendet werden):

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

Vorausgesetzt, Sie können diese Transaktion festschreiben (verwenden Sie Wiederholungsversuche, um Konflikte zu behandeln), haben Sie 200 Schlüssel zugewiesen und können diese nach Bedarf ausgeben.

Mit einer Blockgröße von nur 20 ist dieses Schema 10-mal schneller als die Zuweisung aus einer Oracle-Sequenz und zu 100% auf alle Datenbanken portierbar. Die Zuordnungsleistung entspricht Hi-Lo.

Im Gegensatz zu Amblers Idee wird der Schlüsselraum als zusammenhängende lineare Zahlenlinie behandelt.

Dies vermeidet den Anstoß für zusammengesetzte Schlüssel (die nie wirklich eine gute Idee waren) und vermeidet die Verschwendung ganzer Wörter beim Neustart des Servers. Es generiert "freundliche" Schlüsselwerte auf menschlicher Ebene.

Im Vergleich dazu weist die Idee von Herrn Ambler die hohen 16- oder 32-Bit-Werte zu und generiert große, für den Menschen unfreundliche Schlüsselwerte als Inkrement der Hi-Words.

Vergleich der zugewiesenen Schlüssel:

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

In Bezug auf das Design ist seine Lösung in der Zahlenreihe (zusammengesetzte Schlüssel, große Hi_word-Produkte) wesentlich komplexer als die von Linear_Chunk, ohne dass ein komparativer Vorteil erzielt wird.

Das Hi-Lo-Design entstand früh in der OO-Zuordnung und -Persistenz. Heutzutage bieten Persistenz-Frameworks wie Hibernate standardmäßig einfachere und bessere Allokatoren.

Ich fand, dass der Hi / Lo-Algorithmus perfekt für mehrere Datenbanken mit Replikationsszenarien ist, die meiner Erfahrung nach basieren. Stell dir das vor. Wenn Sie einen Server in New York (Alias ​​01) und einen anderen Server in Los Angeles (Alias ​​02) haben, haben Sie eine PERSON-Tabelle. Wenn also in New York eine Person erstellt wird, verwenden Sie immer 01 als HI-Wert und der LO-Wert ist der nächste Folgewert. Beispiel.

• 010000010 Jason
• 010000011 David
• 010000012 Theo

In Los Angeles verwenden Sie immer den HI 02. Zum Beispiel:

• 020000045 Rupert
• 020000046 Oswald
• 020000047 Mario

Wenn Sie also die Datenbankreplikation (unabhängig von der Marke) verwenden, lassen sich alle Primärschlüssel und Daten einfach und natürlich kombinieren, ohne sich um doppelte Primärschlüssel, Kollisionen usw. sorgen zu müssen.

Dies ist der beste Weg in diesem Szenario.