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

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

Я нашел это в документации NHibernate (это один из способов генерирования уникальных ключей, раздел 5.1.4.2), но я не нашел хорошего объяснения того, как это работает.

Я знаю, что Nhibernate справляется с этим, и мне не нужно знать изнутри, но мне просто любопытно.

5 ответов

Решение

Основная идея заключается в том, что у вас есть два числа для составления первичного ключа - "высокое" число и "низкое" число. Клиент может в основном увеличивать последовательность "high", зная, что затем он может безопасно генерировать ключи из всего диапазона предыдущего "high" значения с помощью множества "low" значений.

Например, предположим, что у вас есть "высокая" последовательность с текущим значением 35, а "низкое" число находится в диапазоне 0-1023. Затем клиент может увеличить последовательность до 36 (чтобы другие клиенты могли генерировать ключи при использовании 35) и знать, что ключи 35/0, 35/1, 35/2, 35/3... 35/1023 все доступно.

Может быть очень полезно (особенно с ORM) иметь возможность устанавливать первичные ключи на стороне клиента, вместо того, чтобы вставлять значения без первичных ключей и затем возвращать их обратно на клиент. Помимо всего прочего, это означает, что вы можете легко установить родительские и дочерние отношения и иметь все ключи на месте, прежде чем делать какие-либо вставки, что упрощает их пакетирование.

В дополнение к ответу Джона:

Он используется, чтобы иметь возможность работать автономно. Затем клиент может запросить у сервера число hi и создать объекты, увеличивающие число lo. Нет необходимости связываться с сервером, пока не будет исчерпан диапазон lo.

Алгоритмы hi/lo разбивают область последовательностей на группы "hi". "Привет" значение назначается синхронно. Каждой группе "hi" дается максимальное количество записей "lo", которые могут быть назначены в автономном режиме, не беспокоясь о параллельных повторяющихся записях.

  1. Токен "hi" назначается базой данных, и два одновременных вызова гарантированно видят уникальные последовательные значения
  2. После получения токена "hi" нам нужен только "incrementSize" (количество записей "lo")
  3. Диапазон идентификаторов задается следующей формулой:

    [(hi -1) * incrementSize) + 1, (hi * incrementSize) + 1)
    

    и значение "lo" будет в диапазоне:

    [0, incrementSize)
    

    применяется от начального значения:

    [(hi -1) * incrementSize) + 1)
    
  4. Когда используются все значения "lo", выбирается новое значение "hi" и цикл продолжается

Вы можете найти более подробное объяснение в этой статье:

И за этой визуальной презентацией также легко следить:

Хотя hi/lo оптимизатор хорош для оптимизации генерации идентификаторов, он не очень хорошо работает с другими системами, вставляющими строки в нашу базу данных, ничего не зная о нашей стратегии идентификаторов.

Hibernate предлагает оптимизатор pooled-lo, который сочетает в себе стратегию генератора hi/lo с механизмом распределения последовательностей взаимодействия. Этот оптимизатор эффективен и совместим с другими системами, являясь лучшим кандидатом, чем предыдущая стратегия идентификаторов hi/lo.

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

create table KEY_ALLOC (
    SEQ varchar(32) not null,
    NEXT bigint not null,
    primary key (SEQ)
);

Чтобы выделить следующие, скажем, 20 ключей (которые затем хранятся в качестве диапазона на сервере и используются по мере необходимости):

select NEXT from KEY_ALLOC where SEQ=?;
update KEY_ALLOC set NEXT=(old value+20) where SEQ=? and NEXT=(old value);

При условии, что вы можете совершить эту транзакцию (используйте повторные попытки для обработки конфликта), вы выделили 20 ключей и можете распределять их по мере необходимости.

При размере фрагмента всего 20 эта схема в 10 раз быстрее, чем выделение из последовательности Oracle, и на 100% переносима среди всех баз данных. Выделение производительности эквивалентно привет-ло.

В отличие от идеи Амблера, он рассматривает пространство клавиш как непрерывную линейную числовую линию.

Это позволяет избежать стимула для составных ключей (что никогда не было хорошей идеей) и позволяет не тратить целые слова при перезапуске сервера. Он генерирует "дружественные", ключевые человеческие ценности.

Идея г-на Амблера, для сравнения, выделяет старшие 16- или 32-битные значения и генерирует большие значения, недружелюбные к человеку, в качестве приращения высоких слов.

Сравнение выделенных ключей:

Linear_Chunk       Hi_Lo
100                65536
101                65537
102                65538
.. server restart
120                131072
121                131073
122                131073
.. server restart
140                196608

Я фактически переписывался с мистером Амблером еще в 90-х, чтобы предложить ему эту улучшенную схему, но он был слишком застрял и упрям, чтобы признать преимущества и очевидную простоту использования линейной числовой линии.

Что касается дизайна, его решение существенно сложнее в отношении числовых линий (составные ключи, большие продукты hi_word), чем Linear_Chunk, но при этом не дает сравнительного преимущества. Его конструкция, таким образом, математически доказана несовершенной.

Я обнаружил, что алгоритм Hi/Lo идеально подходит для нескольких баз данных со сценариями репликации, основанными на моем опыте. Представь себе это. у вас есть сервер в Нью-Йорке (псевдоним 01) и другой сервер в Лос-Анджелесе (псевдоним 02), тогда у вас есть таблица PERSON... так что в Нью-Йорке, когда человек создает... вы всегда используете 01 в качестве значения HI и значение LO является следующей последовательной. Пример.

  • 010000010 Джейсон
  • 010000011 Дэвид
  • 010000012 Тео

в Лос-Анджелесе вы всегда используете HI 02. например:

  • 020000045 Руперт
  • 020000046 Освальд
  • 020000047 Марио

Таким образом, при использовании репликации базы данных (независимо от марки) все первичные ключи и данные легко и естественно объединяются, не беспокоясь о дублировании первичных ключей, коллизиях и т. Д.

Это лучший способ пойти по этому сценарию.

Другие вопросы по тегам