一致性哈希学习

亦凉 2022-05-19 23:23 118阅读 0赞

## 1.简介 ##

### 1.1 一致性哈希定义 ###

维基百科给出的定义： 「 在使用一致性哈希算法后，哈希槽位数（大小）的改变平均只需要对 K/n 个关键字重新映射，其中 K 是关键字的数量，n 是槽位数。」

> 在传统的哈希表中，添加或删除一个槽位需要对所有关键字进行重新映射。

### 1.2 评价哈希的标准 ###

一致性 hash 算法提出了在动态变化的 cache 环境中，判定哈希算法好坏的四个定义：

*  **平衡性（Balance）**： hash 的结果能够尽可能分布到所有的缓冲中，充分使用所有的缓冲空间（很多哈希算法都能满足这一条件）。
 *  **单调性（Monotonicity)**： hash 的结果应能够保证原有已分配的内容可以被映射到原有的缓冲区中，而不会被映射到缓冲集合中的其他缓冲区。
 *  **分散性（Spread）**： 在分布式环境中，终端可能只会看到缓冲区其中的一部分。所以由于终端所见的缓冲范围有可能不同，从而导致哈希结果不一致，最终导致**相同内容被存储到不同缓冲中去** ，降低了系统的存储的效率。分散性的定义就是上述情况发生的严重程度。好的哈希算法应能够尽量避免不一致的情况发生，也就是尽量降低分散性。
 *  **负载（Load）**： 负载实际是从另一个角度看待分散性问题。既然不同终端可能将相同的内容映射到不同的缓冲区中，那么对于一个特定的缓冲区而言，也可能被不同的用户映射为不同的内容。**好的哈希算法应能够尽量降低缓冲的负荷**。

## 2.内容 ##

假设一个简单的场景：有四个 node （ 服务器）组成的集群，当一个对象 object 传入集群使，这个对象应该存储在哪个 node 呢？

*  一致性 hash 的出现是为了解决：**当节点数量改变时，能够使失效的缓存数量尽可能少。**
 *  一致性 hash 的基本思想分为以下两步：  
    
    
     *  把 node 求 hash
     *  把 object 求 hash，然后通过一定规则 (**顺时针 or 逆时针**）决定每个 object 落在哪个node中

### 成环 ###

一致性哈希将整个哈希值空间组织成一个虚拟的圆环，假设某个哈希函数 H 的值的空间为0 - 2^32-1，整个哈希空间如下图（整个空间按照顺时针方向组织，0和2^32-1在零点方式重合)：  
![这里写图片描述][70])

### 将 node 映射到哈希环 ###

对 node 集群所有节点，使用哈希函数计算其在 hash 环中的位置。可以选择服务器的 ip 活主机名作为关键字进行哈希，以确定其在哈希环上的位置，假设对 node 服务器使用 ip 地址哈希后在环空间的位置如下图所示：

![这里写图片描述][70 1]

### 将 object 定位到 node 服务器 ###

将 object 使用相同的哈希函数计算出哈希值，并确定该 object 在此数据环上的位置，从此位置沿环顺时针「行走」，第一个遇到的 node 服务器就是应该定位的服务器。

例如 Object A、B、C、D 四个数据对象，经过哈希计算后，在环空间上的位置如下图：  
![这里写图片描述][70 2]

根据一致性哈希算法， Object A、B、C、D分别回映射到服务器集群的node 1、2、3、4 上。

### 一致性哈希算法的容错性和可扩展性 ###

#### node 服务器挂掉 ####

假设 node 3 不幸宕机，可以看到此时 object A、B、D 不会受到影响，只有 C 对象被重新定位到 node 2。一般的，在一致性哈希算法中，如果一台服务器不可用，**受影响的数据仅仅是原本映射到该服务器上的数据，其它不会受到影响。**

![这里写图片描述][70 3]

#### 新增 node 节点 ####

下面考虑在系统中新增一台服务器 node X，如下图所示  
![这里写图片描述][70 4]

此时对象 Object A、B、D 不受影响，只有对象 C 需要重新定位到新的 node X。一般的，在一致性算法中，如果增加一台服务器，**受影响的数据仅仅是新服务器到其闭环中前一台服务器（即沿着逆时针方向行走遇到的第一台服务器） 之间的数据，其它数据不会受到影响**。

综上所述，一致性哈希算法对于节点的增减都只需要重定位环空间中的小部分数据，具有较好的容错性和扩展性。

#### 虚拟节点 ####

有一种情况是：将 node 进行哈希后，这些值没有均匀地落在环上，最终会导致，这些节点所管辖的范围不均匀，最终导致了数据分布的不均匀：  
![这里写图片描述][70 5]

**注**：一致性哈希算法在服务节点太少时，容易因为节点分布不均匀而造成数据倾斜问题。

此时必然会导致大量的数据会映射到 node 1上，而只有极少量的数据会定位到 node 2。为了解决这种数据倾斜的问题，一致性哈希引入了虚拟节点机制，使得每个节点在环上所「管辖」更均匀。这样就能保证在节点变化时，尽可能小的影响数据分布的变化，而同时又保证数据分布的均匀。  
![这里写图片描述][70 6]  
**注**：同样数据定位算法不变，只是多了一步虚拟节点到实际节点的映射，就解决了服务节点少数据倾斜的问题。

## 3.算法实现 ##

笔者使用的语言是 golang，此处介绍一种 golang 实现的一致性哈希算法。

*  [simhash实现][simhash]

## 4.参考资料 ##

*  [一致性哈希算法的理解与实践][Link 1]
 *  [一致性哈希学习总结][Link 2]
 *  [一致性Hash算法背景][Hash]

[70]: /images/20220520/31c70d6c3c96427bb396c6d90b46dd9e.png
[70 1]: /images/20220520/1d5f46dfa5ca4650b1eae025741920a5.png
[70 2]: /images/20220520/9152db4bd57b4f2eb8277d6236489bad.png
[70 3]: /images/20220520/dda14ad534b24aa0b578435bb54e23b3.png
[70 4]: /images/20220520/f9a117af53ee44e89cefcdb85f38b557.png
[70 5]: /images/20220520/c1f419beea744192aac1f0fcf194327b.png
[70 6]: /images/20220520/8a087c195b594683a97511da493bc43d.png
[simhash]: https://github.com/mfonda/simhash
[Link 1]: https://yikun.github.io/2016/06/09/%E4%B8%80%E8%87%B4%E6%80%A7%E5%93%88%E5%B8%8C%E7%AE%97%E6%B3%95%E7%9A%84%E7%90%86%E8%A7%A3%E4%B8%8E%E5%AE%9E%E8%B7%B5/
[Link 2]: http://lihaoquan.me/2017/1/10/consistent-hashing.html
[Hash]: http://www.cnblogs.com/haippy/archive/2011/12/10/2282943.html