问答中心分类: DATABASE什么是 Hi/Lo 算法?
0
匿名用户 提问 3天 前

什么是 Hi/Lo 算法?
我在休眠文档(这是生成唯一键的一种方法,第 5.1.4.2 节),但我还没有找到一个很好的解释它是如何工作的。
我知道 Nhibernate 处理它,我不需要知道里面,但我只是好奇。

4 Answers
0
Stephan Eggermont 回答 3天 前

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

Developer Marius Žilėnas 回复 3天 前

为了简洁起见,我更喜欢这个。

0
Vlad Mihalcea 回答 3天 前

hi/lo算法将序列域拆分为hi团体。一个hi值是同步分配的。每一个hi组被赋予最大数量lo条目,可以离线分配,而不必担心并发重复条目。

  1. hitoken由数据库分配,保证两个并发调用看到唯一的连续值
  2. 一旦hi检索令牌我们只需要incrementSize(的数量lo条目)
  3. 标识符范围由以下公式给出:
    [(hi -1) * incrementSize) + 1, (hi * incrementSize) + 1)

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

    [0, incrementSize)

    从以下起始值开始应用:

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

这种视觉呈现也很容易理解:
在此处输入图像描述
尽管hi/lo优化器可以很好地优化标识符生成,它不能很好地与其他系统将行插入到我们的数据库中,而对我们的标识符策略一无所知。
Hibernate 提供了pooled-lo优化器,它提供了高/低生成器策略的优势,同时还提供了与其他不了解此序列分配策略的第 3 方客户端的互操作性。
pooled-lo 优化器既高效又可与其他系统互操作,是比传统的 hi/lo 标识符策略更好的候选者。

Adelin 回复 3天 前

我有时真的不明白你哈哈哈所以:虽然 hi/lo 优化器可以很好地优化标识符生成(好的,很好),但它不能很好地与其他系统配合使用(你所说的其他系统是什么意思?,这是第一个那些?)在我们的数据库中插入行(标识符生成不是也用于插入行吗?),而对我们的标识符策略一无所知。

Vlad Mihalcea 回复 3天 前

其他系统,例如尝试运行 INSERT 语句的 DBA。如果她读取当前的序列数据,你认为知道我们在这个特定的数据库表中使用 hilo 很容易找出下一个标识符值吗?

Stefan Golubović 回复 3天 前

如果评论不适合您的答案,我深表歉意,但我想知道默认使用什么优化器?还是它依赖于数据库(我使用的是 PostgreSQL)?因为我无法弄清楚当前序列值和生成的 ID 之间的关系。我在用着@GeneratedValue(strategy = GenerationType.SEQUENCE, generator = "name") @SequenceGenerator(name="name", sequenceName = "name_seq", allocationSize=100)我的身份证。

Huiagan 回复 3天 前

@VladMihalcea,我相信你在第三个项目符号中有错字,第一个片段在, (hi * incrementSize) + 1)… 它应该是, hi * incrementSize), 正确的?

0
Thomas W 回答 3天 前

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 的想法不同,它将键空间视为连续的线性数字线。
这避免了复合键的推动(这从来都不是一个好主意),并避免在服务器重新启动时浪费整个低字。它生成“友好的”、人性化的关键值。
相比之下,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 之类的持久性框架提供了更简单、更好的分配器作为默认设置。

Apocatastasis 回复 3天 前

安布勒先生是谁?

Thomas W 回复 3天 前

Scott Ambler 提倡使用 16 位或 32 位字的所谓“hi-lo”分配策略。这是他的页面:ambysoft.com/scottAmbler.html

richj 回复 3天 前

+1 有趣的答案。我同意绝大多数应用程序都没有从 Hi-Lo 获得比更简单方法的优势。但是我认为 Hi-Lo 更适合高并发应用程序中多个分配器的特殊情况。

Thomas W 回复 3天 前

谢谢@richj!我的观点是,您可以使用多个分配器或大块大小与“线性块分配”,但是 – 与 Hi/Lo 不同 – 它维护一个线性的分配器 NEXT_VAL 与表中的键的对应关系,并且是可调整的。与 HiLo 不同,它不需要乘法——只是没有必要! NEXT_HI 的乘数和存储使 HiLo 更加复杂并破坏了可调整性,因为更改块大小将任意更改要发出的下一个密钥。请参阅:literatejava.com/hibernate/…

richj 回复 3天 前

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

Rock Anthony Johnson 回复 3天 前

表 KEY_ALLOC 的 SEQ 列的用途是什么?它是如何使用的?

Rock Anthony Johnson 回复 3天 前

哦,想来想去,我觉得SEQ列映射到一个表名。例如,Customers 表有一个分配器,Orders 表有一个分配器,以此类推。原谅我,有时候我很慢。

0
Theo 回答 3天 前

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

  • 010000010 杰森
  • 010000011 大卫
  • 010000012 西奥

在洛杉矶,您总是使用 HI 02。例如:

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

因此,当您使用数据库复制(无论是什么品牌)时,所有主键和数据都可以轻松自然地组合在一起,而无需担心重复主键、冲突等。
这是在这种情况下最好的方法。

Dmitry1405 回复 3天 前

它在 Hibernate 中不起作用。 HiLo algrotirm 在每个事务中获取一个新的序列值,因此 HI 计数器相应地递增。但在您的示例中,HI-counter 对于一个 DB 始终是恒定的。