Алгоритм Hi/Lo

Hi/Lo — это алгоритм и стратегия генерации ключей, используемые для генерации уникальных ключей для использования в базе данных в качестве первичного ключа . Для генерации значений он использует шаблон «высокий-низкий» на основе последовательности. Hi/Lo используется в сценариях, где приложению необходимо, чтобы его объекты имели идентификатор перед сохранением. Это стратегия создания ценности. Альтернативой Hi/Lo может быть создание приложением ключей в виде универсально уникальных идентификаторов (UUID).

Объяснение

Предварительные условия:

• Существует константа, определенная для хранения максимально низкого значения . Значение должно быть больше нуля. Подходящим значением может быть 1000 или 32767 .
• Существует переменная, определенная для хранения текущего назначенного высокого значения , и ей присвоено значение 0 (ноль).
• Существует переменная, определенная для хранения текущего присвоенного нижнего значения , и ей присваивается значение максимального нижнего значения плюс 1 (единица).

Шаги:

1. Если текущее назначенное нижнее значение больше или равно максимальному нижнему значению , вызовите функцию для получения нового верхнего значения и сброса текущего назначенного нижнего значения на 0 (ноль).
2. Назначьте ключ, умножив назначенное в данный момент высокое значение на максимальное нижнее значение и добавив назначенное в данный момент нижнее значение .
3. Увеличить текущее присвоенное нижнее значение на 1 (один).

Базе данных нужна таблица со столбцом для имени таблицы и столбцом с высоким значением.

Алгоритм

Переменные current_lo ( (целое) и current_hi целое) являются внутренними переменными состояния. Внутреннее состояние сохраняется при вызовах. Константа max_lo ( целое число) — это опция конфигурации. get_next_hi — это функция, которая получает новое высокое значение с сервера базы данных. В системе управления реляционными базами данных это может осуществляться с помощью хранимой процедуры .

Предварительное условие: для параметра max_lo должно быть установлено значение больше нуля.

algorithm generate_key is
    output: key as a positive integer

    if current_lo ≥ max_lo then
        current_hi := get_next_hi()
        current_lo := 0

    key := current_hi × max_lo + current_lo
    current_lo := current_lo + 1

    return key

Пример

Пример реализации на Python .

class HiloKeyGenerator:
    """Key generator that uses a Hi/Lo algorithm.

    Args:
      get_next_hi: A callable function that retrieves a new high value.
      max_lo: The maximum low value. Defaults to 1000.

    Raises:
      ValueError: If the value of max_lo is not greater than zero.
    """

    def __init__(self, get_next_hi: Callable[[], int], max_lo: int = 1000) -> None:
        if max_lo <= 0:
            raise ValueError("max_lo must be greater than zero.")
        self._current_hi = 0
        self._current_lo = max_lo + 1
        self._get_next_hi = get_next_hi
        self._max_lo = max_lo

    def generate_key(self) -> int:
        """Generate a new unique key."""
        if self._current_lo >= self._max_lo:
            self._current_hi = self._get_next_hi()
            self._current_lo = 0

        key = self._current_hi * self._max_lo + self._current_lo
        self._current_lo += 1

        return key

Выход:

>>> def get_next_hi():
...     return 2  # From database server.
...
>>> generator = HiloKeyGenerator(get_next_hi)
>>> generator.generate_key()
2000
>>> generator.generate_key()
2001
>>> generator.generate_key()
2002

Книги

Очень кратко упоминается в книге «Сохраняемость Java для реляционных баз данных» 2003 года на странице 236. Ричарда Сперко

Очень кратко упоминается в книге Лучше, быстрее, легче Java» 2004 года на странице 137. Брюса Тейта и Джастина Гехтланда «

Очень кратко упоминается в книге Разработка корпоративных Java с ограниченным бюджетом: использование открытого исходного кода Java» 2004 года на странице 386. Брайана Сэма-Боддена и Кристофера М. Джада «

Объясняется в книге «Изучение NHibernate 4» 2015 года на страницах 53 и 144–145. Сухаса Чатекара

Упоминается в книге рецептов NHibernate 4.x 2017 года на странице 35.

Упоминается в книге ASP.NET Core 2 Fundamentals 2018 года на странице 219.

Эта реализация использует алгоритм hi/lo для генерации идентификаторов. Алгоритм использует высокое значение, полученное из базы данных, и объединяет его с диапазоном низких значений для создания уникального идентификатора. Высокое значение из столбца next_id стола hibernate_unique_key по умолчанию. Но вы можете переопределить это, чтобы использовать другую таблицу. Этот алгоритм также поддерживает указание where параметр, который можно использовать для получения высокого значения для разных объектов из разных строк таблицы. hibernate_unique_key стол.

— Сухас Чатекар, Изучение NHibernate 4 (31 июля 2015 г.)

Для работы hilo нужен набор из двух чисел. Один из них — hi , который берется из таблицы базы данных, а другой — lo , который рассчитывается NHibernate. NHibernate объединяет эти два числа с использованием формулы для создания уникального числа, которое можно использовать в качестве идентификатора.

— Сухас Чатекар, Изучение NHibernate 4 (31 июля 2015 г.)

Хотя автоматически увеличиваемые идентификаторы проще, всякий раз, когда вы добавляете объект в контекст, это добавление приводит к принудительной вставке объекта в базу данных. Это связано с тем, что мы можем получить идентификатор только в том случае, если фактическая вставка происходит в случае автоматического увеличения идентификаторов. Алгоритм HiLo освобождает нас от этого ограничения, заранее резервируя идентификаторы с использованием последовательности базы данных.

— Онур Гумус и Мугилан Т.С. Рагупати, Основы ASP.NET Core 2 (30 августа 2018 г.)

Поддерживать

Поддерживается Entity Framework Core (ORM для .NET Core) с Microsoft SQL Server с использованием UseHiLo метод расширения. Не поддерживается предшественником Entity Framework .

Поддерживается Hibernate (ORM для Java) и NHibernate (ORM для .NET) через SequenceHiLoGenerator и TableHiLoGenerator. Поддержка как минимум с 2002 года. Поддержка как минимум с версии 3.2 с кодом, автором которого является Гэвин Кинг.

Поддерживается Доктриной (ORM для PHP) через TableGenerator сорт.

При поддержке Мартена (библиотека персистентности для .NET) с PostgreSQL через HiLoSequence сорт.

При поддержке RavenDB (база данных документов NoSQL).

Не поддерживается Apache Cayenne , ServiceStack.OrmLite, Ruby on Rails Active Record, Dapper и Dashing.

См. также

• Распределенная транзакция
• Доменно-ориентированное проектирование (DDD)
• Первичный ключ

Внешние ссылки

• Что такое алгоритм Hi/Lo? - Переполнение стека
• Алгоритм hi/lo - Влад Михалча