consistent hashing由来?
最初由Karger等人设计。在麻省理工学院用作分布式缓存,现在已经扩大到其他领域。
它被设计来解决hash的什么问题?
假设有m个对象需要被映射到n个node上,简单hash就求余映射hash(object)%n->node,就大致均匀的分布到n个node上了。可是问题在于如果n发生变化(多了或者少了),就必须重新计算保存对象存放到node,这代价未免有点大。consistent hashing就是用来解决这个问题。
一般hash的问题在于,映射关系计算是个死的东西。所以consistent hashing就是要把对象和这个slot和映射关系搞活一点。那么具体是怎么搞活的?
假设有个ring(环),hash(object)和hash(node)都在投影到这个ring上。
映射关系变成:hash(object)->hash(node),
->(映射关系)是:查找用的是在ring上顺时针查找,找到最近的hash(node),建立映射关系。
图大概就是这样子的:
如果有个node被咔嚓剪了或者扑哧多了一个,想象下hash(object)像精子一样顺时针沿着ring游动,碰到最近的hash(node)就结合了。基本上只要很少的object需要重新来hash(object) -> hash(node)。
图看着挺好看挺均匀挺和谐的,可是如果我只有两个node,而且好死不死,hash(node)后的值在ring上又紧挨着。。咋整?
问题问的真好
,node少不要怕,在天朝,啥都不知道,造假还有不知道的吗?对,就是造假,明明只有2个node,我们就整他100~1000个(假的成本毕竟低么),如果你胆大不怕查,你也可以多造点。真的node就叫node,假的就叫virtual node(简称vnode)。然后再维护个vnode->node就可以了。
vnode搞越多,越均匀,越好么?
由于查找object所在的vnode需要O(n)步(n为vnode个数),运气不好,查到最后一个才找到,那就悲催了。
consistent hashing可以用来干嘛呢?
大家都知道的分布式cache中常用这个算法。
我学这个算法不是想用来搞cache,而是我想做个的分布式任务调度系统,用来分发任务到zookeeper的znode上。这样我加个znode或者挂掉个znode,也不用怕了。似乎和consistent hashing解决的典型问题是一样样的。
已有 0 人发表留言,猛击->> 这里<<-参与讨论
ITeye推荐