本文涉及:普通哈希算法存在的问题,分布式系统的哈希一致性算法,哈希一致性算法中的数据倾斜问题
我们知道,在分布式系统中当数据量无法使用单机进行存储时,最简单粗暴的方法就是水平扩展:加机器,搞集群。
然而所有的集群模式都会面临一个数据存放的问题:即一个集群有多台机器,我们怎么知道这次的数据应该放在哪个机器上呢?这次的数据放到了一台机器上我下一次读取的时候能保证还来这台机器上找么?
假如当前我们有一个Redis集群,共5个节点对外提供服务
◆
Hash取模
◆
最开始的解决方案就是首先给5台机器分别编号:1、2、3、4、5
当对一个数据进行操作时首先计算key的hash然后对机器数量5进行取余,得出的余数就是需要放置的机器的编号。
1
|
key应该放置的机器编号=hash(key) % 5
|
这个方案完美解决了文章开始提到的两个问题,但是大家都知道,程序员的智力是没有上限,当然主要是因为问题逼的:
如果其中一台机器宕机了、或者新增了服务器,则整个集群所有的数据都需要重新计算位置,这个过程简直不要太痛苦。
◆
一致性Hash
◆
既然出现了问题,聪明的程序员很快就想到了解决方案:一致性哈希算法
如上图所示,程序员们把所有的机器模拟成了一个虚拟的哈希环,然后设计了一个空间的大小,这个空间被平均分配到了所有机器的中间。当需要对一个key操作时,同样进行进行取模运算,只不过这里的模不再是机器数量而是空间大小,然后根据得出的结果,去离结果顺时针最近的一个节点上操作key。
例如:当一个集群有5个节点、空间大小被设置为500的时候,当要设置一个key的hash值为601时。首先会对key的hash进行取余,601%500 结果为101,然后根据结果101顺时针查找最近的节点找到了192.168.1.3。
同理,设置另一个key,先算hash,假如是888,则首先取余得出结果388然后得出节点192.168.1.5。
使用Hash一致性的时候如果遇到了节点宕机或者新增服务器的情况下可就简单的多了:
节点宕机,只需要把宕机节点的数据迁移到顺时针的下一个服务器上
新增节点仅仅需要迁移逆时针的第一台服务器的部分数据
◆
数据倾斜
◆
一致性哈希算法完美的解决了普通的哈希算法的问题,但是呢,没有十全十美的算法,一致性哈希算法同样存在一些问题。由上方的示例我们可以看出来,当集群内扩缩容次数多了以后,数据很容易出现不均匀的情况,有的机器负责了大半的空间,而有的机器仅仅负责一点点空间。这个问题有一个名词,数据倾斜:
为了解决数据倾斜问题,一致性哈希算法引入了虚拟节点机制,即将每一个服务节点都计算为多个虚拟节点,避免单个节点持有连续的大空间:
相关推荐
基于动态转移的分布式缓存系统一致性哈希算法改进,张昊,张永军,近年来,随着大数据与分布式集群的广泛应用,一致性哈希算法在分布式缓存系统的负载均衡中得到了广泛的应用。一致性哈希算法虽然
#资源达人分享计划#
一致性哈希算法用来解决分布式系统中热点接入与删除管理,是目前公认的最有效的算法,该文档图文并茂,详细解释了这一算法。
#资源达人分享计划#
#资源达人分享计划#
#资源达人分享计划#
#资源达人分享计划#
在分布式系统中,常常需要使用缓存,而且通常是集群,访问缓存和添加缓存都需要一个 hash 算法来寻找到合适的 Cache 节点。但,通常不是用取余hash,而是使用我们今天的主角—— 一致性 hash 算法。
一致性哈希算法是分布式系统中常用的算法,为什么要用这个算法? 比如:一个分布式存储系统,要将数据存储到具体的节点(服务器)上, 在服务器数量不发生改变的情况下,如果采用普通的hash再对服务器总数量取模的...
算法分类:排序算法(如冒泡排序、快速排序、归并排序),查找算法(如顺序查找、二分查找、哈希查找),图论算法(如Dijkstra最短路径算法、Floyd-Warshall算法、Prim最小生成树算法),动态规划,贪心算法,回溯法...
系统设计NameNode : 维护 DataNode节点 列表,用心跳检测 DataNode(一般被动,被动失效时主动询问三次),节点增减等系统信息变化时调整数据并通知 Client;DataNode : 存储具体的数据,向 NameNode 主动发起心跳并...
IMKVS系统使用一致性哈希来决定在何处存储目标。一致性哈希使用起来方法简单,但可能引起网络负载的不平衡。为了提高IMKVS的缓存性能,提出一种软件定义网络中利用IMKVS结合NFV的分布式网络负载均衡策略。该策略包含...
一致性哈希(Consistenthash)很好的解决了这个问题,当节点发生变化时,只会影响到部分数据,而且永远可以找到一个提供服务的节点。对于数据库Sharding的架构,Consistenthash并不十分适合,我们采用了一种新的hash...
RedisJumphash提供了非常快速的一致性哈希函数,以使用Redis构建分布式系统。 用法 JUMPHASH <key> 成功调用将返回给定密钥的存储桶。 它不需要任何存储。 如果您更改存储桶的数量,该算法将保证需要的重定位次数...
php-consistent-hasha good php consistent hash helper,一个用php写的一致性hash 助手,主要用于解决internet中的热点(hot spot)问题特性平衡性(Balance):平衡性是指哈希的结果能够尽可能分布到所有的缓冲中去,...
+ Dubbo泛化调用的地址为一致性哈希负载均衡算法计算所得 + 解决了自定义协议在传输中导致的粘包、拆包问题 + 群聊批量ACK处理,避免因创建过多的超时计时器导致的压力过大 + 利用leaf-sno 【备注】 1、该资源内项目...
为解决分布式协同设计系统中的异地编辑一致性及多副本同步等问题,提出基于分布式哈希表(DHT)的分布式互斥算法,给出该算法的实现方法。通过采用DHT化的优先队列解决了异地编辑一致性操作问题。将传统的“锁”算法...
与传统的一致性哈希算法相比,分布式数据具有更多的平衡。多丽丝建筑高性能Doris提供了高性能的KV访问,并具有低延迟和高吞吐量。 通常的数据访问时间少于4毫秒。可扩展性Doris旨在支持多达2000个以上节点的大规模...