说说你对一致性Hash算法的理解

Love The Way You Lie 2024-03-17 22:48 50阅读 0赞

#### 说说你对一致性Hash算法的理解 ####

*  定义
 *  核心思想
 *  作用
 *  工作原理
 *  相比普通Hash算法的优势

## 定义 ##

一致性hash算法是一种比较特殊、在原本Hash算法上的一个改良。它会尽可能去减少因我们数据存储节点发生变化时候发生的迁移成本。

## 核心思想 ##

它的核心思想是在解决分布式环境下hash表可能存在的动态扩容和缩容的一个问题。

## 作用 ##

一般情况下我们会使用hash表的方式，以key和value的方式来去做数据的一个存储。

但是当数据量比较大的情况下，我们会把数据存储到多个节点上。

然后通过hash取模的方式来决定把当前的key存储到哪一个节点。

![在这里插入图片描述][e6e7a71f888c4865b329358caa57534f.png]  
那么这种方式有一个非常明显的问题，就是当存储的节点增加或者减少的时候，原本映射关系就会发生变化。

也就是需要对所有的数据按照新的节点的数量来重新映射一遍。那么这就涉及了一个大量数据迁移和重新映射一个问题。它的代价很大。

## 工作原理 ##

一致性hash算法就是用来优化这样一个动态变化的场景的一种算法。

它的具体工作原理非常简单：

首先一致性Hash是通过一个hash环的数据结构来实现的。这个环的起点是0，终点是2的32次方减1，也就是说这个环的数据分布范围是0~2^32-1。

![在这里插入图片描述][3b51d9a42a49495bbf7173e9b149f51a.png]  
然后，我们把数据的**存储节点的ip地址**作为key进行hash之后，会落到hash环上的某一个位置。

![在这里插入图片描述][c17e3b52ead3409ba76d75b7b90df771.png]  
那么接下来就是需要把存储的**目标key**使用hash算法计算以后得到一个hash值，同样会落到hash环的某个位置。

然后这个目标key会按照顺时针的方向去找到离自己最近的一个节点来进行数据的存储。

![在这里插入图片描述][792c44f6a5134292a33cef883e203959.png]

## 相比普通Hash算法的优势 ##

假设我们现在需要新增一个节点node4，那么数据的映射的关系的影响范围只会影响到node3和node1这两个节点。也就是说，只有少部分的数据需要进行映射和迁移。

![在这里插入图片描述][93704ba0587f4aa983f7bfa65cee9d13.png]  
如果是已经存在的一个节点，node1因为故障下线了，那么这个时候，我们只需要把原本分配到node1上的数据重新分配到node2上就好了。同样对于数据影响范围是非常小的。

![在这里插入图片描述][9bb92552cd884168bd2d4607b735ba6f.png]  
一致性hash算法的好处是**扩展性很强**，在增加或者减少服务器的时候，**数据迁移的范围是会比较小**，也就是说影响范围有限。

另外在一致性hash算法里面，为了避免hash倾斜导致数据分配不均匀的一个情况，我们可以使用**虚拟节点的方式**来去解决这样的一个问题。

**参考资料**：[Java面试】太强了！高手将这题竟讲的这么透彻，说说你对一致性Hash算法的理解][Java_Hash]

[e6e7a71f888c4865b329358caa57534f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/9fa8c87ce5534eb59898c4190a3314b8.png
[3b51d9a42a49495bbf7173e9b149f51a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/bf72d809d65f4fb288f3d5310e025488.png
[c17e3b52ead3409ba76d75b7b90df771.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/00cddd32d43b4b399ce89fd47c654ab5.png
[792c44f6a5134292a33cef883e203959.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/121a04200a71454daf114de51c9d6e35.png
[93704ba0587f4aa983f7bfa65cee9d13.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/721eea5ac93c4264994c050100c1279b.png
[9bb92552cd884168bd2d4607b735ba6f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/8cdfbc9c47674990a0fd88a76c32aa3c.png
[Java_Hash]: https://www.bilibili.com/video/BV193411u7Lq/?spm_id_from=333.337.search-card.all.click&vd_source=a1af903e57688df870625021f7f3a7eb