Google Maglev 一致性 hash 算法

maglev-hashing.go

package main

import (
	"fmt"
	"hash/crc32"
	"strconv"
)

type table struct {
	next        []int // track the next index in permutation to be condidered for backend i
	entry       []int // stores the final lookup table
	permutation [][]int
}

func newTable(n, m int) *table {
	next := make([]int, n)
	entry := make([]int, m)

	for i := 0; i < n; i++ {
		next[i] = 0
	}
	for j := 0; j < m; j++ {
		entry[j] = -1
	}

	permutation := make([][]int, n)
	for i := 0; i < n; i++ {
		permutation[i] = make([]int, m)
	}

	// 初始化 permutation 随机排列表格
	for i := 0; i < n; i++ {
		name := "backend" + strconv.Itoa(i)
		offset := hash1([]byte(name)) % uint32(m)
		skip := hash2([]byte(name))%uint32(m-1) + 1

		for j := 0; j < m; j++ {
			permutation[i][j] = (int(offset) + j*int(skip)) % m
		}
	}
	return &table{next, entry, permutation}
}

func (t *table) populate() {

	N := len(t.next)
	M := len(t.entry)

	n := 0
	for {
		for i := 0; i < N; i++ {
			c := t.permutation[i][t.next[i]]
			for t.entry[c] >= 0 { // 一直找到一个 t.entry[c] < 0 才退出
				t.next[i] += 1
				c = t.permutation[i][t.next[i]]
			}
			t.entry[c] = i
			t.next[i] += 1
			n++
			if n == M {
				return
			}
		}
	}
}

func hash1(data []byte) uint32 {
	return crc32.Checksum(data, crc32.IEEETable)
}

func hash2(data []byte) uint32 {
	return crc32.Checksum(data, crc32.MakeTable(0xeab84321))
}

func main() {
	t := newTable(3, 7)
	t.populate()

	fmt.Println("next[]:", t.next)
	fmt.Println("entry[]:", t.entry)
	fmt.Println("permutation[][]:", t.permutation)
}