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

1. Introduction

Dans ce tutoriel, nous expliquerons l'algorithme Hi / Lo. Il est principalement utilisé comme stratégie de génération d'identifiant de base de données .

Nous allons commencer par la vue d'ensemble de l'algorithme. Ensuite, nous montrerons un exemple pratique basé sur le framework Hibernate. Enfin, nous discuterons des cas d'utilisation de l'algorithme, de ses avantages et de ses inconvénients.

2. Présentation de l'algorithme Hi / Lo

2.1 Définition

L'objectif principal de l'algorithme Hi / Lo est de créer une plage de nombres pouvant être utilisés en toute sécurité comme identificateurs de base de données . Pour ce faire, il utilise trois variables numériques communément appelées high, low et incrementSize .

La variable incrementSize contient le nombre maximal d'identificateurs pouvant être générés dans un lot. Il doit être traité comme une valeur constante définie au début de l'algorithme. Toute modification d'exécution peut entraîner de graves problèmes dans les environnements où plusieurs clients utilisent la même configuration Hi / Lo pour conserver les entrées.

La variable haute est généralement attribuée à partir d'une séquence de base de données. Dans ce cas, nous sommes sûrs que personne n'obtiendra le même numéro deux fois.

La variable basse contient le numéro actuellement attribué dans la plage [0 , incrementSize ).

Compte tenu de ces points, l'algorithme Hi / Lo génère des valeurs dans la plage [( hi - 1) * incrementSize + 1 , ( hi * incrementSize )).

2.2 Pseudocode

Jetons un coup d'œil aux étapes de génération d'une nouvelle valeur à l'aide de l'algorithme Hi / Lo:

  • si low est supérieur ou égal à incrementSize , attribuez une nouvelle valeur à high et réinitialisez low à 0
  • générer une nouvelle valeur avec la formule: ( high - 1) * incrementSize + low
  • incrément faible par 1
  • renvoyer la valeur générée

3. Exemple pratique

Voyons l'algorithme Hi / Lo en action. Pour ce faire, nous utiliserons le framework Hibernate et son implémentation Hi / Lo.

Tout d'abord, définissons une entité de base de données avec laquelle travailler:

@Entity public class RestaurantOrder { @Id @GeneratedValue(strategy = GenerationType.SEQUENCE, generator = "hilo_sequence_generator") @GenericGenerator( name = "hilo_sequence_generator", strategy = "sequence", parameters = { @Parameter(name = "sequence_name", value = "hilo_seqeunce"), @Parameter(name = "initial_value", value = "1"), @Parameter(name = "increment_size", value = "3"), @Parameter(name = "optimizer", value = "hilo") } ) private Long id; }

C'est une simple commande de restaurant avec un seul champ d' identification . Pour définir correctement l'algorithme Hi / Lo dans Hibernate, dans la définition du champ id , il faut choisir une stratégie de séquence - optimiseur hilo - et spécifier le paramètre increment_size .

Pour montrer l'algorithme Hi / Lo en action, nous conserverons neuf commandes de restaurant dans une boucle:

public void persist() { Transaction transaction = session.beginTransaction(); for (int i = 0; i < 9; i++) { session.persist(new RestaurantOrder()); session.flush(); } transaction.commit(); }

Selon la taille d'incrément spécifiée dans l'entité, nous ne devrions avoir que trois appels à la base de données pour la prochaine valeur élevée . En supposant que la séquence de base de données commence à 1, le premier lot d'identificateurs générés sera dans la plage [1,3].

Lorsque l'algorithme Hi / Lo renvoie 3 et Hibernate demande la valeur de l'identificateur suivant, la valeur de la variable basse est égale à la constante incrementSize . Dans ce cas, le prochain appel à la base de données pour la nouvelle valeur élevée doit être effectué. Ayant 2 comme nouvelle valeur élevée , l'algorithme génère des valeurs dans la plage [4,6].

Enfin, le dernier appel à la base de données pour la prochaine valeur élevée est effectué, et les valeurs dans la plage [7, 9] sont attribuées aux entités.

Les journaux Hibernate capturés lors de l'exécution de la méthode persist () confirment ces valeurs:

Hibernate: call next value for hilo_seqeunce org.hibernate.id.enhanced.SequenceStructure - Sequence value obtained: 1 org.hibernate.event.internal.AbstractSaveEventListener - Generated identifier: 1, using strategy: org.hibernate.id.enhanced.SequenceStyleGenerator org.hibernate.event.internal.AbstractSaveEventListener - Generated identifier: 2, using strategy: org.hibernate.id.enhanced.SequenceStyleGenerator org.hibernate.event.internal.AbstractSaveEventListener - Generated identifier: 3, using strategy: org.hibernate.id.enhanced.SequenceStyleGenerator Hibernate: call next value for hilo_seqeunce org.hibernate.id.enhanced.SequenceStructure - Sequence value obtained: 2 org.hibernate.event.internal.AbstractSaveEventListener - Generated identifier: 4, using strategy: org.hibernate.id.enhanced.SequenceStyleGenerator org.hibernate.event.internal.AbstractSaveEventListener - Generated identifier: 5, using strategy: org.hibernate.id.enhanced.SequenceStyleGenerator org.hibernate.event.internal.AbstractSaveEventListener - Generated identifier: 6, using strategy: org.hibernate.id.enhanced.SequenceStyleGenerator Hibernate: call next value for hilo_seqeunce org.hibernate.id.enhanced.SequenceStructure - Sequence value obtained: 3 org.hibernate.event.internal.AbstractSaveEventListener - Generated identifier: 7, using strategy: org.hibernate.id.enhanced.SequenceStyleGenerator org.hibernate.event.internal.AbstractSaveEventListener - Generated identifier: 8, using strategy: org.hibernate.id.enhanced.SequenceStyleGenerator org.hibernate.event.internal.AbstractSaveEventListener - Generated identifier: 9, using strategy: org.hibernate.id.enhanced.SequenceStyleGenerator

4. Avantages et inconvénients de l'algorithme

Le principal avantage de l'algorithme Hi / Lo est le nombre réduit d'appels à la base de données pour les valeurs de séquence suivantes. L'augmentation de la valeur de incrementSize diminue le nombre d'aller-retour vers la base de données. Évidemment, cela signifie un gain de performances dans notre application. En plus de cela, l'algorithme Hi / Lo est un choix préféré dans les environnements avec une connexion Internet faible .

D'autre part, l'algorithme Hi / Lo n'est pas le meilleur choix dans les environnements où plusieurs clients différents conservent des données dans la même table dans une base de données . Les applications tierces ne connaissent peut-être pas la stratégie Hi / Lo que nous utilisons pour générer des identifiants. En conséquence, ils peuvent utiliser des identifiants d'entité à partir de la plage de nombres générée actuellement utilisée dans notre application. Dans ce cas, lors de la persistance des données, nous pouvons rencontrer des erreurs difficiles à corriger.

5. Conclusion

Dans ce tutoriel, nous avons discuté de l'algorithme Hi / Lo.

Tout d'abord, nous avons expliqué son fonctionnement et discuté de son implémentation de pseudocode. Ensuite, nous avons montré un exemple pratique utilisant l'implémentation de l'algorithme d'Hibernate. Enfin, nous avons répertorié les avantages et les inconvénients du Hi / Lo.

Comme toujours, le code affiché dans cet article est disponible à l'adresse over sur GitHub.