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

图解一致性哈希算法的基本原理一致性哈希的基本原理一致性哈希算法是将每个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)


相关推荐

  • Nginx命令大全[通俗易懂]

    nginx #打开nginxnginx-t   #测试配置文件是否有语法错误nginx-sreopen #重启Nginxnginx-sreload  #重新加载Nginx配置文件,然后以优雅的方式重启Nginxnginx-sstop  #强制停止Nginx服务nginx-squit  #优雅地停止Nginx服务…

  • 分类信息网站大全

    分类信息网站大全

  • 前端使用ajax_ajax属于前端吗

    前端使用ajax_ajax属于前端吗原生AJAX名称:异步的javascriptandxml原理:通过XMLHttpRequest与服务器交换数据服务器数据通过json或者xml格式返回浏览器通过js+css渲染展示数据GET创建xhropen打开连接监听readystatereadyState4准备状态完毕status状态码200响应成功send发送<buttonid=”btn”>点击</button> <pid=”content”></p

  • Hook 技术简介

    Hook 技术简介#include”Windows.h”#include”tchar.h”#include”resource.h”HINSTANCEg_hInstance;staticHHOOKhHook=NULL;INT_PTRCALLBACKProcWinMain(HWNDhWnd,UINTMsg,WPARAMwParam,LPARAMlParam);LR

  • journalctl命令「建议收藏」

    journalctl命令「建议收藏」journalctl命令journalctl命令是Systemd日志系统的一个命令,主要用途是用来查看通过Systemd日志系统记录的日志,在Systemd出现之前,Linux系统及各应用的日志都是分别管理的,Systemd取代了initd之后便开始统一管理了所有Unit的启动日志,可以只用一个journalctl命令,查看所有内核和应用的日志。语法journalctl[OPTIONS…][MATCHES…]参数–no-full,–full,-l:当字段匹配可用列时将其省

  • js获取当前时间标准格式_js获取当前时间年月日并输出

    js获取当前时间标准格式_js获取当前时间年月日并输出/** *获取当前时间格式:yyyy-MM-ddHH:MM:SS */functiongetCurrentTime(){   vardate=newDate();//当前时间   varmonth=zeroFill(date.getMonth()+1);//月   varday=zeroFill(date.getDate());//日   …

发表回复

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

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