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


前言


要了解一致性哈希,我们先从经典的服务器结构说起。

经典服务器结构


整个服务器的结构由前端负载服务器(图中的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可以进行抗压,而不是一堆数据都存在一个服务器上,这叫做负载均衡。


一致性哈希


首先,把任何 输入都进行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即可。因此 数据迁移的代价减少了



问题1


问题2



声明:所有在本站发表的文章,本站都具有最终编辑权。本站全部作品均系币力财经原创或来自网络转载,转载目的在于传递更多信息,并不代表本站赞同其观点和对其真实性负责,所产生的纠纷与本站无关。如涉及作品内容、版权和其它问题,请尽快与本站联系,联系邮箱huiccsu@qq.com。