Maglev : A Fast and Reliable Software Network Load Balancer (using Consistent Hashing)

2023年5月10日 138点热度 0人点赞 0条评论

转自：https://www.evanlin.com/maglev/

2016 年 6 月 2 日

前言（为什么想读这一篇论文）

这一篇论文吸引我注意的原因是，Consistent Hashing本来的特性就是作为分布式缓存之用。谷歌将他们的负载均衡器（代号：Maglev）发布他的实作方式，里面将一致的哈希并做了一些小改版来符合他们的需求。

此前我一直在进一步学习，因为谷歌很好地利用了它的能力，因此更有效地提高了它的能力。就想要阅读这一篇论文。

本篇导读主要内容如下：

介绍 Maglev 的特性和改进的部分
回顾一致哈希
介绍磁悬浮哈希

原始论文

Maglev：快速可靠的软件网络负载均衡器

导读

什么是磁悬浮？

Maglev 是 Google 的软体 Load Balancer ，是一般硬体的 Load Balancer ，他可以在一般的 Linux 机器上面运行。Maglev 在 Google 内部已经运行了超过六年（从 2008 年开始）。一个 Maglev 可以处理 10Gbps 的小封包链接。

磁悬浮主要的功能与特色

Maglev 作为 Google 内部的高效能体软负载均衡器，他有以下两个主要功能：

新的一致性哈希算法称为磁悬浮哈希
连接跟踪

回过头来，那什么是 Consistent Hashing ？

讲到 Consistent Hashing 就必须提到原本分布式缓存的准许靠是 Hash Table 的方式来结果，如：

来源ip：1.2.3.4通过将来源ip做散列之后指向server1
来源ip：1.2.3.5通过将来源ip做散列之后指向server2
来源ip：1.2.4.6通过将来源ip做散列之后指向server3

如果你能确定如果server1发生故障，那么1.2.3.4就无法连接到任何服务器。

Consistent Hashing 就是在这里发挥效果。根据定义的Consistent Hashing 为一个示例的以下表格的表格，根据Hashing 的表格需要不同的条件来满足不同的节点信息，并且满足两个条件

Minimal Disruption：如果有被修改的部分，应该只需要到达该部分影响的部分就可以了。在 Consistent Hashing 里面有下面一个的方式．贯穿整个索引示例后，直接指定下一个节点作为哈希后的结果节点。简单的示例如下：
- 来源 IP 位置1.2.3.4，经过哈希处理后得到的位置 1024（假设）
- 到表格 1024 查询资料，发现 1024 的节点server1服务器已经出现故障．
- 寻找1024个最接近的下一个偏差（假设是1028个）并且到了server2
- 分配server2

负载平衡也有可能会过地地让其他任何人都使用到，不会有某种程度的应用的疑虑。在 Consistent Hashing 里面是使用 Virtual Node ．
- 简单的说，也就是在加入节点的时候，会一并复制多个虚拟节点（通常使用節點#1, 節點#2 ... 修饰方式．
- 透过多个虚拟节点散布在各处，让寻找的时间更变的分布到不同的节点。

对于 Maglev 而言，原本的 Consistent Hashing 有什么缺点（限制）？

Hashing 本身已经解决了许多问题，但是 Google 确实需要考虑以下几个额外的问题：

需要更均匀地配置每个节点位置：由于谷歌的每个节点都可能是一个可能的台机，因此，根据不同的演播信息，需要很大的查找表。
需要更减少干扰：针对谷歌的需求，演算法需要小量的干扰．

关于磁悬浮哈希算法的介绍

可知需要额外考量（应该说是要强化）的更多部分，Google 提出了新的 Consistent Hashing 的演算法，称为Maglev Hashing Algorithm

主要概念：新增偏好列表概念

偏好列表（每一个偏好列表）会分配给一个节点，让自己的位置上去（Permutation）。直到整个表格是完整的。

功效：

这里需要注意，如果 $M$ 相当接近 $N$ 的话，功效很容易落入最差的状况。

如果但是 $M >> N$ ，比较容易实现入户的情况。

平均状况： $O (M l o g M)$
最差情况： $O (M^{2})$

其中：

$M$ 是表示查找表的大小．
$N$ 是表示节点的个数．

流程：

首先 Maglev Hashing 会先把所有的 Preference List 产生出来。
通过并产生好的偏好列表开始将节点一个个地加入产生出的查找表

程序码分析：

计算“排列表格”排列表

下面首先简单排列generatePopulation()，主要目的是建立一个组合表的表格。

<span class="c">//name is the list of backend.</span>
<span class="k">func</span> <span class="n">generatePopulation</span><span class="p">()</span> <span class="p">{</span>
	<span class="c">//如果 []name 是空的就離開</span>
	<span class="k">if</span> <span class="nb">len</span><span class="p">(</span><span class="n">name</span><span class="p">)</span> <span class="o">==</span> <span class="m">0</span> <span class="p">{</span>
		<span class="k">return</span>
	<span class="p">}</span>

	<span class="k">for</span> <span class="n">i</span> <span class="o">:=</span> <span class="m">0</span><span class="p">;</span> <span class="n">i</span> <span class="o"><</span> <span class="nb">len</span><span class="p">(</span><span class="n">name</span><span class="p">);</span> <span class="n">i</span><span class="o">++</span> <span class="p">{</span>
		<span class="n">bData</span> <span class="o">:=</span> <span class="p">[]</span><span class="kt">byte</span><span class="p">(</span><span class="n">name</span><span class="p">[</span><span class="n">i</span><span class="p">])</span>

		<span class="c">//計算 offset 透過 Hash K1</span>
		<span class="n">offset</span> <span class="o">:=</span> <span class="n">siphash</span><span class="o">.</span><span class="n">Hash</span><span class="p">(</span><span class="m">0xdeadbabe</span><span class="p">,</span> <span class="m">0</span><span class="p">,</span> <span class="n">bData</span><span class="p">)</span> <span class="o">%</span> <span class="n">M</span>
		<span class="c">//計算 skip 透過 Hash K2</span>
		<span class="n">skip</span> <span class="o">:=</span> <span class="p">(</span><span class="n">siphash</span><span class="o">.</span><span class="n">Hash</span><span class="p">(</span><span class="m">0xdeadbeef</span><span class="p">,</span> <span class="m">0</span><span class="p">,</span> <span class="n">bData</span><span class="p">)</span> <span class="o">%</span> <span class="p">(</span><span class="n">M</span> <span class="o">-</span> <span class="m">1</span><span class="p">))</span> <span class="o">+</span> <span class="m">1</span>

		<span class="n">iRow</span> <span class="o">:=</span> <span class="nb">make</span><span class="p">([]</span><span class="kt">uint64</span><span class="p">,</span> <span class="n">M</span><span class="p">)</span>
		<span class="k">var</span> <span class="n">j</span> <span class="kt">uint64</span>
		<span class="k">for</span> <span class="n">j</span> <span class="o">=</span> <span class="m">0</span><span class="p">;</span> <span class="n">j</span> <span class="o"><</span> <span class="n">m</span><span class="o">.</span><span class="n">m</span><span class="p">;</span> <span class="n">j</span><span class="o">++</span> <span class="p">{</span>
			<span class="c">//排列組合的表格</span>
			<span class="n">iRow</span><span class="p">[</span><span class="n">j</span><span class="p">]</span> <span class="o">=</span> <span class="p">(</span><span class="n">offset</span> <span class="o">+</span> <span class="kt">uint64</span><span class="p">(</span><span class="n">j</span><span class="p">)</span><span class="o">*</span><span class="n">skip</span><span class="p">)</span> <span class="o">%</span> <span class="n">M</span>
		<span class="p">}</span>

		<span class="n">permutation</span> <span class="o">=</span> <span class="nb">append</span><span class="p">(</span><span class="n">permutation</span><span class="p">,</span> <span class="n">iRow</span><span class="p">)</span>
	<span class="p">}</span>
<span class="p">}</span>

必须M是一个素数（如果不给素数，它的排列就必须有重复值），M=7这个典型的式可能[3, 2, 5, 6, 0, 4, 1]会产生[0, 5, 6, 4, 2, 3, 1]。的排列形式是为之后使用的。

产生查表(查阅表)

论文中的 Populate Maglev Hashing 查找表的 Golang 程序。

这边有两个表格：

entry: 代表表格里面没有走过。架设查找表大小为7，就得0~6 都走了一次。（索引为-1）．而最后的分数就是节点的
next: 代表排列表格的下一个位置，如果有三个，那么有三个表格。这样next大小也有三个分别排列的记录，每一个表格排列成第几个位置。

翻译资料

unc (m *Maglev) populate() {
	if len(m.nodeList) == 0 {
		return
	}

	var i, j uint64
	next := make([]uint64, m.n)
	entry := make([]int64, m.m)
	for j = 0; j < m.m; j++ {
		entry[j] = -1
	}

	var n uint64

	for { //true
		for i = 0; i < m.n; i++ {
			c := m.permutation[i][next[i]]
			for entry[c] >= 0 {
				next[i] = next[i] + 1
				c = m.permutation[i][next[i]]
			}

			entry[c] = int64(i)
			next[i] = next[i] + 1
			n++

			if n == m.m {
				m.lookup = entry
				return
			}
		}

	}

}

下面用简单的翻译资料，希望能够让大家更容易了解。

N = 3
M = 5

m.permutation [0] = [4, 3, 2, 1, 0]
m.permutation [1] = [3, 2, 1, 0, 4]
m.permutation [2] = [0, 1, 2, 3, 4]

通过这个实例，建立出查找表的方式如下：

将刚刚建立出的排列形式来
i=0，从第一个排列表格的第一个挑出分数 c1=4，那么entry[4] = 0（代表查找表中entry[4]指向节点0。
i=1，从第二个排列表格的第一个挑出分数 c2=3，那么entry[3] = 1
i=2，从第三个排列表个的第一个挑出分数 c3=0，那么entry[0] = 2
重i跑回圈， i=0．）挑出一个（索引=走过第二个c4=3，entry[3]往后第一个next[0] +1）m.permutation[0][2]=2entry[2]=0
依此类推所有的n == M。此时，也发现entry[]不再存在任何-1

详细走法如下图：

Maglev Hashing 跟 Consistent Hashing 的比较

推荐部分研究的那部分，应该属于我比较看重的。

一致的哈希
- 准备工作：
  - 将每个节点的分数根据散列键查找表
  - 制作出虚拟节点来达到平衡．
- 如何查询：
  - 将分数贯穿 Hash Key 到一个查找表索引
  - 如果该索引没有节点，往下寻找最接近的节点
磁悬浮哈希
- 准备工作：
  - 需要先建立一个排列表格
  - 请并请先通过排列表格排列一个排序偏好清单。
- 如何查询：
  - 索引的索引 Hash Key 到一个查找表
  - 准备工作，该指数持续存在
  - 传回节点资料