Hash算法和一致性Hash算法（Consistent Hashing）及应用

本文将介绍一致性哈希算法（Consistent Hashing）及其应用的相关知识，以及Hash算法的介绍。

1. 什么是Hash

Hash即Hash算法，又称为散列算法，哈希算法将任意长度的二进制值映射为较短的固定长度的二进制值，这个小的二进制值称为哈希值。哈希值是一段数据唯一且极其紧凑的数值表示形式。如果散列一段明文而且哪怕只更改该段落的一个字母，随后的哈希都将产生不同的值。要找到散列为同一个值的两个不同的输入，在计算上是不可能的，所以数据的哈希值可以检验数据的完整性。一般用于快速查找和加密算法。

2. Hash算法的好坏

判断Hash算法的好坏，可以从以下四种情况看出：

平衡性(Balance)：平衡性是指哈希的结果能够尽可能分布到所有的缓冲中去，这样可以使得所有的缓冲空间都得到利用；很多哈希算法都能够满足这一条件。
单调性(Monotonicity)：单调性是指如果已经有一些内容通过哈希分派到了相应的缓冲中，又有新的缓冲加入到系统中；哈希的结果应能够保证原有已分配的内容可以被映射到原有的或者新的缓冲中去，而不会被映射到旧的缓冲集合中的其他缓冲区。
分散性(Spread)：在分布式环境中，终端有可能看不到所有的缓冲，而是只能看到其中的一部分；当终端希望通过哈希过程将内容映射到缓冲上时，由于不同终端所见的缓冲范围有可能不同，从而导致哈希的结果不一致，最终的结果是相同的内容被不同的终端映射到不同的缓冲区中；这种情况显然是应该避免的，因为它导致相同内容被存储到不同缓冲中去，降低了系统存储的效率。分散性的定义就是上述情况发生的严重程度。好的哈希算法应能够尽量避免不一致的情况发生，也就是尽量降低分散性。
负载(Load)：负载问题实际上是从另一个角度看待分散性问题。既然不同的终端可能将相同的内容映射到不同的缓冲区中，那么对于一个特定的缓冲区而言，也可能被不同的用户映射为不同的内容。与分散性一样，这种情况也是应当避免的，因此好的哈希算法应能够尽量降低缓冲的负荷。

3. Hash算法的应用

典型的应用场景是：有N台服务器提供缓存服务，需要对服务器进行负载均衡，将请求平均分发到每台服务器上，每台机器负责1/N的服务。常用的算法是对Hash结果取余数 (Hash() mod N )：对机器编号从0到N-1，按照自定义的 Hash()算法，对每个请求的Hash()值按N取模，得到余数i，然后将请求分发到编号为i的机器。但这样的算法方法存在致命问题，如果某一台机器宕机，那么应该落在该机器的请求就无法得到正确的处理，这时需要将宕掉的服务器从算法从去除，此时候会有(N-1)/N的服务器的缓存数据需要重新进行计算；如果新增一台机器，会有N /(N+1)的服务器的缓存数据需要进行重新计算。对于系统而言，这通常是不可接受的颠簸(因为这意味着大量缓存的失效或者数据需要转移)。因此，一致性Hash算法得以应用，接下来将介绍一致性Hash算法的原理及应用。

4. 什么是一致性Hash算法（Consistent Hashing）

一致性哈希算法在1997年由麻省理工学院提出的一种分布式哈希（DHT）实现算法，设计目标是为了解决因特网中的热点(Hot spot)问题，初衷和CARP十分类似。一致性哈希修正了CARP使用的简单哈希算法带来的问题，使得分布式哈希（DHT）可以在P2P环境中真正得到应用。

5. 一致性 Hash 算法原理

Consistent Hashing是一种Hash算法，简单的说，在移除/添加一个cache时，它能够尽可能小的改变已存在 key 映射关系，尽可能的满足单调性的要求。下面将介绍该算法的实现过程。

5.1 环形 Hash 空间

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

hash_1

图1

5.2 把对象通过 Hash 算法映射到 Hash 空间

现在四个对象 object1~object4 ，通过 Hash 函数计算出的 Hash 值 key 在环上的分布，如下图2所示：
Hash(object1) = key1;
Hash(object1) = key2;
Hash(object1) = key3;
Hash(object4) = key4;

hash_2

图2

5.3 把 cache 映射到 Hash 空间

Consistent Hashing 的基本思想就是将对象和 cache 都映射到同一个 Hash 数值空间中，并且使用相同的 Hash 算法。
假设当前有 A，B 和 C 共 3 台 cache ，那么其映射结果将如下图3所示，他们在 Hash 空间中，以对应的 Hash 值排列。
Hash(cache A) = key A;
Hash(cache B) = key B;
Hash(cache C) = key C;

hash_3

图3

顺便提一下 cache 的 Hash 计算，一般的方法可以使用 cache 机器的 IP 地址或者机器名作为 Hash 输入。

5.4 把对象映射到 cache 空间

现在 cache 和对象都已经通过同一个 Hash 算法映射到 Hash 数值空间中了，接下来要考虑的就是如何将对象映射到 cache 上面了。
在这个环形空间中，如果沿着顺时针方向从对象的 key 值出发，直到遇见一个 cache ，那么就将该对象存储在这个 cache 上，因为对象和 cache 的 Hash 值是固定的，因此这个 cache 必然是唯一和确定的。这样不就找到了对象和 cache 的映射方法了吗？！
依然继续上面的例子（参见图 3 ），那么根据上面的方法，对象 object1 将被存储到 cache A 上； object2 和 object3 对应到 cache C ； object4 对应到 cache B 。

5.5 添加或移除cache

前面已经讲了，通过 Hash 求余的方法带来的最大问题就在于不能满足单调性，当 cache 有所变动时， cache 会失效，进而对后台服务器造成巨大的冲击，接下来分析一致性 Hash 算法是如何处理的。

假设 cache B 被移除了，根据上面讲到的映射方法，这时受影响的将仅是那些沿 cache B 逆时针遍历直到下一个 cache （ cache C ）之间的对象，也即是本来映射到 cache B 上的那些对象；因此这里仅需要变动对象 object4 ，将其重新映射到 cache C 上即可；如下图 4 所示：

hash_4

图4

假设再考虑添加一台新的 cache D 的情况，假设在这个环形 hash 空间中， cache D 被映射在对象 object2 和 object3 之间。这时受影响的将仅是那些沿 cache D 逆时针遍历直到下一个 cache （ cache B ）之间的对象（它们是也本来映射到 cache C 上对象的一部分），将这些对象重新映射到 cache D 上即可。
因此这里仅需要变动对象 object2 ，将其重新映射到 cache D 上；如下图5所示：

hash_5

图5

通过添加或移除cache的分析，一致性 Hash 算法在保持了单调性的同时，还是数据的迁移达到了最小，这样的算法对分布式集群来说是非常合适的，避免了大量数据迁移，减小了服务器的的压力。

6. 虚拟节点（cache）

考量 Hash 算法的另一个指标是平衡性 (Balance) ，定义如下：
平衡性是指 Hash 的结果能够尽可能分布到所有的缓冲中去，这样可以使得所有的缓冲空间都得到利用。
Hash 算法并不是保证绝对的平衡，如果 cache 较少的话，对象并不能被均匀的映射到 cache 上，比如在上面的例子中，仅部署 cache A 和 cache C 的情况下，在 4 个对象中， cache A 仅存储了 object1 ，而 cache C 则存储了 object2 、 object3 和 object4 ；分布是很不均衡的。为了解决这种情况，一致性 Hash 算法引入了“虚拟节点”的概念，它可以如下定义：

“虚拟节点”（ virtual node ）是实际节点在 Hash 空间的复制品（ replica ），实际个节点对应了若干个“虚拟节点”，这个对应个数也成为“复制个数”，“虚拟节点”在 Hash 空间中以 Hash 值排列。

仍以仅部署 cache A 和 cache C 的情况为例，在图 4 中我们已经看到， cache 分布并不均匀。现在我们引入虚拟节点，并设置“复制个数”为 2 ，这就意味着一共会存在 4 个“虚拟节点”， cache A1, cache A2 代表了 cache A ； cache C1, cache C2 代表了 cache C ；假设一种比较理想的情况，如下图 6 所示：

hash_6

图6

此时，对象到“虚拟节点”的映射关系为：
objec1->cache A2 ； objec2->cache A1 ； objec3->cache C1 ； objec4->cache C2 ；
因此对象 object1 和 object2 都被映射到了 cache A 上，而 object3 和 object4 映射到了 cache C 上；平衡性有了很大提高。

引入“虚拟节点”后，映射关系就从 { 对象 -> 节点 } 转换到了 { 对象 -> 虚拟节点 } ；查询对象所在 cache 时的映射关系如图 7 所示：

hash_7

图7

“虚拟节点”的 Hash 计算可以采用对应节点的 IP 地址加数字后缀的方式。例如假设 cache A 的 IP 地址为 202.168.14.241 。
引入“虚拟节点”前，计算 cache A 的 hash 值：
Hash(“202.168.14.241”);
引入“虚拟节点”后，计算“虚拟节”点 cache A1 和 cache A2 的 hash 值：
Hash(“202.168.14.241#1”); // cache A1
Hash(“202.168.14.241#2”); // cache A2