前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >一文让你彻底明白什么是一致性哈希

一文让你彻底明白什么是一致性哈希

原创
作者头像
xujjj
修改2019-07-01 11:07:37
1.3K0
修改2019-07-01 11:07:37
举报
文章被收录于专栏:IT界的泥石流

经典服务器结构

整个服务器的结构由前端负载服务器(图中的4个小圈圈代表4台前端负载服务器,用于分流)后端的服务器(图中的三个小方块,m0、m1、m2代表三台后端服务器,用于存放数据)组成。

此时客户端发来两条数据{“xu”,666}和{"jian",888},经过前端负载服务器把"xu"和"jian"分别进行hash("xu")和hash("jian")的操作然后模3(因为只有3台机器)分别得到hash("xu")%3=0,hash("jian")%3=2,然后分别把{"xu",666}和{"jian",888}两条数据分别存放在m0和m2上。

这种是经典的服务器结构,它在前端服务器上使用hash函数把数据分流到m0、m1、m2上,因为hash函数具有大样本的情况下均匀分布的特征,因此m0、m1、m2可以进行抗压,而不是一堆数据都存在一个服务器上,这叫做负载均衡

同学A:那我如果想在整个服务器集群上加机器或者减机器怎么办呢?原来是hash值模3,现在我加机器加到100台,那所有的数据不得重新计算了,所有数据都得重新hash然后模100,那数据迁移的代价得多大啊???

同学B:是啊,所以我们就引入了一种叫一致性哈希的结构,它可以把数据迁移的代价降低。而且负载均衡

一致性哈希

首先,把任何输入都进行hash得到哈希值为0~2^64(当然也可以定义别的范围),然后顺时针方向从小到大组成一个圆环

然后后端服务器同样是m1、m2、m3三台服务器组成集群,然后每台机器都有一个唯一的编号,可以使用机器的ip地址、mac地址等其中的一个做每台机器的唯一标识,例如我们使用机器的mac地址,然后进行hash(mac)得到一个哈希值,然后把机器放到该位置上因为三个机器把整个圆均等分成了三份,故数据的存放也是均匀的,所以具有负载均衡的效果。

因此,m0、m1、m2哈希值是递增的序列,这时,客户端同样是三条数据data1、data2、data3,经过前端负载服务器,然后把data1、data2、data3分别进行hash(data1)、hash(data2)和hash(data3)的操作,分别得到三个哈希值,接着按顺时针方向找到最近的机器进行存储。如图,data1存放在m0,data2存放在m1,data3存放在m2上。

因此,由顺时针法则,某数据的哈希值如果在红色的区域,则存放在m0上,哈希值如果在绿色区域,则存放在m1上,哈希值如果在蓝色区域,则存放在m2上。

每个前端负载服务器都有一个按后端服务器哈希值升序排好序的序列,例如每个前端负载服务器都有后端三个按哈希值升序排好序的机器[m1,m3,m2],每当数据来到前端负载服务器时,计算该数据的哈希值,然后从排好序的机器序列中找到第一个比该数据哈希值大的数,就把该数据存到该机器上。该部分可使用二分法进行查找。即使机器很多,但是代价查找只有logn

例如有三台机器m1、m2、m3,它们的哈希值分别是1、5、3,所有按升序排序后的结果如图。

有一个数据data经过前端负载服务器得到hash值为4,然后在[1,3,5]中找到第一个比4大的数,即为5,所以该数据应该存放在哈希值为5对应的机器m2上。

一致性哈希数据迁移问题

假设原来的后端服务器集群只有m1、m2、m3三台机器。

hash值在绿色区间这段的数据存放在m1上,此时加多了一台m3机器,计算hash值后得到的值在m0和m1之间。

因此,按顺时针原则,只需要把哈希值在m0和m3之间的存放在m1上的数据迁移到m3即可。因此数据迁移的代价减少了。

同学A:原来如此,哈希一致性原来就是一种服务器的结构,但是我还有两个问题画个图给你说把。

—问题1—:hash函数是在大样本的情况下才会均匀,如果现在机器比较少的情况下,hash后机器的位置分布不均匀怎么办?

—问题2—:加机器后也会导致不均匀的情况。

以上这两种情况可能会导致负载不均衡,有的负载大有的负载小啊。

同学B:别急哈,有一种叫做技术很好地解决了你提的这两个问题,我现在好饿,得去吃饭了,下次再跟你说把,嘻嘻O(∩_∩)O

更多内容知识干货,欢迎关注我们的微信公众号:IT界的泥石流

原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。

如有侵权,请联系 cloudcommunity@tencent.com 删除。

原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。

如有侵权,请联系 cloudcommunity@tencent.com 删除。

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 经典服务器结构
  • 一致性哈希
  • 一致性哈希数据迁移问题
相关产品与服务
负载均衡
负载均衡(Cloud Load Balancer,CLB)提供安全快捷的流量分发服务,访问流量经由 CLB 可以自动分配到云中的多台后端服务器上,扩展系统的服务能力并消除单点故障。负载均衡支持亿级连接和千万级并发,可轻松应对大流量访问,满足业务需求。
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档