白话解析:一致性哈希算法 consistent hashing

 

在了解一致性哈希算法之前,最好先了解一下缓存中的一个应用场景,了解了这个应用场景之后,再来理解一致性哈希算法,就容易多了,也更能体现出一致性哈希算法的优点,那么,我们先来描述一下这个经典的分布式缓存的应用场景。

场景描述

假设,我们有三台缓存服务器,用于缓存图片,我们为这三台缓存服务器编号为0号、1号、2号,现在,有3万张图片需要缓存,我们希望这些图片被均匀的缓存到这3台服务器上,以便它们能够分摊缓存的压力。也就是说,我们希望每台服务器能够缓存1万张左右的图片,那么,我们应该怎样做呢?如果我们没有任何规律的将3万张图片平均的缓存在3台服务器上,可以满足我们的要求吗?可以!但是如果这样做,当我们需要访问某个缓存项时,则需要遍历3台缓存服务器,从3万个缓存项中找到我们需要访问的缓存,遍历的过程效率太低,时间太长,当我们找到需要访问的缓存项时,时长可能是不能被接受的,也就失去了缓存的意义,缓存的目的就是提高速度,改善用户体验,减轻后端服务器压力,如果每次访问一个缓存项都需要遍历所有缓存服务器的所有缓存项,想想就觉得很累,那么,我们该怎么办呢?原始的做法是对缓存项的键进行哈希,将hash后的结果对缓存服务器的数量进行取模操作,通过取模后的结果,决定缓存项将会缓存在哪一台服务器上,这样说可能不太容易理解,我们举例说明,仍然以刚才描述的场景为例,假设我们使用图片名称作为访问图片的key,假设图片名称是不重复的,那么,我们可以使用如下公式,计算出图片应该存放在哪台服务器上。

hash(图片名称)% N

因为图片的名称是不重复的,所以,当我们对同一个图片名称做相同的哈希计算时,得出的结果应该是不变的,如果我们有3台服务器,使用哈希后的结果对3求余,那么余数一定是0、1或者2,没错,正好与我们之前的服务器编号相同,如果求余的结果为0, 我们就把当前图片名称对应的图片缓存在0号服务器上,如果余数为1,就把当前图片名对应的图片缓存在1号服务器上,如果余数为2,同理,那么,当我们访问任意一个图片的时候,只要再次对图片名称进行上述运算,即可得出对应的图片应该存放在哪一台缓存服务器上,我们只要在这一台服务器上查找图片即可,如果图片在对应的服务器上不存在,则证明对应的图片没有被缓存,也不用再去遍历其他缓存服务器了,通过这样的方法,即可将3万张图片随机的分布到3台缓存服务器上了,而且下次访问某张图片时,直接能够判断出该图片应该存在于哪台缓存服务器上,这样就能满足我们的需求了,我们暂时称上述算法为HASH算法或者取模算法,取模算法的过程可以用下图表示。

hash.png

但是,使用上述HASH算法进行缓存时,会出现一些缺陷,试想一下,如果3台缓存服务器已经不能满足我们的缓存需求,那么我们应该怎么做呢?没错,很简单,多增加两台缓存服务器不就行了,假设,我们增加了一台缓存服务器,那么缓存服务器的数量就由3台变成了4台,此时,如果仍然使用上述方法对同一张图片进行缓存,那么这张图片所在的服务器编号必定与原来3台服务器时所在的服务器编号不同,因为除数由3变为了4,被除数不变的情况下,余数肯定不同,这种情况带来的结果就是当服务器数量变动时,所有缓存的位置都要发生改变,换句话说,当服务器数量发生改变时,所有缓存在一定时间内是失效的,当应用无法从缓存中获取数据时,则会向后端服务器请求数据,同理,假设3台缓存中突然有一台缓存服务器出现了故障,无法进行缓存,那么我们则需要将故障机器移除,但是如果移除了一台缓存服务器,那么缓存服务器数量从3台变为2台,如果想要访问一张图片,这张图片的缓存位置必定会发生改变,以前缓存的图片也会失去缓存的作用与意义,由于大量缓存在同一时间失效,造成了缓存的雪崩,此时前端缓存已经无法起到承担部分压力的作用,后端服务器将会承受巨大的压力,整个系统很有可能被压垮,所以,我们应该想办法不让这种情况发生,但是由于上述HASH算法本身的缘故,使用取模法进行缓存时,这种情况是无法避免的,为了解决这些问题,一致性哈希算法诞生了。

 

我们来回顾一下使用上述算法会出现的问题。

问题1:当缓存服务器数量发生变化时,会引起缓存的雪崩,可能会引起整体系统压力过大而崩溃(大量缓存同一时间失效)。

问题2:当缓存服务器数量发生变化时,几乎所有缓存的位置都会发生改变,怎样才能尽量减少受影响的缓存呢?

 

其实,上面两个问题是一个问题,那么,一致性哈希算法能够解决上述问题吗?

我们现在就来了解一下一致性哈希算法。

 

一致性哈希算法的基本概念

其实,一致性哈希算法也是使用取模的方法,只是,刚才描述的取模法是对服务器的数量进行取模,而一致性哈希算法是对2^32取模,什么意思呢?我们慢慢聊。

 

首先,我们把二的三十二次方想象成一个圆,就像钟表一样,钟表的圆可以理解成由60个点组成的圆,而此处我们把这个圆想象成由2^32个点组成的圆,示意图如下:

圆环的正上方的点代表0,0点右侧的第一个点代表1,以此类推,2、3、4、5、6……直到2^32-1,也就是说0点左侧的第一个点代表2^32-1

我们把这个由2的32次方个点组成的圆环称为hash环。

 

那么,一致性哈希算法与上图中的圆环有什么关系呢?我们继续聊,仍然以之前描述的场景为例,假设我们有3台缓存服务器,服务器A、服务器B、服务器C,那么,在生产环境中,这三台服务器肯定有自己的IP地址,我们使用它们各自的IP地址进行哈希计算,使用哈希后的结果对2^32取模,可以使用如下公式示意。

hash(服务器A的IP地址) %  2^32

通过上述公式算出的结果一定是一个0到2^32-1之间的一个整数,我们就用算出的这个整数,代表服务器A,既然这个整数肯定处于0到2^32-1之间,那么,上图中的hash环上必定有一个点与这个整数对应,而我们刚才已经说明,使用这个整数代表服务器A,那么,服务器A就可以映射到这个环上,用下图示意

同理,服务器B与服务器C也可以通过相同的方法映射到上图中的hash环中

hash(服务器B的IP地址) %  2^32

hash(服务器C的IP地址) %  2^32

通过上述方法,可以将服务器B与服务器C映射到上图中的hash环上,示意图如下

假设3台服务器映射到hash环上以后如上图所示(当然,这是理想的情况,我们慢慢聊)。

 

好了,到目前为止,我们已经把缓存服务器与hash环联系在了一起,我们通过上述方法,把缓存服务器映射到了hash环上,那么使用同样的方法,我们也可以将需要缓存的对象映射到hash环上。

 

假设,我们需要使用缓存服务器缓存图片,而且我们仍然使用图片的名称作为找到图片的key,那么我们使用如下公式可以将图片映射到上图中的hash环上。

hash(图片名称) %  2^32

映射后的示意图如下,下图中的橘黄色圆形表示图片

好了,现在服务器与图片都被映射到了hash环上,那么上图中的这个图片到底应该被缓存到哪一台服务器上呢?上图中的图片将会被缓存到服务器A上,为什么呢?因为从图片的位置开始,沿顺时针方向遇到的第一个服务器就是A服务器,所以,上图中的图片将会被缓存到服务器A上,如下图所示。

没错,一致性哈希算法就是通过这种方法,判断一个对象应该被缓存到哪台服务器上的,将缓存服务器与被缓存对象都映射到hash环上以后,从被缓存对象的位置出发,沿顺时针方向遇到的第一个服务器,就是当前对象将要缓存于的服务器,由于被缓存对象与服务器hash后的值是固定的,所以,在服务器不变的情况下,一张图片必定会被缓存到固定的服务器上,那么,当下次想要访问这张图片时,只要再次使用相同的算法进行计算,即可算出这个图片被缓存在哪个服务器上,直接去对应的服务器查找对应的图片即可。

 

刚才的示例只使用了一张图片进行演示,假设有四张图片需要缓存,示意图如下

1号、2号图片将会被缓存到服务器A上,3号图片将会被缓存到服务器B上,4号图片将会被缓存到服务器C上。

 

一致性哈希算法的优点

经过上述描述,我想兄弟你应该已经明白了一致性哈希算法的原理了,但是话说回来,一致性哈希算法能够解决之前出现的问题吗,我们说过,如果简单的对服务器数量进行取模,那么当服务器数量发生变化时,会产生缓存的雪崩,从而很有可能导致系统崩溃,那么使用一致性哈希算法,能够避免这个问题吗?我们来模拟一遍,即可得到答案。

 

假设,服务器B出现了故障,我们现在需要将服务器B移除,那么,我们将上图中的服务器B从hash环上移除即可,移除服务器B以后示意图如下。

在服务器B未移除时,图片3应该被缓存到服务器B中,可是当服务器B移除以后,按照之前描述的一致性哈希算法的规则,图片3应该被缓存到服务器C中,因为从图片3的位置出发,沿顺时针方向遇到的第一个缓存服务器节点就是服务器C,也就是说,如果服务器B出现故障被移除时,图片3的缓存位置会发生改变

 

但是,图片4仍然会被缓存到服务器C中,图片1与图片2仍然会被缓存到服务器A中,这与服务器B移除之前并没有任何区别,这就是一致性哈希算法的优点,如果使用之前的hash算法,服务器数量发生改变时,所有服务器的所有缓存在同一时间失效了,而使用一致性哈希算法时,服务器的数量如果发生改变,并不是所有缓存都会失效,而是只有部分缓存会失效,前端的缓存仍然能分担整个系统的压力,而不至于所有压力都在同一时间集中到后端服务器上。

 

这就是一致性哈希算法所体现出的优点。

 

hash环的偏斜

在介绍一致性哈希的概念时,我们理想化的将3台服务器均匀的映射到了hash环上,如下图所示

但是,理想很丰满,现实很骨感,我们想象的与实际情况往往不一样。

在实际的映射中,服务器可能会被映射成如下模样。

聪明如你一定想到了,如果服务器被映射成上图中的模样,那么被缓存的对象很有可能大部分集中缓存在某一台服务器上,如下图所示。

上图中,1号、2号、3号、4号、6号图片均被缓存在了服务器A上,只有5号图片被缓存在了服务器B上,服务器C上甚至没有缓存任何图片,如果出现上图中的情况,A、B、C三台服务器并没有被合理的平均的充分利用,缓存分布的极度不均匀,而且,如果此时服务器A出现故障,那么失效缓存的数量也将达到最大值,在极端情况下,仍然有可能引起系统的崩溃,上图中的情况则被称之为hash环的偏斜,那么,我们应该怎样防止hash环的偏斜呢?一致性hash算法中使用”虚拟节点”解决了这个问题,我们继续聊。

 

虚拟节点

话接上文,由于我们只有3台服务器,当我们把服务器映射到hash环上的时候,很有可能出现hash环偏斜的情况,当hash环偏斜以后,缓存往往会极度不均衡的分布在各服务器上,聪明如你一定已经想到了,如果想要均衡的将缓存分布到3台服务器上,最好能让这3台服务器尽量多的、均匀的出现在hash环上,但是,真实的服务器资源只有3台,我们怎样凭空的让它们多起来呢,没错,就是凭空的让服务器节点多起来,既然没有多余的真正的物理服务器节点,我们就只能将现有的物理节点通过虚拟的方法复制出来,这些由实际节点虚拟复制而来的节点被称为”虚拟节点”。加入虚拟节点以后的hash环如下。

“虚拟节点”是”实际节点”(实际的物理服务器)在hash环上的复制品,一个实际节点可以对应多个虚拟节点。

从上图可以看出,A、B、C三台服务器分别虚拟出了一个虚拟节点,当然,如果你需要,也可以虚拟出更多的虚拟节点。引入虚拟节点的概念后,缓存的分布就均衡多了,上图中,1号、3号图片被缓存在服务器A中,5号、4号图片被缓存在服务器B中,6号、2号图片被缓存在服务器C中,如果你还不放心,可以虚拟出更多的虚拟节点,以便减小hash环偏斜所带来的影响,虚拟节点越多,hash环上的节点就越多,缓存被均匀分布的概率就越大。

 

好了,一致性哈希算法的原理就总结到这里,如有错误,欢迎赐教,如需转载,请标注原文链接。

原文链接:白话解析:一致性哈希算法 consistent hashing

 

© 版权声明
THE END
点赞807赞赏
分享
评论 共195条
    • 朱双印
    • xiaoyuemushan0
      博主又公众号吗
      14天前
    • 朱双印
    • GEMINI1
      学到了 通俗易懂 十分感谢
      22天前
    • 朱双印
    • DidiDaDiDa2
      我理解的一致哈希算法的核心是,预先把哈希值分为n个小区间。虽然没有n那么多的服务器,但可以用一台服务器管理其中一批或者几批小区间。当服务器数量变动,分配规则发生改变时,把服务器中不符合当前分配规则的数据区间,搬移到指定服务器。
      1月前
    • 朱双印
    • 憨憨3
      清晰易懂!👍
      2月前
    • 朱双印
    • 0xc0000100701
      这可真是日天秀
      2月前
    • 朱双印
    • MangoDowner2
      循序渐进,深入浅出,讲的真不错
      2月前
    • 朱双印
    • 哇咔咔0
      讲的太好了,很容易理解!感谢楼主
      2月前
    • 朱双印
    • miracle0
      讲的太好了,点赞
      3月前
    • 朱双印
    • Dominic0
      看了redis的哨兵模式有点好奇,学到了!
      3月前
    • 朱双印
    • 周筱明1
      懂了!! 讲的灰常好 通俗易懂 粉了
      4月前
    • 朱双印
    • 吃东西就变脸0
      讲的灰常好 通俗易懂 粉了
      4月前
    • 朱双印
    • 老铁2
      普通的hash算法在取模,也不一定数量改变以后所有缓存都失效,比如前后数量的公倍数,之前是2,后面改成3,哈希值为6的都在0的机器上,当然是这样的数据特别少,可以忽略不计了
      6月前
    • 朱双印
    • kikino0
      讲的真的很清楚
      6月前
    • 朱双印
    • ylong0
      好牛逼的讲解,关注了
      6月前
    • 朱双印
    • lili0
      make,慕名而来
      7月前
    • 朱双印
    • 蒙哥4
      牛逼,这是我第一次看懂哈希一致性
      7月前
    • 朱双印
    • 660
      大佬真是牛逼
      7月前
    • 朱双印
    • yyf0
      讲得太好了!!!
      7月前
    • 朱双印
    • 121210
      说的很好,谢谢
      8月前
    • 朱双印
    • HaoFng1
      博主厉害,我终于看懂了,谢谢
      8月前
    • 朱双印
    • 一只菜鸡5
      我理解能力这么差竟然都看懂了,博主天秀
      8月前
    • 朱双印
    • Leo0
      通俗易懂 感谢
      8月前
    • 朱双印
    • Gaoyze0
      通俗易懂,受教了
      8月前
    • 朱双印
    • 无需有太多0
      确实通俗易懂,牛逼!
      8月前
    • 朱双印
    • 青云0
      讲解得浅显易懂,学习了,谢谢博主~
      8月前
    • 朱双印
    • 进击的巨人0
      写的很不错,受教了
      10月前
    • 朱双印
    • 烟花易冷0
      受教了,之前一直一知半解,这回明白了
      12月前
    • 朱双印
    • 光之巨人0
      牛逼 老哥 一看就懂了
      12月前
    • 朱双印
    • wxttt0
      大佬,请教一下~ 对于虚拟节点那部分,假设有3台服务器,那么在环上构建3个虚拟节点把环均分,再维护虚拟节点和物理节点的映射关系,是不是就可以解决hash环的偏斜问题呢。 虚拟更多的节点,是为了保证在缓存内容映射到hash环上分布不均匀时,也能够平均缓存到不同的服务器上么?
      12月前
    • 朱双印
    • cloudy0
      老哥牛逼,讲的很通俗易懂。感谢老哥
      1年前
    • 朱双印
    • Henru Wang0
      这篇讲解一致性哈希算法的文章写得非常棒。通俗易懂,讲的很全面,很浅显,很易懂。
      1年前
    • 朱双印
    • pdzz0
      学到了,讲的非常好
      1年前
    • 朱双印
    • 松饼0
      简洁易懂,谢谢博主! 😛
      1年前
    • 朱双印
    • tt0
      学到了,感谢博主
      1年前
    • 朱双印
    • 鬼的昵称0
      很多问题啊,你这个例子太多bug了,例如,如果服务器B恢复了,你本该存到B服务器的由于服务器B挂掉而存到C上的数据这时候怎么读取?全局查找?如果算出来的图片哈希和地址哈希一样又是怎么解决?尤其是引入虚拟节点之后?又或者运气不好,新增加的服务器D算出来的哈希和你虚拟节点冲突不是又完了?很多很多问题啊
      1年前
    • 朱双印
    • .st0ne0
      如果情况极端一点,存储的图片也偏斜了,那还是由一个服务器承担大量的存储工作嘛?
      1年前
    • 朱双印
    • 好吃二师兄0
      虚拟节点的IP是如何被计算出来的呢?
      1年前
    • 朱双印
    • 好吃二师兄0
      感谢博主,实在厉害,佩服
      1年前
    • 朱双印
    • waste0
      很容易理解,我可以转载吗,怕以后找不到,会标明出处,谢谢大佬。
      1年前
    • 朱双印
    • 古道瘦马0
      确实讲的非常通俗易懂,还图文并茂。赞!
      2年前
    • 朱双印
    • AllenGFLiu0
      您好,最后提到的虚拟节点处还有一点疑问。为防止hash环的倾斜,由实际节点虚拟出来的一部分虚拟节点是怎么保证虚拟节点能按理想情况下排列的? 还是说生成虚拟节点的算法能自己定义虚拟节点所在的位置?
      2年前
      • 朱双印
        mesen2
        我觉得是你理解错了文中说的hash环倾斜,文中说的倾斜如果理解为数据倾斜就会好理解很多。也就是说,在hash环上的三个节点位置均等分布,但B节点的数据量却格外的多,那么可以在A到B之间增加虚拟节点C,此时,B节点的数据就会被分到C节点一部分,从而减小数据倾斜的概率。
        1年前@AllenGFLiu
    • 朱双印
    • 一抹茶色阳光丶0
      赞!能否转载一下
      2年前
    • 朱双印
    • 迷了一个你0
      为何一定要取余2的32次方,取余一个很大的固定值不行吗?不也可以形成一个值环吗?例如10w
      2年前
      • 朱双印
        夜不语0
        这个和计算机的存储有关系,一个字节有8位,就有2的八次方种排序。四个字节的话就是2的32次方
      • 朱双印
        QF7
        因为文中使用机器的IP地址取模的,IPv4的地址是4组8位2进制数组成,所以用2^32可以保证每个IP地址会有唯一的映射。
    • 朱双印
    • 松鼠病0
      一次就看懂了,感谢博主好文章
      2年前
    • 朱双印
    • 天明2
      楼主文章写的通俗易懂,非常不错。 指正一点:虽然使用取模的算法,会导致添加或者删除节点的时候,导致【大量】数据发生迁移,但是不是【全部】,例如hash值为12,无论是三台添加到四台,还是四台减少到三台,取余都是0,都会落到第0号节点上。当然,这种情况比例比较少,无伤大雅,(* ̄︶ ̄)。
      2年前
    • 朱双印
    • heaphel0
      取模算法是不是可以将取模的基数固定,即使缓存服务器挂了一台,仍然按照3来取模,那么缓存是不是就只有部分失效了
      2年前
    • 朱双印
    • 汐城0
      看了这么多,唯独你的讲得最好,可以转载吗?
      2年前
    • 朱双印
    • 郭郭小哥0
      给个赞,讲个很明白,学习了。
      2年前
    • 朱双印
    • 祥云小镇0
      666赞
      2年前
    • 朱双印
    • 卡密密0
      "复制虚拟节点"这一步骤是通过什么算法来做么?还是单纯的重新算一个哈希出来,落点碰运气?
      2年前
    • 朱双印
    • 陈大富0
      😀 😀 😀 😀 😀 😀 大佬,网站挂了!!!!!
      2年前
      • 挂了和访问被拒绝是两回事啊兄弟,网站会自动封锁一些IP地址,常来捧场,哈哈~
        2年前@陈大富
    • 朱双印
    • 高大先生0
      太棒了
      2年前
    • 朱双印
    • 0
      您写的真的很好,可以转载吗?
      2年前
    • 朱双印
    • 伟阿几0
      有一个问题请教一下,一致性算法中,如果某台缓存机器故障的时候,数据会缓存到下一个节点,那如果这台机器恢复了,取数据的时候回从这台恢复了的机器取,可是这时候这条机器里面没有我想要的数据,这种情况怎么处理的 ??
      2年前
      • 朱双印
        forethought0
        缓存是会失效的,恢复的节点没有数据,就需要去数据库查数据,然后放入到恢复的节点,返回给前端
        2年前@伟阿几
        • 朱双印
          dingdingdongdong0
          恢复的节点还有存的那个key的值,但是在之前,本该存在B的信息在C服务器上进行了更新,B回来了就在B上查询,返回的不是脏数据吗
          1年前@forethought
    • 朱双印
    • MurasakiSeiFu0
      通俗易懂!感谢分享~
      2年前
    • 朱双印
    • 逍遥叹0
      通俗易懂,不错
      2年前
    • 朱双印
    • KongJHong1
      博主问一下,你的图是用什么软件画的?
      2年前
    • 朱双印
    • hhascm0
      楼主写的真好,通俗易懂
      2年前
    • 朱双印
    • JAVA开发0
      老哥牛逼~全网属你讲的最清楚
      2年前
    • 朱双印
    • 二狗子0
      关于虚拟节点的创建和后期机器填充虚拟节点回收或者偏移什么的其实想了解的更多。
      2年前
    • 朱双印
    • 啊啊啊0
      虚拟节点的创建方式有没有好一点的方式呀
      2年前
    • 朱双印
    • chiangwei0
      讲的太好了,看完懂了
      2年前
    • 朱双印
    • 飞奔的蜗牛0
      厉害了,果然通俗易懂,顶顶顶
      2年前
    • 朱双印
    • drf0
      厉害!通俗易懂
      2年前
    • 朱双印
    • Eureka1
      哇,解释的太厉害了,我觉得没有哪个人看完这篇文章还能不懂一致性哈希的基本原理了。
      2年前
    • 朱双印
    • Yukio0
      很厉害,真的是彻彻底底的看懂了,之前对于虚拟节点有点儿懵,不太清楚为什么会有虚拟节点,这一篇看懂了,感谢!
      2年前
    • 朱双印
    • yhz0
      说的非常棒
      3年前
    • 朱双印
    • 偶尔大白0
      完美
      3年前
    • 朱双印
    • zlx0
      厉害,找了很多文章,这篇终于看懂了👍
      3年前
    • 朱双印
    • 老张0
      感谢感谢。 下面是错别字。 时长可能是不能被接收的
      3年前
      • 感谢指正,这里的错误和你之前提出的错误已经改正,有空常来,共勉,加油~~~
        3年前@老张
    • 朱双印
    • ms-53150
      大佬 想转载一下到我的博客可否
      3年前
    • 朱双印
    • shaiya0
      厉害,写的很容易理解
      3年前
    • 朱双印
    • 胡骞0
      读懂了,写得很棒
      3年前
    • 朱双印
    • Vaney0
      很棒,浅显易懂
      3年前
    • 朱双印
    • jaki0
      非常感谢楼主! 佩服技术人在钻研技术的同时 还能用简练通俗的文笔将知识点讲得深入浅出
      3年前
    • 朱双印
    • 火力全开啦0
      要是多一些你这么优秀的作者
      3年前
    • 朱双印
    • 啦啦啦啦0
      这么说来,一致性hash算法只能消除部分缓存失效,当动态添加或删除节点的时候依旧会出现缓存失效的问题
      3年前
    • 朱双印
    • aries0
      最后虚拟节点产生一个疑惑 如果真是节点宕机 那么虚拟节点是否会一同宕机
      3年前
    • 朱双印
    • 把酒言欢0
      写得很棒,比冷冰冰的科普文字来得更易理解,通俗易懂!这篇文章是我看到类似文献最完美呈现的一篇~
      3年前
    • 朱双印
    • zhangliang0
      太厉害啊 最容易理解的文章了
      3年前
    • 朱双印
    • calm-coder0
      解释的很清楚,很赞
      3年前
    • 朱双印
    • 张帅0
      这是我搜索到最简单易懂的资料啦~真的很棒!!!
      3年前
    • 朱双印
    • 易水寒0
      目前为止,写的最通俗易懂的关于介绍一致性哈希的文章了。终于弄明白了困扰我的一些知识盲点。另,请问可否转载到我的博客?还有请问楼主所用什么主题?
      3年前
    • 朱双印
    • 家挖到0
      大佬,有个问题啊?比如abcd四台服务器,数据1按计算是落在c服务器的但是这个时候c挂了,就会落在d上面,去取数据1的时候c又复活,这个时候数据1的hash落在了c上面,但是c没有数据,这个时候要怎么处理呢?
      3年前
    • 朱双印
    • 采菊的老杨0
      感谢大佬,你的文章真不错!有一点不明白:hash环上如何定义虚拟节点的位置?虚拟后的节点总数,是不是ABC每类相等?
      3年前
    • 朱双印
    • 小杰0
      博主,提个小建议哈,可以考虑把顶部Menu固定去掉,其实很不方便阅读。
      3年前
      • 朱双印
        小杰0
        个人习惯,哈哈。
        3年前@小杰
    • 朱双印
    • 菜鸟明0
      大佬的画图软件用的啥呀?
      3年前
    • 朱双印
    • LaoC0
      很强,谢谢作者,受益良多
      3年前
    • 朱双印
    • 陈帅同学0
      1.作为程序人员,能把脑袋中的智慧讲的如此通俗易懂,说明作者逻辑清楚,和很强的作文能力 2.非常喜欢博主的文章,可否转载,会表明出处
      3年前
    • 朱双印
    • morou0
      老铁,干得漂亮
      3年前
    • 朱双印
    • 淘气的王淘气0
      通俗易懂,感谢分享 学习了,想转发一下 可否
      3年前
    • 朱双印
    • hello0
      太棒了
      3年前
    • 朱双印
    • dsss0
      与其这样哈希ip地址算出环的位置,还不如直接把理想的环地址映射到每个节点机器。而且是人为的直接映射。这样更直接,数据就会均匀的哈希落地到各个节点机器。
      3年前
      • 朱双印
        duiozq0
        不就是虚拟节点的思路吗?上面已经描述了呀
        3年前@dsss
      • 朱双印
        June0
        这样的话,由于之前是理想分布的,当增加一个节点时,就会变得“不理想”。想要恢复到理想状态,得移动,这一移动,就意味着数据需要迁移,在迁移完成前,会导致缓存命中率低很多,说不定因此压垮持久层。。
        3年前@dsss
    • 朱双印
    • 小白0
      大神 收膝盖 蟹蟹了
      3年前
    • 朱双印
    • 小马0
      想问下博客中的图都是通过什么软件绘制的啊?
      3年前
    • 朱双印
    • danny0
      如果服务器运行中,A,B,C分别存储了数据。B服去掉。B服的数据也就丢失。从B服也就查询不到数据。是不是需要把B服的数据顺时针手动迁移到C,这样就能查到,博主有什么好的方法吗?
      3年前
    • 朱双印
    • MikeoPerfetc0
      真的非常白话,请问可以转载留念 :mrgreen:
      3年前
    • 朱双印
    • cacheGao0
      请问,hash环被数据节点及服务器节点布满,虽然具有0~2^23-1,但是应该存在布满情况,那这种情况我们又该怎么处理呢?
      3年前
      • 朱双印
        小杰0
        8百多万,还不够你玩的。
        3年前@cacheGao
    • 朱双印
    • 落叶归根0
      写的太棒了,能不能转载一下啊,保留原创的的链接??
      3年前
    • 朱双印
    • lomoye0
      写的很棒,瞬间理解
      3年前
    • 朱双印
    • alexi0
      大佬写的真好,求转载!!!
      3年前
    • 朱双印
    • 风里有梦0
      博主,您好!当ABC三台物理服务器不均匀时,你又如何知道他们会不均匀?是在生成hash环时,对每一个生成的值进行range判断吗?当发现不均匀时,再生成相应的虚拟服务器插入到相应位置去?
      3年前
      • 朱双印
        sugarao0
        可以设计负载因子啊,比如我们刚开始把一个圆二等分,当一个节点负载过大,再把圆四等分,以此下去 负载银子可以用最大节点的ip个数/总的ip,其他计算负载因子的算法也可以
        3年前@风里有梦
    • 朱双印
    • 奕清0
      你好,博主,本文很实际的解决的我的问题,醍醐灌顶,茅塞顿开,很佩服您的独特见解。能否转载一下,保留出处与您的署名,谢谢!
      3年前
    • 朱双印
    • 土著0
      很佩服大佬,以前看运维的时候就一直关注,希望你能继续分享知识! 同时,我想转载,不知可否?
      3年前
    • 朱双印
    • John0
      您好,博主您这篇文章讲得不错,我可以转载到我的博客上么,我会保留原文链接及水印。
      3年前
    • 朱双印
    • 亚瑟0
      讲的太好了,我能否转载一下呀
      3年前
    • 朱双印
    • 王天硕0
      非常棒 清晰明了 大佬求转载
      3年前
    • 朱双印
    • 震灵0
      醍醐灌顶
      3年前
    • 朱双印
    • tt0
      看了那么多,就看你的看懂了。
      3年前
    • 朱双印
    • hellow0
      谢谢博主分享,看了这个一下子就看懂了
      3年前
    • 朱双印
    • 迈神来了0
      很好很强大
      3年前
    • 朱双印
    • vfhky0
      写得很好,用心了!
      3年前
    • 朱双印
    • 隔壁的老王0
      看了三篇文章,您的文章才让我明白。感谢
      3年前
    • 朱双印
    • 月巴狗狗0
      😉 图文并茂 生动形象 受益匪浅 感谢博主 哈哈哈哈
      3年前
    • 朱双印
    • 三石磊0
      写的不错,本人也作了总结,欢迎交流。
      4年前
    • 朱双印
    • lofy0
      厉害,我这个算法白痴都看懂了。
      4年前
    • 朱双印
    • ztq0
      图片a是沿着hash环顺时针查找所在服务器A,如果新增一台服务器B后其hash值映射到图片a顺时针到服务器A范围之内呢?这个时候a的服务器就是B了。
      4年前
      • 朱双印
        Chris0
        和删除一台服务器时一样,都只影响了一小部分对象的存储位置,大多数的对象还是不受影响的
        4年前@ztq
    • 朱双印
    • ztq0
      你好,我有这样一个问题,图片a 查找所在服务器是沿着hash环顺时针查找。存储的时候图片a 沿着hash环顺时针查找到服务器A。当增加一台服务器F时,其hash值刚好映射到图片a和服务器A中间了呢,这样图片a查找到的就是服务器F了。
      4年前
      • 朱双印
        zzzzte0
        同问
        3年前@ztq
    • 朱双印
    • 骑猪逛0
      写的确实通俗易懂,除了在缓存方面的应用,能不能请博主扩展一下其他方面,比如算法实现,算法原理?,有没有其他的例子,读完有种意犹未尽的感觉 为你点赞
      4年前
    • 朱双印
    • 许弋0
      写的非常好,文中有几处hash环写成了hash换,虽然不影响阅读,可以转载?我会注明地址的
      4年前
    • 朱双印
    • jiangjinmvp0
      博主讲的浅显易懂,如果加上一个demo 就完美了。博主辛苦!
      4年前
    • 朱双印
    • snape0
      看了你的场景描述,我终于明白了,谢谢博主。
      4年前
      • 能对客官有所帮助我很开心,谢谢肯定~
        4年前@snape
    • 朱双印
    • zhou0
      请教个问题:如果B服务器消失了,怎么将B中的数据重新放到C中,是怎么操作的?
      4年前
      • B出故障了,就无法从B上获取对应缓存了,客户端只能去后端服务器上获取对应资源,这时对应资源会再被映射,根据一致性哈希算法缓存到顺时针最近的缓存服务器。
        4年前@zhou
        • 朱双印
          zhou0
          后端服务器是什么意思,例如mysql那类吗?那这时候是客户端查询的时候加载数据,做出映射缓存,还是说先全部加载作映射呢?
          4年前@朱双印
    • 朱双印
    • wuling0
      有图有真相,清晰明了;受教了
      4年前
    • 朱双印
    • sean0
      确实讲的很好!小白受教了!
      4年前
    • 朱双印
    • senninha0
      超级棒,真-白话
      4年前
    • 朱双印
    • 原野0
      看过一致性hash算法文章里讲的最透彻的一次。
      4年前
    • 朱双印
    • 明明如月0
      写的很好,希望以后多分享!!
      4年前
    • 朱双印
    • Rico0
      写的真不错:内容好,文笔棒,赞!
      4年前
      • 瞎说什么大实话 😀 不过我喜欢~~
        4年前@Rico
        • 朱双印
          Rico0
          又回来看了一遍,哈哈,真不错,请问博主方便转载嘛?谢谢~
          4年前@朱双印
          • 朱双印
            Rico0
            博主,这是我转载后的链接:http://blog.csdn.net/justloveyou_/article/details/78313649
            4年前@Rico
            • 朱双印
              小张0
              写得很好呢,博主想转载
              3年前@Rico
    • 朱双印
    • 孙小五0
      楼主写得好啊 这才是写的让人看得懂的方式!!
      4年前
    • 朱双印
    • 加速奔跑的蜗牛0
      楼主写的很幽默,也很好懂哦!我在我的博文中推荐了你的文章,好东西嘛要大力推广
      4年前
    • 朱双印
    • 唐家三叔0
      学到了,谢谢博主
      4年前
    • 朱双印
    • 妞妞0
      是这张图片吸引我进来的。。 😀 😀 https://www.zsythink.net/wp-content/uploads/2017/02/020717_1707_11.png
      4年前
      • 人类的天性,释放你自己吧~~骚年~~~ :mrgreen: ~~加油~~
        4年前@妞妞
        • 朱双印
          陨丶c0
          然而现实这张图我觉得也可以啊。
          2年前@朱双印
    • 朱双印
    • 炫迈来一粒0
      写的很好,只是后面的是如何虚拟和虚拟规则,没看懂
      4年前
    • 朱双印
    • 每天都在写0
      说句实话,讲的真的很易懂,适合入门,赞一个!
      4年前
    • 朱双印
    • 没烟0
      通俗易懂 赞
      4年前
    • 朱双印
    • 小D0
      不错的文章!!!!非常感谢博主 用心写的文章!!
      4年前
    • 朱双印
    • coolboy0
      通俗易懂才是好文章, 赞
      4年前
    • 朱双印
    • 马龙0
      这才是真正的好文章啊,可惜能找到的人还太少了。通俗易懂,有理有据。要是能再写上实现一致性Hash的数据结构,加上实现的关键逻辑,就更加完美了。给博主32个赞。
      4年前
    • 朱双印
    • cdmonkey0
      这篇文章写得太好了,受益匪浅!!!
      4年前
    • 朱双印
    • yong0
      文章写的真棒,很好理解;在网上搜了几篇文章,都是晦涩难懂(我只想说:啥啥啥,你说的都是啥)。
      4年前
    • 朱双印
    • wisteria0
      通俗易懂
      4年前
    • 朱双印
    • 水煮鱼0
      写的很不错,看分库分表的时候了解到了一致性hash的概念,找了几个看看。你写这个很清晰易懂。感谢
      4年前
    • 朱双印
    • 华子0
      非常感谢,看明白了,
      4年前
    • 朱双印
    • 宇辰0
      这就是一个小白想找的文章,大赞,大赞啊!!!!!但是,图片名称是怎么通过hash(test.jpg)就转换成数字的?还有怎么增加的节点没搞明白!!
      4年前
    • 朱双印
    • 兴浩0
      写的非常形象,我一般都不留言的-_-
      4年前
    • 朱双印
    • 17岁少年为情所困丶0
      楼主写的清晰易懂,而且图给的太好了,一看就明白了,谢谢楼主。
      4年前
    • 朱双印
    • 城阙0
      好文章,总结的真是好!
      4年前
    • 朱双印
    • july0
      讲的好好!一篇篇都在慢慢的看,对我们这些刚入门的很友好! 博主再写些基础的,补成个系统了,完全可以去出书啊!
      4年前
      • 谢谢这位客官捧场,出书还是差的很远的,把所有的按照系统整合起来也是非常困难的,因为总结一个知识点可能就牵扯一堆知识点,为了尽量明白,一般会按照逻辑顺序先把需要的知识点总结出来,所以更加耗费时间,不过如果这些文章能够对你有所帮助,才是这些文章存在的根本意义,谢谢你的肯定~~~
        4年前@july
    • 朱双印
    • zongheng_ycj0
      想问一下 虚拟节点的生成的生成策略是什么 比方所3台服务器发生偏斜 复制3个虚拟节点 这三个节点又怎么能保证均衡分布呢
      4年前
      • 不能保证这些节点均衡,所以可以尽量多的复制虚机节点,尽量的均衡,降低偏斜的程度。
        4年前@zongheng_ycj
        • 朱双印
          北溟有鹏0
          写得好好呢,不过还是有几个问题不懂,想请教下。 1.如果新加入几台服务器的跟虚拟节点重合了怎么办? 2.为什么一致性hash算法要取2的32次方为底呢,有什么依据吗?
          4年前@朱双印
          • 1,从别人实现的代码来看,会先进行判断,但是我并没有实现过这些代码,不过你可以在网上搜索,一致性哈希算法的具体实现,参考对应代码。 2,网上的解释是hash后的值是一个无符号整数,所以取值范围为2的32次方,具体实现中可以不以2的32次方为底,只要在概念上是一个环就行。 3,上述理论我并没有验证过,只是思路,仅供参考~
            4年前@北溟有鹏
            • 朱双印
              风筝0
              取2的32次方是有依据的,IPV4最大的数量就是2的32次方,这样就能保证所有的ip地址来取余不会重复。一一对应哈希环上面的正数
              4年前@朱双印
              • 朱双印
                天明0
                即使ipv4最大数量时2的32次方,也没有办法保证hash取余不会重复,出现hash冲突的概率虽然不大,但是取余后冲突的概率还是不小的,(* ̄︶ ̄)
                2年前@风筝
    • 朱双印
    • 寒风0
      研究的是越来越深入了,赞!
      4年前
      • 哈哈,谢谢兄弟捧场,多亏你们支持。
        4年前@寒风
    • 朱双印
    • Aceslup1
      真心很通俗易懂。赞一个
      4年前
    • 朱双印
    • 李杨0
      你好,我想问一下,最后的那一块,图片被分配到被虚拟节点平均之后的位置,你在读取某一张图片的时候,你是根据什么算法去hash,然后去对应到虚拟节点获取图片数据呢?
      4年前
      • 朱双印
        geosmart1
        一致性hash的hash算法,md5,crc32这类hash算法就可以,如md5在python中计算hash值的算法 ```python NODES=3 item='172.12.1.21' k = md5(str(item).encoding('utf-8')).digest() # 字节转int/long h = unpack_from(">I", k)[0] n = h % NODES ```
        3年前@李杨