一致的散列与会合(HRW)散列 - 有什么权衡？

Question

网上有很多关于一致性散列的信息,以及可用的多种语言的实现.该主题的Wikipedia条目引用了具有相同目标的另一种算法:

会合哈希

该算法看起来更简单,并且不需要在环周围添加复制品/虚拟来处理不均匀的加载问题.正如文章所提到的,它似乎在O(n)中运行,这对于大n来说是一个问题,但引用一篇文章说明它可以被构造为在O(log n)中运行.

对于在这方面有经验的人来说,我的问题是,为什么人们会选择一致的哈希而不是HRW,反之亦然？是否存在其中一种解决方案是更好的选择的用例？

非常感谢.

Answer 1

主要是我会说一致哈希的优势在于热点问题.根据实现,可以手动修改令牌范围以处理它们.

有了HRW,如果不知何故你最终得到热点(即由糟糕的哈希算法选择引起),除了删除热点并添加一个应该平衡请求之外的新热点之外,没有太多可以解决的问题.

HRW的最大优势是,当您添加或删除节点时,您可以在所有节点之间保持均匀分布.通过一致的哈希,他们通过为每个节点提供大约200个虚拟节点来解决这个问题,这也使得难以手动管理范围.

Answer 2

作为一个只需要在两种方法之间做出选择并最终为HRW哈希进行选择的人:我的用例是一个简单的负载平衡,完全没有重新分配要求 - 如果一个节点死了,那么只选择一个新的并且重新开始.不需要重新平衡现有数据.

1)Consistent Hashing需要节点和vnode的持久性hashmap(或者至少是一个合理的实现,你可以在每个请求上构建所有对象....但你真的不想!).HWR没有(它是无状态的).当机器加入或离开集群时,无需修改任何内容 - 无需担心并发性(除了您的客户端可以很好地查看集群状态,两种情况都相同)

2)HRW更容易解释和理解(代码更短).例如,这是在Riverbed Stingray TrafficScript中实现的完整HRW算法.(注意,有比MD5更好的哈希算法选择 - 这个工作太过分了)

$nodes = pool.listActiveNodes("stingray_test");

# Get the key
$key = http.getFormParam("param");

$biggest_hash = "";
$node_selected = "";

foreach ($node in $nodes) {
   $hash_comparator = string.hashMD5($node . '-' . $key);

   # If the combined hash is the biggest we've seen, we have a candidate
   if ( $hash_comparator > $biggest_hash ) {
      $biggest_hash = $hash_comparator;
      $node_selected = $node;
   }
}

connection.setPersistenceNode( $node_selected );
?

3)当您丢失或获得节点时,HRW提供均匀分布(假设您选择了合理的散列函数).Consistent Hashing不能保证,但是有足够的vnode可能不会成为一个问题

4)一致路由可能更快 - 在正常操作中它应该是一个命令Log(N),其中N是节点数*vnodes的复制因子.但是,如果你没有很多节点(我没有),那么HRW 对你来说可能足够快.

4.1)正如你所提到的,维基百科提到有一种方法可以在log(N)时间内完成HWR.我不知道怎么做!我对5个节点上的O(N)时间感到满意.....

最后,HRW的简单性和无状态性质为我做出了选择....