背景
Maglev是Google開(kāi)發(fā)的基于kernal bypass技術(shù)實(shí)現(xiàn)的4層負(fù)載均衡，它具有非常強(qiáng)大的負(fù)載性能，承載了Google絕大部分接入流量。Maglev在負(fù)載均衡算法上采用自行開(kāi)發(fā)的一致性哈希算法被稱(chēng)為Maglev Hashing，該哈希算法在節(jié)點(diǎn)變化時(shí)能夠盡量少的影響其他幾點(diǎn)，且盡可能的保證負(fù)載的均衡，是一個(gè)非常優(yōu)秀的一致性哈希算法，Google的技術(shù)都是自帶光環(huán)哈！下面想用Golang做一個(gè)簡(jiǎn)單的實(shí)現(xiàn)。
原理說(shuō)明
Maglev Hashing的基本思想是為每一個(gè)節(jié)點(diǎn)生成一個(gè)優(yōu)先填充表，列表的值就是該節(jié)點(diǎn)想要填充查詢(xún)表的位置.
如Table1所示，節(jié)點(diǎn)B0，會(huì)按照順序3，0，4，...依次去嘗試填充查詢(xún)表。實(shí)際上，所有的節(jié)點(diǎn)會(huì)輪流按照各自?xún)?yōu)先列表的值填充查詢(xún)表。也就是說(shuō)，每個(gè)節(jié)點(diǎn)都有幾乎均等的機(jī)會(huì)根據(jù)優(yōu)先表來(lái)填充查詢(xún)表，直到查詢(xún)表被填滿(mǎn)。
當(dāng)出現(xiàn)節(jié)點(diǎn)變化，如B1宕機(jī)時(shí)，查詢(xún)表會(huì)重新生成，因?yàn)楣?jié)點(diǎn)的優(yōu)先填充表不變，所以B0和B2原來(lái)的填充位置不變，B1宕機(jī)后確實(shí)的位置被B0和B2瓜分，按照輪流填充的機(jī)制，B0和B2基本也是均衡的。
算法實(shí)現(xiàn)
設(shè)M為查詢(xún)表的大小。對(duì)與每一個(gè)節(jié)點(diǎn)i，permutation[i]為優(yōu)先填充表，permutation[i]的取值是數(shù)組[0, M-1]的一個(gè)隨機(jī)順序排列，permutation是一個(gè)二維數(shù)組。
下面介紹論文給出的高效生成permutation[i]的方法:
首先使用兩種哈希函數(shù)來(lái)哈希節(jié)點(diǎn)生成兩個(gè)數(shù)字，offset skip. 論文中是計(jì)算節(jié)點(diǎn)名稱(chēng)的哈希值，為了簡(jiǎn)單我就直接計(jì)算了節(jié)點(diǎn)的索引值，哈希函數(shù)我用的是算法導(dǎo)論里提到的乘法散列法，代碼如下：
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)))
}
第二個(gè)哈希函數(shù)我只是修改了一個(gè)參數(shù)值，哈希算法是一樣的。offset skip計(jì)算方式如下：
offset←h1(name[i]) mod M
skip←h2(name[i]) mod (M?1)+1
從而得到permutation[i]中每一個(gè)值的計(jì)算方式：
permutation[ i ][ j ]←(offset+ j×skip) mod M 0<=j<= M-1
這里要注意的是M必須為質(zhì)數(shù)，這樣才能盡可能保證skip與M互斥。尋找合適的質(zhì)數(shù)M我使用了簡(jiǎn)單的篩選算法：
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的質(zhì)數(shù)
for {
if isPrime(n) {
return n
}
n++
}
}
上面介紹了一些輔助函數(shù)，下面介紹算法的具體實(shí)現(xià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,
}
}
定義一個(gè)結(jié)構(gòu)MaglevHash和結(jié)構(gòu)體生成函數(shù)，golang的標(biāo)準(zhǔn)實(shí)現(xiàn)。其中permutation為一個(gè)N*M的二維數(shù)組，entry為長(zhǎng)度N的查詢(xún)表，nodeState為長(zhǎng)度N的記錄節(jié)點(diǎn)時(shí)候的下線(xiàn)的表。
接下來(lái)是生成permutation的函數(shù)，計(jì)算節(jié)點(diǎn)時(shí)實(shí)際上傳入的是節(jié)點(diǎn)索引值加一，避免傳入0，影響哈希值的計(jì)算：
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
}
}
}
生成好節(jié)點(diǎn)優(yōu)先填充表之后，就可以根據(jù)該表填充查詢(xún)表：
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
}
}
}
}
在填充查詢(xún)表時(shí)，會(huì)檢查節(jié)點(diǎn)是否下線(xiàn)，若節(jié)點(diǎn)下線(xiàn)，則會(huì)忽略該節(jié)點(diǎn)。
func (mh *MaglevHash) DownNode(idx int) error {
if idx > mh.n-1 {
return errors.New("invalid idx")
}
mh.nodeState[idx] = false
return nil
}
節(jié)點(diǎn)下線(xiàn)時(shí)，需要調(diào)用該函數(shù)，然后再調(diào)用Populate()重新填充查詢(xún)表。
至此，Maglev hashing 一個(gè)簡(jiǎn)單的實(shí)現(xiàn)就算完成了，后續(xù)希望使用生產(chǎn)環(huán)境的哈希函數(shù)來(lái)替換本文用到哈希函數(shù)，并考慮在nginx上實(shí)現(xiàn)該一致性哈希算法。
