哈希详解(一致性哈希:重点)

谁借莪１个温暖的怀抱￠ 2022-09-05 01:43 243阅读 0赞

### 哈希 ###

*  什么是哈希
 *  什么是哈希表
 *  什么是哈希冲突
 *  如何解决哈希冲突
 *  什么是哈希函数(散列函数)
 *  传统哈希存在的问题
 *  一致性哈希算法负载均衡

# 什么是哈希 #

哈希（Hash）也称为散列，就是把任意长度的输入，通过散列算法，变换成固定长度的输出，这个输出值就是散列值。

# 什么是哈希表 #

哈希表,也这叫做散列表,是一种将数组和链表结合在一起的数据结构.

# 什么是哈希冲突 #

一般来说,Key,Value键值对的个数远远大于哈希表的长度的时候,求当前键值对的哈希值时,与之前的键值对的值相等,两个键值对存放在同一个数组下标位置,就是哈希冲突.

# 如何解决哈希冲突 #

(1)拉链法  
凡是计算出来的数组下标都是同一个位置的键值对,将他们都存储在当前数组下标所连接的链表当中.  
(2)开放地址法  
所谓的开放定址法就是一旦发生了冲突，就去寻找下一个空的散列地址，只要散列表足够大，空的散列地址总能找到，并将记录存入

# 什么是哈希函数(散列函数) #

(1) MD5算法(取模)  
公式：hash(key) = key mod M  
(2)CRC算法  
循环冗余校验（Cyclic Redundancy Check）是一种根据网络数据包或电脑文件等数据，产生简短固定位数校验码的一种散列函数

# 传统哈希存在的问题 #

在讲哈希一致性时,我结合具体的业务场景来讲解更容易理解一些.  
在分布式集群缓存的负载均衡实现中,假设有 3 个服务器节点编号 \[0 - 2\]，6 个缓存键值对编号 \[1 - 6\]，则完成哈希映射之后，三个缓存数据映射情况如下：

哈希计算公式：key % 节点总数 = Hash节点下标
    1 % 3 = 1
    2 % 3 = 2
    3 % 3 = 0
    4 % 3 = 1
    5 % 3 = 2
    6 % 3 = 0

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzU4NjcxMw_size_16_color_FFFFFF_t_70]  
这种传统的哈希如果遇到一些情况时,效果往往不理想:  
1 扩展能力差  
例如到了重大节日,双十一,要增加几台服务器节点的时候,新加进来的机器会使原来计算的哈希值不准确,为了达到负载均衡的效果，要重新计算并更新哈希值，对于更新后哈希值不一致的缓存数据，要迁移到更新后的节点上去。  
假设新增了 1 个服务器节点，由原来的 3 个服务节点变成 4 个节点编号 \[0 - 3\]，哈希映射情况如下：

哈希计算公式：key % 节点总数 = Hash节点下标

1 % 4 = 1
    2 % 4 = 2
    3 % 4 = 3
    4 % 4 = 0
    5 % 4 = 1
    6 % 4 = 2

可以看到后面三个缓存 key ：4、5、6 对应的存储节点全部失效了，这就需要把这几个节点的缓存数据迁移到更新后的节点上 (费时费力) ，也就是由原来的节点 \[1, 2, 0\] 迁移到节点 \[0, 1, 2\]，迁移后存储示意图如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzU4NjcxMw_size_16_color_FFFFFF_t_70 1]  
2. 容错能力不佳  
3. 线上环境服务节点虽然有各种高可用性保证，但还是是有宕机的可能，即使没有宕机也有缩容的需求。不管是宕机和缩容都可以归结为服务节点删除的情况，下面分析下服务节点删除对负载均衡哈希值的影响。

假设删除 1 个服务器节点，由最初的 3 个服务节点变成 2 个，节点编号 \[0 - 1\]，哈希映射情况如下  
哈希计算公式：key % 节点总数 = Hash节点下标

1 % 2 = 1
    2 % 2 = 0
    3 % 2 = 1
    4 % 2 = 0
    5 % 2 = 1
    6 % 2 = 0

下图展示普通哈希负载均衡算法在一个节点宕机时候，导致的的缓存数据迁移分布情况：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzU4NjcxMw_size_16_color_FFFFFF_t_70 2]  
如图所见，在这个例子中，仅仅删除了一个服务节点，也导致了哈希值的大面积更新，哈希值的更新也是意味着节点缓存数据的迁移（缓存数据表示心好累）。

# 一致性哈希算法负载均衡 #

就是普通取模哈希算法的改良版，哈希函数计算方法不变，只不过是通过构建环状的 Hash 空间代替普通的线性 Hash 空间。具体做法如下：  
首先，选择一个足够大的Hash空间（一般是 0 ~ 2^32）构成一个哈希环。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzU4NjcxMw_size_16_color_FFFFFF_t_70 3]  
然后，对于缓存集群内的每个存储服务器节点计算 Hash 值，可以用服务器的 IP 或 主机名计算得到哈希值，计算得到的哈希值就是服务节点在 Hash 环上的位置。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzU4NjcxMw_size_16_color_FFFFFF_t_70 4]  
最后，对每个需要存储的数据 key 同样也计算一次哈希值，计算之后的哈希也映射到环上，数据存储的位置是沿顺时针的方向找到的环上的第一个节点。下图举例展示了节点存储的数据情况，我们下面的说明也是基于目前的存储情况来展开。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzU4NjcxMw_size_16_color_FFFFFF_t_70 5]  
如下图所示，当缓存服务集群要新增一个节点node3时，受影响的只有 key3 对应的数据 value3，此时只需把 value3 由原来的节点 node0 迁移到新增节点 node3 即可，其余节点存储的数据保持不动。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzU4NjcxMw_size_16_color_FFFFFF_t_70 6]  
普通哈希算法当某一服务节点宕机下线，也会导致原来哈希映射的大面积失效，失效的映射触发数据迁移影响缓存服务性能，容错能力不足。一起来看下一致性哈希是如何提升容错能力的。

如下图所示，假设 node2 节点宕机下线，则原来存储于 node2 的数据 value2 和 value5 ，只需按顺时针方向选择新的存储节点 node0 存放即可，不会对其他节点数据产生影响。一致性哈希能把节点宕机造成的影响控制在顺时针相邻节点之间，避免对整个集群造成影响。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzU4NjcxMw_size_16_color_FFFFFF_t_70 7]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzU4NjcxMw_size_16_color_FFFFFF_t_70]: /images/20220829/f05ccc7df41046d4b8bfbb3674ece4be.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzU4NjcxMw_size_16_color_FFFFFF_t_70 1]: /images/20220829/93c6b93fc0814b7b93c1dd62ec952da8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzU4NjcxMw_size_16_color_FFFFFF_t_70 2]: /images/20220829/b30dad0d42eb4902afe203c6f3bd6e86.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzU4NjcxMw_size_16_color_FFFFFF_t_70 3]: /images/20220829/5e5c89bb695e47fa9d3d23f07c60ed8b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzU4NjcxMw_size_16_color_FFFFFF_t_70 4]: /images/20220829/9565a3eece184561a1977323f6817431.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzU4NjcxMw_size_16_color_FFFFFF_t_70 5]: /images/20220829/e689062114cf44a48475b411f0662481.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzU4NjcxMw_size_16_color_FFFFFF_t_70 6]: /images/20220829/a0a17ea7e9ae4f4ebe4e25884b6d795d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzU4NjcxMw_size_16_color_FFFFFF_t_70 7]: /images/20220829/f37cfb7896d14ce9b41b57ec7e38cb18.png