一致性hash算法 java实现_信息的一致性

一致性hash算法 java实现_信息的一致性介绍一致性Hash算法是实现负载均衡的一种策略,后续会写如何实现负载均衡一致哈希是一种特殊的哈希算法。在使用一致哈希算法后,哈希表槽位数(大小)的改变平均只需要对K/n个关键字重新映射,其中K是关键字的数量,n是槽位数量。然而在传统的哈希表中,添加或删除一个槽位的几乎需要对所有关键字进行重新映射。强哈希考虑到单服务器不能承载,因此使用了分布式架构,最初的算法为hash()modn,hash()通常取用户ID,n为节点数。此方法容易实现且能够满足运营要求。缺点是当单点发

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE稳定放心使用

介绍

一致性Hash算法是实现负载均衡的一种策略,后续会写如何实现负载均衡

一致哈希是一种特殊的哈希算法。

在使用一致哈希算法后,哈希表槽位数(大小)的改变平均只需要对 K/n个关键字重新映射,其中K是关键字的数量, n是槽位数量。

然而在传统的哈希表中,添加或删除一个槽位的几乎需要对所有关键字进行重新映射。

强哈希

考虑到单服务器不能承载,因此使用了分布式架构,最初的算法为 hash() mod n, hash()通常取用户ID,n为节点数。

此方法容易实现且能够满足运营要求。缺点是当单点发生故障时,系统无法自动恢复。同样不也不能进行动态增加节点。

一致性hash算法 java实现_信息的一致性

优缺点

强哈希可以将数据均匀的打散到节点上。但是如果新增/删除节点呢?显然会发生大量的节点移动才能继续使用该算法,因此缺点是该算法与节点数目强耦合。

当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 所示:

一致性hash算法 java实现_信息的一致性

图 1 中 Key K 的哈希值在 A 与 B 之间,于是 K 就由节点B来处理。

另外具体机器映射时,还可以根据处理能力不同,将一个实体节点映射到多个虚拟节点。

经过一致性哈希算法散列之后,当有新的机器加入时,将只影响一台机器的存储情况,

例如新加入的节点H的散列在 B 与 C 之间,则原先由 C 处理的一些数据可能将移至 H 处理, 而其他所有节点的处理情况都将保持不变,因此表现出很好的单调性。

而如果删除一台机器,例如删除 C 节点,此时原来由 C 处理的数据将移至 D 节点,而其它节点的处理情况仍然不变。

而由于在机器节点散列和缓冲内容散列时都采用了同一种散列算法,因此也很好得降低了分散性和负载。

而通过引入虚拟节点的方式,也大大提高了平衡性。

缺点

一致性Hash算法的缺点在于节点的插入可能并不是均匀的,节点在hash后在环上并不一定分布均匀,导致了每个节点实际占据换上的区间大小不一定相近,因此节点分布不够均匀

改进

 

基于虚拟节点的一致性哈希

一致性hash算法 java实现_信息的一致性

一台物理服务器,虚拟成若干个虚拟节点,随机分布在环上,压力近似均衡分摊。如有三台物理服务器,每台物理服务器虚拟出150个虚拟节点,随机分配在Hash环上的150个位置上。最后可使三台物理服务器近似均摊压力。当增加一台服务器时,先虚拟150个节点,然后散落在哈希环上。

上图中的例子是有四台物理主机,每台物理主机虚拟成三个节点来保证节点近似均匀分布。

通过测试,每台物理服务的虚拟节点在120到200之间,均衡性更好。

缺点

该方法缺点在于存储虚拟节点信息需要额外空间。

重映射改进

在OpenStack的Swift组件中,使用了一种比较特殊的方法来解决分布不均的问题,改进了这些数据分布的算法,将环上的空间均匀的映射到一个线性空间,这样,就保证分布的均匀性。

一致性hash算法 java实现_信息的一致性

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/188909.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • 关联数据入门——RDF

    关联数据入门——RDF本文是语义网的入门级读本,试图描述一些语义网基本知识……

  • ajaxpro json 使用「建议收藏」

    ajaxpro json 使用「建议收藏」(一)AJAXPro之旅—神奇的小魔盒-站在巨人的肩膀上做自己的事情-博客园 -[Translatethispage]2007年9月10日…JSON.2.dll,AjaxPro.JSON.dll,web.config5个文件.其中.2结尾的是应用在.Net2.0框架下的类库.(个人使用的是2.0的,以下的教程也是应用在2.0下的)…www.cnblogs.c…

  • 一个对文本内容进行排序的小程序的核心代码

    一个对文本内容进行排序的小程序的核心代码

  • Bootstrap3-导航条[通俗易懂]

    1.定义导航条<!–导航条navbar–><divclass=”navbarnav-bar-default”><ulclass=”navnav-pills”> <liclass=”active”><ahref=”#”>首页</a></li> <li><…

  • 空间流介绍[通俗易懂]

    空间流介绍[通俗易懂]stream是802.11n中的空间流的意思,11n协议中最高支持4空间流。11n协议物理层最核心的技术就是MIMO技术,一般AP设备MIMO都后注1×1,2×2,2×3,3×3等,这两个数字前面一个数字式11nAP的发射天线数量,后面一个数字是11nAP的接受天线数量。11n中所谓的空间流实际就是MIMO空间复用支持的多根天线独立地并行发送由单独编码的信号组成的不同的数据流。无线复用的空间流的数量取决于发射天线的数量。你可以这样简单理解,由于11nAP有多个发射天线,形成多个发射物理信道,与以前的WLA

  • CMD命令:不是内部或者外部命令也不是可运行的程序或批处理文件

    CMD命令:不是内部或者外部命令也不是可运行的程序或批处理文件前言:相信有很多小伙伴都比较喜欢使用Command命令来快速的打开或运行程序,但是有些时候命令提示符会和我们开个小玩笑。今天我就教大家如何管教这个不听话的cmd!场景:看有些大神在命令提示符里输入两句命令就能执行一大串东西,本着学习的态度,先试试再说!没成想出现了:“不是内部或外部命令,也不是可运行的程序或批处理文件。”通过各种查各种找,终于…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号