Maglev Hashing介绍

seawish · · 430 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

转自 論文中文導讀-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

参考文献


有疑问加站长微信联系

本文来自:简书

感谢作者:seawish

查看原文:Maglev Hashing介绍

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:812540095

430 次点击  
加入收藏 微博
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传