大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。
Jetbrains全系列IDE稳定放心使用
介绍
一致性Hash算法是实现负载均衡的一种策略,后续会写如何实现负载均衡
一致哈希是一种特殊的哈希算法。
在使用一致哈希算法后,哈希表槽位数(大小)的改变平均只需要对 K/n个关键字重新映射,其中K是关键字的数量, n是槽位数量。
然而在传统的哈希表中,添加或删除一个槽位的几乎需要对所有关键字进行重新映射。
强哈希
考虑到单服务器不能承载,因此使用了分布式架构,最初的算法为 hash() mod n, hash()通常取用户ID,n为节点数。
此方法容易实现且能够满足运营要求。缺点是当单点发生故障时,系统无法自动恢复。同样不也不能进行动态增加节点。
优缺点
强哈希可以将数据均匀的打散到节点上。但是如果新增/删除节点呢?显然会发生大量的节点移动才能继续使用该算法,因此缺点是该算法与节点数目强耦合。
当node数发生变化的时候,hash item所对应的node发生剧烈变化,而发生变化的成本就是我们需要在node数发生变化的时候迁移数据。因而诞生了弱哈希
弱哈希
为了解决单点故障,使用 hash() mod (n/m)
这样任意一个用户都有 m 个服务器备选,可由 client 随机选取。
由于不同服务器之间的用户需要彼此交互,所以所有的服务器需要确切的知道用户所在的位置。
因此用户位置被保存到 memcached 中。当一台发生故障,client 可以自动切换到对应 backup,由于切换前另外 1 台没有用户的 session,因此需要 client 自行重新登录。
- 好处
他比强哈希的好处是:解决了单点问题。
- 缺点
但存在以下问题:负载不均衡,尤其是单台发生故障后剩下一台会压力过大;不能动态增删节点;节点发生故障时需要 client 重新登录
因而出现了一致性hash,一致性 hash 算法适用于动态变化的 Cache 环境。
一致性Hash算法
一致性哈希算法有多种具体的实现,包括 Chord 算法,KAD 算法等实现,以上的算法的实现都比较复杂。
这里介绍一种网上广为流传的一致性哈希算法的基本实现原理,感兴趣的同学可以根据上面的链接或者去网上查询更详细的资料。
一致性哈希算法的基本实现原理是将机器节点和key值都按照一样的hash算法映射到一个0~2^32
的圆环上。
当有一个写入缓存的请求到来时,计算 Key 值 k 对应的哈希值 Hash(k),如果该值正好对应之前某个机器节点的 Hash 值,则直接写入该机器节点, 如果没有对应的机器节点,则顺时针查找下一个节点,进行写入,如果超过 2^32
还没找到对应节点,则从0开始查找(因为是环状结构)。
如图 1 所示:
图 1 中 Key K 的哈希值在 A 与 B 之间,于是 K 就由节点B来处理。
另外具体机器映射时,还可以根据处理能力不同,将一个实体节点映射到多个虚拟节点。
经过一致性哈希算法散列之后,当有新的机器加入时,将只影响一台机器的存储情况,
例如新加入的节点H的散列在 B 与 C 之间,则原先由 C 处理的一些数据可能将移至 H 处理, 而其他所有节点的处理情况都将保持不变,因此表现出很好的单调性。
而如果删除一台机器,例如删除 C 节点,此时原来由 C 处理的数据将移至 D 节点,而其它节点的处理情况仍然不变。
而由于在机器节点散列和缓冲内容散列时都采用了同一种散列算法,因此也很好得降低了分散性和负载。
而通过引入虚拟节点的方式,也大大提高了平衡性。
缺点
一致性Hash算法的缺点在于节点的插入可能并不是均匀的,节点在hash后在环上并不一定分布均匀,导致了每个节点实际占据换上的区间大小不一定相近,因此节点分布不够均匀
改进
基于虚拟节点的一致性哈希
一台物理服务器,虚拟成若干个虚拟节点,随机分布在环上,压力近似均衡分摊。如有三台物理服务器,每台物理服务器虚拟出150个虚拟节点,随机分配在Hash环上的150个位置上。最后可使三台物理服务器近似均摊压力。当增加一台服务器时,先虚拟150个节点,然后散落在哈希环上。
上图中的例子是有四台物理主机,每台物理主机虚拟成三个节点来保证节点近似均匀分布。
通过测试,每台物理服务的虚拟节点在120到200之间,均衡性更好。
缺点
该方法缺点在于存储虚拟节点信息需要额外空间。
重映射改进
在OpenStack的Swift组件中,使用了一种比较特殊的方法来解决分布不均的问题,改进了这些数据分布的算法,将环上的空间均匀的映射到一个线性空间,这样,就保证分布的均匀性。
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/188909.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...