一致性哈希

经典的哈希方法使用哈希函数来生成伪随机数,然后除以内存空间的大小,将随机标识符转变成可用空间内的一个位置。

结果看起来如下:location = hash(key)mod size。

179006941_1561691532297_ib0lz9vax1

在分布式的场景下,我们需要一种机制将请求均匀的分布到节点上,以实现负载均衡。

如果使用hash方法,则节点有变动(增加删除)的时候,我们最终需要重新计算每一个键的哈希值,因为新映射依赖节点数量/内存位置。

只是重新计算哈希值的分布式系统(每个键的位置都移动)存在一个问题,那就是每个节点上都存储了状态。

比如说,集群规模的微小变化可能导致大量的工作,以便重新调整集群内的所有数据。

一致性哈希如何处理请求?

一致性哈希如何决定哪个请求将由哪个服务器节点来处理?如果我们假设环是有序的,以便环的顺时针遍历与位置地址的递增顺序对应,那么每个请求可以由最先出现在该顺时针遍历中的那个服务器节点来处理。

如何高效地实施一致性哈希算法?

给节点生成随机哈希值。

计算请求中标识符的哈希值,找到大于该值的最近的节点。

179006941_1561691532245_sh1fadgd69

让这更公平的一种方法是,为每个节点生成多个随机哈希值,确保每个节点负责环的同等部分,从而使负载均匀地分配。rhtsk12goq

假设现在我们向环添加一个名为 C 的新节点,我们为 C 生成随机哈希值,0xa2d65c0+1 和 0xe12f751c(用于哈希到 A)之间的环空间现在被委托给 C。所有的其他请求将继续哈希到与之前相同的那个节点。

8q55yqdnrp

comments powered by Disqus