Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Maglev for redis
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
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.