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é une bonne explication de la façon dont il 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.

InformationsquelleAutor DiegoCofre | 2008-11-11

510

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 vous faire tout inserts, ce qui rend le dosage plus simples.
- Dites-vous que "portées" sont coordonnés dans le client, tandis que le "haut" séquence correspond à une DB séquence?
- Yup, c'est principalement ça.
- Sont la hi & lo valeurs généralement composé en une seule valeur entière, ou une partie de deux clés d'affaires?
- comme une adresse IP, alors - de l'ICANN, vous donne un grand "réseau" certain nombre, vous avez alors que de nombreux bas "hôte" de numéros que vous le souhaitez, dans la limite de la CIDR gamme que vous êtes donné.
- Quel est l'avantage de l'algorithme hi/lo plus simplement avoir des clients dessiner lots de clés à partir de la séquence centrale en vrac?
- Fondamentalement, rien - c'est juste potentiellement moins cher pour incrémenter une valeur (le "haut" de la partie) que de générer un trousseau de clefs. (C'est potentiellement bien moins cher en termes de transfert de données - vous pouvez "réserve" un grand nombre de touches avec un minimum de bande passante).
- Vrai. Si, dans la pratique, les clients n'ont pas besoin d' virement le lot de clés. La séquence centrale pourrait simplement être incrémenté par une plus grande quantité, de manière efficace en réservant ces touches pour le client.
- C'est vrai que si les clés sont seulement des nombres. Pas tellement pour les Guid 🙂 Mais oui, dans le cas de simples numéros, toute atomique "incrémenter par un montant fixe" on va le faire. C'est effectivement ce que hi-lo est en train de faire, si vous pensez à elle comme à un nombre divisé en deux sections.
- Oui, c'est efficace what hi-lo est en train de faire. Vous êtes le point de non-touches numériques finalement a été le déclic pour moi. Comment naïf de ma part, en supposant que les clés sont des nombres. 🙂
- Donc, c'est juste une façon particulière à attribuer au client un éventail de clés primaires au lieu d'une seule clé primaire, ce qui est souhaitable pour des raisons de performances?
- C'est ma compréhension, oui. Bien sûr, il pourrait y avoir des subtilités que je suis en manque 🙂
- Dans l'exemple de la séquence- 35/0, 35/1, 35/2, 35/3... 35/1023, ne devrait pas l'être c'36 au lieu de 35?
- Lorsque Hi) est égal à 35 cela signifie que 35 est d'abord inoccupé de la séquence. Toutes les séquences de moins de 35 ans sont déjà utilisés par d'autres clients. Par incrémentation Salut de la valeur que le client se réserve de 35 à soi, et informe les autres clients que 36 à devenir le premier inoccupé de la séquence.
- Comment est la clé stockée dans la db? Et je suppose que le salut du nombre de semences pour la prochaine utilisateur devrait être stocké dans un tableau de référence et augmente lorsque la demande?
- Il serait stocké dans la base de données que la valeur complète, sous la forme d'un nombre (les bits élevés et les bits de poids faible écrasé dans un plus grand champ) ou, éventuellement, sous forme de deux champs. (Il n'y a pas beaucoup de point en faisant de ce dernier.) La graine dépend de la base de données, il pourrait être une séquence Oracle, par exemple, ou tout simplement une ligne dans une table séparée.
- Selon les données sur l'insertion des scénarios, il semble qu'il peut entraîner des lacunes dans id-s et beaucoup de gaspillage id-s? Est-il une version de hi-lo algorithme attaquer?
- Si vous avez une grande gamme d'Identifiants (par exemple, 64 ou 128 bits) les lacunes n'ont pas vraiment d'importance. Si vous êtes limité à un bas de gamme, vous affecter moins par la "haute" partie - par exemple, que de leur donner dans des morceaux de 256. Vous aurez toujours de "déchets" certains Identifiants, mais dans la plupart des cas, c'est vraiment n'est pas un problème.
- Si je n'ai pas mal compris votre moyenne, l'Id'value est généré par hilo dans le client sans être dans le serveur de base de données? Est-il une bonne raison de le faire ? merci.
- Vous parlez de la base de données de réserver un "morceau" de l'IDs: il vous donne un "salut" de la valeur dont il ne reviendra pas à quelqu'un d'autre, et puis vous remplissez le "lo" valeurs localement. Cela signifie que vous avez juste besoin d'1 à la base de données, dans le but d'obtenir une grande partie de l'IDs, au lieu d'un par entité.
- Je vois, Il est vraiment intelligent et efficace pour générer de l'Id de la liste . Merci de votre réponse!
- dans l'exemple que vous avez mentionné, quelles sont les principales clés pour être écrit à la table de base de données? sont-ils 35-0, 35-1, ou qch? Aussi, comment puis-je définir élevé et de faibles effectifs, ce sont les relations de ces numéros pour hibernate_sequence table?
- Vous feriez soit avoir une certaine manière de composer les différentes parties en un seul chiffre (par exemple, en multipliant la partie haute de 100 000 ou quelque chose, puis en ajoutant la partie basse) ou vous auriez une clé primaire composite. Je ne suis pas sûr de ce que vous entendez par "définir haute et basse numéros" - et ça fait trop longtemps depuis que j'ai travaillé avec Hibernate pour vous donner les détails de cet aspect. Désolé!
- Cet algorithme peut être utilisé avec d'autres (Micro) Orm comme Dapper? Est-il magiques supplémentaires NHibernate n'en dehors de la tables que nous créons, qui devront être intégrées dans Dapper?
- Je ne sais rien à propos de Dapper, j'en ai peur.
InformationsquelleAutor Jon Skeet
150

En plus de 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é.
- Je préfère ce pour des raisons de concision.
InformationsquelleAutor Stephan Eggermont
24

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 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 ainsi:

Tout en hi/lo optimizer est bien pour l'optimisation de l'identificateur de génération, il ne joue pas bien avec les autres systèmes de l'insertion de lignes dans notre base de données, sans rien connaître de notre identificateur de la stratégie.

Hibernate offre la commun-lo optimizer, qui combine une chaîne hi/lo générateur de stratégie avec une interopérabilité séquence mécanisme d'allocation. Cette optimizer est à la fois efficace et interopérable avec d'autres systèmes, d'être un meilleur candidat que le précédent héritage hi/lo identificateur de stratégie.
- Je ne comprends vraiment pas vous parfois hahaha donc: Tout en hi/lo optimizer est bien pour l'optimisation de l'identificateur de génération (bon Ok), il ne joue pas bien avec les autres systèmes(que voulez-vous dire par d'autres systèmes ?, qui sont les premiers ?) l'insertion de lignes dans notre base de données(Ne pas identificateur de génération utilisé pour insérer des lignes trop ?) sans rien connaître de notre identificateur de la stratégie.
- D'autres systèmes, comme un DBA essayez d'exécuter une instruction INSERT. Si elle lit la séquence actuelle de données, pensez-vous qu'il est facile de trouver la prochaine valeur de l'identifiant sachant que nous utilisons hilo dans cette table DB?
InformationsquelleAutor Vlad Mihalcea
20

Lo est une mise en cache de l'allocateur qui divise l'espace en gros morceaux, généralement basés sur une certaine machine taille de mot, plutôt que de façon significative de la taille des plages (par exemple l'obtention de 200 touches à la fois) dont un être humain peut raisonnablement choisir.

Hi-Lo utilisation tend à déchets d'un grand nombre de touches de redémarrage du serveur, et de générer de grandes humain hostile valeurs de clé.

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 & génère homme nice-amicale des valeurs.
```
create table KEY_ALLOC (
    SEQ varchar(32) not null,
    NEXT bigint not null,
    primary key (SEQ)
);
```
D'allouer une nouvelle, disons, 200 clés (qui sont alors considéré comme une plage dans le serveur & utilisé comme nécessaire):
```
select NEXT from KEY_ALLOC where SEQ=?;
update KEY_ALLOC set NEXT=(old value+200) 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é 200 clés & peut s'en passer si nécessaire.

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
```
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.

La Hi-Lo design se leva tôt OO de la cartographie et de la persistance. Ces jours persistance des frameworks tels que Hibernate offre plus simple et mieux allocateurs en tant que par défaut.
- Qui est monsieur Ambler?
- Scott Ambler la promotion d'un soi-disant "hi-lo" stratégie de répartition de l'aide de 16 ou 32 bits. Voici sa page: ambysoft.com/scottAmbler.html
- Post-Nice, mais vous n'êtes pas à répondre à la question.
- +1 pour une réponse intéressante. Je suis d'accord que la grande majorité des applications, aucun avantage de Hi-Lo sur l'approche la plus simple; cependant, je pense que Hi-Lo est mieux adapté au cas particulier de plusieurs allocateurs hautement applications simultanées.
- Merci @richj! Mon point est que vous pouvez utiliser plusieurs allocateurs ou de grandes tailles de bloc avec "linéaire du bloc d'allocation", mais que, contrairement à la Hi/Lo -- il maintient un linéaire de la correspondance de l'allocateur de NEXT_VAL clés dans la table, et est accordables. Contrairement à HiLo, pas de multiplication est nécessaire, c'est juste pas nécessaire! Le multiplicateur & de stockage de NEXT_HI fait HiLo plus complexe & pauses tuneability, puisque la modification de la taille des blocs va modifier arbitrairement la touche next pour être publié.. Voir: literatejava.com/hibernate/...
- Je suis intéressé dans de multiples indépendants allocateurs. Avec Hi-Lo, il est évident que la valeur peut être partitionné en allocateur ID/bloc ID. Il n'était pas immédiatement évident (pour moi) que la même approche peut être appliquée à Linéaire Morceau, mais c'est fondamentalement le même problème de la division de la plage totale entre les allocateurs. Je l'ai maintenant. Merci.
- Quel est le but de la SEQ colonne du tableau KEY_ALLOC? Comment est-il utilisé?
- Oh, après réflexion, je pense que le SEQ colonne correspond à un nom de table. Par exemple, il y a un allocateur de la table Clients, un pour la table Commandes, et ainsi de suite. Pardonnez-moi, je suis lent, parfois.
InformationsquelleAutor Thomas W
1

J'ai trouvé l'algorithme Hi/Lo est parfait pour de multiples bases de données avec des scénarios de réplication de base de mon expérience. Imaginer cela. vous disposez d'un serveur à New York (alias 01) et un autre serveur à Los Angeles (alias 02), alors vous avez une PERSONNE de la table...
ainsi, à New York, lorsqu'une personne est créer... vous utilisez toujours 01 que le SALUT de la valeur et de la valeur LO est la prochaine secuential. por exemple.
- 010000010 Jason
- 010000011 David
- 010000012 Theo
à Los Angeles, vous utilisez toujours le SALUT 02. par exemple:
- 020000045 Rupert
- 020000046 Oswald
- 020000047 Mario
Donc, lorsque vous utilisez la réplication de base de données (n'importe quelle marque) toutes les clés primaires et les données de combiner facilement et naturellement, sans vous soucier de dupliquer des clés primaires, collissions, etc.

C'est la meilleure façon d'aller dans ce scénario.
- Il se complique fonctionne pas en mode veille prolongée. HiLo algrotirm obtient une nouvelle valeur de l'ordre dans chaque transaction, de sorte que HI-compteur s'incrémente accordinally. Mais dans votre exemple, HI-compteur est toujours constant pour un DB.
InformationsquelleAutor Theo

Vous devez vous connecter pour publier un commentaire.