有人问我一致哈希的一些缺点。但我认为它只比传统的 hash%N 哈希值多一点。正如标题所说,如果一致性哈希非常好,我们为什么不直接使用它呢?
你知道更多吗?谁能告诉我一些?
有人问我一致哈希的一些缺点。但我认为它只比传统的 hash%N 哈希值多一点。正如标题所说,如果一致性哈希非常好,我们为什么不直接使用它呢?
你知道更多吗?谁能告诉我一些?
我知道的一致散列的唯一重大缺点是实现它比简单的散列更复杂。更多的代码意味着更多的地方可以引入错误,但现在有免费可用的选项。
从技术上讲,一致的散列会消耗更多的 CPU;查询排序列表以确定将对象映射到哪个服务器是 O(log n) 操作,其中 n 是服务器数量 X 每个服务器的插槽数,而简单散列是 O(1)。
但在实践中,O(log n) 是如此之快,这并不重要。(例如,8 个服务器 X 每台服务器 1024 个插槽 = 8192 个项目,log2(8192) = 在最坏的情况下最多进行 13 次比较。)原作者对其进行了测试,发现使用一致散列计算缓存服务器只需 20 微秒。设置。同样,一致的散列会消耗空间来存储服务器插槽的排序列表,而简单的散列不占用空间,但所需的量是微不足道的,大约为 Kb。
为什么不为人所知?如果我不得不猜测,我会说这只是因为学术思想传播到工业需要时间。(原论文写于 1997 年。)
实现一致的散列并不是一件容易的事,在许多情况下,您拥有一个很少或从不需要重新映射或者可以相当快地重新映射的散列表。
我假设您是在专门谈论哈希表,因为您提到了 mod N。如果我的假设有误,请纠正我,因为哈希用于各种不同的事物。
原因是一致性哈希并不能真正解决哈希表迫切需要解决的问题。在重新散列时,哈希表可能需要重新分配其元素的很大一部分,无论如何,可能是其中的大部分。这是因为我们可能正在重新散列以增加表格的大小,这通常是二次完成的;例如,一旦表开始变得太满,节点的数量就会增加一倍,这是非常典型的。
因此,在一致的散列术语中,我们不仅仅是添加一个节点;而是添加一个节点。我们将节点数量增加了一倍。这意味着,在最好的情况下,我们正在移动一半的元素。当然,一致的散列技术可以减少移动,并尝试接近这个理想,但最好的情况改进只是 2 倍的常数因子,这不会改变我们的整体复杂性。
从另一端接近,在大多数应用程序中,哈希表都是关于缓存性能的。让它们快速运行的所有兴趣都在于尽可能快地计算东西,尽可能少地触及内存。无论您如何看待,添加一致的散列可能会超过 2 倍的减速;最终,一致性哈希会变得更糟。
最后,从另一个角度来看,这整个问题有点不重要。我们希望重新散列快速,但更重要的是我们根本不重新散列。在任何正常的实际情况下,当程序员看到他由于重新散列而遇到问题时,正确的答案几乎总是找到一种方法来避免(或至少限制)重新散列,首先选择合适的大小。鉴于这是典型的场景,为不应该发生的事情维持相当大的侧面结构显然不是胜利,而且再次让我们整体变慢。
几乎所有对哈希表的优化工作要么是如何更快地计算哈希,要么是如何更快地执行冲突解决。这些事情发生的时间尺度比我们谈论的一致性哈希要小得多,这通常用于我们谈论以微秒甚至毫秒为单位的时间尺度,因为我们必须进行 I/O 操作。
原因是因为一致散列往往会在读取端对范围扫描查询造成更多的工作。
例如,如果您想搜索按特定列排序的条目,那么您需要将查询发送到每个节点,因为一致的哈希甚至会将“相邻”项目放置在单独的节点中。
通常更喜欢使用与使用模式匹配的分区。更好的是在许多不同的分区/格式中复制相同的数据