Hash一致算法_分布式一致性hash

Hash一致算法_分布式一致性hash一致性hash算法是什么?一致性hash算法,是麻省理工学院1997年提出的一种算法,目前主要应用于分布式缓存当中。一致性hash算法可以有效地解决分布式存储结构下动态增加和删除节点所带来的问题。在Memcached、Key-ValueStore、BittorrentDHT、LVS中都采用了一致性hash算法,可以说一致性hash算法是分布式系统负载均衡的首选算法。传统hash算法的弊…

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

Jetbrains全系列IDE稳定放心使用

一致性hash算法是什么?

一致性hash算法,是麻省理工学院1997年提出的一种算法,目前主要应用于分布式缓存当中。
一致性hash算法可以有效地解决分布式存储结构下动态增加和删除节点所带来的问题。
在Memcached、Key-Value Store、Bittorrent DHT、LVS中都采用了一致性hash算法,可以说一致性hash算法是分布式系统负载均衡的首选算法。

传统hash算法的弊端

常用的算法是对hash结果取余数 (hash() mod N):对机器编号从0到N-1,按照自定义的hash算法,对每个请求的hash值按N取模,得到余数i,然后将请求分发到编号为i的机器。但这样的算法方法存在致命问题,如果某一台机器宕机,那么应该落在该机器的请求就无法得到正确的处理,这时需要将宕掉的服务器使用算法去除,此时候会有(N-1)/N的服务器的缓存数据需要重新进行计算;如果新增一台机器,会有N /(N+1)的服务器的缓存数据需要进行重新计算。对于系统而言,这通常是不可接受的颠簸(因为这意味着大量缓存的失效或者数据需要转移)。

传统求余做负载均衡算法,缓存节点数由3个变成4个,缓存不命中率为75%。计算方法:穷举hash值为1-12的12个数字分别对3和4取模,然后比较发现只有前3个缓存节点对应结果和之前相同,所以有75%的节点缓存会失效,可能会引起缓存雪崩。

一致性hash算法

  1. 首先,我们将hash算法的值域映射成一个具有232 次方个桶的空间中,即0~(232)-1的数字空间。现在我们可以将这些数字头尾相连,组合成一个闭合的环形。

  2. 每一个缓存key都可以通过Hash算法转化为一个32位的二进制数,也就对应着环形空间的某一个缓存区。我们把所有的缓存key映射到环形空间的不同位置。

  3. 我们的每一个缓存节点也遵循同样的Hash算法,比如利用IP或者主机名做Hash,映射到环形空间当中,如下图

image

  1. 如何让key和缓存节点对应起来呢?很简单,每一个key的顺时针方向最近节点,就是key所归属的缓存节点。所以图中key1存储于node1,key2,key3存储于node2,key4存储于node3。

image

  1. 当缓存的节点有增加或删除的时候,一致性哈希的优势就显现出来了。让我们来看看实现的细节:
  • 增加节点
    当缓存集群的节点有所增加的时候,整个环形空间的映射仍然会保持一致性哈希的顺时针规则,所以有一小部分key的归属会受到影响。

image

有哪些key会受到影响呢?图中加入了新节点node4,处于node1和node2之间,按照顺时针规则,从node1到node4之间的缓存不再归属于node2,而是归属于新节点node4。因此受影响的key只有key2。

image

最终把key2的缓存数据从node2迁移到node4,就形成了新的符合一致性哈希规则的缓存结构。

  • 删除节点
    当缓存集群的节点需要删除的时候(比如节点挂掉),整个环形空间的映射同样会保持一致性哈希的顺时针规则,同样有一小部分key的归属会受到影响。

image

有哪些key会受到影响呢?图中删除了原节点node3,按照顺时针规则,原本node3所拥有的缓存数据就需要“托付”给node3的顺时针后继节点node1。因此受影响的key只有key4。

image

最终把key4的缓存数据从node3迁移到node1,就形成了新的符合一致性哈希规则的缓存结构。

说明:这里所说的迁移并不是直接的数据迁移,而是在查找时去找顺时针的后继节点,因缓存未命中而刷新缓存。

计算方法:假设节点hash散列均匀(由于hash是散列表,所以并不是很理想),采用一致性hash算法,缓存节点从3个增加到4个时,会有0-33%的缓存失效,此外新增节点不会环节所有原有节点的压力。

一致性hash算法的结果相比传统hash求余算法已经进步很多,但可不可以改进一下呢?或者如果出现分布不均匀的情况怎么办?比如下图这样,按顺时针规则,所有的key都归属于统一个节点。

image

一致性hash算法+虚拟节点

为了优化这种节点太少而产生的不均衡情况。一致性哈希算法引入了虚拟节点的概念。
所谓虚拟节点,就是基于原来的物理节点映射出N个子节点,最后把所有的子节点映射到环形空间上。

image

虚拟节点越多,分布越均匀。使用一致性hash算法+虚拟节点这种情况下,缓存节点从3个变成4个,缓存失效率为25%,而且每个节点都平均的承担了压力。

一致性hash算法+虚拟节点的实现

原理理解了,实现并不难,主要是一些细节:

  1. hash算法的选择。Java代码不要使用hashcode函数,这个函数结果不够散列,而且会有负值需要处理。
    这种计算Hash值的算法有很多,比如CRC32_HASH、FNV1_32_HASH、KETAMA_HASH等,其中KETAMA_HASH是默认的MemCache推荐的一致性Hash算法,用别的Hash算法也可以,比如FNV1_32_HASH算法的计算效率就会高一些。
  2. 数据结构的选择。根据算法原理,我们的算法有几个要求:
  • 要能根据hash值排序存储
  • 排序存储要被快速查找 (List不行)
  • 排序查找还要能方便变更 (Array不行)

另外,由于二叉树可能极度不平衡。所以采用红黑树是最稳妥的实现方法。Java中直接使用TreeMap即可。

哎呀,如果我的名片丢了。微信搜索“全菜工程师小辉”,依然可以找到我

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

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

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

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

(0)
blank

相关推荐

  • 多尺度空间概念_人文地理学空间和尺度概念

    多尺度空间概念_人文地理学空间和尺度概念 1.图像的尺度这里图像的尺度并非指图像的大小,而是指图像的模糊程度,例如,人近距离看一个物体和远距离看一个物体模糊程度是不一样的,从近距离到远距离图像越来越模糊的过程,也是图像的尺度越来越大的过程。2.尺度空间的作用1.用机器视觉系统分析未知场景时,计算机并不预先知道图像中物体的尺度。我们需要同时考虑图像在多尺度下的描述,获知感兴趣物体的最佳尺度。2.不同的尺度下都有…

    2022年10月14日
  • 关于 java JSONArray JSONObject转换问题

    关于 java JSONArray JSONObject转换问题importlhy.client.json.JSONArray;importlhy.client.json.JSONException;importlhy.client.json.JSONObject;publicclassMyJson{publicstaticvoidmain(String[]args)throwsJSO…

  • 不确定度用计算机怎么算,算A类不确定度用计算器该怎样按[通俗易懂]

    不确定度用计算机怎么算,算A类不确定度用计算器该怎样按[通俗易懂]不可以。根号也只能显示平方根,立方根以上就别想了,这三次方程解出来不知道是几次方根。这种计算器下面那个L-R=0是用来检验的,说明就不是用公式解的,估计是二分法或者什么其它近似解法,L-R=0只是在计算器内部算法允许的精度范围内保证L-R=0,所以肯定不支持根号。A类不确定度的计算方法。n=6时,u(a)=S(x)。数据平均值设为q。用贝塞尔公式S(x)*S(x)=[(X1-q)*(X1-q)+(…

  • python后缀是啥_python文件后缀

    python后缀是啥_python文件后缀python文件的后缀名有:“.py”、“.py3”、“.pyc”、“.pyo”、“.pyd”、“.pyi”、“.pyx”、“.pyz”、“.pywz”、“.rpy”、“.pyde”、“.pyp”、“.pyt”。python文件后缀总结:(1).py:以py扩展名的文件是Python源码文件,由python.exe解释,可在控制台下运行。可用文本编辑器读写。(2).py3:Python…

  • 基于51单片机八路抢答器课程设计(含proteus仿真图及代码)

    基于51单片机八路抢答器课程设计(含proteus仿真图及代码)一、设计要求:1、可满足8个选手的抢答2、具有主持者控制开关,用来控制系统清零和抢答开始3、抢答器具有数据锁存功能、显示功能和声音提示功能4、抢答开始后,若有选手按动抢答器按钮,编号立即锁存,并在LED数5、码管上显示选手的编号,同时灯亮且伴随声音提示,还要禁止其后的抢答输入二、实验设计和分析1 总体设计方案方案一:采用数字电路控制。采用数字显示电路的好处就是设计简单。用以在P0口…

    2022年10月20日
  • 微信二维码登录的原理是什么_请使用微信扫描二维码登录

    微信二维码登录的原理是什么_请使用微信扫描二维码登录在电脑上使用微信时,你可能已经发现微信不提供传统的账号密码登陆,取而代之的是通过扫描二维码进行登陆。今天就要研究下次登陆方式微信时如何实现的?1、每次用户打开PC端登陆请求,系统返回一个唯一的uid,

发表回复

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

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