一致性 hash 算法（ consistent hashing ）

      consistent hashing 算法早在 1997 年就在论文 中被提出，如今在 cache 体系 中操纵越来越普及 ；

1 根本 场景

比如 你有 N 个 cache 做事器（后头简称 cache ），那么怎样 将一个器材 object 映射到 N 个 cache 上呢，你很也许会采用 类似下面的通用行动 打定 object 的 hash 值，然后匀称 的映射到到 N 个 cache ；

hash(object)%N

统统 都运行正常，再思量 如下的两种情况；

1 一个 cache 做事器 m down 掉了（在实际 操纵中必需 要思量 这种情况），如许 全部 映射到 cache m 的器材 都市 失效，怎么办，必要 把 cache m 从 cache 中移除，这时间 cache 是 N-1 台，映射公式变成 了 hash(object)%(N-1) ；

2 由于拜访加重，必要 添加 cache ，这时间 cache 是 N+1 台，映射公式变成 了 hash(object)%(N+1) ；

1 和 2 意味着什么？这意味着忽然 之间险些 全部 的 cache 都失效了。对付 做事器而言，这是一场劫难 ，大水 般的拜访都市 直接冲向靠山做事器；

再来思量 第三个题目 ，由于硬件手段 越来越强，你也许想让后头添加的节点多做点活，显然上面的 hash 算法也做不到。

有什么行动 可以变化 这个状况呢，这就是 consistent hashing…

2 hash 算法和单调性

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

单调性是指假如 已经有一些内容通过哈希分派 到了相应的缓冲中，又有新的缓冲介入到体系 中。哈希的结果应可以或许 担保原有已分派 的内容可以被映射到新的缓冲中去，而不会被映射到旧的缓冲聚拢 中的其他缓冲区。

轻易 看到，上面的大略 hash 算法 hash(object)%N 难以满意 单调性哀求 。

3 consistent hashing 算法的原理

consistent hashing 是一种 hash 算法，大略 的说，在移除 / 添加一个 cache 时，它可以或许 尽也许小的变化 已存在 key 映射相干，尽也许的满意 单调性的哀求 。

下面就来服从 5 个步调 大略 讲讲 consistent hashing 算法的根本 原理。

3.1 环形hash 空间

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

图 1 环形 hash 空间

3.2 把器材 映射到hash 空间

接下来思量 4 个器材 object1~object4 ，通过 hash 函数打定出的 hash 值 key 在环上的散播如图 2 所示。

hash(object1) = key1;

… …

hash(object4) = key4;

图 2 4 个器材 的 key 值散播

3.3 把cache 映射到hash 空间

Consistent hashing 的根本 头脑 就是将器材 和 cache 都映射到同一个 hash 数值空间中，并且 应用 相同 的 hash 算法。

假设当前有 A,B 和 C 共 3 台 cache ，那么其映射结果将如图 3 所示，他们在 hash 空间中，以对应的 hash 值分列 。

hash(cache A) = key A;

… …

hash(cache C) = key C;

图 3 cache 和器材 的 key 值散播

说到这里，趁便 提一下 cache 的 hash 打定，一样平常 的行动 可以应用 cache 呆板 的 IP 所在可能呆板 名作为 hash 输入。

3.4 把器材 映射到cache

如今 cache 和器材 都已经通过同一个 hash 算法映射到 hash 数值空间中了，接下来要思量 的就是怎样 将器材 映射到 cache 上面了。

在这个环形空间中，假如 沿着顺时针方向 从器材 的 key 值启程，直到遇见一个 cache ，那么就将该器材 存储在这个 cache 上，由于 器材 和 cache 的 hash 值是牢靠的，因此这个 cache 一定 是唯一和断定 的。如许 不就找到了器材 和 cache 的映射行动 了吗？！

依然连续 上面的例子（拜见 图 3 ），那么按照 上面的行动 ，器材 object1 将被存储到 cache A 上； object2 和 object3 对应到 cache C ； object4 对应到 cache B ；

3.5 视察 cache 的改观

前面讲过，通过 hash 然后求余的行动 带来的最大题目 就在于不能满意 单调性，当 cache 有所改观 时， cache 会失效，进而对靠山做事器造成伟大的攻击，如今 就来说明说明 consistent hashing 算法。

3.5.1 移除 cache

思量 假设 cache B 挂掉了，按照 上面讲到的映射行动 ，这时受影响的将仅是那些沿 cache B 逆时针遍历直到下一个 cache （ cache C ）之间的器材 ，也便是 本来 映射到 cache B 上的那些器材 。

因此这里仅必要 改观 器材 object4 ，将其重新映射到 cache C 上即可；拜见 图 4 。

图 4 Cache B 被移除后的 cache 映射

3.5.2 添加 cache

再思量 添加一台新的 cache D 的情况，假设在这个环形 hash 空间中， cache D 被映射在器材 object2 和 object3 之间。这时受影响的将仅是那些沿 cache D 逆时针遍历直到下一个 cache （ cache B ）之间的器材 （它们是也本来 映射到 cache C 上器材 的一部分 ），将这些器材 重新映射到 cache D 上即可。

因此这里仅必要 改观 器材 object2 ，将其重新映射到 cache D 上；拜见 图 5 。

图 5 添加 cache D 后的映射相干

4 假造 节点

考量 Hash 算法的另一个指标是均衡 性 (Balance) ，界说 如下：

均衡 性

均衡 性是指哈希的结果可以或许 尽也许散播到全部 的缓冲中去，如许 可以使得全部 的缓冲空间都得到操作。

hash 算法并不是担保绝对的均衡 ，假如 cache 较少的话，器材 并不能被匀称 的映射到 cache 上，比如 在上面的例子中，仅陈设 cache A 和 cache C 的情况下，在 4 个器材 中， cache A 仅存储了 object1 ，而 cache C 则存储了 object2 、 object3 和 object4 ；散播是很不均衡 的。

为了解 决这种情况， consistent hashing 引入了“假造 节点”的观念 ，它可以如下界说 ：

“假造 节点”（ 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 。

图 6 引入“假造 节点”后的映射相干

此时，器材 到“假造 节点”的映射相干为：

objec1->cache A2 ； objec2->cache A1 ； objec3->cache C1 ； objec4->cache C2 ；

因此器材 object1 和 object2 都被映射到了 cache A 上，而 object3 和 object4 映射到了 cache C 上；均衡 性有了很大前进。

引入“假造 节点”后，映射相干就从 { 器材 -> 节点 } 转换到了 { 器材 -> 假造 节点 } 。查询物体地点 cache 时的映射相干如图 7 所示。

图 7 查询器材 地点 cache

“假造 节点”的 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

5 小结

Consistent hashing 的根本 原理就是这些，具体 的散播性等理论说明应当 是很繁杂 的，不外 一样平常 也用不到。

上面有一个 java 版本的例子，可以参考。

转载了一个 PHP 版的实当代 码。