Что такое алгоритм Hi / Lo? - PullRequest
447 голосов
/ 11 ноября 2008

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

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

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

Ответы [ 5 ]

509 голосов
/ 11 ноября 2008

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

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

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

147 голосов
/ 12 ноября 2008

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

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

24 голосов
/ 23 июня 2014

Алгоритмы 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» и цикл продолжается

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

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

enter image description here

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

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

20 голосов
/ 26 августа 2013

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

Привет-ло использование имеет тенденцию тратить большое количество ключей при перезапуске сервера и генерировать большие значения, недружественные для человека.

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

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

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

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

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

При размере фрагмента всего 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

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

Дизайн Hi-Lo возник на ранних этапах OO-картографирования и постоянства. В наши дни структуры персистентности, такие как Hibernate, предлагают более простые и лучшие средства выделения по умолчанию.

1 голос
/ 23 сентября 2016

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

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

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

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

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

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

...