提问



什么是Hi/Lo算法?


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


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

最佳参考


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


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


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

其它参考1


除了Jon的回答:


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

其它参考2


比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,比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


我实际上是在90年代与Ambler先生通信,向他推荐这个改进的方案,但他太过坚持和顽固地承认使用线性数字线的优点和简单明了。


在设计方面,他的解决方案在数字线(复合键,大型hi_word产品)上基本上比Linear_Chunk更复杂,同时没有实现相对的好处。因此,他的设计在数学上被证明是有缺陷的。

其它参考3


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值并继续循环



您可以在本文中找到更详细的解释:[8]


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


[9]


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


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

其它参考4


根据我的经验,我发现Hi/Lo算法非常适合具有复制方案的多个数据库。想象一下。你有一个服务器在纽约(别名01)和另一台服务器在洛杉矶(别名02)然后你有一个PERSON表......
所以在纽约,当一个人被创造时...你总是使用01作为HI值而LO值是下一个secuential。例子。



  • 010000010 Jason

  • 010000011 David

  • 010000012 Theo



在洛杉矶,你总是使用HI 02.例如:



  • 020000045鲁珀特

  • 020000046 Oswald

  • 020000047 Mario



因此,当您使用数据库复制(无论什么品牌)时,所有主键和数据都可以轻松自然地组合,而无需担心重复的主键,冲突等。


这是此方案中的最佳方式。