什么是 Hi/Lo 算法？

Question

什么是 Hi/Lo 算法？

databasealgorithmprimary-keyidentifierhilo

505

什么是Hi/Lo算法？

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

我知道NHibernate处理它，我不需要知道内部细节，但我只是很好奇。

- DiegoCofre

“合作式ID生成”这个名字比“Hi/Lo”好多了。 - Георги Кременлиев

5个回答

173

除了Jon的答案之外：

它被用于能够脱机工作。客户端可以向服务器请求一个高号码，并自己增加对象创建低号码。在低号范围用尽之前，不需要联系服务器。

- Stephan Eggermont

5

我更喜欢这个版本因为它更加简洁。 - Developer Marius Žilėnas

42

“hi/lo”算法将序列域分成了“hi”组。同步地分配了一个“hi”值。每个“hi”组都被赋予了最大数量的“lo”条目，可以离线分配，而不必担心并发重复条目。请保留HTML标签。

The hi token is assigned by the database, and two concurrent calls are guaranteed to see unique consecutive values
Once a hi token is retrieved we only need the incrementSize (the number of lo entries)
The identifiers range is given by the following formula:
```
 [(hi -1) * incrementSize) + 1, (hi * incrementSize) + 1)
```
and the “lo” value will be in the range:
```
 [0, incrementSize)
```
being applied from the start value of:
```
 [(hi -1) * incrementSize) + 1)
```
When all lo values are used, a new hi value is fetched and the cycle continues

同时，这种视觉呈现方式也非常易于理解：

虽然 hi/lo 优化器对于优化标识符生成来说很好，但是它与其他向数据库插入行的系统不兼容，而这些系统并不知道我们的标识符策略。

Hibernate 提供了 pooled-lo 优化器，它提供了 hi/lo 生成器策略的优点，同时也提供了与其他第三方客户端的互操作性，这些客户端并不知道这个序列分配策略。

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

- Vlad Mihalcea

有时候我真的不太理解你，哈哈哈。虽然 hi/lo 优化器对于优化标识符生成很好，但它与其他系统不兼容（你所说的其他系统是什么？哪些是首要的？），这些系统在向数据库中插入行时没有了解我们的标识符策略。（生成标识符不也用于插入行吗？） - Adelin

2

其他系统，比如一位DBA试图运行一个INSERT语句。如果她读取当前的序列数据，您认为在知道我们在这个特定的数据库表中使用hilo的情况下，找出下一个标识符值容易吗？ - Vlad Mihalcea

非常抱歉，如果我的评论不适合您的答案，但我想知道默认使用哪个优化器？还是这取决于数据库（我正在使用PostgreSQL）？因为我无法找出当前序列值和生成的ID之间的关系。我正在使用

@GeneratedValue(strategy = GenerationType.SEQUENCE, generator = "name") @SequenceGenerator(name="name", sequenceName = "name_seq", allocationSize=100)

来生成我的ID。 - Stefan Golubović

1

@VladMihalcea，我相信你在第三个项目符号中有一个错别字，即第一段代码片段中的, (hi * incrementSize) + 1)... 它应该是, hi * incrementSize)，对吗？ - Huiagan

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的想法不同，它将键空间视为连续的线性数字线。

这避免了复合键的冲动（这从未是一个好主意），并在服务器重新启动时避免浪费整个lo-words。它生成“友好”的、人类规模的关键值。

相比之下，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

在设计方面，他的解决方案在数轴上基本上比Linear_Chunk复杂得多（包括复合键、大型hi_word乘积），同时却没有获得任何比较优势。

Hi-Lo设计早在OO映射和持久化中就出现了。如今，像Hibernate这样的持久化框架提供更简单、更好的分配器作为默认值。

- Thomas W

1

安布勒先生是谁？ - Apocatastasis

2

我同意大多数应用程序在简单方法和 Hi-Lo 方法之间没有任何优势；然而，我认为 Hi-Lo 更适合于高度并发应用程序中的多个分配器的特殊情况。 - richj

2

感谢@richj！我的观点是，您可以使用多个分配器或大块大小进行“线性块分配”，但与Hi/Lo不同的是，它维护了分配器NEXT_VAL对表中键的线性对应关系，并且可调整。与HiLo不同，不需要乘法-这不是必要的！NEXT_HI的乘法器和存储使得HiLo更加复杂并破坏了可调性，因为更改块大小将任意更改发行的下一个密钥。请参见：http://literatejava.com/hibernate/linear-block-allocator-a-superior-alternative-to-hilo/ - Thomas W

3

我对多个独立的分配器很感兴趣。使用Hi-Lo方法，很明显高位值可以被分割成分配器ID/块ID。对于Linear Chunk，这种方法不是很明显（对我而言），但本质上它与在分配器之间划分总范围的问题相同。现在我明白了。谢谢。 - richj

2

哦，经过思考，我认为SEQ列映射到表名。例如，有一个分配器用于Customers表，一个用于Orders表，等等。请原谅我，有时候我比较慢。 - Rock Anthony Johnson

显示剩余2条评论

2

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

010000010 Jason
010000011 David
010000012 Theo

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

020000045 Rupert
020000046 Oswald
020000047 Mario

因此，当使用数据库复制（无论品牌如何）时，所有主键和数据都可以轻松自然地组合，而不必担心重复的主键、冲突等问题。

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

- Theo

1

它在Hibernate中不起作用。HiLo算法在每个事务中获得一个新的序列值，因此HI计数器相应地增加。但是在您的示例中，对于一个DB，HI计数器始终保持不变。 - Dmitry1405

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Jon Skeet · Accepted Answer

基本思想是您有两个数字来组成一个主键——一个"高"数字和一个"低"数字。客户端可以基本上递增"高"序列，知道它可以安全地从之前的"高"值范围内使用各种"低"值生成密钥。

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

这可能非常有用（特别是与ORM一起使用），即能够在客户端设置主键，而不是插入没有主键的值，然后将其取回到客户端。除此之外，它意味着您可以轻松地创建父/子关系，并在进行任何插入之前就将密钥全部放置好，使批处理变得更加简单。