Google Maglev Hashing实现

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

背景

Maglev是Google开发的基于kernal bypass技术实现的4层负载均衡,它具有非常强大的负载性能,承载了Google据大部分接入流量。Maglev在负载均衡算法上采用自行开发的一致性哈希算法被称为Maglev Hashing,该哈希算法在节点变化时能够尽量少的影响其他几点,且尽可能的保证负载的均衡,是一个非常优秀的一致性哈希算法,Google的技术都是自带光环哈!下面想用Golang做一个简单的实现。

原理说明

Maglev Hashing的基本思想是为每一个节点生成一个优先填充表,列表的值就是该节点想要填充查询表的位置.
lookup table

如Table1所示,节点B0,会按照顺序3,0,4,...依次去尝试填充查询表。实际上,所有的节点会轮流按照各自优先列表的值填充查询表。也就是说,每个节点都有几乎均等的机会根据优先表来填充查询表,直到查询表被填满。

当出现节点变化,如B1宕机时,查询表会重新生成,因为节点的优先填充表不变,所以B0和B2原来的填充位置不变,B1宕机后确实的位置被B0和B2瓜分,按照轮流填充的机制,B0和B2基本也是均衡的。

算法实现

M为查询表的大小。对与每一个节点ipermutation[i]为优先填充表,permutation[i]的取值是数组[0, M-1]的一个随机顺序排列,permutation是一个二维数组。

下面介绍论文给出的高效生成permutation[i]的方法:
首先使用两种哈希函数来哈希节点生成两个数字,offset skip. 论文中是计算节点名称的哈希值,为了简单我就直接计算了节点的索引值,哈希函数我用的是算法导论里提到的乘法散列法,代码如下:

func Hash1(k int) int {
    s := uint64(2654435769)
    p := uint32(14)
    tmp := (s * uint64(k)) % (1 << 32)
    return int(tmp / (1 << (32 - p)))
}

func Hash2(k int) int {
    s := uint64(1654435769)
    p := uint32(14)
    tmp := (s * uint64(k)) % (1 << 32)
    return int(tmp / (1 << (32 - p)))
}

第二个哈希函数我只是修改了一个参数值,哈希算法是一样的。offset skip计算方式如下:

offset←h1(name[i]) mod M
skip←h2(name[i]) mod (M−1)+1

从而得到permutation[i]中每一个值的计算方式:
permutation[ i ][ j ]←(offset+ j×skip) mod M 0<=j<= M-1
这里要注意的是M必须为质数,这样才能尽可能保证skip与M互斥。寻找合适的质数M我使用了简单的筛选算法:

func isPrime(n int) bool {
    if n < 2 {
        return false
    }
    end := int(math.Sqrt(float64(n)))
    for i := 2; i <= end; i++ {
        if n%i == 0 {
            return false
        }
    }
    return true
}

func findPrime(n int) int {
    //始终有大于n的质数
    for {
        if isPrime(n) {
            return n
        }
        n++
    }
}

上面介绍了一些辅助函数,下面介绍算法的具体实现流程:

type MaglevHash struct {
    m, n        int
    permutation [][]int
    entry       []int
    nodeState   []bool
}

func NewMaglevHash(n int) *MaglevHash {
    m := findPrime(5 * n)
    permutation := make([][]int, n)
    entry := make([]int, m)
    nodeState := make([]bool, n)
    for idx, _ := range nodeState {
        nodeState[idx] = true
    }

    return &MaglevHash{
        m:           m,
        n:           n,
        permutation: permutation,
        entry:       entry,
        nodeState:   nodeState,
    }
}

定义一个结构MaglevHash和结构体生成函数,golang的标准实现。其中permutation为一个N*M的二维数组,entry为长度N的查询表,nodeState为长度N的记录节点时候的下线的表。

接下来是生成permutation的函数,计算节点时实际上传入的是节点索引值加一,避免传入0,影响哈希值的计算:

func (mh *MaglevHash) Permutate() {
    for idx, _ := range mh.permutation {
        mh.permutation[idx] = make([]int, mh.m)
    }
    for i := 0; i < mh.n; i++ {
        offset := Hash1(i+1) % mh.m
        skip := Hash2(i+1)%(mh.m-1) + 1
        for j := 0; j < mh.m; j++ {
            mh.permutation[i][j] = (offset + j*skip) % mh.m
        }
    }
}

生成好节点优先填充表之后,就可以根据该表填充查询表:

func (mh *MaglevHash) Populate() {
    for idx, _ := range mh.entry {
        mh.entry[idx] = -1
    }
    next := make([]int, mh.n)
    n := 0
    for {
        for i := 0; i < mh.n; i++ {
            if !mh.nodeState[i] {
                continue
            }
            c := mh.permutation[i][next[i]]
            for mh.entry[c] >= 0 {
                next[i]++
                c = mh.permutation[i][next[i]]
            }
            mh.entry[c] = i
            next[i]++
            n++
            if n == mh.m {
                return
            }
        }
    }
}

在填充查询表时,会检查节点是否下线,若节点下线,则会忽略该节点。

func (mh *MaglevHash) DownNode(idx int) error {
    if idx > mh.n-1 {
        return errors.New("invalid idx")
    }
    mh.nodeState[idx] = false
    return nil
}

节点下线时,需要调用该函数,然后再调用Populate()重新填充查询表。

至此,Maglev hashing 一个简单的实现就算完成了,后续希望使用生产环境的哈希函数来替换本文用到哈希函数,并考虑在nginx上实现该一致性哈希算法。


有疑问加站长微信联系(非本文作者)

本文来自:简书

感谢作者:Damon_330b

查看原文:Google Maglev Hashing实现

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

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