首先看一个最简单的hash函数
通过调用simple_hash对5、8、9三个值进行哈希,结果如下:
在实际应用中,HASH_RANGE是代表着一定的实际意义的,比如机器的台数,本文就以机器台数为例。当HASH_RANGE=5的时候,机器节点编号为0 ~ 4,simple_hash(5) = 0 表示key为5的数据将被放置到0号机器节点中。查询的时候,只需要将key 5进行hash得到节点号0,则可以找到节点,从而读出数据。
就这样,系统运行了一段时间,数据来来去去,天下太平。
有一天,系统中增加了一台新机器,这个时候HASH_RANGE = 6,我们会发现,5、8、9三个值的哈希值已经改变了!这意味着什么呢?在新的函数看来,原来5、8、9三个值被分配到了错误的机器上。如果有人用key=5来查询,则返回的节点此时变成了5,而不是0,显然,这次查询会失败。因为数据还在0号节点上呢!
在教科书上,HASH_RANGE被称作哈希因子。
如何才能保证机器台数的增加的情况下还等读到正确的数据呢?最简单的方法是不用机器台数作为哈希因子
,而是选取一些不变量为哈希因子。Consistency Hash就是在这种指导思想下产生的。
先通过下图看看一致性哈希的基本思想:
机器数(node)不再作为哈希因子,而是通过一个通用的hash函数哈希到[0, 2^32)的范围上,所有的key也被哈希到这个范围上,然后顺着数轴环“往前”找node,首先找到的那个就是key要存放到的机器。
Consistency Hash并不完美。当系统中有新机器加入的时候,部分key还是需要重新分布,如下图。但是,通用的hash函数还是用原来那个。从效果上看,Consistency Hash比普通hash的影响要小得多。
更多一致性哈希的内容,感兴趣的朋友可以到维基百科上阅读
。
在普通hash函数中,哈希和存储是紧耦合的,而在Consistency Hash中,哈希和存储被分离,首先通过hash来确定大致范围,再通过向前寻址的方式找到最近的节点以存储。
Hash函数存在的本质问题并没有解决,Consistency Hash只是弱化了Hash函数在算法中的地位,引入一些新思路来解决问题而已。
Remarks:
1. 文中图片截自:Memcached全面剖析
p28
2. 为了避免数据都hash到很近的地方,Consistency Hash还使用了虚拟节点的概念。即一个物理节点可能被虚拟成200个虚拟节点,并且均匀分布在环上。这种思路也很巧妙,值得学习。
分享到:
相关推荐
一致性哈希算法
对已有的负载平衡的改进算法,通过一致性哈希算法,负载平衡更加的有效。
一致性哈希算法,广泛应用于分布式计算,C版实现,属于分布式服务器管理的核心算法。
一致性哈希算法的php版,希望能帮到phper了解一致性哈希
#资源达人分享计划#
Mycat一致性哈希分片算法.zip Mycat一致性哈希分片算法.zip Mycat一致性哈希分片算法.zip Mycat一致性哈希分片算法.zip Mycat一致性哈希分片算法.zip
NULL 博文链接:https://blackbeans.iteye.com/blog/1129256
24一致性哈希:如何高效地均衡负载?1
#资源达人分享计划#
Mycat一致性哈希分片算法1
运行平台:VS 2019 一致性哈希算法演示项目,演示新增节点key分布情况;移除节点key分布情况! C#,C#,C#.......
* 有两种方案,第一种普通hash分布,第二种一致性哈希分布 * * 普通hash分布 * 首先将key处理为一个32位字符串,取前8位,在经过hash计算处理成整数并返回,然后映射到其中一台服务器 * $servers[$this->...
哈希算法 基于C# 实现的一致性哈希算法
基于动态转移的分布式缓存系统一致性哈希算法改进,张昊,张永军,近年来,随着大数据与分布式集群的广泛应用,一致性哈希算法在分布式缓存系统的负载均衡中得到了广泛的应用。一致性哈希算法虽然
#资源达人分享计划#
白话解析:一致性哈希算法1
Ketama算法是一致性hash算法的一个优秀实现。增删节点后数据命中率及均分率都很高。
本文将会从实际应用场景出发,介绍一致性哈希算法(Consistent Hashing)及 其在分布式系统中的应用。首先本文会描述一个在日常开发中经常会遇到的问题 场景,借此介绍一致性哈希算法以及这个算法如何解决此问题;接...
一致性哈希算法应用及优化(最简洁明了的教程)