简单哈希算法和一致性哈希算法和哈希槽对比

落日映苍穹つ 2024-03-27 14:00 177阅读 0赞

#### 目录 ####

*   *  简单哈希算法
     *  一致性哈希算法
     *  哈希槽

### 简单哈希算法 ###

> 假设有三台机，数据落在哪台机的算法为：  
> c = Hash(key) % 3

> 例如 key A 的哈希值为4，4 % 3 = 1，则落在第二台机。Key ABC 哈希值为11，11 % 3 = 2，则落在第三台机上。  
> 利用这样的算法，假设现在数据量太大了，需要增加一台机器。A 原本落在第二台上，现在根据算法4 % 4 = 0，落到了第一台机器上了，但是第一台机器上根本没有 A 的值。这样的算法会导致增加机器或减少机器的时候，引起大量的缓存穿透，造成雪崩。

### 一致性哈希算法 ###

在1997年，麻省理工学院的 Karger 等人提出了一致性哈希算法，为的就是解决分布式缓存的问题。  
在一致性哈希算法中，整个哈希空间是一个虚拟圆环。  
![在这里插入图片描述][2fa54b3d7d774b5aabfd6e7fe265758b.png]  
假设有四个节点 Node A、B、C、D，经过 ip 地址的哈希计算，它们的位置如下：  
![在这里插入图片描述][bf3cac8dfdf24b2b9d1845b66a68fd12.png]  
有4个存储对象 Object A、B、C、D，经过对 Key 的哈希计算后，它们的位置如下：

![在这里插入图片描述][7fd611db254942f2ac2bcf7d94490c69.png]

*  对于各个 Object，它所真正的存储位置是按顺时针找到的第一个存储节点。例如 Object A 顺时针找到的第一个节点是 Node A，所以 Node A 负责存储 Object A，Object B 存储在 Node B。
 *  一致性哈希算法大概如此，那么它的容错性和扩展性如何呢？
 *  假设 Node C 节点挂掉了，Object C 的存储丢失，那么它顺时针找到的最新节点是 Node D。也就是说 Node C 挂掉了，受影响仅仅包括 Node B 到 Node C 区间的数据，并且这些数据会转移到 Node D 进行存储。

![在这里插入图片描述][0865cb8a9eb84419a7ce19701d9777a9.png]

*  同理，假设现在数据量大了，需要增加一台节点 Node X。Node X 的位置在 Node B 到 Node C 直接，那么受到影响的仅仅是 Node B 到 Node X 间的数据，它们要重新落到 Node X 上。
 *  所以一致性哈希算法对于容错性和扩展性有非常好的支持。但一致性哈希算法也有一个严重的问题，就是数据倾斜。
 *  如果在分片的集群中，节点太少，并且分布不均，一致性哈希算法就会出现部分节点数据太多，部分节点数据太少。也就是说无法控制节点存储数据的分配。如下图，大部分数据都在 A 上了，B 的数据比较少。

![在这里插入图片描述][5ab13d4faef7438ca7a3b6f067d1ce01.png]

### 哈希槽 ###

一个 Redis Cluster包含16384（0~16383）个哈希槽，存储在Redis Cluster中的所有键都会被映射到这些slot中，集群中的每个键都属于这16384个哈希槽中的一个。按照槽来进行分片，通过为每个节点指派不同数量的槽，可以控制不同节点负责的数据量和请求数.

**当前集群有3个节点,槽默认是平均分的**:

*  节点 A （6381）包含 0 到 5499号哈希槽.
 *  节点 B （6382）包含5500 到 10999 号哈希槽.
 *  节点 C （6383）包含11000 到 16383号哈希槽.

**哈希槽计算公式**  
集群使用公式slot=CRC16（key）/16384来计算key属于哪个槽，其中CRC16(key)语句用于计算key的CRC16 校验和。

**哈希槽的优点**  
这种结构很容易添加或者删除节点.  
比如如果我想新添加个节点D，我需要从节点 A, B, C中得部分槽到D上.  
如果我想移除节点A，需要将A中的槽移到B和C节点上，然后将没有任何槽的A节点从集群中移除即可.

[2fa54b3d7d774b5aabfd6e7fe265758b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/e3120930ae6b478485db41dfc88fed26.png
[bf3cac8dfdf24b2b9d1845b66a68fd12.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/2dcbff44c961434ebffb3ce0b152f37a.png
[7fd611db254942f2ac2bcf7d94490c69.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/dde81e4ed91146d78f50cc358f900b91.png
[0865cb8a9eb84419a7ce19701d9777a9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/cff01ad12651449d9e64bc4e0abe800e.png
[5ab13d4faef7438ca7a3b6f067d1ce01.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/ebee0a6c088b417ca1bb993bcd41af07.png