黑帮分地盘

转自： 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(磕他妈)算法，是一致性算法比较常用的版本

http://cn.last.fm/user/RJ/journal/2007/04/10/rz_libketama_-_a_consistent_hashing_algo_for_memcache_clients

 

一个哥们对几种字符HASH在一致性中的使用效率统计

http://www.blogjava.net/killme2008/archive/2009/03/10/258838.html

PHP版本的一致性哈希，我就是看这个才明白的。不过算法这东西，用PHP写可能效率还是差点，学习一下就好了。