一致性hash面试题_java面试算法

一致性hash面试题_java面试算法为什么要用一致性hash算法?在学习一致性hash算法之前,首先要考虑下为什么要使用它,使用它能解决什么样的问题。带着问题去学习相信理解起来会更容易。大家都知道我们在使用redis分片技术,mycat对数据库进行分库分表时都会面临数据操作规则的问题;比如我们把一条记录存入redis3服务器,那么我们获取的时候如果不指定规则就会根据key在所有的redis服务器中进行遍历查找,显然这种情况是…

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

Jetbrains全系列IDE稳定放心使用

为什么要用一致性hash算法?

在学习一致性hash算法之前,首先要考虑下为什么要使用它,使用它能解决什么样的问题。带着问题去学习相信理解起来会更容易。

大家都知道我们在使用redis分片技术,mycat对数据库进行分库分表时都会面临数据操作规则的问题;比如我们把一条记录存入redis3服务器,那么我们获取的时候如果不指定规则就会根据key在所有的redis服务器中进行遍历查找,显然这种情况是我们不想看到的。所以这时候我们就需要引入一些规则来确保数据放入某个redis服务器,取的时候直接去对应的服务器进行查询,而不需要遍历多台服务器。常用的规则有根据hash值来决定存放位置。比如存入一个记录时,我们根据key进行hash运算再用hash值与服务器的数量进行取模:hash(key)/3=X;得出的结果就是记录存放的服务器位置,查询的时候按照相同的公式进行计算,这样就不会遍历所有的服务器,从而大大提供了性能。

虽然使用hash算法可以提高性能,但是也会有一些缺陷,主要体现在服务器数量发生变化(增加/减少)时,所有缓存的位置都会发生改变。例如我们要增加一台缓存服务器(之前三台),hash算法如下hash(key)/4=X;这种情况带来的结果就是服务器数量发生变化时会造成缓存失效,此时请求会发往后端数据库,可能导致缓存雪崩问题。我们不允许这种现象发生,但是利用hash值取模进行缓存时这种情况无法避免,为了解决这些问题,hash一致性算法诞生了。

一致性hash算法背景

一致性哈希算法在1997年由麻省理工学院的Karger等人在解决分布式Cache中提出的,设计目标是为了解决因特网中的热点(Hot spot)问题,初衷和CARP十分类似。一致性哈希修正了CARP使用的简单哈希算法带来的问题,使得DHT可以在P2P环境中真正得到应用。

一致性hash算法:

一致性hash算法也是使用取模的方法,只是上述hash算法是对服务器数量记性取模运算,而一致性hash是对2^32取模。也就是说一致性hash算法将整个hash空间组织成一个圆环:

计算一致性hash步骤如下:

1 首先根据缓存服务器的ip,端口等信息算出哈希值,并将其配置到个数为2的32次方的圆上。

2 然后同样的方法算出存储数据的键的哈希值,并映射到相同的圆上。

3 从数据存储位置开始顺时针查找,将数据保存到找到的第一个服务器上,如果超过2的32次方仍然找不到服务器就会保存在第一台服务器上;取值操作完全相同。

整个环按照顺时针方向进行组织。然后可以用服务器ip,port作为key进行hash从而确定在环中的位置,对数据进行存储时也进行相同的hash算法对key运算确定数据在此环上的位置,从此位置沿顺时针开始遇到的第一个服务器就是数据存放的服务器:

一致性hash面试题_java面试算法

 

当添加一台redis缓存服务器时,只有增加服务器的位置和逆时针方向第一台服务器之间的键会受影响:

一致性hash面试题_java面试算法

一致性hash算法对于节点的增减都只需要重定位环空间中的一小部分数据,具有良好的容错性和可扩展性。

hash环的数据倾斜问题:

一致性hash算法在服务节点太少的情况下容易因为节点部分不均匀造成数据倾斜问题(数据大部分集中在一台缓存服务器);

一致性hash面试题_java面试算法

为了解决这种数据倾斜问题,hash算法引入了虚拟节点机制,即对每一个服务节点计算多个哈希,每个结果未知都放置一个此服务节点,称为虚拟节点,数据定位算法不变,只是多了一个虚拟节点到实际节点的映射,例如定位到NodeA#1,2,3三个虚拟节点的数据均定位到NodeA节点,这样就解决了服务节点少时的数据倾斜问题。在实际应用中,通常将虚拟节点数设置为32甚至更大,这样即使很少的服务节点也能做到相对均匀的数据分布。

一致性hash面试题_java面试算法

一致性hash特性说明:

平衡性(balance)

平衡性是指hash的结果能够尽可能分布有缓存中去,这样可以使得所有的缓存空间都得到利用,当数据出现负载不均时,则采用虚拟节点平衡数据。

单调性(monotonicity)

单调性是指如果已经有一些内容通过哈希分派到了相应的缓冲中,又有新的缓冲区加入到系统中,那么哈希的结果应能够保证原有已分配的内容可以被映射到新的缓冲区中去,而不会被映射到旧的缓冲集合中的其他缓冲区。

分散性(spread)

在分布式环境中,终端有可能看不到所有的缓冲,而是只能看到其中的一部分。当终端希望通过哈希过程将内容映射到缓冲上时,由于不同终端所见的缓冲范围有可能不同,从而导致哈希的结果不一致,最终的结果是相同的内容被不同的终端映射到不同的缓冲区中。

负载(load)

负载问题实际上是从另一个角度看待分散性问题,终端有可能看不到所有的缓冲从而导致不同的key 保存到了相同的位置。

 

现在一致性hash算法在分布式系统中得到了广泛应用,例如memcached,redis等分布式缓存数据库,要注意的是服务端本身不提供分布式cache的一致性,而是由客户端提供的。一致性hash算法是分布式组件负载均衡的首选算法,它即可在客户端实现,也可以在中间件上实现:其应用有:

分布式散列表(DHT)设计;

分布式关系数据库(mysql),分库分表时计算数据与节点的映射关系;

分布式缓存;

RPC框架dubbo,用来选择服务提供者;

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

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

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

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

(0)
blank

相关推荐

  • 51单片机流水灯电路以及C代码「建议收藏」

    51单片机流水灯电路以及C代码「建议收藏」流水灯是51单片机的入门级实验,以下是其电路图以及C代码流水灯proteus电路图此图发光二极管采用共阳极式连接流水灯C代码#include<reg51.h>voiddelay1s(unsignedcharn);voidMovinglight(){ unsignedcharcodeMovinglightA

  • Matlab矩阵复制扩充

    考虑这个问题:定义一个简单的行向量a    如何复制10行呢?即:    同理,对于一个列向量,如何复制10列呢?  关键函数1:repmat(A,m,n):将向量/矩阵在垂直方向复制m次,在水平方向复制n次。      再举一个例子,对于a=[12;34]:         垂直方向复制3次,水平方向复制2次,

  • Springboot上传文件到Linux服务器

    Springboot上传文件到Linux服务器jar打包方式不支持将文件动态写入文件,这时需要通过映射的方式将文件上传到映射某一个文件夹,通过映射获取文件,在页面显示。1.yml配置配置本地上传地址或者服务器地址,springboot项目可以通过映射获取文件,从而页面显示 注意:这里配置的地址一定要加一个”/”在最后面!!!!file:#服务器地址uploadurl:”/u01/upload/images/”#本地地址#localurl:”D:/springbootFile/upload/images/”

  • 【Hibernate】关系映射

    【Hibernate】关系映射【Hibernate】关系映射

  • IOS-导航路线_iphone导航

    IOS-导航路线_iphone导航1.可以将需要导航的位置丢给系统自带的APP进行导航2.发送网络请求到公司服务器获取导航数据,然后自己手动绘制导航3.利用三方SDK实现导航(百度)>当点击开始导航时获取用户输入的起点和

  • 学习笔记-正则表达式[通俗易懂]

    学习笔记-正则表达式[通俗易懂]学习笔记-正则表达式

发表回复

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

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