内容简介: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 属性?如何正确实现这个属性?
- 自己实现集合框架(十):顺序栈的实现
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
HTML 编码/解码
HTML 编码/解码
RGB CMYK 转换工具
RGB CMYK 互转工具