黑帮分地盘
转自： http://blog.sina.com.cn/s/blog_4e6b346e0100eokj.html
一致性哈希是最近在看MEMCACHE在分布式应用时听到的概念，了解了一下，以下用个我喜欢的方式解释一下：
黑帮抢地盘
四个黑帮想抢一块圆环型的地盘（像halo里的空间站）怎么分呢？大球长说这样，咱们把这个地分成12等分（像时钟），你们把你们的名字笔画模12，得到一个数，你们就住在这个数的区域里，从你的区域按顺时针向前数直到前一个老大的区域都属于你们。于是4位老大算了算，各自占了自己的域名
1 2 3 4 5 6 7 8 9 10 11 12
| 一 | 老大一| 二 | 二 | 三 | 三 | 三 | 三 | 老大三 | 四 | 老大四 |一| ->回到1
---------顺时针----------> ---------顺时针----------> ---------顺时针---------->
四位老大看了看，分是分了，但不平均啊。大球长又说，你们各找三个老二（加上老大一共12个人），咱们再分一次，于是，12个区域被平均分配给了4位老大。新来到此地的居民，也按自己的名字被分别分配到了12个区域，很平均，也算过得踏实
时间不久，又来了两位老大（5不能被12整除，所以加了两个老大）也要抢地盘，这怎么办，还按之前的规则，前面的四位相当于每人分出2块区域给新的老大，而他们之前的区域不变。这样，12块地，又被平分了。而且，四位老大之前点的区域，由于居民已经适应，一切都很平安，跟了新老大的居民也渐渐习惯了新的老大。
以上就是一致性哈希，
老大就是memcache，居民就是数据，就算再加MC，原来的分配表可以得到最大的保持，所以分配是相对稳定的。
各老二就是所谓虚节点,它们实际还是指向各自的老大，即mc节点。它们的作用有两个：
一是提高分配的平均，虚节点越多，越平均，直到多到一个数据一个区域，多平均。但老二越多，维持越困难，运算效率就越低。
二是，如果一个老大很牛B，比别人厉害，，就多找点老二，他分到的地就更多（当然权力越大责任越大）。比如一个MC的容量是2G，其他都是1G（忽略CPU等其他消耗），它理应比别人扛的数据更多。
名字笔画模十二就是用来分配资源的哈希算法，我们估且称其为SUB_HASH
最常见的一致性哈希算法是LASM.FM网站员工写的ketama算法（克他妈,这儿子真丧）它使用的SUB_HASH是MD5。
分布式应用在PHP中的应用：
PHP中主要的MC操作工具有两个
memcache 这个比较常用，功能相对比较简单，是纯粹为PHP应用编写的扩展
Memcached 注意，这个不是memcache daemon！！！是对libmemcache包的封装，内部提供了一致性哈希的封装。使用起来也比较简单
//开启一致性哈希取模（默认）/一致性
$mc->setOption(Memcached::OPT_DISTRIBUTION,Memcached::DISTRIBUTION_CONSISTENT);
//开启ketama算法兼容，注意，打开本算法时，sub_hash会使用KETAMA默认的MD5
$mc->setOption(Memcached::OPT_LIBKETAMA_COMPATIBLE,true);
//设置哈希算法，当不使用KETAMA算法时，这个设置才生效，有几种可选择，不过如果启用ketama，这个选项是没用的//$mc->setOption(Memcached::OPT_HASH , Memcached::HASH_MD5 );
参考：
日本人（MIXI员工）写对于分布式MC应用的说明
http://tech.idv2.com/2008/07/24/memcached-004/
last.fm的工作写人员写的ketama(磕他妈)算法，是一致性算法比较常用的版本
一个哥们对几种字符HASH在一致性中的使用效率统计
http://www.blogjava.net/killme2008/archive/2009/03/10/258838.html
PHP版本的一致性哈希，我就是看这个才明白的。不过算法这东西，用PHP写可能效率还是差点，学习一下就好了。