Что такое алгоритм Hi/Lo?

1. Введение

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

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

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

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

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

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

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

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

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

2.2. Псевдокод

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

• если low больше или равен incrementSize , присвоить новое значение high и сбросить low до 0
• сгенерировать новое значение по формуле: ( high - 1) * incrementSize + 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] назначаются объектам.

Журналы Hibernate, захваченные во время выполнения метода 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 .