Hi/Lo算法是什么?

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

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


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

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

能够在客户端设置主键非常有用(特别是对于orm),而不是插入没有主键的值,然后将它们取回到客户端。除此之外,这意味着您可以轻松地建立父/子关系,并在进行任何插入之前将键都准备好,这使得批处理更简单。

除了Jon的回答:

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

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

这避免了使用复合键(这从来都不是一个好主意),并避免在服务器重新启动时浪费整个low -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

在设计方面,他的解决方案在数字线上(复合键,大型hi_word产品)比Linear_Chunk更复杂,但没有获得相应的好处。

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

hi/lo算法将序列域划分为hi组。hi值是同步分配的。每个hi组都有一个最大的lo条目数,可以离线分配,而不用担心并发的重复条目。

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提供了池-lo优化器,它提供了hi/lo生成器策略的优点,同时还提供了与其他不知道此序列分配策略的第三方客户机的互操作性。

由于池-lo优化器既高效又可与其他系统互操作,因此它比传统的hi/lo标识符策略更好。

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

010000010杰森 010000011大卫 010000012西奥

在洛杉矶你总是用HI - 02。例如:

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

因此,当您使用数据库复制(无论什么品牌)时,所有主键和数据都可以轻松自然地组合在一起,而不必担心重复的主键、碰撞等问题。

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