488

什么是 Hi/Lo 算法？

我在NHibernate文档中找到了这一点（这是生成唯一密钥的一种方法，第 5.1.4.2 节），但我还没有找到关于它如何工作的很好的解释。

我知道 Nhibernate 处理它，我不需要知道里面，但我只是好奇。

4

5 回答 5

575

基本思想是你有两个数字来组成一个主键——一个“高”数字和一个“低”数字。客户端基本上可以增加“高”序列，知道它可以安全地从前一个“高”值的整个范围内生成具有各种“低”值的键。

例如，假设您有一个当前值为 35 的“高”序列，而“低”数字在 0-1023 范围内。然后客户端可以将序列增加到 36（以便其他客户端能够在使用 35 时生成密钥）并知道密钥 35/0、35/1、35/2、35/3... 35/1023 是全部可用。

能够在客户端设置主键，而不是在没有主键的情况下插入值然后将它们取回客户端，这可能非常有用（尤其是使用 ORM）。除此之外，这意味着您可以轻松地建立父/子关系并在执行任何插入之前将键全部到位，这使得它们的批处理更简单。

于 2008-11-11T20:57:35.020 回答
166

除了乔恩的回答：

它用于能够断开连接工作。然后，客户端可以向服务器请求一个 hi 号码并创建增加 lo 号码本身的对象。在 lo 范围用完之前，它不需要联系服务器。

于 2008-11-11T22:08:43.860 回答
41

该hi/lo算法将序列域分成hi组。一个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 生成器策略的优势，同时还提供了与其他不了解此序列分配策略的 3rd 方客户端的互操作性。

pooled-lo 优化器既高效又可与其他系统互操作，是比传统的 hi/lo 标识符策略更好的候选者。

于 2014-06-23T14:27:11.250 回答
27

Lo 是一个缓存分配器，它将键空间分成大块，通常基于一些机器字大小，而不是人类可能明智地选择的有意义大小的范围（例如，一次获得 200 个键）。

Hi-Lo 的使用往往会在服务器重启时浪费大量的密钥，并生成大量对人类不友好的密钥值。

比 Hi-Lo 分配器更好的是“线性块”分配器。这使用了类似的基于表的原则，但分配了小的、大小方便的块并生成了对人类友好的值。

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，比从 Oracle 序列分配快 10 倍，并且在所有数据库中 100% 可移植。分配性能相当于hi-lo。

与 Ambler 的想法不同，它将键空间视为连续的线性数字线。

这避免了复合键的推动（这从来都不是一个好主意），并避免在服务器重新启动时浪费整个低字。它生成“友好的”、人性化的关键值。

相比之下，Ambler 先生的想法是分配高 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 之类的持久性框架提供了更简单、更好的分配器作为默认设置。

于 2013-08-26T09:29:34.877 回答
1

根据我的经验，我发现 Hi/Lo 算法非常适合具有复制场景的多个数据库。想象一下。您在纽约有一台服务器（别名 01），在洛杉矶有另一台服务器（别名 02），然后您有一个 PERSON 表......所以在纽约创建一个人时......您总是使用 01 作为 HI 值LO 值是下一个连续的。例如。

  • 010000010 杰森
  • 010000011 大卫
  • 010000012 西奥

在洛杉矶，您总是使用 HI 02。例如：

  • 020000045 鲁珀特
  • 020000046 奥斯瓦尔德
  • 020000047 马里奥

因此，当您使用数据库复制（无论是什么品牌）时，所有主键和数据都可以轻松自然地组合在一起，而无需担心重复主键、冲突等。

这是在这种情况下最好的方法。

于 2016-09-23T17:08:32.163 回答