一致性哈希算法 Consistent Hashing 探讨以及相应的新问题出现解决

一致性哈希算法 Consistent Hashing 探讨以及相应的新问题出现解决2014-12-25一、业务场景

假如我们现在有12台Redis服务器（其它的什么东西也行），有很多User（用户）的数据数据从前端过来，然后往12台redis服务器上存储，在存储中就会出现一个问题，12台服务器，有可能其中几台Redis服务器上（简称集群A）存了很多的数据，然后另外几台Redis服务器（简称集群B）上存的数据很少，这样的话那 A 上的读写压力就会很大（当然，这个要看你的数据量的大小了，如果你数据量很小的话，基本无压力了，但是数据量很大，那就、、、），对于这样的问题，我们通常的解决办法是什么呢？一般通常会想到的就是哈希取余了吧！也就是 Hash（userid）% N （N=12），这样的话也能适当的减小很多压力了，但是这样的话又会产生一些新的问题，增加节点跟减少节点：

1、减少节点：

假如有一台Redis服务器挂掉了，那么是否这样 Hash（userid）% N （N=12）哈希取余到该Redis的数据会全部丢失呢？如果不要该节点，那么只剩下11台Redis服务器了，原来的映射关系 Hash（userid）% N （N=12）变成了 Hash（userid）% （N-1）（N=12），重点是数据丢失如何找回？

2、增加节点：

假如有一天想增加Redis服务器了，这时候麻烦来了，这时候需要将原来的映射关系 Hash（userid）% N （N=12）变成 Hash（userid）% （N+1）（N=12）了，跟减少节点一样，这岂不是以前所有的映射全部失效了？这不是坑爹么！！！数据混乱，后台可能瞬间垮掉，那样的代价很大、、、

3、硬件越来越便宜了，公司越来越大了，然后服务器越来越多了：

哈希取余 Hash（userid）% N （N=12）就也完全不能满足需求了，不能修改映射关系，修改之后灰常麻烦。

这时候该怎么办呢？有什么办法可以改变这个状况呢，当然就是一致性哈希 Consistent Hashing了 ......

自己懒得写原理了，下面引用了 http://blog.csdn.net/sparkliang/article/details/5279393，详细介绍了一致性哈希，灰常好、、、

二、 hash 算法和单调性

Hash 算法的一个衡量指标是单调性（ Monotonicity ），定义如下：

单调性是指如果已经有一些内容通过哈希分派到了相应的缓冲中，又有新的缓冲加入到系统中。哈希的结果应能够保证原有已分配的内容可以被映射到新的缓冲中去，而不会被映射到旧的缓冲集合中的其他缓冲区。

容易看到，上面的简单 hash 算法 hash（object）%N 难以满足单调性要求。

三、Consistent hashing 算法的原理

Consistent Hashing 是一种 hash 算法，简单的说，在移除 / 添加一个 cache 时，它能够尽可能小的改变已存在 key 映射关系，尽可能的满足单调性的要求。

下面就来按照 5 个步骤简单讲讲 consistent hashing 算法的基本原理。

四、环形hash 空间

考虑通常的 hash 算法都是将 value 映射到一个 32 为的 key 值，也即是 0~2^32-1 次方的数值空间；我们可以将这个空间想象成一个首（ 0 ）尾（ 2^32-1 ）相接的圆环，如下面图 1 所示的那样。

图 1 环形 hash 空间

五、把对象映射到hash 空间

接下来考虑 4 个对象 object1~object4 ，通过 hash 函数计算出的 hash 值 key 在环上的分布如图 2 所示。

hash（object1） = key1;

… …

hash（object4） = key4;

图 2 4 个对象的 key 值分布