8

如果我开始使用 HiLo 生成器为表分配 ID，然后决定增加或减少容量（即最大 'lo' 值），这会导致与已经分配的 ID 发生冲突吗？

我只是想知道我是否需要在数字周围加上一个大红旗，说“永远不要改变这个！”

注意 - 不是 NHibernate 特定的，我只是对 HiLo 算法感到好奇。

4

5 回答 5

20

HiLo 算法通常基本上将两个整数映射到一个整数 ID。它保证这对数字在每个数据库中都是唯一的。通常，下一步是保证一对唯一的数字映射到唯一的整数 ID。

在这个先前的 SO 答案中给出了一个很好的解释 HiLo 在概念上是如何工作的

更改 max_lo 将保留您的一对数字将是唯一的属性。但是，它会确保映射的 ID 是唯一且无冲突的吗？

我们来看看 Hibernate 对 HiLo 的实现。他们似乎使用的算法（从我收集的内容来看）是：（我可能会在技术上偏离）

h = high sequence (starting at 0)
l_size = size of low block
l = low sequence (starting at 1)

ID = h*l_size + l

因此，如果您的低块是 100，那么您保留的 ID 块将变为 1-100、101-200、201-300、301-400...

您的 High 序列现在是 3。如果您突然将 l_size 更改为 10，会发生什么情况？你的下一个区块，你的高点增加，你会得到4*10+1 = 41

哎呀。这个新值肯定属于1-100. 具有高序列 0 的人会想，“好吧，我有1-100专为我保留的范围，所以我只会在 处放一个41，因为我知道它是安全的。”

降低l_max时肯定有非常非常高的碰撞机会。

相反的情况呢，提高它？

回到我们的示例，让我们将 l_size 提高到 500，将下一个键变为4*500+1 = 2001，保留范围 2001-2501。

在 HiLo 的这个特定实现中，当提高l_max时，看起来可以避免碰撞。

当然，您应该自己做一些测试，以确保这是实际的实现，或者接近它。一种方法是将 l_max 设置为 100 并找到前几个键，然后将其设置为 500 并找到下一个。如果像这里提到的那样有一个巨大的跳跃，你可能是安全的。

但是，我绝不建议在现有数据库上提高 l_max 是最佳做法。

使用您自己的判断力；HiLo 算法并非完全考虑到不同的 l_max 算法，您的结果最终可能无法预测，具体取决于您的具体实现。也许有过提高 l_max 和发现问题经验的人可以证明这个计数是正确的。

所以总而言之，即使理论上，Hibernate 的 HiLo 实现在提高 l_max 时很可能会避免冲突，但它可能仍然不是一个好的实践。您应该像 l_max 不会随时间变化一样进行编码。

但如果你觉得幸运...

于 2010-06-21T12:04:05.143 回答
3

请参阅线性块表分配器——这在逻辑上是解决同一问题的更简单和正确的方法。

什么是 Hi/Lo 算法？

通过从数字空间分配范围NEXT并直接表示，而不是用高字或乘数使逻辑复杂化，您可以直接看到将生成哪些键。

本质上，“线性块分配器”使用加法而不是乘法。如果 NEXT 是 1000 并且我们已经配置了 range-size 20，NEXT 将前进到 1020，我们将保留键 1000-1019 进行分配。

范围大小可以随时调整或重新配置，而不会丢失完整性。分配器的 NEXT 字段、生成的键和表中存在的 MAX(ID) 之间存在直接关系。

（相比之下，“Hi-Lo”使用乘法。如果下一个是 50 并且乘数是 20，那么您分配的密钥在 1000-1019 左右。NEXT、生成的密钥和 MAX(ID) 之间没有直接关联表中，很难安全地调整 NEXT 并且在不干扰当前分配点的情况下无法更改乘数。）

使用“线性块”，您可以配置每个范围/块的大小——1 的大小相当于传统的基于表的“单一分配器”并命中数据库以生成每个键，10 的大小在分配时快 10 倍一次 10 的范围，50 或 100 的大小仍然更快..

65536 的大小会生成难看的密钥，在服务器重启时浪费大量的密钥，相当于 Scott Ambler 的原始 HI-LO 算法。

简而言之，Hi-Lo 是一种错误的复杂和有缺陷的方法，它在概念上应该很简单——沿着数轴分配范围。

于 2013-11-08T01:00:33.127 回答
2

我试图通过一个简单的 helloWrold-ish 休眠应用程序来挖掘 HiLo 算法的行为。

我尝试了一个休眠示例

<generator class="hilo">
<param name="table">HILO_TABLE</param>
<param name="column">TEST_HILO</param>
<param name="max_lo">40</param>
</generator>

使用单列“TEST_HILO”创建的名为“HILO_TABLE”的表最初我将 TEST_HILO 列的值设置为 8。

update HILO_TABLE set TEST_HILO=8;

我观察到创建 ID 的模式是

hivalue * lowvalue + hivalue

hivalue 是 DB 中的列值（即从 HILO_TABLE 中选择 TEST_HILO） lowvalue 来自配置 xml（40）

所以在这种情况下，ID 从 8*40 + 8 = 328 开始

在我的休眠示例中，我在一个会话中添加了 200 行。所以行是用 ID 328 到 527 创建的，在 DB 中，hivalue 一直递增到 13。递增逻辑似乎是：-

new hivalue in DB = inital value in DB + (rows_inserted/lowvalue + 1 )

= 8 + 200/40 = 8 + 5 =13

现在，如果我运行相同的休眠程序来插入行，ID 应该从 13*40 + 13 = 533 开始

当运行程序时，它被确认。

于 2012-11-08T09:23:44.653 回答
1

凭经验我会说：是的，减少会导致碰撞。当您的最大低点较低时，您将获得较低的数字，这与数据库中的高值无关（处理方式相同，例如，在 NH 的情况下随每个会话工厂实例递增）。

有可能增加不会导致碰撞。但是您要么需要尝试，要么需要询问比我更了解的人才能确定。

于 2010-06-21T11:41:46.177 回答
0

老问题，我知道，但值得回答“是的，你可以”

只要您根据表的当前 ID 号重新计算 hibernate_unique_key 表，您就可以随时增加或减少您的 nex_hi。

在我们的例子中，每个实体都有一个 ID，hibernate_unique_key 表有两列：

  • next_hi
  • 实体名称。

任何给定 ID 的 next_hi 计算为

SELECT MAX(Id) FROM TableName/(@max_lo + 1) + 1

下面的脚本遍历每个带有 Id 列的表并更新我们的 nex_hi 值

DECLARE @scripts TABLE(Script VARCHAR(MAX))
DECLARE @max_lo VARCHAR(MAX) = '100';
    
INSERT INTO @scripts
SELECT '
INSERT INTO hibernate_unique_key (next_hi, EntityName)
SELECT
(SELECT ISNULL(Max(Id), 0) FROM ' + name + ')/(' + @max_lo + ' + 1) + 1, ''' + name + ''' 
'
FROM sys.tables WHERE type_desc = 'USER_TABLE' 
AND COL_LENGTH(name, 'Id') IS NOT NULL
AND NOT EXISTS (select next_hi from hibernate_unique_key k where name = k.EntityName)


DECLARE curs CURSOR FOR SELECT * FROM @scripts
DECLARE @script VARCHAR(MAX)

OPEN curs 
FETCH NEXT FROM curs INTO @script

WHILE @@FETCH_STATUS = 0
BEGIN
    --PRINT @script 
    EXEC(@script)
    FETCH NEXT FROM curs INTO @script
END
CLOSE curs
DEALLOCATE curs
于 2020-11-17T19:41:39.520 回答