# 一致性Hash算法(Consistent Hashing)

- URL: https://www.yidoo.xyz/consistent-hashing
- 作者: 核动力蜗牛
- 发布时间: 2013-11-08
- 更新时间: 2013-11-08
- 分类: 优雅的算法
- 标签: distributed_systems

一致性 Hash 算法（Consistent hashing）早在 1997 年就在论文  [Consistent hashing and random trees](http://portal.acm.org/citation.cfm?id=258660)  中被提出，目前在 cache 系统中应用越来越广泛。

# 应用场景

假设有 N 个 cache 服务器，那么如何将一个对象 object 映射到 N 个 cache 服务器上呢，你很可能会采用类似下面的通用方法计算 object 的 hash 值，然后均匀的映射到到 N 个 cache：

```bash
hash(object)%N
```

考虑如下的两种情况；  
1）假设一个 cache 服务器 m 挂掉了，这样所有映射到 cache m 的对象都会失效。这时需要把 cache 服务器 m 从系统中移除，cache 服务器数变成 N-1 台，因此映射公式变成：

```bash
hash(object)%(N-1)
```

2）如果需要添加 cache 服务器 ，cache 服务器数变成 N+1 台，映射公式变成：

```bash
hash(object)%(N+1)
```

这两种情况的出现，使得原来的 cache 都失效了。可见上述的 Hash 算法并不能很好的适应 cache 系统，因此为了解决这两种情况我们引入一致性 Hash。

# 一致性 Hash 算法

算法具体步骤如下：

1.  首先求出每个 Cache 服务器的 hash（可以利用 IP 来计算），并将其配置到一个 0~2^32 的圆环区间上。
2.  使用同样的方法求出需要存储对象的 hash，也将其配置到这个圆环上。
3.  从数据映射到的位置开始顺时针查找，将数据保存到找到的第一个 Cache 节点上。如果超过 2^32 仍然找不到 Cache 节点，就会保存到第一个 Cache 节点上。  
    ![image](https://www.yidoo.xyz/images/3761ca5c18c4d52043151a4c51bda4cd.gif)

## 新增 Cache 服务器

假设在这个环形哈希空间中，cache5 被映射在 Cache3 和 Cache4 之间，那么受影响的将仅是沿 Cache5 逆时针遍历直到下一个 Cache（Cache3）之间的对象（它们本来映射到 Cache4 上）。

![image](https://www.yidoo.xyz/images/0055af6bc76f03669946b7821e90b649.gif)

- 移除 Cache 服务器

假设在这个环形哈希空间中，Cache3 被移除，那么受影响的将仅是沿 Cache3 逆时针遍历直到下一个 Cache（Cache2）之间的对象（它们本来映射到 Cache3 上）。

![image](https://www.yidoo.xyz/images/35ed91ce14f99b20da0dabc54dca7fc9.gif)

# 虚拟 Cache 服务器

考虑到哈希算法并不是保证绝对的平衡，尤其 Cache 较少的话，对象并不能被均匀的映射到 Cache 上。为了解决这种情况，一致性 Hash 引入了“虚拟节点”的概念： 一个实际节点对虚拟成若干个“虚拟节点”，这个对应个数也成为“复制个数”，“虚拟节点”在哈希空间中以哈希值排列。仍以 4 台 Cache 服务器为例，在下图中看到，引入虚拟节点，并设置“复制个数”为 2 后，共有 8 个“虚拟节点”分部在环形区域上，缓解了映射不均的情况。

![image](https://www.yidoo.xyz/images/660a38d2997de82f49ca7db33decd594.gif)

引入了“虚拟节点”后，映射关系就从【对象--->Cache 服务器】转换成了【对象--->虚拟节点---> Cache 服务器】。查询对象所在 Cache 服务器的映射关系如下图所示。

![image](https://www.yidoo.xyz/images/4ff6cba20889ddafc7118cb6d226ce63.gif)

# 参考资料

一致性 hash 算法 - consistent hashing: <http://blog.csdn.net/sparkliang/article/details/5279393>  
一致性哈希算法（Consistent Hashing）: <http://blog.csdn.net/x15594/article/details/6270242>  
一致性 hash 和 solr 千万级数据分布式搜索引擎中的应用: <http://blog.jobbole.com/47023/">http://blog.jobbole.com/47023/>