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

轉自：https://www.evanlin.com/maglev/ 2016 年 6 月 2 日前言（為什麼想讀這一篇論文）這一篇論文吸引我註意的原因是，Consistent Hashing本來的特性就是作為分散式緩存之用。谷歌將他們的負載均衡器（代號：Maglev）發佈他的實作方式，裡面將一 ...

轉自：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()，主要目的是建立一個組合表的表格。

//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

參考

如果是此文是轉載文章，本人會附上轉載鏈接，此篇文章的版權歸原創作者所屬，如果侵權請與我聯繫，我會刪除此文。

若沒有標明轉載鏈接，此篇文章屬於本人的原創文章，其版權所屬：
作者：feiquan
出處：http://www.cnblogs.com/feiquan/
版權聲明：本文版權歸作者和博客園共有，歡迎轉載，但未經作者同意必須保留此段聲明，且在文章頁面明顯位置給出原文連接，否則保留追究法律責任的權利。
大家寫文都不容易，請尊重勞動成果~ 這裡謝謝大家啦(*/ω＼*)