最近在看关于NoSQL的资料，发现总是提到这个东西。这东西吧，非常简单，数据结构讲过，但是那时候一直搞不懂这是个什么玩意儿，这次结合实际环境，终于理解了这个东西。
首先，看问题和背景：
我们知道，hash算法实际上是将一个值映射到另一个值的过程，而一致性哈希则具有自己的两个特点，比如类似的MD5算法，看以看成一种32位的哈希算法，将一个字符串对应到一个32位的字符串中。我们还是看问题，假设现在需要一个负载均衡的算法，要把流量均匀的分布到后端的Cache服务器上面去。最常用的做法，当然是取用户的cookie，取服务器（n）的模，这样基本上能保持流量均分，而且能够保证用户每一次访问能够落入到同一台机器。本来也相安无事，但是，如果摘掉一台机器呢？（一台机器down机是经常的事情），或者是加1台机器，那么本来的n值发生了变化，因此所有的流量命中的机器也全部发生了变化。
eg: 本来11的客户，一共有5台cache机器，那么11%5=1，会落到第一台机器上，但是如果少一台，变成4，则结果会变成11%4=3，这样，所有的值都会改变。如此一来，整个系统瞬间所有的cache将失效，系统会雪崩。注：此处的cache可以想象成memcache，各个机器间的cache无法共享，所以需要人为的制定clent连接到哪台机器。
问题交代清楚了，而一致性哈希就是为解决这一类问题而生的，他的原理其实非常简单。
他有两个特征：
hash 算法和单调性
考虑通常的 hash 算法都是将 value 映射到一个 32 为的 key 值，也即是 0~2^32-1 次方的数值空间；我们可以将这个空间想象成一个首（ 0 ）尾（ 2^32-1 ）相接的圆环，如下面图 1 所示的那样。
每一个Key对应的hash地址，是这个圆上的一个点（2^32-1的其中一个），这是步骤一。
用个别人的图举个例子：
接下来考虑 4 个对象 object1~object4 ，通过 hash 函数计算出的 hash 值 key 在环上的分布如图 2 所示。
hash(object1) = key1;
… …
hash(object4) = key4;
此处对象，类似我们的客户端
他们分布在圈圈上的位置如图。
Consistent hashing 的基本思想就是将对象和 cache 都映射到同一个 hash 数值空间中，并且使用相同的 hash 算法。
假设当前有 A,B 和 C 共 3 台 cache ，那么其映射结果将如图 3 所示，他们在 hash 空间中，以对应的 hash 值排列。
hash(cache A) = key A;
… …
hash(cache C) = key C;
此处为步骤二。这里，我们可以把cache想象成我们的服务器，可以用他的ip或者是机器名作为hash的key值
现在 cache 和对象都已经通过同一个 hash 算法映射到 hash 数值空间中了，接下来要考虑的就是如何将对象映射到 cache 上面了。
在这个环形空间中，如果沿着顺时针方向从对象的 key 值出发，直到遇见一个 cache ，那么就将该对象存储在这个 cache 上，因为对象和 cache 的 hash 值是固定的，因此这个 cache 必然是唯一和确定的。这样不就找到了对象和 cache 的映射方法了吗？！
依然继续上面的例子（参见图 3 ），那么根据上面的方法，对象 object1 将被存储到 cache A 上； object2 和 object3 对应到 cache C ； object4 对应到 cache B ；
注意，当服务器发生变动的时候，
考虑假设 cache B 挂掉了，根据上面讲到的映射方法，这时受影响的将仅是那些沿 cache B 逆时针遍历直到下一个 cache （ cache C ）之间的对象，也即是本来映射到 cache B 上的那些对象。
因此这里仅需要变动对象 object4 ，将其重新映射到 cache C 上即可；参见图 4 。
也就是说，当B节点挂掉的时候，其实影响的仅仅是Object4这个对象的缓存，就是cacheA和cacheB之间的对象。如果Cache够多，那么影响的将会更少。后面会讲到使用虚拟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 。
可以看到，当我们加入CacheD的时候，影响的仅仅是他上一个节点B和D之间的对象，一言蔽之就是：无论是加入还是减少，只要改变了，那么影响的就是当前改动的节点与他上一个节点之间的这些对象（以前听老师讲，怎么都不理解，原来是缺少例子啊）这个就是他的单调性，只影响那一小块，其他的不变，很单调吧。。。。
考量 Hash 算法的另一个指标是平衡性 (Balance) ，定义如下：
平衡性就是讲，流量要尽可能的均匀的分配到各个机器上，我们从图中看到，A、B、C之间的弧度，长短不一的，那么怎么提高呢？答案是将其切的更碎
为了解决这种情况， 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 ；
引入“虚拟节点”前，计算 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
Consistent hashing 的基本原理就是这些，具体的分布性等理论分析应该是很复杂的，不过一般也用不到。
http://weblogs.java.net/blog/2007/11/27/consistent-hashing 上面有一个 java 版本的例子，可以参考。
http://blog.csdn.net/mayongzhan/archive/2009/06/25/4298834.aspx 转载了一个 PHP 版的实现代码。
http://www.codeproject.com/KB/recipes/lib-conhash.aspx C语言版本
感谢原作者的文章，让我受益：http://blog.csdn.net/sparkliang/article/details/5279393
感谢wordpress的自动保存功能，要不然就没有这些东西了