对一致性 hash 算法的理解

在互联网项目中，会大量的用到缓存，例如：

192.168.0.10/192.168.0.11/192.168.0.12 三台机器上都有缓存.

现在用户A 要查询 key 对应的 value 放在那台机器上，那应该怎么处理了？

一般的思路是通过模运算来解决，例如：用 x % N 的结果去对应的机器上去查找.
比如：1 = x % N, 那么就去 192.168.0.10 这台机器上查找.

但是这有一个问题，当一个机器宕机的时候，或者随着访问量的增大，需要新增加机器，那么这时候，通过模运算将会存在大量的不命中. 因为不管是宕机或者新增加机器，都会涉及到 N 的变化，就会导致和以前存储时获得的 x % N 值不同.

现在的解决思路是：采用一致性 hash 算法.

一致性 hash 算法说的是：0~ 2^32 -1 构成一个环,192.168.0.10/192.168.0.11/192.168.0.12 通过 hash 算法映射到 0~2^32-1 这个空间上，当 <k,v> 存储的时候，首先通过 hash(k) 算出在 0~2^32-1 空间上的位置，然后按照顺时针的方向旋转，将 <k,v> 存放在最近的一台机器上.

这时候，不管是宕机，或者新增机器，就不会产生大面积的不命中.

分析：

假设192.168.0.11 这台机器宕机了，也只是说这台机器上存储的数据失效了，但是不会影响192.168.0.10/192.168.0.12 这两台机器已经存在的数据命中问题.