[轉(zhuǎn)]Maglev Hashing介紹

轉(zhuǎn)自論文中文導(dǎo)讀-Maglev奉狈。原文為繁體字嫉柴，為方便閱讀耍攘，此處改為簡體恕酸。

Maglev

前言

這一篇論文吸引我注意的原因是堪滨， Consistent Hashing 本來的特性就是作為 Distributed Caching 之用．但是 Google 將他們的 Load Balancer (代號: Maglev ) 公布他的實作方式，里面并且將 Consistent Hashing 做了一些小改版來符合他們的需求．
由于我之前就有學(xué)習(xí)過 Consistent Hashing 尸疆，所以相當(dāng)好奇 Google 能夠如何地將它更進(jìn)一步地做提升．就想要閱讀這一篇論文．
本篇導(dǎo)讀主要內(nèi)容如下:

介紹 Maglev 的特性與其改善的部分
回顧 Consistent Hashing
介紹 Maglev Hashing

原始論文

Maglev: A Fast and Reliable Software Network Load Balancer

導(dǎo)讀

什么是Maglev椿猎？

Maglev 是 Google 的軟體 Load Balancer ，不像是一般硬體的 Load Balancer 寿弱，他可以運行在一般的 Linux 機器上面． Maglev 在 Google 內(nèi)部已經(jīng)運行了超過六年 ( since 2008 ) ．一臺 Maglev 可以處理 10Gbps 的小封包連結(jié)．

Maglev 主要的功能與特色

Maglev 主要的功能與特色Maglev 作為 Google 內(nèi)部的高效能軟體 Load Balancer 犯眠，他有以下兩個主要功能：

新的 Consistent Hashing Algorithm 稱為 Maglev Hashing
Connection Tracking

回過來講，那什么是 Consistent Hashing ?

Consistent Hashing

講到 Consistent Hashing 就必須要提到原本 distributed caching 的運作是靠 Hash Table 的方式來達(dá)成症革，比如說:

來源 ip : 1.2.3.4 透過將來源 ip 做 Hashing 過后指向 server1
來源 ip : 1.2.3.5 透過將來源 ip 做 Hashing 過后指向 server2
來源 ip : 1.2.4.6 透過將來源 ip 做 Hashing 過后指向 server3

依照原先的設(shè)計如果 server1 發(fā)生了故障筐咧，那麼不論如何 1.2.3.4 就無法連接到任何一個伺服器．
于是 Consistent Hashing 就是在這裡發(fā)揮效果．根據(jù)定義 Consistent Hashing 為一個排序的環(huán)狀的表格，上面根據(jù) Hashing 的數(shù)值來存放不同的節(jié)點資訊噪矛，并且需要滿足以下兩個條件:

ring range

Minimal Disruption: 這邊指的就是如果有節(jié)點被刪除量蕊，應(yīng)該要達(dá)到只有該節(jié)點影響到的部分要修改而已。在Consistent Hashing里面透過選取下一個的方式艇挨，通過將索引排序后残炮，直接選取下一個節(jié)點作為Hashing后的結(jié)果節(jié)點。簡單的范例如下：
- 來源 IP 位置 1.2.3.4 缩滨，經(jīng)過 Hashing 后得到位置 1024 (假設(shè))
- 到表格 1024 查詢資料势就，發(fā)現(xiàn) 1024 的節(jié)點服務(wù)器server1 已經(jīng)出現(xiàn)故障．
- 尋找 1024 最接近的下一個節(jié)點（假設(shè)是 1028 ) 並且對應(yīng)到 server2
- 分配 server2
  
  hash過程

對于 Maglev 而言，原本的 Consistent Hashing 有哪些缺點（限制)脉漏？

雖然 Consisten Hashing 本身已經(jīng)解決了許多的問題苞冯，但是對于 Google 而言，他們有以下兩個額外的部份需要考量：

需要更均勻地分配每個節(jié)點位置：由于 Google 的每個節(jié)點可能都是數(shù)百臺的機器侧巨，由于來源資料龐大舅锄，根據(jù)舊的演算法可能需要相當(dāng)大的 lookup table 才能負(fù)荷．
需要更減少 Disruption : 對于 Google 的需求，演算法需要容忍小量的 disruption ．

關(guān)于 Maglev Hashing Algorithm 的介紹

根據(jù)以上兩個需要額外考量（應(yīng)該說是要更加強化）的部分司忱， Google 提出了新的 Consistent Hashing 的演算法皇忿，稱為 Maglev Hashing Algorithm

主要概念: 新增 Preference List 概念

Preference List (偏好清單) 會分配給每一個節(jié)點，讓每一個節(jié)點去填上自己偏好的位址( Permutation )．直到整個表格是填滿的狀態(tài)．

效能:

這裡需要注意坦仍，如果 M 相當(dāng)接近 N 的話轧叽，整體效能很容易落入最差狀況．

但是如果 M>>N 黍判，比較容易將效能落入平均的狀況．

平均狀況: O(MlogM)
最差狀況: O(M2)

其中：

M 是表示 lookup table 的大衅ぁ．
N 是表示節(jié)點的個數(shù)．

流程:

首先 Maglev Hashing 會先把所有的 Preference List 產(chǎn)生出來．
透過產(chǎn)生好的 Preference List 開始將節(jié)點一個個地加入并且產(chǎn)生出Lookup table

程式碼分析:

計算 “排列表格” Permutation Table

以下先簡單列出 generatePopulation()掀亩，主要目的就是建立permutation table也就一個排列組合的表格．

//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 必須是一個prime number （如果不給 prime number ，找出的 permutation 就會有重複值) ，舉例 M=7 這個函式就會產(chǎn)生可能是 [3, 2, 5, 6, 0, 4, 1] 或是 [0, 5, 6, 4, 2, 3, 1] ．這樣的排列表格是為之后使用的．

產(chǎn)生查表表格(Lookup Table)

論文中的 Populate Maglev Hashing lookup table 的 Golang 程式碼．

這邊有兩個表格:

entry: 代表表格中有沒有走過．假設(shè) lookup table 大小為 7铺峭，就得 0 ~ 6 都走過一次．（不然為 -1)．而最后裡面的數(shù)值就是節(jié)點的索引．
next: 代表排列表格的下一個位置．如果節(jié)點有三個墓怀，那麼排列表格就有三組．于是 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]

透過這個范例，建立出 Lookup table 的方式如下：

將剛剛建立出的排列表格拿出來
i=0 莉炉，從第一個排列表格的第一個挑出數(shù)值 c1=4 钓账，那麼 entry[4] = 0 (代表 lookup table 中的 entry[4] 是指向節(jié)點 0．
i=1 ，從第二個排列表格的第一個挑出數(shù)值 c2=3 絮宁，那麼 entry[3] = 1
i=2 梆暮，從第三個排列表個的第一個挑出數(shù)值 c3=0 ，那麼 entry[0] = 2
重跑 i 迴圈绍昂， i=0 ．從第一個排列表格的第二個( index=1 )挑出數(shù)值 c4=3 啦粹，由于 entry[3] 走過了，往后走一個（next[0] +1) 走到 m.permutation[0][2]=2窘游，于是 entry[2]=0
依此類推唠椭，直到所有的 n == M ．此時，也會發(fā)現(xiàn) entry[] 不再存在任何 -1
詳細(xì)走法如下圖：

maglev查找表

Maglev Hashing 跟 Consistent Hashing 的比較

這部分比較屬于我的心得忍饰，建議各位看完論文后再看這段．

Consistent Hashing
- 準(zhǔn)備工作:
  - 將每個節(jié)點數(shù)值根據(jù) Hashing key 加入 lookup table
  - 製作出 Virtual Node 來達(dá)到平衡．
- 如何查詢:
  - 將數(shù)值透過 Hash Key 對應(yīng)到一個 lookup table 的索引 index
  - 如果該 index 沒有節(jié)點贪嫂，往下尋找最接近的節(jié)點
Maglev Hashing
- 準(zhǔn)備工作:
  - 需要先建立一個排列表格
  - 并請需要先透過排列表格做出偏好清單．注意這時候所有 lookup table 每一個索引都有一個節(jié)點分配．
- 如何查詢:
  - 數(shù)值透過 Hash Key 對應(yīng)到一個 lookup table 的索引 index
  - 由于準(zhǔn)備工作，該 index 必定存在數(shù)值
  - 傳回節(jié)點資料

完整代碼

這邊有我的完整代碼艾蓝，大家可以參考以下：

https://github.com/kkdai/maglev

參考文獻(xiàn)

Wiki Consistent_hashing
Go implementation of maglev hashing
每天進(jìn)步一點點——五分鐘理解一致性哈希算法(consistent hashing)
Distributed Systems Part-1: A peek into consistent hashing!