一致性hash算法

Posted on feb. 2 2014

一致性hash算法 - consistent hashing

您还未登录！|登录|注册|帮助

sparkliang的专栏

#

一致性hash算法 - consistent hashing

分类：算法艺术 2010-02-02 09:19 46510人阅读评论(80) 收藏举报算法 cache object 服务器存储 c

目录(?)[+]

张亮

consistent hashing 算法早在 1997 年就在论文 Consistent hashing and random trees 中被提出，目前在 cache 系统中应用越来越广泛；

1 基本场景

比如你有 N 个 cache 服务器（后面简称 cache ），那么如何将一个对象 object 映射到 N 个 cache 上呢，你很可能会采用类似下面的通用方法计算 object 的 hash 值，然后均匀的映射到到 N 个 cache ；

hash(object)%N

一切都运行正常，再考虑如下的两种情况；

1 一个 cache 服务器 m down 掉了（在实际应用中必须要考虑这种情况），这样所有映射到 cache m 的对象都会失效，怎么办，需要把 cache m 从 cache 中移除，这时候 cache 是 N-1 台，映射公式变成了 hash(object)%(N-1) ；

2 由于访问加重，需要添加 cache ，这时候 cache 是 N+1 台，映射公式变成了 hash(object)%(N+1) ；

1 和 2 意味着什么？这意味着突然之间几乎所有的 cache 都失效了。对于服务器而言，这是一场灾难，洪水般的访问都会直接冲向后台服务器；

再来考虑第三个问题，由于硬件能力越来越强，你可能想让后面添加的节点多做点活，显然上面的 hash 算法也做不到。

有什么方法可以改变这个状况呢，这就是 consistent hashing...

2 hash 算法和单调性

Hash 算法的一个衡量指标是单调性（ Monotonicity ），定义如下：

单调性是指如果已经有一些内容通过哈希分派到了相应的缓冲中，又有新的缓冲加入到系统中。哈希的结果应能够保证原有已分配的内容可以被映射到新的缓冲中去，而不会被映射到旧的缓冲集合中的其他缓冲区。

容易看到，上面的简单 hash 算法 hash(object)%N 难以满足单调性要求。

3 consistent hashing 算法的原理

consistent hashing 是一种 hash 算法，简单的说，在移除 / 添加一个 cache 时，它能够尽可能小的改变已存在 key 映射关系，尽可能的满足单调性的要求。

下面就来按照 5 个步骤简单讲讲 consistent hashing 算法的基本原理。

3.1 环形hash 空间

考虑通常的 hash 算法都是将 value 映射到一个 32 为的 key 值，也即是 0~2^32-1 次方的数值空间；我们可以将这个空间想象成一个首（ 0 ）尾（ 2^32-1 ）相接的圆环，如下面图 1 所示的那样。

circle space

图 1 环形 hash 空间

3.2 把对象映射到hash 空间

接下来考虑 4 个对象 object1~object4 ，通过 hash 函数计算出的 hash 值 key 在环上的分布如图 2 所示。

hash(object1) = key1;

… …

hash(object4) = key4;

object

图 2 4 个对象的 key 值分布

3.3 把cache 映射到hash 空间

Consistent hashing 的基本思想就是将对象和 cache 都映射到同一个 hash 数值空间中，并且使用相同的 hash 算法。

假设当前有 A,B 和 C 共 3 台 cache ，那么其映射结果将如图 3 所示，他们在 hash 空间中，以对应的 hash 值排列。

hash(cache A) = key A;

… …

hash(cache C) = key C;

cache

图 3 cache 和对象的 key 值分布

说到这里，顺便提一下 cache 的 hash 计算，一般的方法可以使用 cache 机器的 IP 地址或者机器名作为 hash 输入。

3.4 把对象映射到cache

现在 cache 和对象都已经通过同一个 hash 算法映射到 hash 数值空间中了，接下来要考虑的就是如何将对象映射到 cache 上面了。

在这个环形空间中，如果沿着顺时针方向从对象的 key 值出发，直到遇见一个 cache ，那么就将该对象存储在这个 cache 上，因为对象和 cache 的 hash 值是固定的，因此这个 cache 必然是唯一和确定的。这样不就找到了对象和 cache 的映射方法了吗？！

依然继续上面的例子（参见图 3 ），那么根据上面的方法，对象 object1 将被存储到 cache A 上； object2 和 object3 对应到 cache C ； object4 对应到 cache B ；

3.5 考察cache 的变动

前面讲过，通过 hash 然后求余的方法带来的最大问题就在于不能满足单调性，当 cache 有所变动时， cache 会失效，进而对后台服务器造成巨大的冲击，现在就来分析分析 consistent hashing 算法。

3.5.1 移除 cache

考虑假设 cache B 挂掉了，根据上面讲到的映射方法，这时受影响的将仅是那些沿 cache B 逆时针遍历直到下一个 cache （ cache C ）之间的对象，也即是本来映射到 cache B 上的那些对象。

因此这里仅需要变动对象 object4 ，将其重新映射到 cache C 上即可；参见图 4 。

remove

图 4 Cache B 被移除后的 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 。

add

图 5 添加 cache D 后的映射关系

4 虚拟节点

考量 Hash 算法的另一个指标是平衡性 (Balance) ，定义如下：

平衡性

平衡性是指哈希的结果能够尽可能分布到所有的缓冲中去，这样可以使得所有的缓冲空间都得到利用。

hash 算法并不是保证绝对的平衡，如果 cache 较少的话，对象并不能被均匀的映射到 cache 上，比如在上面的例子中，仅部署 cache A 和 cache C 的情况下，在 4 个对象中， cache A 仅存储了 object1 ，而 cache C 则存储了 object2 、 object3 和 object4 ；分布是很不均衡的。

为了解决这种情况， 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 ；假设一种比较理想的情况，参见图 6 。

virtual nodes

图 6 引入“虚拟节点”后的映射关系

此时，对象到“虚拟节点”的映射关系为：

objec1->cache A2 ； objec2->cache A1 ； objec3->cache C1 ； objec4->cache C2 ；

因此对象 object1 和 object2 都被映射到了 cache A 上，而 object3 和 object4 映射到了 cache C 上；平衡性有了很大提高。

引入“虚拟节点”后，映射关系就从 { 对象 -> 节点 } 转换到了 { 对象 -> 虚拟节点 } 。查询物体所在 cache 时的映射关系如图 7 所示。

map

图 7 查询对象所在 cache

“虚拟节点”的 hash 计算可以采用对应节点的 IP 地址加数字后缀的方式。例如假设 cache A 的 IP 地址为 202.168.14.241 。

引入“虚拟节点”前，计算 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

5 小结

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://portal.acm.org/citation.cfm?id=258660

http://en.wikipedia.org/wiki/Consistent_hashing

http://www.spiteful.com/2008/03/17/programmers-toolbox-part-3-consistent-hashing/

http://weblogs.java.net/blog/2007/11/27/consistent-hashing

http://tech.idv2.com/2008/07/24/memcached-004/

http://blog.csdn.net/mayongzhan/archive/2009/06/25/4298834.aspx

分享到：

上一篇：Map Reduce – the Free Lunch is not over?
下一篇：Hadoop分布式文件系统：架构和设计要点查看评论

70楼 Spark-zh 2013-07-09 20:27发表 [回复] [引用] [举报]感谢楼主的讲解，很明了。69楼 thomastianqq 2013-07-09 17:26发表 [回复] [引用] [举报]单调性是指如果已经有一些内容通过哈希分派到了相应的缓冲中，又有新的缓冲加入到系统中。哈希的结果应能够保证原有已分配的内容可以被映射到新的缓冲中去，而不会被映射到旧的缓冲集合中的其他缓冲区。 Hi,LZ，文中关于单调性的阐述是错误的。正确的应该是：哈希的结果应能够保证原有已分配的内容可以被映射到原有的或者新的缓冲中去，而不会被映射到旧的缓冲集合中的其他缓冲区。68楼 lgfeng218 2013-06-26 11:59发表 [回复] [引用] [举报]通俗易懂67楼 midstr 2013-06-18 14:54发表 [回复] [引用] [举报]通俗易懂，顶一个哈66楼 zxh87 2013-06-03 15:18发表 [回复] [引用] [举报]很好，又看了一次！65楼 fanjiabing 2013-05-22 16:00发表 [回复] [引用] [举报]写的很好!64楼 mydreamongo 2013-05-20 16:27发表 [回复] [引用] [举报]讲的很好。。63楼 bingmo01 2013-05-17 00:31发表 [回复] [引用] [举报]很给力。基本上看懂62楼 perfectshark 2013-05-11 13:26发表 [回复] [引用] [举报]浅显易懂！61楼 pymqqq 2013-05-04 20:18发表 [回复] [引用] [举报]非常好，谢谢楼主！学习了！60楼草原面朝大海 2013-04-30 22:59发表 [回复] [引用] [举报]假设我们已经在cache A中存储了一个object 1，然后不巧的是cacheA在之后被删除了，这时候我们需要访问object1，难道再一次进行hash，将object1存到下一个cache中吗？如果上述成立，问题是我们如何将object1从cacheA中读取出来，因为在实际情况中，很有可能是cacheA是一下子坏掉了。Re: 总版主 2013-05-07 17:08发表 [回复] [引用] [举报]回复zhaowenchaofang：我觉得可以把OBJ存三份，分别再顺时针往后三个cache中，这样就算cache瞬间崩溃了，那么重新复制一份备份保证有三个备份即可，加CACHE也不是问题，剪切一部分obj到新增的cache上即可。59楼 sc274491910 2013-04-19 18:07发表 [回复] [引用] [举报]加入了虚拟节点后，出现加减节点的情况，这种情况怎么权衡呢？58楼 r4t5y6u7 2013-04-07 13:46发表 [回复] [引用] [举报]讲的太好了，清晰明了，浅显易懂57楼轻舞飘扬 2013-03-30 17:09发表 [回复] [引用] [举报]非常好56楼 scncpb 2013-03-27 15:13发表 [回复] [引用] [举报]作者写的和老外写的一样通俗易懂55楼 mail_f5 2013-02-21 17:55发表 [回复] [引用] [举报]图文并茂，不错54楼 zhouxiaoqingelse 2013-02-20 18:18发表 [回复] [引用] [举报]非常清晰，感谢。53楼 sight_ 2013-01-22 11:08发表 [回复] [引用] [举报]楼主，有个问题请教一下,这个算法是如何保证后面添加的服务器能承担更多的任务，我应该如何控制"更多"这个量。例如我的服务器是分等级的，如何根据这个等级来控制hash到它上面的任务。Re: sparkliang 2013-01-22 13:57发表 [回复] [引用] [举报]回复sight：首先新加入的节点，将会把后继节点的部分数据分流给自己；后面的新数据将会根据hash结果，无区别的分配到各节点上；从我了解的来看，hash本身解决不了你说的分等级问题；hash环上的所有节点都是无差别对待的。不过对于引入虚拟节点的hash环来说，一个方法就是根据优先级来设置vnode的个数，这样也可以做到能力强的节点承担更多数据的结果，从统计意义上，实际上可能略有偏差。52楼林大虫 2012-12-24 13:44发表 [回复] [引用] [举报]讲得很清晰啊51楼 dream1baby 2012-12-18 11:32发表 [回复] [引用] [举报]赞，学习了！50楼 blueskyltt 2012-12-03 18:30发表 [回复] [引用] [举报]楼主讲的很浅显易懂，赞49楼 syzcch 2012-11-12 09:11发表 [回复] [引用] [举报]讲的浅显易懂48楼 jixianwu2009 2012-11-05 10:03发表 [回复] [引用] [举报]清晰明了47楼月亮床 2012-10-23 18:27发表 [回复] [引用] [举报]受益非浅46楼 ju136 2012-10-16 09:32发表 [回复] [引用] [举报]good45楼 yangqisheng 2012-10-07 13:42发表 [回复] [引用] [举报]楼主写的很好，一看就懂。我非常喜欢图文并茂的说明。谢谢楼主。44楼 lcw918110 2012-09-05 10:14发表 [回复] [引用] [举报]3.5.1中，这时受影响的将仅是那些沿 cache B 逆时针遍历直到下一个 cache （ cache C ）之间的对象。其中的cache C如图所示应为 A。请楼主检查下。谢谢楼主的博文。Re: sparkliang 2012-09-05 15:42发表 [回复] [引用] [举报]回复lcw918110：赞，看的很仔细；逆时针是在A上，顺时针落在C上。Re: lcw918110 2012-09-07 11:40发表 [回复] [引用] [举报]回复sparkliang：楼主，关于cache中使用的hash算法，楼主知道的还有哪些？学习学习。43楼 renjunyi6666 2012-08-23 11:38发表 [回复] [引用] [举报]受益!谢谢42楼 Myxiao7 2012-08-17 21:05发表 [回复] [引用] [举报]学习了41楼 skywhsq1987 2012-08-02 10:35发表 [回复] [引用] [举报]ding40楼 m_vptr 2012-08-02 09:25发表 [回复] [引用] [举报]好文章39楼 boYwell 2012-08-01 09:08发表 [回复] [引用] [举报]文笔很好，赞一个38楼 YcdoiT 2012-07-26 16:40发表 [回复] [引用] [举报]顶一个，我这种悟性的都能看懂了37楼大城小爱 2012-07-06 19:02发表 [回复] [引用] [举报]讲得很清晰，不错不错36楼 brucest0078 2012-06-18 11:44发表 [回复] [引用] [举报]关于virtualNode 有一些问题，因为你的key在存储的时候可以这样，但是读取的时候只有原生的key去相关的内容，而不会把vNode的ip之类的带进去，所以这里只是理论呢还是已经有实践过？表示怀疑。Re: sparkliang 2012-06-18 13:52发表 [回复] [引用] [举报]回复BruceXX：读取的时候，关vnode什么事呢。读取者事先是不知道key存在那个节点上的。35楼 Honeybb 2012-06-12 09:44发表 [回复] [引用] [举报]最近在看这方面的文章，很迷茫。楼主，分布式网络关于资源定位与一致性哈希算法和paxos算法的关系，请楼主明示啊！Re: sparkliang 2012-06-18 13:52发表 [回复] [引用] [举报]回复Honeybb：一致性哈希算法和paxos算法，没什么关联34楼 laigege 2012-06-02 09:48发表 [回复] [引用] [举报]楼主是好人33楼 dengjm_2011 2012-05-23 16:41发表 [回复] [引用] [举报]很不错的文章，简单明了！32楼 zcl198715 2012-04-29 21:34发表 [回复] [引用] [举报]分析的很好！赞一个！31楼 leonkyd 2012-04-21 10:28发表 [回复] [引用] [举报]非常好的技术文章，赞一个30楼 wumucheng 2012-04-06 20:04发表 [回复] [引用] [举报]讲得非常清晰，赞！29楼 lqbbduck 2012-03-30 00:51发表 [回复] [引用] [举报]分析得很好28楼 TCCaiWQ 2012-03-15 16:54发表 [回复] [引用] [举报]简洁明了27楼 RunZhi1989 2012-03-05 17:22发表 [回复] [引用] [举报]赞，我看英文维基百科一直没看懂，博主的东西真是简洁明了。赞赞赞！26楼 libobo5954451 2012-02-10 18:02发表 [回复] [引用] [举报]非常好25楼 humingchun 2012-01-02 19:44发表 [回复] [引用] [举报]偶竟然看明白了说明写的很清楚呵呵24楼 jmx_zhidai 2011-11-24 16:31发表 [回复] [引用] [举报]写的非常明白，赞一个！！！23楼 yfk 2011-11-16 15:27发表 [回复] [引用] [举报]很赞的文章谢谢lZ22楼南山道人 2011-11-16 12:47发表 [回复] [引用] [举报]顶，非常感谢！21楼 zhaopeinow 2011-10-20 17:52发表 [回复] [引用] [举报]顶20楼 lbqBraveheart 2011-10-12 15:03发表 [回复] [引用] [举报]顶19楼向良玉 2011-10-11 13:59发表 [回复] [引用] [举报]好文章18楼 xgtogd 2011-09-25 23:26发表 [回复] [引用] [举报]很好17楼 fairywell 2011-09-12 21:54发表 [回复] [引用] [举报]好文，图文并茂，让我一下就看明白了：） Mark并收藏~~16楼 parakpurple 2011-08-29 17:09发表 [回复] [引用] [举报]写的太棒了深入浅出15楼 bokee 2011-08-06 16:12发表 [回复] [引用] [举报]很清晰啊，想问下你的图是用什么工具画的？Re: sparkliang 2011-08-30 09:19发表 [回复] [引用] [举报]回复bokee：visio啊14楼 dahai_888 2011-07-16 17:12发表 [回复] [引用] [举报]不得了。13楼 wayon_yang 2011-05-30 11:49发表 [回复] [引用] [举报][e01] 英语不好之前没看懂现在清晰多了12楼 laoyi19861011 2011-05-13 20:45发表 [回复] [引用] [举报]这么好的一篇文章居然没有推荐，csdn的编辑干嘛吃去了11楼 chemila 2011-03-31 17:45发表 [回复] [引用] [举报][e01]10楼 liomao 2011-03-29 09:13发表 [回复] [引用] [举报][e10]9楼 xunujNext 2011-02-17 22:28发表 [回复] [引用] [举报]不得不[e01]8楼 printfabcd 2010-12-17 14:51发表 [回复] [引用] [举报]请问虚拟节点，怎么保证均匀分布在，那个环上呢？？O(∩∩)O~Re: sparkliang 2011-03-11 15:31发表 [回复] [引用] [举报]回复 printfabcd：这就要由hash算法来保证了，均匀分布是概率上的均匀，当虚拟节点足够时，就能保证大概均匀了。7楼 ccnuliu 2010-06-23 00:01发表 [回复] [引用] [举报]假如cache通过hash函数计算出的值和 object通过hash函数计算出来的值是同一个hash值怎么办？那object应该指向哪个cache?Re: sparkliang 2010-06-24 09:41发表 [回复] [引用] [举报]回复 ccnuliu：如果碰巧相同，就是指向具有相同hash值的cache。选择的原则是cache.hash >= object.hash；（当然在环的衔接处是例外）Re: a43350860 2011-03-05 18:27发表 [回复] [引用] [举报]回复 sparkliang：假设我给hash环开启一扇大门，所有的值进来都必须经过这一扇门，那么我只要在这一扇大门里加一个hash关卡，我不关心你传进来的值是什么类型，是什么形态，我都是统一做hash运算，然后再分配到相应的节点上面去。6楼 ccnuliu 2010-06-23 00:01发表 [回复] [引用] [举报]问你一个问题加入cache通过hash函数计算出的值和 object通过hash函数计算出来的值是同一个hash值怎么办？那object应该指向哪个cache?5楼 chengqianl 2010-06-02 16:53发表 [回复] [引用] [举报]收益了4楼 specific_intel 2010-05-12 16:26发表 [回复] [引用] [举报][e01] 非常清晰，谢谢！3楼 yayaaishenghuo 2010-03-09 13:46发表 [回复] [引用] [举报]讲得太好了2楼匿名用户 2010-02-22 10:06发表 [回复] [引用] [举报][e10]1楼匿名用户 2010-02-22 10:05发表 [回复] [引用] [举报][e01] 您还没有登录,请[登录]或[注册]