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

我们从一个简单的缓存应用来谈谈HASH一致性算法，首先如果我们有3台Redis缓存服务器：

redis_1：第一台缓存redis
redis_2：第二台缓存redis
redis_3：第三台缓存redis

如果现在我们有一个门户网站，需要将相关文章缓存到上述三个Redis中，那么我们可以通过文章的唯一标志Hash值除以Redis服务器台数所得到的余数来存放到相应的Redis中，公式如下：

hash(文章唯一标识) % count(redis_*)               

如（为了便于大家看清楚，这里hash值这里是假设状态）：
     hash(1) % 3 = 1
     hash(2) % 3 = 2
     hash(3) % 3 = 0
     hash(4) % 3 = 1
     hash(5) % 3 = 2
     hash(6) % 3 = 0
     ...

  上面大家可能有疑问，如果我们要缓存的内容没有ID呢？怎么办，其实大家不用着急，我们可以通过唯一的标识通过Hash算法得到一个整数，然后通过上述的公式计算得到缓存服务器。

  所以我们可以将所有文章全部缓存到上面的三台Redis服务器中，那么现在问题来了，如果我们现在服务器增加到5台Redis，那么这时候就会出现很多缓存未命中的情况，如：

     hash(1) % 5 = 1
     hash(2) % 5 = 2
     hash(3) % 5 = 3 （未命中）
     hash(4) % 5 = 4 （未命中）
     hash(5) % 5 = 0 （未命中）
     hash(6) % 5 = 1 （未命中）
     ... (还有更多的没有命中)

如果出现上述增加了服务器后出现大面积缓存没有命中的情况后，那么很多请求压力就会直接打到后端数据库上，这样就可能造成严重的后果。那么我们能否有解决方案呢？

答案是肯定的，首先我们将一个圆上均匀分布0~2³²每个值，然后我们将每个Redis分配一个固定的值，固定到对应的点上【如下图】：

现在只要有一个文章唯一标识通过Hash算法得到的数值，就根据得到的数值按照顺时针的方向去找下一个Redis的hash值，找到就存放到该Redis上。如：

redis_1对应的值：10000
redis_2对应的值: 100000
redis_3对应的值: 1000000

假如：hash(文章1唯一标识)=100，存到redis_1；
假如：hash(文章2唯一标识)=20000，存到redis_2；
假如：hash(文章3唯一标识)=500000，存到redis_3；

这样一来，我们就将所有文章分摊到三台Redis服务器上，这时候如果我们增加第四台和第五台服务器，如下：

当一部分缓存到Redis1和redis2上的数据不会被命中，有部分数据会命中到redis_4和redis_5上，这样就能保证我们不会出现大面积数据未命中的情况。

如果我们出现下面的一种hash节点：

这样就会出现更多的缓存在redis_1上面，redis_2和redis_3上存的缓存非常上，这种情况就被称为hash倾斜，要想解决Hash倾斜，就需要给每个节点增加较多的虚拟节点，如下图：

这样就可以实现缓存均匀分布到不同节点上了。

  考虑到分布式系统每个节点都有可能失效，并且新的节点很可能动态的增加进来，如何保证当系统的节点数目发生变化时仍然能够对外提供良好的服务，这是值得考虑的，尤其实在设计分布式缓存系统时，如果某台服务器失效，对于整个系统来说如果不采用合适的算法来保证一致性，那么缓存于系统中的所有数据都可能会失效（即由于系统节点数目变少，客户端在请求某一对象时需要重新计算其hash值（通常与系统中的节点数目有关），由于hash值已经改变，所以很可能找不到保存该对象的服务器节点），因此一致性hash就显得至关重要，良好的分布式cahce系统中的一致性hash算法应该满足以下几个方面：

平衡性(Balance)

平衡性是指哈希的结果能够尽可能分布到所有的缓冲中去，这样可以使得所有的缓冲空间都得到利用。很多哈希算法都能够满足这一条件。

单调性(Monotonicity)

单调性是指如果已经有一些内容通过哈希分派到了相应的缓冲中，又有新的缓冲区加入到系统中，那么哈希的结果应能够保证原有已分配的内容可以被映射到新的缓冲区中去，而不会被映射到旧的缓冲集合中的其他缓冲区。简单的哈希算法往往不能满足单调性的要求，如最简单的线性哈希：x = (ax + b) mod §，在上式中，P表示全部缓冲的大小。不难看出，当缓冲大小发生变化时(从P1到P2)，原来所有的哈希结果均会发生变化，从而不满足单调性的要求。哈希结果的变化意味着当缓冲空间发生变化时，所有的映射关系需要在系统内全部更新。而在P2P系统内，缓冲的变化等价于Peer加入或退出系统，这一情况在P2P系统中会频繁发生，因此会带来极大计算和传输负荷。单调性就是要求哈希算法能够应对这种情况。

分散性(Spread)

在分布式环境中，终端有可能看不到所有的缓冲，而是只能看到其中的一部分。当终端希望通过哈希过程将内容映射到缓冲上时，由于不同终端所见的缓冲范围有可能不同，从而导致哈希的结果不一致，最终的结果是相同的内容被不同的终端映射到不同的缓冲区中。这种情况显然是应该避免的，因为它导致相同内容被存储到不同缓冲中去，降低了系统存储的效率。分散性的定义就是上述情况发生的严重程度。好的哈希算法应能够尽量避免不一致的情况发生，也就是尽量降低分散性。

负载(Load)

负载问题实际上是从另一个角度看待分散性问题。既然不同的终端可能将相同的内容映射到不同的缓冲区中，那么对于一个特定的缓冲区而言，也可能被不同的用户映射为不同的内容。与分散性一样，这种情况也是应当避免的，因此好的哈希算法应能够尽量降低缓冲的负荷。

平滑性(Smoothness)

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