一致性Hash算法-问题

一致性哈希算法是一种特殊的哈希算法， 当目标槽位数量发生变化时，它会尽力降低的重新映射的数量。 传统的哈希表设计中，添加或者删除一个槽位，会造成全量的重新映射， 一致性哈希则追求的是增量式重新映射。

一致性哈希最早由Karger在1997年提出¹，多用于分布式系统中的扩容缩容问题、 分布式哈希表的设计等等。

为什么需要一致性哈希

假设我们有一个简单的kvStore，支持两个简单的操作：

• get(key) ->v 表示查询键为 k的值为 v
• set(key,value) 表示把键为 k的值更新为 v

由于单节点系统的服务能力有限， 因此我们要考虑多节点的架构方案。 一种简单的架构方案是：前面做一个代理服务，把请求分割到不同的后端节点上， 这是常说的sharding模式。首先，一个必要前提是对同一个 key的所有读写请求都必须一致地分配给同一个后端节点，这样 sharding 模式才能解决性能问题，这种特性也被叫做一致性。其次，分配的负载应该尽量均衡。防止出现倾斜或热点问题。

换句话讲， 我们需要寻找一种映射函数， 把随机字符串 key，一致地映射到 n个桶中。 此外，我们也希望，这个映射要做到尽量平均。

hash表

哈希表是一种常用的基本数据结构。 它把随机到来的字符串 k输入到哈希函数 中， 然后映射到一张连续内存表上。Hash函数本身保证了映射的分布平均和一致性。一般地，常见的哈希函数(如 md5, sha1)都是映射到uint32这样很大的空间的， 所以哈希表一般对哈希函数的结果取余数来映射到槽位， 即Mod-N Hash。对于 N 个服务器，用哈希对密钥进行取模，获取到的余数就是服务器列表中对应的服务器索引。

server := serverList[hash(key) % N]

这种方法有许多优点。很容易解释。计算也很迅速。但是它有一个很严重的问题。

集群服务器数量变化可以简单概括为两种：

• 扩容
• 下线

下面以扩容为例,将服务器从4台扩容为5台

key/服务器[4]	0	1	2	3
16	X
14			X
11				X
5		X

key/服务器[5]	0	1	2	3	4
16		X
14					X
11		X
5	X

如果更改服务器数量，几乎每个密钥都会映射到其他节点。也就是说需要在全集群内迁移数据，显然太麻烦了， 我们要寻找增量扩容的方式。

也就是说，对要寻找的映射函数的一致性要求更高了， 不仅要求对相同的 k的多次映射结果一致， 还要尽可能减少 n变化时带来的不一致性映射的变化。 构造这种映射的算法，就是一致性哈希算法。即构造一种函数 $f(k,n)→m$ 把字符串映射到 n个槽上:

• 它的输入是随机到来的字符串 k和 槽的个数 n
• 输出是映射到的槽的标号 m, m<n.

这个函数需要有这样的性质:

• 映射均匀： 对随机到来的输入 k， 函数返回任一个 m的概率都应该是 1/n。
• 一致性：相同的 k, n输入， 一定会有相同的输出。当槽的数目增减时， 映射结果和之前不一致的字符串的数量要尽量少。更严格的定义是： 当添加一个槽时， 只需要对 k/n个字符串进行进行重新映射。

更一般的来说，在动态变化的环境中，判定一致性哈希算法好坏有四个定义：

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

参考

• [1] Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web