Question Quel est l'algorithme Hi / Lo?


Quel est l'algorithme Hi / Lo?

J'ai trouvé ça dans le NHibernate documentation (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 le gère, et je n'ai pas besoin de connaître l'intérieur, mais je suis juste curieux.


425
2017-11-11 20:53


origine


Réponses:


L'idée de base est que vous avez deux nombres pour constituer une clé primaire - un nombre "haut" et un nombre "bas". 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, supposons que vous ayez une séquence "haute" avec une valeur courante de 35, et que le nombre "bas" soit dans la plage 0-1023. Ensuite, le client peut incrémenter la séquence à 36 (pour que les autres clients puissent générer des clés alors qu'il utilise 35) et savoir que les touches 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 et de les récupérer ensuite sur le client. Mis à part toute autre chose, cela signifie que vous pouvez facilement établir des relations parents / enfants et avoir les clés en place avant de faire tout insère, ce qui rend les lots plus simples.


482
2017-11-11 20:57



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 lui-même le nombre de lo. Il n'est pas nécessaire de contacter le serveur avant que la plage lo ne soit utilisée.


142
2017-11-11 22:08



Mieux que l’allocateur Hi-Lo, l’allocateur "Linear Chunk". Cela utilise un principe similaire à celui des tables, mais alloue de petits morceaux de taille pratique et génère de belles valeurs respectueuses de l'homme.

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

Pour allouer le prochain, par exemple, 20 clés (qui sont ensuite maintenues comme une plage dans le serveur et utilisé au besoin):

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

À condition que vous puissiez valider cette transaction (utilisez les tentatives pour gérer les conflits), vous avez alloué 20 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 d'une séquence Oracle, et est 100% portable parmi toutes les bases de données. Les performances d'allocation sont équivalentes à celles de la fonction hi-lo.

Contrairement à l'idée d'Ambler, elle traite l'espace-clé comme une ligne numérique contiguë.

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

L'idée de M. Ambler, par comparaison, alloue les hauts 16 ou 32 bits, et génère de grandes valeurs de clé inamicales humaines comme l'incrément de hi-mots.

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

J'ai effectivement correspondu avec M. Ambler dans les années 90 pour lui suggérer ce schéma amélioré, mais il était trop coincé et obstiné pour reconnaître les avantages et la clarté de l'utilisation d'une ligne linéaire.

Du point de vue du design, sa solution est fondamentalement plus complexe sur la ligne numérique (clés composites, grands produits hi_word) que sur Linear_Chunk, tout en n'obtenant aucun avantage comparatif. Sa conception est donc mathématiquement prouvée déficiente.


18
2017-08-26 09:29



Les algorithmes hi / lo divisent le domaine des séquences en groupes "hi". Une valeur "hi" est attribué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 doublons simultanés.

  1. Le jeton "salut" 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 avons seulement besoin 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:

enter image description here

Alors que l'optimiseur hi / lo convient parfaitement à l'optimisation de la génération d'identificateurs, 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'identifiant.

Hibernate offre le pooled-lo optimiseur, qui combine une stratégie de générateur hi / lo avec un mécanisme d'allocation de séquence d'interopérabilité. Cet optimiseur est à la fois efficace et interopérable avec les autres systèmes, ce qui en fait un meilleur candidat que l’ancienne stratégie d’identification hi / lo.


18
2018-06-23 14:27



J'ai trouvé l'algorithme Hi / Lo 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 ... Ainsi, à New York, lorsqu'une personne est créée ... vous utilisez toujours 01 comme valeur HI et la valeur LO est la valeur secondaire suivante. 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 la base de données (quelle que soit la marque), toutes les clés et données primaires se combinent facilement et naturellement sans se soucier des clés primaires, des collisions, etc. en double.

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


1
2017-09-23 17:08