Hi/Lo算法是什么?

Hi/Lo算法是什么?

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

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

104824 次浏览

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

例如,假设您有一个电流值为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个key &可以根据需要分发。

该方案的块大小只有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项,可以离线分配,而不用担心并发重复项。

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

  2. 一旦hi令牌被检索到,我们只需要incrementSize (lo项的数量)

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

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

    而“lo”值将在以下范围内:

     [0, incrementSize)
    

    从的起始值开始应用:

     [(hi -1) * incrementSize) + 1)
    
  4. 当所有的lo值都被使用时,一个新的hi值被获取,循环继续

这个视觉展示也很容易理解:

enter image description here

虽然hi/lo优化器用于优化标识符生成,但它不适用于其他系统在不了解标识符策略的情况下向我们的数据库插入行。

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

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

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

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

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

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

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