5

我不是在谈论分布式键/值系统，例如通常与 memcached 一起使用的，它使用一致的散列来使添加/删除节点成为一个相对便宜的过程。

我说的是你的标准内存哈希表，比如 python 的 dict 或 perl 的哈希。

通过降低调整哈希表大小的成本，使用一致散列的好处似乎也适用于这些标准数据结构。实时系统（和其他对延迟敏感的系统）将受益于/需要针对低成本增长优化的哈希表，即使整体吞吐量略有下降。

维基百科提到“增量调整大小”，但基本上是在谈论调整大小的热/冷替换方法；有一篇关于“可扩展散列”的单独文章使用 trie 进行存储桶查找来完成廉价的重新散列。

只是好奇是否有人听说过使用一致哈希来降低增长成本的核心单节点哈希表。还是使用其他方法（上面列出的两个维基百科位）更好地满足此要求？

或者......我的整个问题是否被误导了？内存分页考虑是否使复杂性不值得？也就是说，一致性哈希的额外间接性让您只重新哈希总键的一小部分，但这可能并不重要，因为您可能必须从每个现有页面中读取，因此内存延迟是您的主要因素，以及是否与内存访问的成本相比，您重新散列部分或全部键并不重要......但另一方面，通过一致的散列，您的所有键重映射都有相同的目标页面，所以会有与您的键重新映射到任何现有页面相比，内存抖动更少。

编辑：添加“数据结构”标签，澄清最后一句说“页面”而不是“桶”。

4

1 回答 1

4

我还没有听说过这个，但如果你选择正确的一致性哈希实现可能是个好主意。具体来说， Google 等人的Jump Consistent Hashing。首先，我将介绍为什么要 Jump，然后我将介绍它如何在本地数据结构中发挥作用。

跳转一致哈希

Jump Consistent Hashing（我将简称为 Jump）非常适合这个空间，原因有几个。Jump 假设节点不会失败，这对于本地数据结构来说非常有用，因为它们不会失败！这使得 Jump 仅是对一系列数字的映射[0, numBuckets)，只需要 2-4 个字节的空间。

此外，实施简单且快速。如果我们删除参考实现的浮点除法并用一半的整数除法替换它们，速度会更快。（顺便说一句，我们可以。）

所有这些都可以用于...

并发哈希映射

但首先，Java 的Concurrent Hash Map是高级别的。

Java 的 ConcurrentHashMap 由多个buckets参数化。这个分片因子在地图的整个生命周期中都是不变的。这些桶中的每一个本身都是一个带有自己锁的哈希映射。

将键值对插入映射时，键被散列到其中一个桶中。获取该键的锁，并在释放锁之前将该项目插入到存储桶的哈希映射中。在插入存储桶时，x另一个线程可以同时插入存储桶y，但如果插入存储桶，它将等待锁x。因此Java 的 ConcurrentHashMap 具有 n-way concurrency，其中n是构造函数的桶参数。

就像任何哈希映射一样，ConcurrentHashMap 中的存储桶可能会被填满并需要增长。就像常规的哈希映射一样，它通过将其大小加倍并将桶中的所有内容重新哈希回更大的自身来实现这一点。除了“它更大的自我”只是桶的“自我”。如果一个桶是热点并且获得的密钥超过其公平份额，那么与其他桶相比，该桶将不成比例地增长。并且每次存储桶增长时，重新散列到自身所需的时间就会越来越长。最后一点不仅是热点问题，而且当哈希表普通旧获取更多键时。

想象一下，如果我们可以随着键数量的增加而增加桶的数量。有了这个，我们可以抑制每个桶的增长量。

输入一致的哈希，这允许我们添加更多的桶！

ConcurrentHashMap 采取 2：一致的哈希样式

我们可以通过两个简单的步骤让 ConcurrentHashMap 增加它的桶数。

首先将映射到每个桶的函数替换为跳转一致哈希函数。到目前为止，一切都应该是一样的。

第二个当一个桶装满时拆分一个新的桶；也长满了桶。实际上，只有当装满的桶成为容量最大的桶时，才拆分出一个新的桶。这可以在不迭代桶的情况下计算出来。

通过一致的散列，拆分只会将键定向到新存储桶中，而不是向后进入任何旧存储桶。

尾注

我相信这个方案可以改进。也就是说，拆分存储桶需要进行全表扫描才能将键移动到新存储桶中。这肯定不比普通哈希映射差，而且可能更好，但它对可能不需要进行完整扫描的 ConcurrentHashMap 实现不利。

于 2016-05-11T05:27:32.557 回答