koko的oracle杂货铺

consistent hashing

普通hash算法实现分布式的时候，当节点数量发生变化时，hash重组的代价太大，于是就有了下面提到的consistent hashing.

 基本模型为一个2的32次方均匀分布的同心圆，首先计算出节点的hash值，将其放在同心圆对应的位置上，用同样的hash运算算出key的hash值，对应到圆上相应的位置，由此位置顺时针找过去，找到的第一个节点就为该值的接受节点，找完2的32次方后没找到，放到第一个节点上。

当增加或减少节点时，受影响的只会是上一个节点和新增加节点之间的这一部分值，其他值不会受到影响。

 
当然根据这个模型，如果节点数比较少的话，每个节点的负载是不均匀的，因此很多consistent hash算法一般会采用虚拟节点的概念，比如上面这个图，如果将这5个物理节点配置成100或200个虚拟节点，根据虚拟节点来进行分布，然后再映射到物理节点，就可以很大程度上解决分布不均衡的问题。