网站首页 返回列表像“草根”一样，紧贴着地面，低调的存在，冬去春来，枯荣无恙。

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

2020-06-10 02:43:28 admin 694

# 问题提出

一致性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原理

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

## 推荐阅读

[扫微信二维码实现网站登陆提供体验地址和源代码](https://links.jianshu.com/go?to=https%3A%2F%2Fwww.techidea8.com%2Farchives%2F46)

[开源项目golang go语言后台管理框架restgo-
admin](https://links.jianshu.com/go?to=https%3A%2F%2Fwww.techidea8.com%2Farchives%2F34)

[支持手势触摸,可左右滑动的日历插件](https://links.jianshu.com/go?to=https%3A%2F%2Fwww.techidea8.com%2Farchives%2F22)

[你必须知道的18个互联网业务模型](https://links.jianshu.com/go?to=https%3A%2F%2Fwww.techidea8.com%2Farchives%2F31)

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

关键字词hash 架构师

分享到：

上一篇：Golang笔记—反射

下一篇：golang微服务框架go-micro 入门笔记2.1 micro工具之micro api

如需留言，请登录，没有账号？请注册

0 条评论 0 人参与

网站首页 返回列表像“草根”一样，紧贴着地面，低调的存在，冬去春来，枯荣无恙。

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

zhou 3年前

zhou 3年前

zhou 3年前

zhou 3年前

武云 3年前

网站首页 返回列表 像“草根”一样，紧贴着地面，低调的存在，冬去春来，枯荣无恙。

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

zhou 3年前

zhou 3年前

zhou 3年前

zhou 3年前

武云 3年前

网站首页返回列表像“草根”一样，紧贴着地面，低调的存在，冬去春来，枯荣无恙。