确保哈希函数与切片很好地混合在一起

Ensuring a hash function is well-mixed with slicing

提问人:Slater Victoroff 提问时间:6/27/2013 更新时间:3/2/2014 访问量:198

问:

如果这个问题很愚蠢,请原谅我,但我开始学习一致的哈希,在阅读了 Tom White 的博客文章后,我意识到大多数默认哈希函数没有很好地混合,我有一个想法,确保任意哈希函数的混合程度最低。

我的想法最好用这样的例子来解释:

Bucket 1: 11000110
Bucket 2: 11001110
Bucket 3: 11010110
Bucket 4: 11011110

在跨这些存储桶进行一致缓存的标准哈希环实现下,您将获得糟糕的性能,并且几乎每个条目都会归入存储桶 1。但是,如果我们在每种情况下都使用位 4 和 5 作为 MSB,那么这些存储桶会突然很好地混合在一起,并且将新对象分配给缓存变得微不足道,只需要检查 2 位。

在我看来,当跨多个节点构建分布式网络时,这个概念可以很容易地扩展。在我的特定情况下,我将使用它来确定将给定数据放入哪个缓存。提高放置速度并不是一个真正的问题,但确保我的缓存混合良好是,我正在考虑只选择几个为我给定的缓存最佳混合的位。以后编入索引的任何信息都将基于相同的位进行编入索引。

在我幼稚的头脑中,这是一个比引入虚拟节点或构建更好的哈希函数更简单的解决方案。也就是说,我看不到任何提到这样的方法,我担心在我的哈希无知中我在这里做错了什么,我可能会引入意想不到的后果。

这种方法安全吗?我应该使用它吗?这种方法以前是否使用过,是否有任何既定的算法来确定最小的唯一位组?

语言无关位 操作 一致哈希

评论

0赞 ShreevatsaR 6/26/2014
您实际上是在更改哈希函数,从具有更多位的函数更改为具有较少位的哈希函数(并且只能使用 4 个存储桶)。这怎么可能有帮助?如何添加新的第五个存储桶?这似乎解决了与consistnet哈希设计完全不同的问题。
0赞 Slater Victoroff 7/3/2014
@ShreevatsaR我没有删除任何位,只是重新排列它们。添加第五个存储桶照常进行。不要忽略其他存储桶,只是更改位的位置。
0赞 Tony Delroy 1/27/2015
“不要忽略其他铲斗,只是改变钻头的位置。”- 在不让大多数现有对象开始映射到另一个缓存的情况下,您打算如何做到这一点?
1赞 Tony Delroy 1/28/2015
映射到另一个缓存只是 ~1/5th 值的想法 - 那些未分配给“第五个存储桶”的值应保留其旧分配。我看不出你多样化的位选择想法将如何动态地维持这种关系,除非它是动态的,否则我看不出任何意义......您将失去一致哈希的所有属性。无论如何,也许你应该实现你想到的任何东西,所以我们谈论的是具体的代码和行为......然后,如果您有特定问题,但仍认为您的想法可以工作,则可以提出更具体的问题。
1赞 Maarten Bodewes 8/16/2015
我投票说这是“不清楚你在问什么”,因为你显然没有指定完整的算法,例如,为什么所有东西都会放在桶 1 中,以及为什么特定位比其他位更有可能。

答: 暂无答案