一致性hash算法在分布式系统里面使用比较广,我也只是听说过这个概念,今天看到一个一致性hash开源库,随手写篇文章,记录下吧。
假如我们使用普通的哈希方式来处理负载均衡,到目标机器的映射使用的算法为:
hash(o) mod n (n表示机器的总数)
如果需要增加或减少一台机器的时候,算法就变为 hash(o) mod (n + 1) / hash(o) mod (n - 1)
不仅需要重新编写代码,当服务器做了大量变更,大量的o会重定向不同的服务器而导致了缓冲不被命中,所以此时,就提出了一致性hash算法。
一致性哈希算法
简单的说,哈希函数将o映射到 0 ~ 2^32 - 1的值区间,将这些数字头尾相连,然后将它们组织成一个闭合的圆环。如图一所示:
要实现一致性哈希算法,思路就是下面2个步骤: