一致性Hash算法原理

算法介绍

consistent hash算法如图所示：首先将服务节点映射到一个0~2^32的圆上。例如server1~server3，hash(server1), hash(server2), hash(server3)

图1. 将server映射到圆上

然后将key值同样映射到圆上，并沿着顺时针查找第一个server节点，那么这个key值就会被保存到对应的server上。如图2.

图2.将key用同样的算法映射到圆上并寻找对应的server

如果添加或减少一个节点，响应会调整对应的节点和server的对应关系。如图3.

图3. 增加server4后，节点重新分布。

从图3看出，只有server4到server4之间的key会改变映射关系，key5会保存到server4.其他部分不会受到影响。

均匀分布

如图1-3， server在圆上的映射可能不是均匀的，这会导致有些节点映射的key比较多，有些则比较少。为了尽可能的均匀分布，我们引入了虚节点的概念。

所谓虚节点，就是将每个server在圆上映射多个hash值，例如server1，可以通过编号进行hash值映射计算：hash(server1#1),hash(server1#2)...hash(server1#n).一般每个server在圆上映射100-200个虚节点以后，key的分布会比较平均。

之前有一篇测试hash平均分布的文章，传送门。