Maglev Hashing介绍

转自 論文中文導讀-Maglev。原文为繁体字，为方便阅读，此处改为简体。

Maglev

前言

这一篇论文吸引我注意的原因是， Consistent Hashing 本来的特性就是作为 Distributed Caching 之用． 但是 Google 将他们的 Load Balancer (代号: Maglev ) 公布他的实作方式，里面并且将 Consistent Hashing 做了一些小改版来符合他们的需求．
由于我之前就有学习过 Consistent Hashing ，所以相当好奇 Google 能够如何地将它更进一步地做提升． 就想要阅读这一篇论文．
本篇导读主要内容如下:

• 介绍 Maglev 的特性与其改善的部分
• 回顾 Consistent Hashing
• 介绍 Maglev Hashing

原始论文

Maglev: A Fast and Reliable Software Network Load Balancer

导读

什么是Maglev？

Maglev 是 Google 的软体 Load Balancer ，不像是一般硬体的 Load Balancer ， 他可以运行在一般的 Linux 机器上面． Maglev 在 Google 内部已经运行了超过 六年 ( since 2008 ) ．一台 Maglev 可以处理 10Gbps 的小封包连结．

Maglev 主要的功能与特色

Maglev 主要的功能与特色Maglev 作为 Google 内部的高效能软体 Load Balancer ，他有以下两个主要功能：

• 新的 Consistent Hashing Algorithm 称为 Maglev Hashing
• Connection Tracking

回过来讲，那什麽是 Consistent Hashing ?

Consistent Hashing

讲到 Consistent Hashing 就必须要提到原本 distributed caching 的运作是靠 Hash Table 的方式来达成，比如说:

• 来源 ip : 1.2.3.4 透过将来源 ip 做 Hashing 过后指向 server1
• 来源 ip : 1.2.3.5 透过将来源 ip 做 Hashing 过后指向 server2
• 来源 ip : 1.2.4.6 透过将来源 ip 做 Hashing 过后指向 server3

依照原先的设计如果 server1 发生了故障，那麽不论如何 1.2.3.4 就无法连接到任何一个伺服器．
于是 Consistent Hashing 就是在这裡发挥效果． 根据定义 Consistent Hashing 为一个排序的环状的表格，上面根据 Hashing 的数值来存放不同的节点资讯，并且需要满足以下两个条件:

ring range

• Minimal Disruption: 這邊指的就是如果有節點被刪除，應該要達到只有該節點影響到的部分要修改而已． 在 Consistent Hashing 裡面透過選取下一個的方式． 透過將索引排序後，直接選取下一個節點作為 Hashing 後的結果節點．簡單的範例如下:
  • 來源 IP 位置 1.2.3.4 ，經過 Hashing 後得到位置 1024 (假設)
  • 到表格 1024 查詢資料，發現 1024 的節點伺服器 server1 已經出現故障．
  • 尋找 1024 最接近的下一個節點 （假設是 1028 ) 並且對應到 server2
  • 分配 server2
    
    

    hash过程

对于 Maglev 而言，原本的 Consistent Hashing 有哪些缺点（限制)？

虽然 Consisten Hashing 本身已经解决了许多的问题，但是对于 Google 而言，他们有以下两个额外的部份需要考量：

• 需要更均匀地分配每隔节点位置： 由于 Google 的每个节点可能都是数百台的机器，由于来源资料庞大，根据旧的演算法可能需要相当大的 lookup table 才能负荷．
• 需要更减少 Disruption : 对于 Google 的需求，演算法需要容忍小量的 disruption ．

关于 Maglev Hashing Algorithm 的介绍

根据以上两个需要额外考量（应该说是要更加强化）的部分， Google 提出了新的 Consistent Hashing 的演算法，称为 Maglev Hashing Algorithm

主要概念: 新增 Preference List 概念

Preference List (偏好清单) 会分配给每一个节点，让每一个节点去填上自己偏好的位址( Permutation )．直到整个表格是填满的状态．

效能:

这裡需要注意，如果 M 相当接近 N 的话，整体效能很容易落入最差状况．

但是如果 M>>N ，比较容易将效能落入平均的状况．

• 平均状况: O(MlogM)

• 最差状况: O(M2)

其中：

• M 是表示 lookup table 的大小．
• N 是表示 节点的个数．

流程:

• 首先 Maglev Hashing 会先把所有的 Preference List 产生出来．
• 透过产生好的 Preference List 开始将节点一个个地加入并且产生出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 这个函式就会产生可能是 [3, 2, 5, 6, 0, 4, 1] 或是 [0, 5, 6, 4, 2, 3, 1] ． 这样的排列表格是为之后使用的．

产生查表表格(Lookup Table)

论文中的 Populate Maglev Hashing lookup table 的 Golang 程式码．

这边有两个表格:

• entry: 代表表格中有没有走过．架设 lookup table 大小为 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]

透过这个范例，建立出 Lookup table 的方式如下：

• 将刚刚建立出的排列表格拿出来
• i=0 ，从第一个排列表格的第一个挑出数值 c1=4 ，那麽 entry[4] = 0 (代表 lookup table 中的 entry[4] 是指向节点 0．
• i=1 ，从第二个排列表格的第一个挑出数值 c2=3 ，那麽 entry[3] = 1
• i=2 ，从第三个排列表个的第一个挑出数值 c3=0 ，那麽 entry[0] = 2
• 重跑 i 迴圈， i=0 ． 从第一个排列表格的第二个( index=1 )挑出数值 c4=3 ，由于 entry[3] 走过了，往后走一个 （next[0] +1) 走到 m.permutation[0][2]=2， 于是 entry[2]=0

• 依此类推，直到所有的 n == M ．此时，也会发现 entry[] 不再存在任何 -1
  详细走法如下图：

  
  
  

  maglev查找表

Maglev Hashing 跟 Consistent Hashing 的比較

这部分比较属于我的心得，建议各位看完论文后再看这段．

• Consistent Hashing
  • 准备工作:
    • 将每个节点数值根据 Hashing key 加入 lookup table
    • 製作出 Virtual Node 来达到平衡．
  • 如何查询:
    • 将数值透过 Hash Key 对应到一个 lookup table 的索引 index
    • 如果该 index 没有节点，往下寻找最接近的节点
• Maglev Hashing
  • 准备工作:
    • 需要先建立一个排列表格
    • 并请需要先 透过排列表格做出偏好清单．注意这时候所有 lookup table 每一个索引都有一个节点分配．
  • 如何查询:
    • 数值透过 Hash Key 对应到一个 lookup table 的索引 index
    • 由于准备工作，该 index 必定存在数值
    • 传回节点资料

完整代码

这边有我的完整代码，大家可以参考以下：

https://github.com/kkdai/maglev

参考文献

• Wiki Consistent_hashing
• Go implementation of maglev hashing
• 每天进步一点点——五分钟理解一致性哈希算法(consistent hashing)
• Distributed Systems Part-1: A peek into consistent hashing!