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

相关推荐

  • Android实战——ShareSDk的使用,实现一键分享微信好友、朋友圈、QQ

    Android实战——ShareSDk的使用,实现一键分享微信好友、朋友圈、QQShareSDk的使用,实现一键分享微信好友、朋友圈、QQ事先说明:ShareSDK默认QQ可以分享,微信分享则需要在微信的开放平台上认证并申请应用填入对应信息即可微信认证和申请应用涉及到打包和签名APK,请大家自行查询相关资料进行操作关于ShareSDK的开发,参考ShareSDK官网为准欢迎关注CSDN博客:Hensen_的个人主

  • 数据结构之hash表

    哈希(散列)技术既是一种存储方法,也是一种查找方法。然而它与线性表、树、图等结构不同的是,前面几种结构,数据元素之间都存在某种逻辑关系,可以用连线图示表示出来,而哈希技术的记录之间不存在什么逻辑关系,

    2021年12月28日
  • python实现卷积操作

    python实现卷积操作文章目录调用tf.nn.conv2d()实现卷积自己实现卷积函数我们知道,tensorflow里面自带卷积函数,tf.nn.conv2d()就可以实现相关功能,本文主要是自己实现卷积操作,然后和tf.nn.conv2d()函数的结果对比,验证正确性。调用tf.nn.conv2d()实现卷积首先是调用卷积函数实现卷积操作:这里说明一下conv2d的定义及参数含义:参考【定义:】tf.n…

  • java 对象拷贝方法beanutils_java copy方法

    java 对象拷贝方法beanutils_java copy方法一、简介:BeanUtils提供对Java反射和自省API的包装。其主要目的是利用反射机制对JavaBean的属性进行处理。我们知道,一个JavaBean通常包含了大量的属性,很多情况下,对JavaBean的处理导致大量get/set代码堆积,增加了代码长度和阅读代码的难度。二、用法:如果你有两个具有很多相同属性的JavaBean,一个很常见的情况…

  • C语言实现推箱子游戏

    C语言实现推箱子游戏很早就想过做点小游戏了,但是一直没有机会动手。今天闲来无事,动起手来。过程还是蛮顺利的,代码也不是非常难。今天给大家分享一下~一、介绍开发语言:C语言开发工具:Dev-C++5.11日期:2019年9月28日作者:ZackSock也不说太多多余的话了,先看一下效果图:游戏中的人物、箱子、墙壁、球都是字符构成的。通过wasd键移动,规则的话就是推箱子的规则,也就不多说了。二、代…

  • 什么叫做解析几何_笛卡尔心形函数

    什么叫做解析几何_笛卡尔心形函数解析几何是进行科学研究的重要的数学工具。比如说,要确定船只在大海中航行的位置,就要确立经纬度,这就需要精确的掌握夭体运行的规律;要改善枪炮的性能,就要精确地掌握抛射物体的运行规律。解决这些问题必须采用解析几何。因为它可以利用字母表示流动坐标,用方程刻划一般平面的曲线。解析几何的发明人就是伟大的数学家笛卡尔。笛卡尔15%年出生在法国,父亲是一位相当富有的律师。8岁时,父亲把他送进荃督教会学校读书。他…

    2022年10月10日

发表回复

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

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