database - Quel est l'algorithme Hi / Lo?




3 Answers

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 créer des relations parents / enfants et que les clés sont toutes en place avant de faire des insertions, ce qui simplifie la mise en lots.

Quel est l'algorithme Hi / Lo?

J'ai trouvé ceci dans la documentation de 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 comment cela fonctionne.

Je sais que Nhibernate le gère, et je n'ai pas besoin de connaître l'intérieur, mais je suis juste curieux.




Mieux que l'allocateur Hi-Lo, est 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. La performance d'allocation est équivalente à 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. Son design est donc déficient mathématiquement.




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 PERSON ... donc à New York quand une personne est créée ... vous utilisez toujours 01 comme valeur HI et la valeur de LO est le prochain secuential. 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 avoir à se soucier des clés primaires, des collisions, etc.

C'est la meilleure façon d'aller dans ce scénario.




Related