Maglev for redis

maglev.go

package main

const TableSize = uint16(1 << 14)

type Table []uint16

type Shard struct {
	Hash   uint64
	Weight float64
}

type shardGen struct {
	start uint16
	pos   uint16
	add   uint16
	mult  uint16
	w     float64
	sh    *Shard
}

func BuildTable(shards []Shard, sliceSize uint16) Table {
	table := make(Table, TableSize)

	averageWeight := 0.0
	generators := make([]shardGen, 0, len(shards))
	for i, sh := range shards {
		gen := shardGen{
			start: uint16(sh.Hash>>48) &^ (sliceSize - 1),
			pos:   0,
			add:   (uint16(sh.Hash>>32) | 1) * sliceSize,
			mult:  uint16(sh.Hash>>16)&^3 | 1,
			w:     0,
			sh:    &shards[i],
		}
		generators = append(generators, gen)
		averageWeight += sh.Weight
	}
	averageWeight /= float64(len(shards))

	rest := TableSize

	for i := uint16(0); rest > 0; i++ {
		shn := i % uint16(len(generators))
		sh := &generators[shn]
		sh.w += sh.sh.Weight
		for sh.w > averageWeight && rest > 0 {
			cur := (sh.start + sh.pos) % TableSize
			if table[cur] == 0 {
				for k := uint16(0); k < sliceSize; k++ {
					table[cur+k] = shn + 1
				}
				rest -= sliceSize
				sh.w -= averageWeight
			}
			sh.pos = sh.pos*sh.mult + sh.add
		}
	}

	for i := range table {
		table[i]--
	}

	return table
}