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

这一篇论文吸引我注意的原因是，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）。直到整个表格是完整的。

功效：

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

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

• 平均状况：O (米l奥克米_ _)○(米l○G米)
• 最差情况：Ø (米2)○(米2)

其中：

• 米米是表示查找表的大小．
• ññ是表示节点的个数．

流程：

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

程序码分析：

计算“排列表格”排列表

下面首先简单排列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 程序。

这边有两个表格：

• 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 到一个查找表
    • 准备工作，该指数持续存在
    • 传回节点资料

完整的程序码

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

https://github.com/kkdai/maglev

参考

• Wiki Consistent_hashing
• Go 实现磁悬浮哈希
• 每天进步一点点——五分钟理解一致哈希算法（consistent hashing）
• 分布式系统第 1 部分：一窥一致性哈希！