浅谈一致性hash原理

爱被打了一巴掌 2023-02-25 15:25 150阅读 0赞

### 一致性hash的作用 ###

*  一致性hash常用于实现负载均衡，并在增加节点的情况，极大降低数据迁移的代价

--------------------

#### hash函数的重要性质 ####

> 1.输入域无穷大，输出域又穷
> 
> 2.输入一样，输出一定一样
> 
> 3.输入不一样，输出也可能一样
> 
> 4.输出在输出域均匀分布
> 
> 5.输入数据差别很小，输出可能差别巨大
> 
> 引申特性：可以通过输出域（模）%m，可将输出域缩减到0~(m-1)，当然缩减后也是均匀分布

--------------------

#### 以下以通熟易懂的案例浅析一致性hash ####

> 假设有三台后台机器，怎么均分接收到的请求？
> 
> 如果需要增加一台机器，怎么还保证负载均衡，而且原有数据也均分在四台机器当中？

--------------------

#### 一致性hash原理 ####

> 把hash函数输出域当作一个环，利用hash函数计算出三台机器在环上的位置（例如通过机器的ip地址，或者mac地址作为输入）
> 
> ![format_png][]
> 
> 接收到的每个请求，也进行hash计算，输出会在环上的某个位置，顺时针找到离自己最近的机器（因为输出域是有序排列，可以将每个机器的hash值保存为有序数组进行二分查找，并找到该请求属于哪台机器）
> 
> 假如key计算出来在machine0-machine1区间，那么就是machine1处理这个区间的请求，存值和取值道理一样
> 
> --------------------
> 
> 添加机器
> 
> ![format_png 1][]
> 
> #### 这种扩容方式很明显存在问题 ####
> 
> 机器很少的情况下，很难保证它们掌管的域一样大
> 
> #### 解决方案：虚拟节点 ####
> 
> 每台机器维护1000个虚拟节点，通过任意一个虚拟节点值都能找到真实的物理机器
> 
> 对这些虚拟节点进行hash计算，这样3台机器就相当于把整个环分成3000份，每台机器几乎均匀分布
> 
> 增加机器也很容易，同样维护1000个虚拟节点进行计算，并插入环，再进行数据迁移，这样向当于均匀的分担已有三台机器负责的域

[format_png]: /images/20230209/143f0b5d233248d3913c9ccf038d417b.png
[format_png 1]: /images/20230209/b67e728903d4488682d5145266df09cb.png