一、定义

一致性哈希算法（Consistent Hashing Algorithm）于1997年由麻省理工学院的Karger等人在论文《Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web》中提出，用来解决计算机网络分布式Cache的问题。一致性就是一贯的、始终如一、稳定性之意。

一致性哈希算法的产生也源于业务的需求。随着业务的增长，一台单机已经不能满足业务的需要，分布式架构应运而生。分布式环境下，多台机器需要协同作业，如果保证数据在分布式环境下的一致性，就成为了亟待解决的问题。一致性哈希算法，就是为了解决多台机器，在动态增删的情况下，能够最大限度地保证信息的一致性。

一致性哈希算法是一种分布式哈希算法，设计目标是为了实现负载均衡或解决互联网中的热点(Hot spot)问题。一致性Hashing在分布式系统或缓存系统中经常会被用到，用于尽可能地降低节点变动带来的数据迁移开销或保证大部分cache有效。

一致性哈希算法是在普通哈希算法基础上，提出的在动态变化的Cache环境中，哈希算法应该满足的5个适应条件：

平衡性(Balance)

平衡性是指Hash的结果能够尽可能分布均匀，充分利用所有缓存空间。平衡性不仅仅指的是平均分配，可以理解为一种加权的平均，根据每台服务器的能力，把任务分配下去，充分利用每台机器的资源。

单调性(Monotonicity)

单调性是指如果已经有一些内容通过哈希分派到了相应的缓冲中，又有新的缓冲加入到系统中，哈希的结果应能够保证原有已分配的内容可以被映射到新的缓冲中去，而不会被映射到旧的缓冲集合中的其他缓冲区。如果我们采用简单的哈希算法，比如使用节点的哈希运算：hash(IP地址#编号)%节点数N，作为哈希值，映射到节点上。那么，一旦节点数N发生了变化，所有的哈希值都会失效。单调性就是为了解决这个问题。

分散性(Spread)

分散性定义了分布式环境中，不同终端通过Hash过程将内容映射至缓存上时，因可见缓存不同，Hash结果不一致，相同的内容被不同的终端映射至不同的缓冲区。

负载(Load)

负载是对分散性要求的另一个纬度。既然不同的终端可以将相同的内容映射到不同的缓冲区中，那么对于一个特定的缓冲区而言，也可能被不同的用户映射为不同的内容。

平滑性(Smoothness)

平滑性是指缓存服务器的数目平滑改变与缓存对象的平滑改变是一致的。

二、问题的提出

1.现有千万级用户或海量数据的访问量，你如何提高数据库服务器的IO读取效率？

分布式架构中，对千万级用户或海量数据的访问，分布式缓存服务器成了标配。如你有N台cache服务器(即缓存服务器，其作用是缓存热点数据，用户访问数据会先访问缓存服务器，如果没找到，才会访问数据库服务器，提高IO效率)，那么如何将一个对象 object 映射到 N 个 cache 上呢，你很可能会采用类似下面的通用方法计算 object的hash 值，然后均匀的映射到N个cache : hash(object) % N。

期望一切运行正常，这只是一厢情愿，实际应用中会出现如下两种情形：

第一种情况，第m台缓存服务器意外宕掉了，这样所有映射到m的对象都会失效，怎么办，需要把m从缓存服务器队列中移除，这时候cache是N-1 台，映射公式变成了 hash(object) % (N-1)；另一种情况，由于访问加重，需要添加cache，这时候cache是 N+1 台，映射公式变成了 hash(object) % (N+1) 。

这两种情况意味着什么？这意味着突然之间几乎所有的 cache 都失效了。对于数据库服务器或后台服务器而言，这是一场灾难，洪水般的访问都会直接冲向数据库服务器或后台服务器。

2. 现在有亿级用户，每日产生千万级订单，如何将订单进行分片分表？

首先要解决的是要找出一个唯一不变的属性来进行分片/分表，手机号如何？用户手机号会变动，不可行。订单属性中保持不变的就是会员ID，就可以根据会员ID进行分片/分表。千万级订单根据会员ID分片/分表存储在众多的分布式节点中，实际运行中，节点的宕机、某个节点加入或者移出集群是常事。普通的Hash计算公式：Hash(Key)%M，M改变，整个哈希表要重新计算。所有对象需要重新分配移动，这种移动就造成网络负担。

3. 项目运算量巨大，如何进行分布式任务调度？

在一个分布式任务调度系统中，执行任务的节点有n台机器，现有m个job在这n台机器上运行，这m个Job需要逐一映射到n个节点中一个，简单的Hash算法: Hash(Job)%n, 可以让m个Job均匀分布到n个节点中。如果n改变，基本上所有的Job会被重新分配，意味着需要迁移几乎所有正在运行的Job，想想这样会给系统带来多大的复杂性和性能损耗。

三、一致性哈希算法

简单的哈希算法往往不能满足单调性的要求，如最简单的线性哈希：

x → (ax + b) mod (P)

在上式中，P表示全部缓冲的大小。不难看出，当缓冲大小P发生变化时，原来所有的哈希结果均会发生变化，从而不满足单调性的要求。

哈希结果的变化意味着当缓冲空间发生变化时，所有的映射关系需要在系统内全部更新。例如，在P2P系统内，缓冲的变化等价于Peer加入或退出系统，这一情况在P2P系统中会频繁发生，因此会带来极大计算和传输负荷。单调性就是要求哈希算法能够避免这一情况的发生。

普通哈希函数不能满足单调性的要求：缩减或扩容会影响到所有元素的移动。为了解决这个问题，一致性哈希算法闪亮登场了。

一致性哈希算法，其实就是把哈希函数可映射的空间固定下来，比如固定为:0~2^32-1，并组织成环的形状。如图3-1所示。

一致性哈希算法采用一种新的方式来解决问题，不再仅仅依赖object本身的哈希值，而且将Cache的配置也进行哈希运算。具体步骤如下：

1. 首先求出每个Cache的哈希值，并将其配置到一个0~2^32-1的圆环区间上。当然闭环的大小不一定是2^32-1，而是可选的。
2. 使用同样的方法求出Object的哈希值，也将其配置到这个圆环上。
3. 从数据映射到的位置开始顺时针查找，将数据保存到找到的第一个Cache节点上。

图3-1四台Cache服务器映射到固定大小的哈希环中。四台机器一共将整个环分成了四部分：(A,B)、 (B,C)、 (C,D)、 (D,A)。

机器A负责存储落在（D,A）范围内的Object数据，机器B负责存储落在（A,B）范围内的数据，依次类推。也就是说，对数据进行Hash时，数据的地址会落在环上的某个点上，数据就存储在该点的顺时针方向上的那台机器上。

对于缩减，如果B机器被移除了，那落在（A,B）范围内的数据全部由C机器来存储，也就只影响到落在（A,B）这个范围内的数据。

同时，扩容也很方便，比如在（C,D）这段环上再添加一台机器E，只需要将D上的一部分数据拷贝到机器E上即可。如图3-2所示。

相比于普通哈希方式，一致性哈希的好处就是：当添加新机器或者删除机器时，不会影响到全部数据的存储，而只是影响到邻近机器上所存储的数据。

四、引入虚拟节点的一致性哈希算法

我们已经知道，添加和删除节点都会影响缓存数据的分布。尽管hash算法具有分布均匀的特性，但是当集群中服务器数量很少时，他们可能在环中的分布并不是特别均匀，进而导致缓存数据不能均匀分布到所有的服务器。比如图3-1中，如果D机器被移除了，Object数据都被映射在环的右半边机器A、B、C上。

引入虚拟节点，可以有效地防止物理节点(机器)映射到哈希环中出现不均匀的情况。使用虚拟节点的思想：为每个物理节点（server）在环上分配100～200个点，这样环上的节点较多，就能抑制分布不均匀。当为cache定位目标server时，会先定位到虚拟节点上，就表示cache真正的存储位置是在该虚拟节点代表的实际物理server上。另外，如果每个实际server节点的负载能力不同，可以赋予不同的权重，根据权重分配不同数量的虚拟节点。

一般，虚拟节点会比物理节点多很多，并可均衡分布在环上，从而可以提高负载均衡的能力。如图4-1（虚拟节点的hash计算可以采用对应节点的 IP 地址加数字后缀的方式）。

引入了虚拟节点后，映射关系就从对象->Cache服务器转换成了对象->虚拟节点-> Cache服务器。查询对象所在Cache服务器的映射关系如图4-2所示。

①如果虚拟节点与物理机器映射得好，某一台物理机器宕机后，其上的数据可由其他若干台物理机器共同分担。

②如果新添加一台机器，它可以对应多个不相邻环段上的虚拟节点，从而使得hash的数据存储得更分散。

五、结束语

在我们的web开发应用中的分布式缓存系统里，哈希算法承担着系统架构上的关键点。使用更合理的哈希算法可以使得多个服务节点间的负载相对均衡，可以最大程度的避免资源的浪费以及服务器过载。使用一致性哈希算法，可以最大程度的降低服务硬件环境变化带来的数据迁移代价和风险。使用更合理的配置策略和算法可以使分布式缓存系统更加高效稳定地为我们整体的应用服务。有代表性的使用了一致性哈希算法的应用系统：

• Memcached，开源的分布式的高速缓存系统;
• Cassandra, 开源分布式Key-Value存储系统;
• Dynamo，开源的三维可视化编程软件。