Qu'est-ce que l'algorithme Hi / Lo?

464

Qu'est-ce que l'algorithme Hi / Lo?

J'ai trouvé cela dans la documentation NHibernate (c'est une méthode pour générer des clés uniques, section 5.1.4.2), mais je n'ai pas trouvé une bonne explication de son fonctionnement.

Je sais que Nhibernate s'en occupe, et je n'ai pas besoin de connaître l'intérieur, mais je suis juste curieux.

DiegoCofre
la source

Réponses:

541

L'idée de base est que vous avez deux nombres pour constituer une clé primaire - un nombre «élevé» et un nombre «faible». Un client peut fondamentalement incrémenter la séquence "haute", sachant qu'il peut alors générer en toute sécurité des clés à partir de toute la plage de la valeur "haute" précédente avec la variété de valeurs "basses".

Par exemple, en supposant que vous avez une séquence "élevée" avec une valeur actuelle de 35 et que le nombre "faible" soit compris entre 0 et 1023. Ensuite, le client peut incrémenter la séquence à 36 (pour que d'autres clients puissent générer des clés pendant qu'il utilise 35) et savoir que les clés 35/0, 35/1, 35/2, 35/3 ... 35/1023 sont tous disponibles.

Il peut être très utile (en particulier avec les ORM) de pouvoir définir les clés primaires côté client, au lieu d'insérer des valeurs sans clés primaires, puis de les récupérer sur le client. En plus de toute autre chose, cela signifie que vous pouvez facilement établir des relations parent / enfant et que les clés sont toutes en place avant de faire des insertions, ce qui rend leur traitement par lots plus simple.

Jon Skeet
la source
14
Voulez-vous dire que les "plages basses" sont coordonnées au sein du client, tandis que la "séquence haute" correspond à une séquence DB?
Chris Noe
14
Les valeurs hi & lo sont-elles alors généralement composées en une seule valeur entière ou en tant que clé métier en deux parties?
Chris Noe
51
comme une adresse IP - l'ICANN vous donne un numéro «réseau» élevé, vous avez alors autant de numéros «hôtes» bas que vous le souhaitez, dans la limite de la plage CIDR qui vous est donnée.
gbjbaanb
6
@Adam: Fondamentalement, rien - il est juste potentiellement moins cher d'augmenter une valeur (la partie "élevée") que de générer un trousseau de clés. (C'est potentiellement beaucoup moins cher en termes de transfert de données - vous pouvez "réserver" un grand nombre de clés avec une bande passante minimale.)
Jon Skeet
4
@Adam: C'est vrai si les clés ne sont que des chiffres. Pas tant pour les GUID :) Mais oui, dans le cas de nombres simples, n'importe quel "incrément atomique d'un montant fixe" fera l'affaire. C'est effectivement ce que fait hi-lo, si vous le considérez comme un numéro divisé en deux sections.
Jon Skeet
157

En plus de la réponse de Jon:

Il est utilisé pour pouvoir travailler déconnecté. Un client peut alors demander au serveur un nombre élevé et créer des objets en augmentant le nombre lo lui-même. Il n'a pas besoin de contacter le serveur tant que la plage lo n'est pas utilisée.

Stephan Eggermont
la source
1
Je préfère cela par souci de concision.
Développeur Marius Žilėnas
34

Puisque c'est une question très courante, j'ai écrit cet article , sur lequel cette réponse est basée.

Les algorithmes hi / lo divisent le domaine des séquences en groupes «hi». Une valeur «hi» est affectée de manière synchrone. Chaque groupe «hi» reçoit un nombre maximum d'entrées «lo», qui peuvent être attribuées hors ligne sans se soucier des entrées en double simultanées.

  1. Le jeton «hi» est attribué par la base de données et deux appels simultanés sont garantis pour voir des valeurs consécutives uniques
  2. Une fois qu'un jeton «hi» est récupéré, nous n'avons besoin que de «incrementSize» (le nombre d'entrées «lo»)
  3. La plage d'identifiants est donnée par la formule suivante:

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

    et la valeur "lo" sera dans la plage:

    [0, incrementSize)

    étant appliqué à partir de la valeur de départ de:

    [(hi -1) * incrementSize) + 1)
  4. Lorsque toutes les valeurs «lo» sont utilisées, une nouvelle valeur «hi» est récupérée et le cycle continue

Vous pouvez trouver une explication plus détaillée dans cet article :

Et cette présentation visuelle est également facile à suivre:

entrez la description de l'image ici

Bien que l'optimiseur hi / lo soit idéal pour optimiser la génération d'identifiants, il ne fonctionne pas bien avec d'autres systèmes insérant des lignes dans notre base de données, sans rien savoir de notre stratégie d'identifiants.

Hibernate propose l' optimiseur pool-lo , qui offre les avantages de la stratégie de générateur hi / lo tout en assurant l'interopérabilité avec d'autres clients tiers qui ne connaissent pas cette stratégie d'allocation de séquence.

À la fois efficace et interopérable avec d'autres systèmes, l'optimiseur pooled-lo est un bien meilleur candidat que la stratégie d'identificateur hi / lo héritée.

Vlad Mihalcea
la source
Je ne vous comprends vraiment pas parfois hahaha donc: Bien que l'optimiseur hi / lo soit bien pour optimiser la génération d'identifiants (ok bon), il ne fonctionne pas bien avec d'autres systèmes (que voulez-vous dire par d'autres systèmes?, Qui sont les premiers uns?) insérer des lignes dans notre base de données (la génération d'identifiant n'insère-t-elle pas aussi des lignes?), sans rien savoir de notre stratégie d'identification.
Adelin
D'autres systèmes, comme un DBA essayant d'exécuter une instruction INSERT. Si elle lit les données de séquence actuelles, pensez-vous qu'il est facile de déterminer la prochaine valeur d'identifiant sachant que nous utilisons hilo dans cette table de base de données particulière?
Vlad Mihalcea
Mes excuses si le commentaire ne convient pas à votre réponse, mais je me demandais quel optimiseur est utilisé par défaut? Ou cela dépend-il de DB (j'utilise PostgreSQL)? Parce que je ne peux pas comprendre la relation entre la valeur de séquence actuelle et les ID générés. J'utilise @GeneratedValue(strategy = GenerationType.SEQUENCE, generator = "name") @SequenceGenerator(name="name", sequenceName = "name_seq", allocationSize=100)pour mes identifiants.
Stefan Golubović
1
Depuis Hibernate 5, Pooled est le nouvel optimiseur, pas Hi / lo. Consultez cet article pour plus de détails sur l'optimiseur de pool.
Vlad Mihalcea
@VladMihalcea, je crois que vous avez une faute de frappe dans la puce trois, premier extrait à , (hi * incrementSize) + 1)... ça devrait l'être , hi * incrementSize), non?
Huiagan
23

Lo est un allocateur mis en cache qui divise l'espace de clés en gros morceaux, généralement basés sur une certaine taille de mot machine, plutôt que sur des plages de taille significative (par exemple, l'obtention de 200 clés à la fois) qu'un humain pourrait raisonnablement choisir.

L'utilisation de Hi-Lo a tendance à gaspiller un grand nombre de clés au redémarrage du serveur et à générer de grandes valeurs de clé peu conviviales.

Mieux que l'allocateur Hi-Lo, l'allocateur "Linear Chunk". Cela utilise un principe similaire basé sur une table mais alloue de petits morceaux de taille pratique et génère de belles valeurs conviviales.

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

Pour allouer les 200 clés suivantes, disons (qui sont ensuite conservées en tant que plage dans le serveur et utilisées selon les besoins):

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

À condition que vous puissiez valider cette transaction (utilisez des tentatives pour gérer les conflits), vous avez alloué 200 clés et pouvez les distribuer au besoin.

Avec une taille de bloc de seulement 20, ce schéma est 10 fois plus rapide que l'allocation à partir d'une séquence Oracle et est 100% portable dans toutes les bases de données. Les performances d'allocation sont équivalentes à hi-lo.

Contrairement à l'idée d'Ambler, il traite l'espace de clés comme une ligne de nombre linéaire contiguë.

Cela évite l'impulsion pour les clés composites (qui n'ont jamais vraiment été une bonne idée) et évite de gaspiller des mots entiers au redémarrage du serveur. Il génère des valeurs clés «conviviales» à taille humaine.

L'idée de M. Ambler, par comparaison, alloue les 16 ou 32 bits les plus élevés et génère de grandes valeurs de clé peu conviviales en tant qu'incrément des mots forts.

Comparaison des clés allouées:

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

Du point de vue de la conception, sa solution est fondamentalement plus complexe sur la ligne numérique (clés composites, grands produits hi_word) que Linear_Chunk sans aucun avantage comparatif.

La conception Hi-Lo est apparue au début de la cartographie et de la persistance OO. De nos jours, les frameworks de persistance tels que Hibernate offrent des allocateurs plus simples et meilleurs par défaut.

Thomas W
la source
4
Beau message, mais vous ne répondez pas à la question.
orbfish
1
+1 pour une réponse intéressante. Je suis d'accord que la grande majorité des applications ne tirent aucun avantage de Hi-Lo sur l'approche plus simple; Cependant, je pense que Hi-Lo est mieux adapté au cas particulier des allocateurs multiples dans les applications hautement simultanées.
richj
1
Merci @richj! Mon point est que vous pouvez utiliser plusieurs allocateurs ou de grandes tailles de bloc avec une "allocation de bloc linéaire", mais que, contrairement à Hi / Lo, il maintient une correspondance linéaire de l'allocateur NEXT_VAL avec les clés de la table et est ajustable. Contrairement à HiLo, aucune multiplication n'est nécessaire - ce n'est tout simplement pas nécessaire! Le multiplicateur et le stockage de NEXT_HI rendent HiLo plus complexe et interrompent l'accord, car la modification de la taille de bloc changera arbitrairement la prochaine clé à émettre. Voir: literatejava.com/hibernate/…
Thomas W
2
Je suis intéressé par plusieurs allocateurs indépendants. Avec Hi-Lo, il est évident que la valeur élevée peut être partitionnée en ID d'allocateur / ID de bloc. Il n'était pas immédiatement évident (pour moi) que la même approche puisse être appliquée à Linear Chunk, mais c'est essentiellement le même problème de division de la plage totale entre les allocateurs. Je l'ai maintenant. Merci.
richj
1
Oh, après y avoir réfléchi, je pense que la colonne SEQ correspond à un nom de table. Par exemple, il existe un allocateur pour la table Customers, un pour la table Orders, etc. Pardonnez-moi, je suis lent, parfois.
Rock Anthony Johnson
1

J'ai trouvé que l'algorithme Hi / Lo est parfait pour plusieurs bases de données avec des scénarios de réplication basés sur mon expérience. Imagine ça. vous avez un serveur à New York (alias 01) et un autre serveur à Los Angeles (alias 02) alors vous avez une table PERSONNE ... donc à New York quand une personne est créée ... vous utilisez toujours 01 comme valeur HI et la valeur LO est la prochaine sécuentielle. par exemple.

  • 010000010 Jason
  • 010000011 David
  • 010000012 Theo

à Los Angeles, vous utilisez toujours le HI 02. Par exemple:

  • 020000045 Rupert
  • 020000046 Oswald
  • 020000047 Mario

Ainsi, lorsque vous utilisez la réplication de base de données (quelle que soit la marque), toutes les clés primaires et les données se combinent facilement et naturellement sans se soucier des clés primaires en double, des collisions, etc.

C'est la meilleure façon de procéder dans ce scénario.

Théo
la source
Cela ne fonctionne pas dans Hibernate. HiLo algrotirm obtient une nouvelle valeur de séquence dans chaque transaction, donc le compteur HI s'incrémente en conséquence. Mais dans votre exemple, le compteur HI est toujours constant pour une base de données.
Dmitry1405