文档章节

关于一致性hash,这可能是全网最形象生动最容易理解的文档,想做架构师的你来了解一下

 非正式解决方案
发布于 08/24 00:20
字数 1524
阅读 5
收藏 0

问题提出

一致性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`

此时为了保证数据的准确性,我们需要 将数据ObjectXN3迁移到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原理

原理网络上太多,这里不做进一步阐述。

© 著作权归作者所有

粉丝 0
博文 7
码字总数 10436
作品 0
私信 提问
java版Memcached的理解

阿里岑文初的memcached虽然添加了不少功能,但我觉得好像还不是那么完美,有些细节在使用时还是需要注意…… 优点: 1.配置改用文件,代替代码初始化,带来方便 2.增加cluster和keySet等方法...

wuxian_Abs
2014/04/14
165
0
大型网站架构系列:20本技术书籍推荐

学习是技术人员成长的基础,本次分享20本技术方面的书籍,这些书不是每一本都是经典,但是每一本都有其特点。以下20本大部分本人都看过,因此推荐给大家。(本次推荐的20本只是一个参考,比如...

xumaojun
2018/05/03
0
0
查找--深入理解一致性哈希算法

注:本篇博客只是讲述了一致性哈希的思想,我们会在之后讲述分布式哈希表以及一致性哈希的一种实现(Chord算法)。 什么是一致性哈希算法? 引用自维基百科: 一致性哈希是一种特殊的哈希算法...

珩翊
2018/06/26
0
0
分布式设计与开发(二)------几种必须了解的分布式算法

分布式设计与开发中有些疑难问题必须借助一些算法才能解决,比如分布式环境一致性问题,感觉以下分布式算法是必须了解的(随着学习深入有待添加): Paxos算法 一致性Hash算法 Paxos算法 1)...

商者
2016/04/05
35
0
分布式设计与开发(二)------几种必须了解的分布式算法

分布式设计与开发中有些疑难问题必须借助一些算法才能解决,比如分布式环境一致性问题,感觉以下分布式算法是必须了解的(随着学习深入有待添加): Paxos算法 一致性Hash算法 Paxos算法 1)...

山哥
2012/03/19
1K
2

没有更多内容

加载失败,请刷新页面

加载更多

nginx学习笔记

中间件位于客户机/ 服务器的操作系统之上,管理计算机资源和网络通讯。 是连接两个独立应用程序或独立系统的软件。 web请求通过中间件可以直接调用操作系统,也可以经过中间件把请求分发到多...

码农实战
今天
5
0
Spring Security 实战干货:玩转自定义登录

1. 前言 前面的关于 Spring Security 相关的文章只是一个预热。为了接下来更好的实战,如果你错过了请从 Spring Security 实战系列 开始。安全访问的第一步就是认证(Authentication),认证...

码农小胖哥
今天
12
0
JAVA 实现雪花算法生成唯一订单号工具类

import lombok.SneakyThrows;import lombok.extern.slf4j.Slf4j;import java.util.Calendar;/** * Default distributed primary key generator. * * <p> * Use snowflake......

huangkejie
昨天
12
0
PhotoShop 色调:RGB/CMYK 颜色模式

一·、 RGB : 三原色:红绿蓝 1.通道:通道中的红绿蓝通道分别对应的是红绿蓝三种原色(RGB)的显示范围 1.差值模式能模拟三种原色叠加之后的效果 2.添加-颜色曲线:调整图像RGB颜色----R色增强...

东方墨天
昨天
11
1
将博客搬至CSDN

将博客搬至CSDN

算法与编程之美
昨天
13
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部