一致性哈希算法

1.哈希算法的局限性

通过哈希算法,每个 key 都可以寻址到对应的服务器,比如,查询 key 是 key-01,计算公式为 hash(key-01) % 3 ,经过计算寻址到了编号为 1 的服务器节点 A。

但如果服务器数量发生变化,基于新的服务器数量来执行哈希算法的时候,就会出现路由寻址失败的情况,Proxy 无法找到之前寻址到的那个服务器节点。假如 3 个节点不能满足业务需要了,这时我们增加了一个节点,节点的数量从3 变化为 4,那么之前的 hash(key-01) % 3 = 1,就变成了 hash(key-01) % 4 = X,因为取模运算发生了变化,所以这个 X 大概率不是 1(可能 X 为 2),这时你再查询,就会找不到数据了,因为 key-01 对应的数据,存储在节点 A 上,而不是节点 B:

同样的道理,如果我们需要下线 1 个服务器节点(也就是缩容),也会存在类似的可能查询不到数据的问题。
而解决这个问题的办法,在于我们要迁移数据,基于新的计算公式 hash(key-01) % 4 ,来重新对数据和节点做映射。需要你注意的是,数据的迁移成本是非常高的。为了便于你理解,我举个例子,对于 1000 万 key 的 3 节点 KV 存储,如果我们增加 1 个节点,变为 4 节点集群,则需要迁移 75% 的数据。

$ go run ./hash.go -keys 10000000 -nodes 3 -new-nodes 4
74.999980%

2.一致性哈希怎么做

一致哈希算法也用了取模运算,但与哈希算法不同的是,哈希算法是对节点的数量进行取模运算,而一致哈希算法是对 2^32 进行取模运算。你可以想象下,一致哈希算法,将整个哈希值空间组织成一个虚拟的圆环,也就是哈希环。
哈希环的空间是按顺时针方向组织的,圆环的正上方的点代表 0,0点右侧的第一个点代表 1,以此类推,2、3、4、5、6……直到 2^32-1,也就是说 0 点左侧的第一个点代表 2^32-1。
在一致哈希中,你可以通过执行哈希算法(为了演示方便,假设哈希算法函数为“c-hash()”),将节点映射到哈希环上,比如选择节点的主机名作为参数执行 c-hash(),那么每个节点就能确定其在哈希环上的位置了:

当需要对指定 key 的值进行读写的时候,你可以通过下面 2 步进行寻址:
1.首先,将 key 作为参数执行 c-hash() 计算哈希值,并确定此 key 在环上的位置;
2.然后,从这个位置沿着哈希环顺时针“行走”,遇到的第一节点就是 key 对应的节点。
为了帮助你更好地理解如何通过一致哈希进行寻址,我举个例子。假设 key-01、key-02、key-03 三个 key,经过哈希算法 c-hash() 计算后,在哈希环上的位置如下:

假设有一个节点故障:

你可以看到,key-01 和 key-02 不会受到影响,只有 key-03 的寻址被重定位到 A。一般来说,在一致哈希算法中,如果某个节点宕机不可用了,那么受影响的数据仅仅是,会寻址到此节点和前一节点之间的数据。比如当节点 C 宕机了,受影响的数据是会寻址到节点 B和节点 C 之间的数据(例如 key-03),寻址到其他哈希环空间的数据(例如 key-01),不会受到影响。
假设需要扩容一个节点:

你可以看到,key-01、key-02 不受影响,只有 key-03 的寻址被重定位到新节点 D。一般而言,在一致哈希算法中,如果增加一个节点,受影响的数据仅仅是,会寻址到新节点和前一节点之间的数据,其它数据也不会受到影响。
让我们一起来看一个例子。使用一致哈希的话,对于 1000 万 key 的 3 节点 KV 存储,如果我们增加 1 个节点,变为 4 节点集群,只需要迁移 24.3% 的数据:

$ go run ./consistent-hash.go -keys 10000000 -nodes 3 -new-nodes 4
24.301550%

3.虚拟节点

在哈希寻址中常出现这样的问题:客户端访问请求集中在少数的节点上,出现了有些机器高负载,有些机器低负载的情况,那么在一致哈希中,有什么办法能让数据访问分布的比较均匀呢?答案就是虚拟节点。
在一致哈希中,如果节点太少,容易因为节点分布不均匀造成数据访问的冷热不均,也就是说大多数访问请求都会集中少量几个节点上:

你能从图中看到,虽然有 3 个节点,但访问请求主要集中的节点 A 上。那如何通过虚拟节点解决冷热不均的问题呢?
其实,就是对每一个服务器节点计算多个哈希值,在每个计算结果位置上,都放置一个虚拟节点,并将虚拟节点映射到实际节点。比如,可以在主机名的后面增加编号,分别计算“Node-A-01”“Node-A-02”“Node-B-01”“Node-B-02”“Node-C-01”“Node-C-02”的哈希值,于是形成 6 个虚拟节点:

本文转载于网络 如有侵权请联系删除

相关文章

  • Matplotlib三维绘图,这一篇就够了

    这篇博客将介绍使用mplot3d工具包进行三维绘图,支持简单的3D图形,包括曲面、线框、散点图和条形图。1.效果图1.13D线效果图3D线图效果如下:可自定义线的颜色及点的样式;1.23D散点效果图3D散点图(标记了着色以呈现深度外观)效果如下:1.33D随机颜色散点效果图3D随机颜色散点图效果如下:1.43D散点不同mark点效果图3D官方散点图不同mark点效果如下:1.53D线框效果图3D线框图效果如下:1.63D曲面不透明效果图3D曲面图不透明如下:1.73D曲面透明效果图3D曲面图透明如下:2.源码#matplotlib3D绘图 #3D轴(属于Axes3D类)是通过将projection="3d"关键字参数传递给Figure.add_subplot来创建的: frommpl_toolkits.mplot3dimportaxes3d importmatplotlib.pyplotasplt importnumpyasnp x=np.arange(100) y=np.random.randint(0,300,100) z=np.random.randint

  • dubbo泛化实现与引用

    现在分布式架构盛行,RPC框架也被大家熟知,目前就国内而言,dubbo可以说是中小型企业的首选。我们先看一下官网上的一张图:这张图从架构的角度展现了,dubbo框架的关键组件和实现方式。那么我们在日常开发中的使用方式大概如下图:也就是说服务提供者,有一个interface(也叫client),还有一个服务实现,interface给消费者依赖。这样做没问题,我们分析一下,这种方式有优点也会优缺点:优点:1)消费端像调用本地服务一样调用远程服务,使用简单缺点:1)服务端interface会带过来一些依赖可能和消费端某些依赖冲突2)服务端interface也许会把自己的配置传递到消费端,导致消费端平白无故要多配置完全和自己无关或者不关心的项假如我有一下这些场景:1)消费端只依赖了服务端一个服务(或者说很少)2)消费端不想把interface的依赖带过来,导致需要花费人力成本去排包,让依赖变得特别重3)消费端只依赖服务,只关心它所以来的服务调用方式和返回结果,完全不关心你服务怎么实现的,你依赖什么配置,你把这些配置传递给我,我是无法接受的基于上述问题和描述的应用场景,dubbo提供了泛化引用。

  • 4K+UHD浸入式音频直播(2018FIFA世界杯)

    本文为媒矿工厂编译的技术文章原标题:4KUHDHDRANDIMMERSIVEAUDIOLIVESTREAMING2018FIFAWORLDCUPRUSSIAFORSAMSUNGSMARTTVSAPP原文作者:L.Carvano,A.T.Gomes,A.S.Murakami翻译整理:郝明月本文来自IBC2019。本文旨在介绍巴西Globosat公司和三星(巴西)合作实现的2018俄罗斯FIFA世界杯56场比赛直播的经验,挑战,技术和结果,这次合作主要针对的是配备4KUHDHDR和浸入式音频设备的电视用户。合作内容包括由Globosat公司制作的进行了浸入式音频混合的4KUHDHDR信号以及180°中央摄像机拍摄的4KUHDSDR信号(国际音频)。直播开始于比赛前15分钟,于比赛结束后5分钟停止。本次合作的两个最大挑战是缩短4K视频直播的延迟以及在比赛结束后尽快上线相应比赛的整个视频点播服务。直播APP的相关技术细节是2160p@60Hz,BT.2020,HDR-10(结合杜比全景声音频),在测试开始时,APP上直播的初始延迟是2分钟,在经过一系列的参数调整(比特率,块大小,杜比全景声设备

  • 打破深度学习局限,强化学习、深度森林或是企业AI决策技术的“良药”

    算法、算力和数据是人工智能时代的三驾马车,成为企业赋能人工智能的动力,但它们自身的特性也为企业和高校在研究和落地应用过程带来了重重挑战。比如,训练算法的成本高昂,数据从采集、处理到存储已面临瓶颈,目前针对算法的加速芯片已成为硬件开发商的一大趋势。但问题是,这些加速芯片是否能对不断适应提出的新算法?在这些挑战下,降低算法成本,加速训练,推进决策,已成为所以高校、企业共同迫切的需求。 8月31日,英特尔第二期AI实践者之声夏令营活动走进南京大学。南京大学人工智能学院教授俞扬、英特尔(中国)人工智能行业客户总监孙宇和创新工场南京国际人工智能研究院执行院长冯霁围绕打破理论与实践的壁垒,助力企业高效应用落地,推动未来人工智能服务新架构等内容进行了技术分享与探讨。提高算法效力,打破强化学习落地门槛机器学习中一个经典的分类是监督学习、非监督学习和强化学习。监督学习是预测的过程,而强化学习即为决策的过程。现在,人工智能的识别与预测任务已经得到了广泛落地。但实际应用场景中,如推荐系统其实是一个决策过程,并非预测任务,因此系统仅有识别与预测并不够,还需要完成大量目标任务,采取一系列动作或行为使之具备决策能

  • 云计算---openstack创建虚拟机过程

    虚拟机创建过程: (1)界面或命令行通过RESTfulAPI向keystone获取认证信息。 (2)keystone通过用户请求认证信息,并生成auth-token返回给对应的认证请求。 (3)界面或命令行通过RESTfulAPI向nova-api发送一个bootinstance的请求(携带auth-token)。 (4)nova-api接受请求后向keystone发送认证请求,查看token是否为有效用户和token。 (5)keystone验证token是否有效,如有效则返回有效的认证和对应的角色(注:有些操作需要有角色权限才能操作)。 (6)通过认证后nova-api和数据库通讯。 (7)初始化新建虚拟机的数据库记录。 (8)nova-api通过rpc.call向nova-scheduler请求是否有创建虚拟机的资源(HostID)。 (9)nova-scheduler进程侦听消息队列,获取nova-api的请求。 (10)nova-scheduler通过查询nova数据库中计算资源的情况,并通过调度算法计算符合虚拟机创建需要的主机。 (11)对于有符合虚拟机创建的主机,nov

  • SpringCloudGateway笔记(6)-请求体不全

    版权声明:本文为博主原创文章,遵循CC4.0BY-SA版权协议,转载请附上原文出处链接和本声明。本文链接:https://blog.csdn.net/yingziisme/article/details/94591049实际使用遇到的问题–在filter里面获取RequestBody不完整以及LEAKMEMORY的问题第一种获取方式在网上找到的最常见的一种获取RequestBody的方式是privateStringresolveBodyFromRequest(ServerHttpRequestserverHttpRequest){ //获取请求体 Flux<DataBuffer>body=serverHttpRequest.getBody(); StringBuildersb=newStringBuilder(); body.subscribe(buffer->{ byte[]bytes=newbyte[buffer.readableByteCount()]; buffer.read(bytes); DataBufferUtils.release(buffer);

  • Python中的偏函数和函数柯里化

    偏函数(partial)和函数柯里化(currying)是函数式编程中常用的技术。有时候我们在复用已有函数时可能需要固定其中的部分参数,这除了可以通过默认值参数来实现之外,还可以使用偏函数。例如有个函数用来实现3个数字相加:defadd3(a,b,c):returna+b+c如果现在需要一个类似的函数,与上面的函数add3()的区别仅在于参数b固定为一个数字(例如666),这时就可以使用偏函数的技术来复用上面的函数,例如:defadd2(a,c):returnadd3(a,666,c)print(add2(1,1))或者使用标准库functools提供的partial方法:fromfunctoolsimportpartialadd2=partial(add3,b=666)print(add2(a=1,c=1))函数柯里化除了可以实现偏函数类似的功能之外,还可以利用单参数函数来实现多参数函数,这要归功于Python对函数嵌套定义和lambda表达式的支持。例如:deffunc(a):returnlambdab:a+bprint(func(3)(5))或者deffunc(a):deffun

  • Intellij IDEA调试功能使用总结

    专注于Java领域,追求简洁,每天为您推送高质量技术文章,实用教程。专注于Java领域,追求简洁,每天推送高质量技术文章,实用教程。这段时间一直在使用IntellijIDEA,今天把调试区工具的使用方法记录于此。先编译好要调试的程序。1.设置断点选定要设置断点的代码行,在行号的区域后面单击鼠标左键即可。2.开启调试会话点击红色箭头指向的小虫子,开始进入调试。IDE下方出现Debug视图,红色的箭头指向的是现在调试程序停留的代码行,方法f2()中,程序的第11行。红色箭头悬停的区域是程序的方法调用栈区。在这个区域中显示了程序执行到断点处所调用过的所用方法,越下面的方法被调用的越早。3.单步调试3.1stepover点击红色箭头指向的按钮,程序向下执行一行(如果当前行有方法调用,这个方法将被执行完毕返回,然后到下一行)3.2stepinto点击红色箭头指向的按钮,程序向下执行一行。如果该行有自定义方法,则运行进入自定义方法(不会进入官方类库的方法)。具体步骤如下:在自定义方法发f1()处设置断点,执行调试点击3.3Forcestepinto 该按钮在调试的时候能进入任何方法。3.4step

  • 腾讯云云游戏游戏预热

    腾讯云云游戏提供了游戏预热功能,预热功能可将选定的游戏,在分组内的并发提前运行。当请求该分组的对应游戏时,将启动完成的游戏画面快速呈现,减少用户等待时间。 注意事项 分组内的并发仅可预热一款游戏,当其他游戏请求该分组的并发时,选中的并发会关闭正在预热的游戏,再正常启动新的游戏。 预热设置变更需要时间生效,首次预热设置生效时间约1分钟,预热变更生效时间约1分钟。 取消分组预热,确认后将关闭分组下,空闲状态并发中正在预热的游戏。 操作步骤 开启游戏预热 进入腾讯云云游戏控制台。 单击左侧导航栏云游戏实例>分组管理。 在实例分组列表中,选择需要被修改实例分组,单击右侧的预热设置。 选择要预热的游戏,确认生效。 取消游戏预热 进入腾讯云云游戏控制台。 单击左侧导航栏云游戏实例>分组管理。 在实例分组列表中,选择需要取消预热的实例分组,单击右侧的取消预热,确认生效。

  • python常见面试集合

    Python面试题目一、Python1.python的多进程与多线程的运行机制是什么?有什么区别?分别在什么情况下用?2.Python的装饰器的原理是什么,在什么情况会用到装饰器。请手写Python装饰器代码3.如何提高Python的运行效率,请说出不少于2种提高运行效率的方法。4.介绍下“消费者”和“生产者”模型。https://blog.csdn.net/sanyuesan0000/article/details/52996586https://www.cnblogs.com/alex09/p/6675664.html 二、HTTP/HTTPS,TCP/IP协议1.关于HTTP/HTTPS的区别,分别应该在什么场合下。 超文本传输协议HTTP协议被用于在Web浏览器和网站服务器之间传递信息,HTTP协议以明文方式发送内容,不提供任何方式的数据加密,如果攻击者截取了Web浏览器和网站服务器之间的传输报文,就可以直接读懂其中的信息,因此,HTTP协议不适合传输一些敏感信息,比如:信用卡号、密码等支付信息。 为了解决HTTP协议的这一缺陷,需要使用另一种协议:安全套接字层超文本传输协议H

  • python基础之socket套接字基础part2

    基于UDP的socket 面向无连接的不可靠数据传输,可以没有服务器端,只不过没有服务器端,发送的数据会被直接丢弃,并不能到达服务器端 1#客户端 2importsocket 3ip_port=('127.0.0.1',8080) 4BUFSIZE=1024 5sock_client=socket.socket(socket.AF_INET,socket.SOCK_DGRAM)#SOCK_DGRAM就是UDP 6whileTrue: 7msg=input('>>').strip() 8ifnotmsg:continue 9sock_client.sendto(msg.encode('utf-8'),ip_port)#UDP用的是sendto发送数据复制 UDP服务端+客户端 1#服务端 2importsocket 3ip_port=('127.0.0.1',8080) 4BUFSIZE=1024 5sock_server=socket.socket(socket.AF_INET,socket.SOCK_DGRAM) 6sock_server.bind(ip_port)

  • 无法搜索联机扩展 因为尝试与服务器联系 Visual studio 怎么解决?

    根目录: devenv.exe.config 编辑: 修改如下即可: <system.net> <defaultProxyuseDefaultCredentials="true"enabled="true"> <proxyusesystemdefault="true"/> </defaultProxy> <settings> <ipv6enabled="true"/> </settings> </system.net>复制  

  • jQuery页面滚动数字增长插件

    <!DOCTYPEhtml> <html> <head> <metacharset="UTF-8"> <title></title> <linkrel="stylesheet"href="jQuery.running.css"/> <style> ul,li{list-style:none;} h3{font-size:50px;} html,body{ height:200%; } </style> </head> <body> <divclass="item"> <ul> <li><h3><spanclass="animateNum"data-animatetarget="999.9">999.9</span>万</h3></li><!--需要为小数点--> <li><h3><spanclass="animateNu

  • #【Python】【demo实验23】【练习实例】【 三人比赛顺序问题 】

    原题: 两个乒乓球队进行比赛,各出三人。甲队为a,b,c三人,乙队为x,y,z三人。已抽签决定比赛名单。有人向队员打听比赛的名单。a说他不和x比,c说他不和x,z比,请编程序找出三队赛手的名单。     我的源码:     原题给出的解答:       ————————(我是分割线)———————— 参考: 1.RUNOOB.COM:https://www.runoob.com/python/python-exercise-example22.html     备注: 初次编辑时间:2019年10月6日09:37:55 环境:Windows7  /Python3.7.2 ———————— 欢迎访问我的博客; 如果您觉得有用,请点赞! 说明: 标题带有*表示重要或待重新查看确认 标题带有#表示未编辑完成;待补充 标题带有######表示为概要目录

  • libpcap编程实例

    1#include<stdio.h> 2#include<stdlib.h> 3#include<pcap.h> 4#include<errno.h> 5#include<sys/socket.h> 6#include<netinet/in.h> 7#include<arpa/inet.h> 8 9intmain(intargc,char**argv) 10{ 11char*dev; 12char*net; 13char*mask; 14intret; 15charerrbuf[PCAP_ERRBUF_SIZE]; 16bpf_u_int32netp; 17bpf_u_int32maskp; 18structin_addraddr; 19 20 21dev=pcap_lookupdev(errbuf); 22 23 24if(dev==NULL) 25{ 26printf("%s\n",errbuf); 27exit(1); 28} 29 30 31printf("DEV:%s\n",dev); 3

  • Custom Email Attribute在客户端不起作用原因

    原文发布时间为:2011-07-16——来源于本人的百度文章[由搬家工具导入]CustomEmailAttribute在客户端不起作用原因,就是未实现IClientValidatable接口。必须实现这个接口,才可以。如下:  publicclassEmailAttribute:RegularExpressionAttribute,IClientValidatable   {       publicEmailAttribute()           :base(@"^([a-zA-Z0-9_\-\.]+)@((\[[0-9]{1,3}\.[0-9]{1,3}\.[0-9]{1,3}\.)|(([a-zA-Z0-9\-]+\.)+))([a-zA-Z]{2,4}|[0-9]{1,3})$")     &nbs

  • LeetCode 20

    20.有效的括号 思路:用一个栈记录右括号,遍历整个字符串,每遇到一个左括号,便将其对应的右括号压入栈中,可知内层的括号在栈顶,如果遇到右括号,分为两种情况,其一,栈内无元素,说明该右括号无落单,其二,弹出的栈顶元素与该右括号不同,说明该右括号匹配失败,两种情况都为false。最后,如果栈中仍然有元素,说明左括号落单,返回false,若无元素,则为true。 Java classSolution{ publicbooleanisValid(Strings){ Stack<Character>st=newStack<>(); for(charc:s.toCharArray()){ if(c=='('){ st.push(')'); }elseif(c=='['){ st.push(']'); }elseif(c=='{'){ st.push('}'); }elseif(st.isEmpty()||c!=st.pop()){ returnfalse; } } returnst.isEmpty(); } } 复制

  • WebSocket与消息推送

    注:转载自https://www.cnblogs.com/best/archive/2016/09/12/5695570.html WebSocket与消息推送   目录 一、Socket简介 二、WebSocket简介与消息推送 三、WebSocket客户端 四、WebSocket服务器端 五、测试运行 六、小结与消息推送框架 6.1、开源Java消息推送框架Pushlet 6.2、开源DotNet消息推送框架SignalR 七、代码下载 7.1、Java实现的服务器端代码与客户端代码下载 7.2、DotNet服务器端手动连接实现代码下载 7.3、DotNet下使用SuperWebSocket三方库实现代码下载 B/S结构的软件项目中有时客户端需要实时的获得服务器消息,但默认HTTP协议只支持请求响应模式,这样做可以简化Web服务器,减少服务器的负担,加快响应速度,因为服务器不需要与客户端长时间建立一个通信链接,但不容易直接完成实时的消息推送功能,如聊天室、后台信息提示、实时更新数据等功能,但通过polling、Longpolling、长连接、Flas

  • python print end=&#39; &#39; 不换行

    python3.x实现print不换行   python中print之后是默认换行的,是因为其默认属性end默认值为"\n"(\n为换行符)。   做练习99乘法表时不想换行,改变print默认换行的属性就可以了。   方法:   print('win147',end='!@#$%^&*') # end就表示print将如何结束,默认为end="\n"(\n为换行符)   例如:     print('23祝大家天天开心',end='!')  >>>23祝大家天天开心!复制  

  • JTA Entity JPA 事务(Transaction) 会话(Conversation)

    JTA深度历险-原理与实现 JTA使用 EntityManager使用方法-merge/flush/createNaiveQuery EntityManager方法简介 EJB之JPA(EntityManager—类似于3千问) bean的写法-JPA实体的映射 J2EE持久层持久化上下文的传播以及会话(Conversation)实现 @OneToMany、@ManyToOne @OneToMany、@ManyToOne以及@ManyToMany @OneToMany、@ManyToOne例子 EntityManager详解 Hibernate-JPA-Derby http://hibernate-jpa-derby-example.blogspot.com/ http://michaljedynak.blogspot.com/2013/01/hibernate-jpa-sample-project.html http://stackoverflow.com/questions/12688162/java-standalone-app-with-jpa-hibernate-or

  • 清空SQL Server数据库中所有表数据的方法

    其实删除数据库中数据的方法并不复杂,为什么我还要多此一举呢,一是我这里介绍的是删除数据库的所有数据,因为数据之间可能形成相互约束关系,删除操作可能陷入死循环,二是这里使用了微软未正式公开的sp_MSForEachTable存储过程。   也许很多读者朋友都经历过这样的事情:要在开发数据库基础上清理一个空库,但由于对数据库结构缺乏整体了解,在删除一个表的记录时,删除不了,因为可能有外键约束,一个常见的数据库结构是一个主表,一个子表,这种情况下一般都得先删除子表记录,再删除主表记录。   说道删除数据记录,往往马上会想到的是delete和truncate语句,但在遇到在两个或多个表之间存在约束的话,这两个语句可能都会失效,而且最要命的是这两个命令都只能一次操作一个表。那么真正遇到要删除SQLServer数据库中所有记录时,该怎么办呢?有两个选择:   1.按照先后顺序逐个删除,这个方法在表非常多的情况下显得很不现实,即便是表数量不多,但约束比较多时,你还是要花费大量的时间和精力去研究其间的约束关系,然后找出先删哪个表,再删哪个表,最后又删哪个表。   2.禁用所有约束,删除所有数据,最后再

相关推荐

推荐阅读