图解一致性哈希算法的基本原理

图解一致性哈希算法的基本原理一致性哈希的基本原理一致性哈希算法是将每个Node节点映射到同一个圆上。将各Node的key采用hash计算,可得到一个整数数组。将该数组排序后,首尾相连即是一个圆。如下图所示简单来说,一致性Hash算法将整个哈希值空间组织成一个虚拟的圆环,如假设某哈希函数H的值空间为0-2^32-1(即哈希值是一个32位无符号整形),整个哈希环如下:整个空间按顺时针方向组织,圆环的正上方的点代表0,0点右侧的第一个点代表1,以此类推,2、3、4、5、6……直到2^32-1,也就是说0点左侧..

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

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

一致性哈希的基本原理

一致性哈希算法是将每个Node节点映射到同一个圆上。将各Nodekey采用hash计算,可得到一个整数数组。将该数组排序后,首尾相连即是一个圆。如下图所示

图解一致性哈希算法的基本原理

 

简单来说,一致性Hash算法将整个哈希值空间组织成一个虚拟的圆环,如假设某哈希函数H的值空间为0-2^32-1(即哈希值是一个32位无符号整形),整个哈希环如下:

图解一致性哈希算法的基本原理

 

整个空间按顺时针方向组织,圆环的正上方的点代表0,0点右侧的第一个点代表1,以此类推,2、3、4、5、6……直到2^32-1,也就是说0点左侧的第一个点代表2^32-1, 0和2^32-1在零点中方向重合,我们把这个由2^32个点组成的圆环称为Hash环

假如有4个服务器节点,分别为NodeA、NodeB、NodeC和NodeD,根据他们的IP或者服务名称计算hash值对2^32取模就可以分别得到它们在圆环上的位置。

图解一致性哈希算法的基本原理

 

接下来使用如下算法定位数据访问到相应服务器:  将数据key使用相同的函数Hash函数计算出哈希值,并确定此数据在环上的位置,从此位置沿环顺时针找到的第一个服务器就是其本次访问的服务器。

 

容错性和可扩展性

 

假如Node C此时宕机,A、B、D节点不受影响,受影响的是此节点C到其前面一个节点(Node B)之间的环空间会受影响。但是如果我们在Node C宕机时及时将其从圆环中移除,则原本可能受影响的环空间可以沿着顺时针找到下一个节点(Node D)

图解一致性哈希算法的基本原理

 

 

新增节点X,那么节点X到其前面一个节点(Node B)环上的对象会从原本请求的节点(Node D)调整到Node X节点上。所以一致性哈希算法有非常好的容错性和可扩展性。 

图解一致性哈希算法的基本原理

 

解决Hash环的倾斜问题

一致性Hash算法在服务节点太少时,往往会出现节点分布不均匀的情况,如下图所示

图解一致性哈希算法的基本原理

 

这样就导致服务器请求不均衡,请求到Node A上的对象远远大于请求到节点B上的对象。为了解决哈希环倾斜的问题往往在实际应用一致性哈希算法时会引入虚拟节点

这些由实际节点虚拟复制而来的节点被称为“虚拟节点”,即对每一个服务节点计算多个哈希,每个计算结果位置都放置一个此服务节点,称为虚拟节点。具体做法可以在服务器IP或主机名的后面增加编号来实现。

 

例如上面的情况,可以为每台服务器计算三个虚拟节点,于是可以分别计算 “Node A#1”、“Node A#2”、“Node A#3”、“Node B#1”、“Node B#2”、“Node B#3”的哈希值,于是形成六个虚拟节点:

图解一致性哈希算法的基本原理

 

由于hash是随机的,所以虚拟节点越多hash环上的节点分布就会越均匀

图解一致性哈希算法的基本原理

 

一致性哈希的性质

1.平衡性(Balance)

平衡性是指哈希的结果能够尽可能分布到所有的缓冲中去,这样可以使得所有的缓冲空间都得到利用。很多哈希算法都能够满足这一条件。

 

2.单调性(Monotonicity)

单调性是指如果已经有一些内容通过哈希分派到了相应的缓冲中,又有新的缓冲区加入到系统中,那么哈希的结果应能够保证原有已分配的内容可以被映射到新的缓冲区中去,而不会被映射到旧的缓冲集合中的其他缓冲区。简单的哈希算法往往不能满足单调性的要求,如最简单的线性哈希:x = (ax + b) mod (P),在上式中,P表示全部缓冲的大小。不难看出,当缓冲大小发生变化时(从P1到P2),原来所有的哈希结果均会发生变化,从而不满足单调性的要求。哈希结果的变化意味着当缓冲空间发生变化时,所有的映射关系需要在系统内全部更新。而在P2P系统内,缓冲的变化等价于Peer加入或退出系统,这一情况在P2P系统中会频繁发生,因此会带来极大计算和传输负荷。单调性就是要求哈希算法能够应对这种情况。

 

3. 分散性(Spread)

在分布式环境中,终端有可能看不到所有的缓冲,而是只能看到其中的一部分。当终端希望通过哈希过程将内容映射到缓冲上时,由于不同终端所见的缓冲范围有可能不同,从而导致哈希的结果不一致,最终的结果是相同的内容被不同的终端映射到不同的缓冲区中。这种情况显然是应该避免的,因为它导致相同内容被存储到不同缓冲中去,降低了系统存储的效率。分散性的定义就是上述情况发生的严重程度。好的哈希算法应能够尽量避免不一致的情况发生,也就是尽量降低分散性。

 

4. 负载(Load)

负载问题实际上是从另一个角度看待分散性问题。既然不同的终端可能将相同的内容映射到不同的缓冲区中,那么对于一个特定的缓冲区而言,也可能被不同的用户映射为不同的内容。与分散性一样,这种情况也是应当避免的,因此好的哈希算法应能够尽量降低缓冲的负荷。

 

5. 平滑性(Smoothness)

平滑性是指缓存服务器的数目平滑改变和缓存对象的平滑改变是一致的。

 

以上内容主要整理自:https://blog.csdn.net/my8688/article/details/85264880

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

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

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

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

(0)
blank

相关推荐

  • matlab求解下面的线性规划和整数规划[通俗易懂]

    matlab求解下面的线性规划和整数规划[通俗易懂]matlab求解下面的线性规划和整数规划  本篇博客主要讲了用matlab实际求解整数规划问题,目前还没有时间去自己实现整数规划算法,只能通过调用MATLAB的函数去实现。题目代码第一小题%线性规划代码%authorCanlongf=[-3,-2];A=[2,3;1,0.5];b=[14;4.5];C=[];d=[];xm=[0;0];xM=1e+10*[…

  • GoLand 2022.01.4激活码(JetBrains全家桶)

    (GoLand 2022.01.4激活码)好多小伙伴总是说激活码老是失效,太麻烦,关注/收藏全栈君太难教程,2021永久激活的方法等着你。IntelliJ2021最新激活注册码,破解教程可免费永久激活,亲测有效,下面是详细链接哦~https://javaforall.cn/100143.htmlGTRPTN90LV-eyJsaWNlbnNlSW…

  • 神经网络–反向传播详细推导过程

    神经网络–反向传播详细推导过程概述以监督学习为例,假设我们有训练样本集  ,那么神经网络算法能够提供一种复杂且非线性的假设模型  ,它具有参数  ,可以以此参数来拟合我们的数据。为了描述神经网络,我们先从最简单的神经网络讲起,这个神经网络仅由一个“神经元”构成,以下即是这个“神经元”的图示:这个“神经元”是一个以  及截距  为输入值的运算单元,其输出为  ,其中函数  被称为“激活函数”。在本教程中,我们选用sigmoid函…

  • DOS命令Copy 合并文件

    DOS命令Copy 合并文件我们都知道DOS命令Copy的主要作用是复制文件,可是你是否知道,它还有一个作用是合并文件呢?一般情况下,它主要用于合并相同类型的文件,比如将两个文本文件合并为一个文本文件、将两个独立的MPEG视频文件合并为一个连续的视频文件等。那么,如果用它合并两个不同类型的文件,结果会怎样呢?笔者发现,巧妙地将一个文本文件合并到一个非文本文件中,可以实现隐藏秘密的作用。一起来看看吧。比如你有一段私人信息…

  • 第 三 十 八 天:Apache 选 项 和 模 块 问 题 附:php

    第 三 十 八 天:Apache 选 项 和 模 块 问 题 附:php

  • “双击Pycharm无响应”解决方案「建议收藏」

    “双击Pycharm无响应”解决方案「建议收藏」问题描述昨晚直接关机,导致pycharm强制关闭,今早打开时双击图标无响应解决方法第一步:找到该路径下的cmd.exe,右键管理员身份打开;第二步:在cmd窗口中,输入netshwinsockreset,回车;第三步:重启电脑,尝试重新打开pycharm关于指令winsock是Windows网络编程接口netsh是一个能够通过命令行操作几乎所有网络相关设置的接口netshwinsockreset命令,作用是重置Winsock目录这个命令可以重新初始化网

发表回复

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

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