什么是Hi/Lo算法？

什么是Hi/Lo算法？

我在NHibernate文档中找到了这个(它是生成唯一键的一种方法,第5.1.4.2节),但我没有找到它如何工作的很好的解释.

我知道Nhibernate处理它,我不需要知道内部,但我只是好奇.

1> Jon Skeet..：

---

基本思想是你有两个数字来组成一个主键 - 一个"高"数字和一个"低"数字.客户端基本上可以递增"高"序列,因为它知道它可以安全地从具有各种"低"值的先前"高"值的整个范围生成密钥.

例如,假设您有一个当前值为35的"高"序列,而"低"号则在0-1023范围内.然后客户端可以将序列递增到36(对于其他客户端,当它使用35时能够生成密钥)并且知道密钥35/0,35/1,35/2,35/3 ... 35/1023是全部可用.

能够在客户端设置主键,而不是插入没有主键的值,然后将它们提取回客户端,这可能非常有用(特别是使用ORM).除了其他任何东西,它意味着您可以轻松地建立父/子关系,并在执行任何插入之前将所有键都放在适当的位置,这使得批处理更简单.

---

就像IP地址那样 - ICANN为您提供了一个高"网络"号码,然后您可以在您给出的CIDR范围内获得尽可能多的低"主机"号码.

---

您是说在客户端内协调"低范围",而"高序列"对应于DB序列？

---

是否通常将hi&lo值组合成单个整数值,或者作为两部分业务键？

---

@Adam:从根本上说,没什么 - 增加一个值("高"部分)比生成一堆密钥要便宜得多.(在数据传输方面它可能*便宜得多* - 你可以用最少的带宽"保留"大量的密钥.)

---

@Adam:如果键只是数字,那就是真的.对GUID来说并非如此:)但是,在简单数字的情况下,任何原子"固定数量的增量"都可以.这实际上是hi-lo正在做的事情,如果你认为它是一个分为两个部分的数字.

---

是的,基本上就是这样.

---

@HanuAthena当Hi等于35时,意味着35是第一个未被占用的序列.35以下的所有序列已被其他客户使用.通过递增Hi值,客户端将35保留为self并通知其他客户端36成为第一个未占用的序列.

2> Stephan Egge..：

---

除了Jon的回答:

它用于能够断开连接.然后,客户端可以向服务器请求hi数字并创建增加lo数量的对象.在lo范围用完之前,它不需要联系服务器.

3> Vlad Mihalce..：

---

hi/lo算法将序列域分成"hi"组.同步分配"hi"值.每个"hi"组都被赋予最大数量的"lo"条目,可以通过离线分配而不必担心并发重复条目.

"hi"令牌由数据库分配,并且两个并发调用保证看到唯一的连续值

一旦检索到"hi"令牌,我们只需要"incrementSize"("lo"条目的数量)

标识符范围由以下公式给出:

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

并且"lo"值将在以下范围内:

[0, incrementSize)

从起始值应用:

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

当使用所有"lo"值时,获取新的"hi"值并继续循环

您可以在本文中找到更详细的说明:

这种视觉呈现也很容易理解:

虽然hi/lo优化器适用于优化标识符生成,但它不能很好地与其他系统在我们的数据库中插入行,而不了解我们的标识符策略.

Hibernate提供了pooled-lo优化器,它将hi/lo生成器策略与互操作性序列分配机制相结合.该优化器既高效又可与其他系统互操作,是比以前的传统hi/lo标识符策略更好的候选者.

4> Thomas W..：

---

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位,并在hi-words增量时产生大的人类不友好的键值.

分配键的比较:

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等持久性框架提供了更简单,更好的分配器作为默认设置.

---

好帖子,但你没有回答这个问题.

---

我对多个独立分配器感兴趣.使用Hi-Lo,很明显可以将高值分区为分配器ID /块ID.(对我来说)同样的方法可以应用于Linear Chunk并不是很明显,但它基本上是划分分配器之间的总范围的相同问题.我现在知道了.谢谢.