一致性哈希算法在1997年由麻省理工学院提出(参见扩展阅读[1]),设计目标是为了解决因特网中的热点(Hot spot)问题,初衷和CARP十分类似。一致性哈希修正了CARP使用的简单哈希算法带来的问题,使得DHT可以在P2P环境中真正得到应用。
基本场景
现在互联网分布式系统应用越来越普遍,不可避免的要碰到集群中单节点破坏后系统负载的问题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都失效了。对于服务器而言,这是一场灾难,洪水般的访问都会直接冲向后台服务器;比如你N个cache服务器(后面简cache),那么如何将一个对象object映射到N个cache上呢,你很可能会采用类似下面的通用方法计算object的hash值,然后均匀的映射到到N个cache;有什么方法可以改变这个状况呢,这就是consistent
hashing...
Hash算法的一个衡量指标是单调性(Monotonicity),定义如下:
再来考虑第三个问题,由于硬件能力越来越强,你可能想让后面添加的节点多做点活,显然上面的hash算法也做不到。
单调性是指如果已经有一些内容通过哈希分派到了相应的缓冲中,又有新的缓冲加入到系统中。哈希的结果应能够保证原有已分配的内容可以被映射到新的缓冲中去,而不会被映射到旧的缓冲集合中的其他缓冲区。
容易看到,上面的简单hash算法hash(object)%N难以满足单调性要求。
但是一致性哈希的路由算法尚有不足之处。在查询过程中,查询消息要经过O(N)步(O(N)表示与N成正比关系,N代表系统内的节点总数)才能到达被查询的节点。不难想象,当系统规模非常大时,节点数量可能超过百万,这样的查询效率显然难以满足使用的需要。换个角度来看,即使用户能够忍受漫长的时延,查询过程中产生的大量消息也会给网络带来不必要的负荷。
分享到:
相关推荐
对已有的负载平衡的改进算法,通过一致性哈希算法,负载平衡更加的有效。
一致性哈希算法
一致性哈希算法,广泛应用于分布式计算,C版实现,属于分布式服务器管理的核心算法。
#资源达人分享计划#
Ketama算法是一致性hash算法的一个优秀实现。增删节点后数据命中率及均分率都很高。
哈希算法 基于C# 实现的一致性哈希算法
运行平台:VS 2019 一致性哈希算法演示项目,演示新增节点key分布情况;移除节点key分布情况! C#,C#,C#.......
基于动态转移的分布式缓存系统一致性哈希算法改进,张昊,张永军,近年来,随着大数据与分布式集群的广泛应用,一致性哈希算法在分布式缓存系统的负载均衡中得到了广泛的应用。一致性哈希算法虽然
#资源达人分享计划#
一致性哈希算法的php版,希望能帮到phper了解一致性哈希
#资源达人分享计划#
白话解析:一致性哈希算法1
一致性哈希算法用来解决分布式系统中热点接入与删除管理,是目前公认的最有效的算法,该文档图文并茂,详细解释了这一算法。
一致性哈希算法应用及优化(最简洁明了的教程)
#资源达人分享计划#
#资源达人分享计划#
在分布式系统中,常常需要使用缓存,而且通常是集群,访问缓存和添加缓存都需要一个 hash 算法来寻找到合适的 Cache 节点。但,通常不是用取余hash,而是使用我们今天的主角—— 一致性 hash 算法。
Mycat一致性哈希分片算法.zip Mycat一致性哈希分片算法.zip Mycat一致性哈希分片算法.zip Mycat一致性哈希分片算法.zip Mycat一致性哈希分片算法.zip
Mycat一致性哈希分片算法1