Quel est l'algorithme Hi/Lo?

Question

Quel est l'algorithme Hi/Lo?

J'ai trouvé ça dans le NHibernate de la 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é de bonne explication de comment ça fonctionne.

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

Answer 1

L'idée de base est que vous avez deux numéros pour faire une clé primaire - un niveau "élevé" nombre et un "faible" nombre. Un client peut, en gros, incrémenter le "haut" de la séquence, en sachant qu'il peuvent alors générer des clés de l'ensemble de la gamme de "haute valeur" avec la variété de "faible" des valeurs.

Par exemple, supposons que vous avez un niveau "élevé" de la séquence avec une valeur actuelle de 35, et le "faible" nombre dans la plage de 0û1023. Ensuite, le client peut incrémenter la séquence à 36 (pour d'autres clients pour être en mesure de générer des clés alors que c'est à l'aide de 35) et de 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) pour être en mesure de définir les clés primaires sur le côté client, au lieu d'insérer des valeurs sans les clés primaires et ensuite de les chercher en arrière sur le client. À côté de quelque chose d'autre, cela signifie que vous pouvez facilement faire des relations parent/enfant et avoir les clés tout en place avant de faire toute inserts, ce qui rend le dosage plus simples.

Answer 2

En plus Jon réponse:

Il est utilisé pour être en mesure de travailler déconnecté. Un client peut alors demander au serveur pour un hi nombre et de créer des objets à l'augmentation de la lo nombre lui-même. Il n'a pas besoin de contacter le serveur jusqu'à ce que le lo plage est utilisé.

Answer 3

Le hi/lo algorithmes divise les séquences de domaine en "hi" groupes. Un "salut" la valeur est affectée de manière synchrone. Chaque "hi" groupe reçoit un nombre maximum de "lo" entrées, qui peuvent être affectés hors-ligne, sans vous soucier de la simultanée des entrées en double.

1. Le "salut" jeton est attribué par la base de données, et de deux appels simultanés sont garantis pour voir unique des valeurs consécutives
2. Une fois qu'un "salut" jeton est récupéré, nous avons seulement besoin de la "incrementSize" (le nombre de "lo" entrées)

3. Les identificateurs de gamme est donnée par la formule suivante:

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

   et le "lo" valeur sera dans la gamme:

   [0, incrementSize)
   

   être appliquée à partir de la valeur de début:

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

4. Lorsque tous les "lo" les valeurs sont utilisées, une nouvelle "hi" valeur est extraite et le cycle continue

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

Et la présentation visuelle est facile à suivre:

Answer 4

Mieux que le Hi-Lo allocateur, est le "Linéaire Morceau" l'allocateur. Il utilise une table similaire à base de principe, mais alloue de petites, idéalement gros morceaux de taille et génère homme nice-amicale des valeurs.

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

Pour allouer de la côté de, disons, 20 clés (qui sont alors considéré comme une plage dans le serveur et utilisé selon les besoins):

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

Fournir vous pouvez valider cette transaction (l'utilisation de nouvelles tentatives pour gérer le conflit), vous avez alloué 20 clés et peut s'en passer.

Avec un morceau de taille de 20, ce schéma est 10x plus rapide que l'attribution d'un Oracle de la séquence, et est 100% portable parmi toutes les bases de données. Répartition de la performance est équivalente à la hi-lo.

Contrairement à Ambler idée, il considère l'espace comme un contiguë linéaire numberline.

Cela évite l'impulsion pour les clés composites (qui n'ont jamais été vraiment une bonne idée) et évite de gaspiller l'ensemble de la lo-dire lorsque le serveur redémarre. Il génère des "amis", à taille humaine, des valeurs clés.

M. Ambler l'idée, par comparaison, alloue le haut de 16 ou 32 bits, et génère un grand homme hostile valeurs de clé comme la hi-mots de l'incrément.

Comparaison de l'allocation de touches:

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

J'ai fait correspondu avec M. Ambler retour dans les années 90 pour suggérer l'amélioration de ce régime à lui, mais il était trop coincé et obstiné de reconnaître les avantages et claire de la simplicité de l'utilisation d'un linéaire de numéro de ligne.

Conception-sage, sa solution est fondamentalement plus complexe sur le nombre de ligne (clés composites, grand hi_word produits) que Linear_Chunk tout en réalisant pas d'avantages comparatifs. Sa conception est donc mathématiquement prouvé déficientes.