对码当歌,猿生几何?

一致性哈希算法


普通的哈希算法采用简单取模的方式,将缓存服务器进行散列,通常情况下是没有问题的,但是当缓存服务器的个数发生变动时,将会产生较大的影响

如上图所示,之前有4台缓存服务器,当增加1台缓存服务器之后,除数的变化(4 -> 5)导致求模结果变化,所有缓存查询均未命中

即缓存服务器的个数发生变化时,在一段时间内(缓存重建完毕之前),会有大量缓存查询未命中,导致这段时间内的服务整体性能下降特别严重

一致性哈希算法能有效降低服务器个数变化对整体缓存的影响,基本实现原理是将Hash函数的值域空间组织成一个圆环,将服务器节点进行哈希,并将哈希结果映射到圆环上,当有一个写入缓存的请求到来时,使用相同的Hash函数,计算Key的哈希值在圆环上对应的位置,按顺时针方向,将请求定位至离其最近的服务器节点

如下图所见,当增加一台缓存服务器Server5后,Server4和Server5之间的点将被定位至Server5,Server5和Server之间的点依然定位至Server,并且对Server2,Server3和Server4没影响,比起简单的求模哈希,未命中的缓存查询少了很多,整体服务性能不会下降过大

当然在实际使用过程中会在圆环上添加很多虚拟缓存服务器节点,以便缓存分布更加均匀.