Какво представлява алгоритъмът Hi / Lo?

1. Въведение

В този урок ще обясним алгоритъма Hi / Lo. Използва се най-вече като стратегия за генериране на идентификатор на база данни .

Ще започнем с общия преглед на алгоритъма. След това ще покажем практически пример, базиран на Hibernate framework. Накрая ще обсъдим случаите на използване на алгоритъма, неговите предимства и недостатъци.

2. Преглед на алгоритъма Hi / Lo

2.1 Определение

Основната цел на алгоритъма Hi / Lo е да създаде набор от числа, които могат безопасно да се използват като идентификатори на база данни . За да направи това, той използва три числови променливи, които обикновено се наричат висока, ниска и инкрементСайз .

В incrementSize променлива притежава максимален брой идентификатори, които могат да бъдат генерирани в една партида. Тя трябва да се третира като постоянна стойност, определена в началото на алгоритъма. Всяка модификация по време на изпълнение може да причини сериозни проблеми в среди, където множество клиенти използват една и съща Hi / Lo конфигурация, за да продължат записите.

На високо променлива обикновено се определя от последователност данни. В този случай сме сигурни, че никой няма да получи едно и също число два пъти.

В ниско променливата държи понастоящем е определен брой в диапазона [0 , incrementSize ).

Като се имат предвид тези точки, алгоритъмът Hi / Lo генерира стойности в диапазон [( hi - 1) * incrementSize + 1 , ( hi * incrementSize )).

2.2 Псевдокод

Нека да разгледаме стъпките за генериране на нова стойност с помощта на алгоритъма Hi / Lo:

  • ако ниската е по-голяма или равна на incrementSize , задайте нова стойност на висока и нулирайте ниската на 0
  • генерирайте нова стойност с формулата: ( висока - 1) * incrementSize + ниска
  • увеличаване на ниското с 1
  • връща генерираната стойност

3. Практически пример

Нека видим Hi / Lo алгоритъма в действие. За да направим това, ще използваме рамката Hibernate и нейната Hi / Lo реализация.

Първо, нека дефинираме обект на база данни, с който да работим:

@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; }

Това е проста поръчка в ресторант с едно поле за идентификация . За да дефинираме правилно Hi / Lo алгоритъма в Hibernate, в дефиницията на полето id трябва да изберем стратегия за последователност - hilo optimizer - и да посочим параметъра increment_size .

За да покажем алгоритъма Hi / Lo в действие, ще запазим девет поръчки на ресторант в цикъл:

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

Според посочения размер на нарастване в обекта, трябва да имаме само три извиквания към базата данни за следващата висока стойност. Ако приемем, че последователността на базата данни започва от 1, първата партида от генерирани идентификатори ще бъде в диапазона [1,3].

Когато алгоритъмът Hi / Lo връща 3 и Hibernate иска стойността на следващия идентификатор, стойността на ниската променлива е равна на константата incrementSize . В този случай трябва да се направи следващото извикване на базата данни за новата висока стойност. Имайки 2 като нова висока стойност, алгоритъмът генерира стойности в диапазона [4,6].

Накрая се прави последното извикване на базата данни за следващата висока стойност и стойностите в диапазона [7, 9] се присвояват на обектите.

Дневниците на хибернация, заснети по време на изпълнението на метода persist () , потвърждават тези стойности:

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. Ползи и недостатъци на алгоритъма

Основното предимство на Hi / Lo алгоритъма е намаленият брой извиквания на база данни за следващите стойности на последователността. Увеличаването на стойността на incrementSize намалява броя на обратните пътувания до базата данни. Очевидно това означава повишаване на производителността в нашето приложение. В допълнение към това, алгоритъмът Hi / Lo е предпочитан избор в среди със слаба интернет връзка .

От друга страна, алгоритъмът Hi / Lo не е най-добрият избор в среди, където множество различни клиенти поддържат данни в една и съща таблица в база данни . Приложенията на трети страни може да не знаят за стратегията Hi / Lo, която използваме за генериране на идентификатори. В резултат на това те могат да използват идентификатори на обекти от генерирания диапазон от числа, използвани в момента в нашето приложение. В този случай, при продължаващи данни, може да срещнем грешки, които е трудно да се поправят.

5. Заключение

В този урок обсъдихме алгоритъма Hi / Lo.

Първо обяснихме как работи и обсъдихме изпълнението на псевдокода. След това показахме практически пример с използване на алгоритъма на Hibernate. И накрая, изброихме предимствата и недостатъците на Hi / Lo.

Както винаги, кодът, показан в тази статия, е достъпен в GitHub.