«1. Введение

В этом уроке мы объясним алгоритм Hi/Lo. Он используется в основном как стратегия генерации идентификатора базы данных.

Начнем с обзора алгоритма. Затем мы покажем практический пример, основанный на фреймворке Hibernate. Наконец, мы обсудим варианты использования алгоритма, его преимущества и недостатки.

2. Обзор алгоритма Hi/Lo

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

Основной целью алгоритма Hi/Lo является создание диапазона чисел, которые можно безопасно использовать в качестве идентификаторов базы данных. Для этого он использует три числовые переменные, обычно называемые high, low и incrementSize.

Переменная incrementSize содержит максимальное количество идентификаторов, которое может быть сгенерировано в одном пакете. Его следует рассматривать как постоянное значение, определенное в начале алгоритма. Любая модификация среды выполнения может вызвать серьезные проблемы в средах, где несколько клиентов используют одну и ту же конфигурацию Hi/Lo для сохранения записей.

Переменная high обычно назначается из последовательности базы данных. В этом случае мы уверены, что никто не получит одно и то же число дважды.

Нижняя переменная содержит текущий назначенный номер в диапазоне [0, incrementSize).

Учитывая эти точки, алгоритм Hi/Lo генерирует значения в диапазоне [(hi – 1) * incrementSize + 1, (hi * incrementSize)).

2.2 Псевдокод

Давайте рассмотрим шаги для генерации нового значения с помощью алгоритма Hi/Lo:

    если low больше или равен incrementSize, присвоить новое значение high и сбросить low на 0 сгенерировать новое значение по формуле: (high — 1) * incrementSize + low увеличить low на 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;
}

Это простой заказ в ресторане с одним полем id. Чтобы правильно определить алгоритм Hi/Lo в Hibernate, в определении поля id мы должны выбрать стратегию последовательности — оптимизатор hilo — и указать параметр 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 запрашивает значение следующего идентификатора, значение переменной low равно константе 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.