一致性hash算法及其在均衡负载中的应用研究

摘要

1997年由麻省理工学院提出的一种分布式哈希（DHT）实现算法——一致性哈希算法，初衷和CARP十分类似。一致性哈希修正了CARP使用的简单哈希算法带来的问题，使得分布式哈希（DHT）可以在P2P环境中真正得到应用。

一致性hash算法提出了在动态变化的Cache环境中的四个概念和原则：

平衡性(Balance)：平衡性是指哈希的结果能够尽可能分布到所有的缓冲（节点）中去，这样可以使得所有的缓冲空间（节点）都得到充分利用。

单调性(Monotonicity)：哈希的结果应能够保证原有已分配的内容可以被映射到原有的或者新的缓冲（节点）中去，而不会被映射到旧的缓冲集合中的其他缓冲区（节点）。如果是用签名取模算法，缓冲区（节点）变更会使得整个网络的映射关系更改。如果是carp，会使得1/n的映射关系更改。一致性哈希的目标，是缓冲区（节点）变更，不会改变网络的映射关系。

分散性(Spread)：分散性即同一份数据，存储到不同的缓冲区（节点），也就是说系统冗余。分散性的定义就是上述情况发生的严重程度。好的哈希算法应能够尽量避免不一致的情况发生，也就是尽量降低分散性。

负载(Load)：和平衡性(Balance)类似，只不过平衡性(Balance) 指的是访问均衡，而负载（Load）针对数据存储均衡。负载问题实际上是从另一个角度看待分散性问题。为了减小负载合理的使用一致性哈希算法能达到意想不到的效果。

一致性哈希算法有多种实现算法，其中最关键的问题是如何定义数据分割策略和节点快速查询。常用的算法有CHORD以及在CHORD基础上进行优化的KAD。除此之外还有许多优秀的算法。但是其核心还是相同的，即数据分割策略和节点快速查询。

一致性哈希算法的应用场景非常广泛，目前较为流行的应用场景为非关系数据库（NoSql）以及均衡负载服务器。例如目前主流非关系数据库Cassandra和MongoDB均使用了一致性哈希算法。

而在均衡负载中，一致性哈希算法被使用的玲离尽致。一致性哈希算法可以使当摸个缓冲区（节点）发生故障时，极其容易的退出哈希环，且当修复后也能简单的加入哈希环中。这一个退出加入的动作发生时，不会影响集群中其他缓冲区（节点）。这一特性大大的减小了运维人员的工作量。

关键词　哈希 简单哈希算法 一致性哈希算法 分布式哈希 哈希环 均衡负载

目录

摘要 I

引言 1

课题背景 1

第1章 哈希算法 2

1.1 简单哈希算法 2

1.1.1 简单哈希算法应用于均衡负载 2

1.1.2 简单哈希算法应用于均衡负载的问题 3

1.2 一致性哈希算法 3

1.2.1 一致性哈希算法的原理 3

1.2.2 均衡负载中的使用 5

第2章 一致性哈希算法的实现 10

2.1 代码实现 10

2.2 一致性哈希算法优化 13

2.3 一致性哈希算法仿真 14

第3章 一致性哈希算法的优势及劣势 16

3.1 一致性哈希算法的优势 16

3.2 一致性哈希算法的劣势 17

第4章 一致性哈希算法的其他实现方法列举 18

4.1 CHORD 18

4.2 KAD 19

第5章 结论 20

参考文献 21