关于一致性hash,这可能是全网最形象生动最容易理解的文档,想做架构师的你来了解一下
source link: https://www.tuicool.com/articles/IbaQF36
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
问题提出
一致性hash是什么?假设有4台缓存服务器 N0,N1,N2,N3
,现在需要存储数据 OBJECT1,OBJECT2,OBJECT3,OBJECT4,OBJECT5,OBJECT5,OBJECT7,OBJECT8
,
我们需要将这些数据缓存到这4台服务器上,相应的问题是
如何设计数据存放策略?即ObjectX 应该存放在哪台服务器上?
为了解决这个问题,我们有如下几个思路。
1. 余数hash方案
采用hash(Objectx)%4来确定服务器节点
假设 hash(OBJECT1)=2
,由 2%4=2,可知, Object1
则应该存放到节点 N2
上
假设 hash(OBJECT2)=3
,由 3%4=3,可知, Object2
则应该存放到节点 N3
上
假设 hash(OBJECT3)=1
,由 1%4=1,可知, Object3
则应该存放到节点 N1
上
假设 hash(OBJECT4)=0
,由 1%4=1,可知, Object4
则应该存放到节点 N0
上
假设 hash(OBJECT5)=5
,由 5%4=1,可知, Object5
则应该存放到节点 N1
上
假设 hash(OBJECT6)=6
,由 6%4=2,可知, Object6
则应该存放到节点 N2
上
假设 hash(OBJECT7)=7
,由 7%4=3,可知, Object7
则应该存放到节点 N3
上
假设 hash(OBJECT8)=8
,由 8%4=0,可知, Object8
则应该存放到节点 N0
上
假设我们需要读取 Object3
的数据,则由 hash(object3)=1
可知,我们只需要访问节点 N1
即可。
1.1 现在假设 N3
忽然故障下线
我们面临缓存重新构造的问题
采用hash(Objectx)%3来确定服务器节点
假设 hash(OBJECT1)=2
,由 2%3=2,可知, Object1
则应该存放到节点 N2
上
假设 hash(OBJECT2)=3
,由 3%3=0,可知, Object2
则应该存放到节点 N0
上
假设 hash(OBJECT3)=1
,由 1%3=1,可知, Object3
则应该存放到节点 N1
上
假设 hash(OBJECT4)=0
,由 0%3=0,可知, Object4
则应该存放到节点 N0
上
假设 hash(OBJECT5)=5
,由 5%3=2,可知, Object5
则应该存放到节点 N2
上
假设 hash(OBJECT6)=6
,由 6%3=0,可知, Object6
则应该存放到节点 N0
上
假设 hash(OBJECT7)=7
,由 7%3=1,可知, Object7
则应该存放到节点 N1
上
假设 hash(OBJECT8)=8
,由 8%3=2,可知, Object8
则应该存放到节点 N2
上
此时为了保证数据的准确性,我们需要
将数据Object2
从 N3
迁移到 N0
将数据
Object5
从 N1
迁移到 N2
将数据
Object6
从 N2
迁移到 N0
将数据
Object7
从 N3
迁移到 N1
将数据 Object8
从 N0
迁移到 N2
1.2 现在假设我们添加一台新的服务器 N4
我们面临缓存重新构造的问题
采用hash(Objectx)%5来确定服务器节点
假设 hash(OBJECT1)=2
,由 2%5=2,可知, Object1
则应该存放到节点 N2
上
假设 hash(OBJECT2)=3
,由 3%5=3,可知, Object2
则应该存放到节点 N3
上
假设 hash(OBJECT3)=1
,由 1%5=1,可知, Object3
则应该存放到节点 N1
上
假设 hash(OBJECT4)=0
,由 0%5=0,可知, Object4
则应该存放到节点 N0
上
假设 hash(OBJECT5)=5
,由 5%5=0,可知, Object5
则应该存放到节点 N0
上
假设 hash(OBJECT6)=6
,由 6%5=1,可知, Object6
则应该存放到节点 N1
上
假设 hash(OBJECT7)=7
,由 7%5=2,可知, Object7
则应该存放到节点 N2
上
假设 hash(OBJECT8)=8
,由 8%5=3,可知, Object8
则应该存放到节点 N3
上
此时为了保证数据的准确性,我们需要
将数据 Object2
从 N3
迁移到 N0
将数据 Object5
从 N1
迁移到 N0
将数据 Object6
从 N2
迁移到 N1
将数据 Object7
从 N3
迁移到 N2
将数据 Object8
从 N0
迁移到 N3
从上述俩种情况可以看出,一旦机器数目变化,我们面临大量的缓存变化问题,换言之,缓存大部分失效,很可能会导致雪崩。
2.一致性hash方案
现在我们更换如下策略
0<hash(Objectx)%8<=2 ,则存放在 N0
2<hash(Objectx)%8<=4 ,则存放在 N1
4<hash(Objectx)%8<=6 ,则存放在 N2
6<hash(Objectx)%8<=8 ,则存放在 N3
2.1 现在假设 N3
忽然故障下线
我们面临缓存重新构造的问题,调整策略如下
0<hash(Objectx)%8<=2 ,则存放在 N0
2<hash(Objectx)%8<=4 ,则存放在 N1
4<hash(Objectx)%8<=6 ,则存放在 N2
6<hash(Objectx)%8<=8 ,则存放在 N0
此时为了保证数据的准确性,我们需要
将数据 ObjectX
从 N3
迁移到 N0
,受影响的数据仅仅N3相关的数据。
2.2 现在假设我们添加一台新的服务器 N4
我们面临缓存重新构造的问题,调整策略如下
0<hash(Objectx)%8<=2 ,则存放在 N0
2<hash(Objectx)%8<=4 ,则存放在 N1
4<hash(Objectx)%8<=5 ,则存放在 N2
5<hash(Objectx)%8<=6 ,则存放在 N4
6<hash(Objectx)%8<=8 ,则存放在 N3
此时为了保证数据的准确性,我们需要
将数据从 N2
复制到 N4
,受影响的仅仅N2相关的用户。
比较上述俩种做法,可见方案2更优. 方案2就是一致性hash
2.3 缺点
机器越少,则每台机器上负载将越不均匀,解决这个问题的方法是添加虚拟节点,调整策略,如下,可以想象,数据越多,分布越均匀。
0<hash(Objectx)%8<=1 ,则存放在 N0
1<hash(Objectx)%8<=2 ,则存放在 N1
2<hash(Objectx)%8<=3 ,则存放在 N2
3<hash(Objectx)%8<=4 ,则存放在 N3
4<hash(Objectx)%8<=5 ,则存放在 N0
5<hash(Objectx)%8<=6 ,则存放在 N1
6<hash(Objectx)%8<=7 ,则存放在 N2
7<hash(Objectx)%8<=8 ,则存放在 N3
3. 一致性Hash原理
原理网络上太多,这里不做进一步阐述。
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK