怎么分析一致性HASH算法

共计 3711 个字符，预计需要花费 10 分钟才能阅读完成。

今天就跟大家聊聊有关怎么分析一致性 HASH 算法，可能很多人都不太了解，为了让大家更加了解，丸趣 TV 小编给大家总结了以下内容，希望大家根据这篇文章可以有所收获。

一致性 HASH 算法研究 1. 引言

在研究 Ceph CRUSH 算法时，看到有文章说它是一种特殊的一致性 HASH 算法，于是我便开始研究一致性 HASH 算法做先期准备，发现理念确实接近，区别在于虚拟节点和物理节点的映射办法不同，这是 Ceph 的核心算法，非常关键, 此处不表，下文分解。

2. 一致性 HASH 的出现背景及其优势

在分布式系统中，常常利用 HASH 算法进行数据分布，目的是希望将数据均匀的分布到各节点，分担压力，尤其是在缓存系统中。一个典型的设计如下：

2.1 场景说明

为了提升系统性能，解决数据库的性能瓶颈，设置 N 个缓存服务器，将应用和数据库进行隔离，每个缓存服务器负责数据库 1 / N 的数据。应用程序在访问数据时，根据关键字计算得到 hash 值，并根据一定规则找到数据所在的缓存节点。

2.2 最简单模型

最简单的办法是，采用 hash(key) mode N 的办法计算文件落在的服务器位置，那么在 Find Cache Server 步骤中，需要增加一个取摸操作，存在的问题是：
集群添加机器，计算公式变为 hash(key) / (N + newAddedCount)
集群退出机器，计算公式变为 hash(key) / (N – removedCount)
由于计算公式的分母变化，计算值也都将发生变化。通过取摸运算，找到的节点错误，缓存将失效。我们需要一种方法，当对集群扩容，或者从集群中移除失效机器时，只会导致少量的数据失效，可以很快的在正常的机器或者新增的机器上重新构建起缓存。

2.3 一致性 HASH 模型

基于这个想法，一些专业人士更提出了明确的要求，并形成论文 一致性 HASH 论文

2.3.1 一致性 HASH 基本设计思路

一致性哈希构造了一个 hash 环，将服务器节点映射到环上，将 obj 也映射到环上，将他们至于同一个空间中（0~2^32-1），针对每一个对象，顺时针查找第一个 =hash(obj) 的节点，就是它要存放的目标系统，如果没有找到，按照顺时针，就回归到第一个服务器。

![在上图实例中，根据一致性 HASH 规则，分配后的结果如下：
obj1 ~ obj3 归属于 Cache Server B；
obj4 ~ obj7 归属于 Cache Server C;
obj8~obj11 归属于 Cache Server A. 正是按照上述规则分析下来的结果。

但是存在一个数据分布不均衡的问题，在下图中可以看到，大量的数据会落在服务器 A 上，但是 B,C 上只有少量数据。数据分布明显不平衡。

为了解决数据不均衡的问题，一致性 HASH 中引入了虚拟节点，将对象均匀的映射到虚拟节点，再将虚拟节点映射到物理节点。

通过设置大量的虚拟节点，将数据平均分布到虚拟节点上，最终达到平均分布到物理节点上的效果。此处的关键点是：通过为每个物理节点配置虚拟节点，所有的虚拟节点可以平均的散布到 hash 环上此处一看使用的 hash 函数；另外看物理节点设置的虚拟节点数量；

此处，一致性 hash 是符合我们的期望的：

1、平衡性 (Balance)：hash 后的结果能够平均分布，比如在存储中，数据可以平均分布到各节点，不会出现个别节点数据量特别少，个别特别多的情况；
2、单调性 (Monotonicity)：当新增或者移除节点时，要么映射到原来的位置，或者映射到新节点；不会映射到无效节点；

2.3.2 数据分布均衡测试

为了测试一致性 hash 算法的特性以及虚拟节点对数据分布平衡的影响，我用 C ++ 实现了一个一致性 hash 算法，进行统计试验。

在相同的测试数据，相同的物理节点下，测试不同虚拟节点数量下，数据的分布情况：测试样本：10000 条 URL 记录，用作对象名称，作为 hash 函数的输入 采用的 hash 函数：c++11 中默认的 std::hash() 数据中虚拟节点数量参数是指每个物理节点对应的虚拟节点数量。

 1 节点
101.71.4.31:80 764
101.71.4.32:80 2395
101.71.4.33:80 1478
101.71.4.34:80 786
101.71.4.35:80 4577
101.71.4.31:80 1139
101.71.4.32:80 4862
101.71.4.33:80 1484
101.71.4.34:80 1243
101.71.4.35:80 1272
100 节点
101.71.4.31:80 2646
101.71.4.32:80 2576
101.71.4.33:80 1260
101.71.4.34:80 705
101.71.4.35:80 2813
512 虚拟节点
101.71.4.31:80 2015
101.71.4.32:80 2038
101.71.4.33:80 1948
101.71.4.34:80 2128
101.71.4.35:80 1871
1024 虚拟节点
101.71.4.31:80 2165
101.71.4.32:80 1389
101.71.4.33:80 2045
101.71.4.34:80 2123
101.71.4.35:80 2278
2048 节点
101.71.4.31:80 1976
101.71.4.32:80 1939
101.71.4.33:80 1892
101.71.4.34:80 2164
101.71.4.35:80 2029

101.71.4.34:80 1879
101.71.4.35:80 1915

从数据可以看到，随着对应的虚拟节点越来越多，数据的分布也越来越平衡，但是虚拟节点到达一定数量后，到达了瓶颈，毕竟不可能实现绝对的平衡。

2. 通过增加或者移除节点，查看数据的移动情况：移除节点 采用 1024 虚拟节点的情况下，使 32 节点失效，得到如下的统计结果：

101.71.4.31:80 2392
101.71.4.33:80 2374
101.71.4.34:80 2635
101.71.4.35:80 2599

我对记录文件进行了对比，发现 31,33,34,35 原来各自属于自身的数据没变，多出来的是 32 上的数据，被平均分布到了还有效的四台机器。

增加节点，采用 1024 虚拟节点的情况下，增加 36 节点，得到如下结果：

101.71.4.31:80 1726
101.71.4.32:80 1271
101.71.4.33:80 1776
101.71.4.34:80 1743
101.71.4.35:80 1768
101.71.4.36:80 1716

我对记录文件进行了对比，发现 31,32，33,34,35 上的数据还是以前属于他的数据，但是各自有部分迁移到了 36 机器上。

这两个实验都说明了一致性 Hash 的单调性。

2.3.3 一致性 hash 算法实现

// 构建带虚拟节点的 hash 环，对每个真实的物理节点，配置若干虚拟节点，并进行排序
for (RNode node : rnodes)
 for (int i = 1; i  = virtual_node_count; i++)
 VNode vnode;
 vnode.ip_port = node.ip_port +  #  + to_string(i);
 vnode.id = myhash(vnode.ip_port); // 虚拟节点在 hash 环上的映射
 circle.push_back(vnode);
 node.virtual_nodes.push_back(vnode);
sort(circle.begin(), circle.end(), cmpVNode);

// 计算每个 URL 落在那个虚拟节点
VNode getLocation(string url, vector VNode  vnodes)
 VNode tmp;
 tmp.id = myhash(url.c_str());
 vector VNode ::iterator iter = std::lower_bound(vnodes.begin(), vnodes.end(), tmp, cmpVNode);
 if (iter == vnodes.end())
 return vnodes[0];
 }else 
 return *iter;
// 根据虚拟节点，找到对应物理节点
string real_node = getRealNodeInfo(vnode);

3.CRUSHMAP 的进一步研究

研究一致性 HASH 的目的是为了更好的理解 Ceph CRUSHMAP 算法，此处简单说明 Ceph 中对象是如何映射到具体设备的某块硬盘上。在 Ceph 中，每个对象都属于某个 PG，我把这些 PG 理解为一致性哈希中的虚拟节点，目的是为了让对象分布更均匀。而 pg 是如何映射到 OSD 呢。在上文中，这种映射关系比较简单，就是多对一，在 ceph 中则比较复杂，因为映射关系依赖于集群的拓扑结构, 而每个对象都还有多副本, 需要指定的映射算法，计算出 pg 所在的主 OSD 以及副本 OSD。

看完上述内容，你们对怎么分析一致性 HASH 算法有进一步的了解吗？如果还想了解更多知识或者相关内容，请关注丸趣 TV 行业资讯频道，感谢大家的支持。