内容简介:Maglev是Google开发的基于kernal bypass技术实现的4层负载均衡,它具有非常强大的负载性能,承载了Google据大部分接入流量。Maglev在负载均衡算法上采用自行开发的一致性哈希算法被称为Maglev Hashing,该哈希算法在节点变化时能够尽量少的影响其他几点,且尽可能的保证负载的均衡,是一个非常优秀的一致性哈希算法,Google的技术都是自带光环哈!下面想用Golang做一个简单的实现。Maglev Hashing的基本思想是为每一个节点生成一个优先填充表,列表的值就是该节点想要
背景
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
为查询表的大小。对与每一个节点 i
, permutation[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上实现该一致性哈希算法。
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网
猜你喜欢:- php如何实现session,自己实现session,laravel如何实现session
- AOP如何实现及实现原理
- webpack 实现 HMR 及其实现原理
- Docker实现原理之 - OverlayFS实现原理
- 为什么实现 .NET 的 ICollection 集合时需要实现 SyncRoot 属性?如何正确实现这个属性?
- 自己实现集合框架(十):顺序栈的实现
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
Algorithms Unlocked
Thomas H. Cormen / The MIT Press / 2013-3-1 / USD 25.00
Have you ever wondered how your GPS can find the fastest way to your destination, selecting one route from seemingly countless possibilities in mere seconds? How your credit card account number is pro......一起来看看 《Algorithms Unlocked》 这本书的介绍吧!