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

转自：https://www.evanlin.com/maglev/ 2016 年 6 月 2 日

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

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

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

本篇导读主要内容如下：



原始论文

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



导读

什么是磁悬浮？

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

磁悬浮主要的功能与特色

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

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

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

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

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

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

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

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

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

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

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

功效：

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

如果但是米> >无米>>ñ，比较容易实现入户的情况。

其中：

流程：

程序码分析：

计算“排列表格”排列表

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

//name is the list of backend.
func generatePopulation() {
	//如果 []name 是空的就離開
	if len(name) == 0 {
		return
	}

	for i := 0; i < len(name); i++ {
		bData := []byte(name[i])

		//計算 offset 透過 Hash K1
		offset := siphash.Hash(0xdeadbabe, 0, bData) % M
		//計算 skip 透過 Hash K2
		skip := (siphash.Hash(0xdeadbeef, 0, bData) % (M - 1)) + 1

		iRow := make([]uint64, M)
		var j uint64
		for j = 0; j < m.m; j++ {
			//排列組合的表格
			iRow[j] = (offset + uint64(j)*skip) % M
		}

		permutation = append(permutation, iRow)
	}
}

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

产生查表(查阅表)

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

这边有两个表格：

翻译资料

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]

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

详细走法如下图：

Maglev Hashing 跟 Consistent Hashing 的比较

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

完整的程序码

这里有我的完整程序码，大家可以参考一下：

https://github.com/kkdai/maglev

参考