在分布式系统中,如果某业务可以由多个相同的节点处理,很容易想到用HASH的方式将业务请求分散到这些节点处理,如果有N个节点,计算方法为:HASH(id)% N。
如果只是简单的计算,不涉及用户状态,这是一个简单有效的方案。如果节点的计算涉及用户状态,比如维护购物车、Memcache缓存服务等,好像也没什么 问题,只要用同一个数据做id,上述HASH的结果也保持不变。但如果节点数量发生变化,比如由于业务量的增大而增加节点或由于机器宕机而减少节点,上述 HASH的结果就不一样了。若增加2个节点,某id原处理节点为HASH(id)% N,新的处理节点就变成了HASH(id)% (N + 2),可能会将大量id的处理节点打乱重新分配,就会发现之前某节点保存的用户数据用不到了,而新的处理节点根本没有这些数据。在这段时间内,这些用户的
状态受到破坏,如果是购物车,车里的东西都没了,如果是缓存服务,之前的缓存都消失了,起不到缓存的效果。可能需要用户重新登录,可能需要从数据库更新缓 存,可能由此引入新的问题。
一致性哈希在一定程度上缓解了这个问题,步骤为:
1.将整个哈希值空间组织成一个虚拟圆环,假设某哈希函数H的值空间为0-(2^32-1),即32位无符号整数
2.将各节点用H函数哈希,可以将服务器的IP或主机名作为关键字哈希,这样每个节点就能确定其在哈希环上的位置
3.将id用H函数映射到哈希空间的一个值,沿该值向后,将遇到的第一个节点做为处理节点
下图中,若某id的HASH值落在node1和node2各自HASH值的中间位置,则此id对应的业务请求由node2处理。
当增加服务节点时,只会影响与之相邻的某一节点,其他节点不受影响。如果在node2和node4之间增加一个node5,则只有node4处理的部分 id(HASH值落在node2之后、node5之前的那部分id)变为由node5来处理,其他节点处理的id不变。比开头所述的简单HASH方式有了 很大的改善。
如果节点数不多,将这些节点映射到值空间之后,分布可能会很不均匀,必然会造成个别节点处理的id数量远大于其他节点,这就起不到负载均衡的效果。这可以 通过引入虚拟节点的方式解决,即对每一个节点计算多个HASH值,尽量保证这些HASH值比较均匀的分布在值空间中。当根据id查找节点时,找到的是虚拟 节点,然后再根据虚拟节点查找对应的真实节点。多了一次查找的过程。
Memcached的客户端库libmemcached已经支持此算法。
分享到:
相关推荐
对已有的负载平衡的改进算法,通过一致性哈希算法,负载平衡更加的有效。
一致性哈希算法
一致性哈希算法,广泛应用于分布式计算,C版实现,属于分布式服务器管理的核心算法。
#资源达人分享计划#
运行平台:VS 2019 一致性哈希算法演示项目,演示新增节点key分布情况;移除节点key分布情况! C#,C#,C#.......
哈希算法 基于C# 实现的一致性哈希算法
基于动态转移的分布式缓存系统一致性哈希算法改进,张昊,张永军,近年来,随着大数据与分布式集群的广泛应用,一致性哈希算法在分布式缓存系统的负载均衡中得到了广泛的应用。一致性哈希算法虽然
#资源达人分享计划#
#资源达人分享计划#
一致性哈希算法用来解决分布式系统中热点接入与删除管理,是目前公认的最有效的算法,该文档图文并茂,详细解释了这一算法。
#资源达人分享计划#
白话解析:一致性哈希算法1
#资源达人分享计划#
Ketama算法是一致性hash算法的一个优秀实现。增删节点后数据命中率及均分率都很高。
一致性哈希算法应用及优化(最简洁明了的教程)
基于NIO-EPOOL模型netty实现的具备一致性哈希算法的NAT端口映射器
在分布式系统中,常常需要使用缓存,而且通常是集群,访问缓存和添加缓存都需要一个 hash 算法来寻找到合适的 Cache 节点。但,通常不是用取余hash,而是使用我们今天的主角—— 一致性 hash 算法。
其次介绍了系统的实现流程,阐明了系统的关键技术:利用录音服务器对其镜像端口的SIP报文进行解析获得媒体流并解码、采用一致性哈希算法的内存数据库作为解码数据的缓存机制、利用Ckafka技术在两者之间构建实时数据...
ufire-springcloud-platform 学习微服-基于一致性哈希算法实现websocket分布式扩展的尝试。