百木园-与人分享,
就是让自己快乐。

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

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

前言(为什么想读这一篇论文)

这一篇论文吸引我注意的原因是,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奥克米_ _)(lG)
  • 最差情况:Ø (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=3entry[3]往后第一个next[0] +1m.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 部分:一窥一致性哈希!

 

如果是此文是转载文章,本人会附上转载链接,此篇文章的版权归原创作者所属,如果侵权请与我联系,我会删除此文。

若没有标明转载链接,此篇文章属于本人的原创文章,其版权所属:

作者:feiquan

出处:http://www.cnblogs.com/feiquan/

版权声明:本文版权归作者和博客园共有,欢迎转载,但未经作者同意必须保留此段声明,且在文章页面明显位置给出原文连接,否则保留追究法律责任的权利。

大家写文都不容易,请尊重劳动成果~ 这里谢谢大家啦(*/ω\*)


来源:https://www.cnblogs.com/feiquan/p/16289675.html
本站部分图文来源于网络,如有侵权请联系删除。

未经允许不得转载:百木园 » Maglev : A Fast and Reliable Software Network Load Balancer (using Consistent Hashing)

相关推荐

  • 暂无文章