Some configs have buckets with 0 hits

[vmihailenco]

E.g. following program

package main

import (
	"log"
	"strconv"

	"github.com/dgryski/go-maglev"
)

func main() {
	names := make([]string, 32)
	for i := range names {
		names[i] = strconv.Itoa(i)
	}

	counts := make([]int, len(names))

	table := maglev.New(names, maglev.SmallM)
	for i := 0; i < 10000; i++ {
		idx := table.Lookup(uint64(i))
		counts[idx]++
	}

	log.Println(counts)
}

produces [322 317 315 0 310 333 328 324 319 323 328 319 326 307 312 325 328 330 314 334 335 317 318 342 330 333 333 302 352 299 308 317] - 4th bucket has zero hits.

If I change 10000 iterations to 100k iterations - distribution is balanced again - so it is not too bad/wrong.

[vmihailenco]

What I am trying to achieve is to consistently distribute 1024 Postgres shards/schemas to 32 physical servers - such sharding scheme is described at https://instagram-engineering.com/sharding-ids-at-instagram-1cf5a71e5a5c. So I have low constant number of keys/shards (1024) and constantly growing number of servers (from 1 to ~100).

This is the program that uses maglev and jump hashes:

package main

import (
	"fmt"
	"strconv"
	"unsafe"

	"github.com/dgryski/go-farm"
	"github.com/dgryski/go-jump"
	"github.com/dgryski/go-maglev"
)

const (
	numServer = 32
	numShard  = 1024
)

var servers = make([]string, numServer)

func main() {
	for i := range servers {
		servers[i] = strconv.Itoa(i)
	}

	maglevRaw()
	maglevHash()
	jumpRaw()
	jumpHash()
}

func maglevRaw() {
	counts := make([]int, len(servers))

	table := maglev.New(servers, maglev.BigM)
	for i := 0; i < numShard; i++ {
		idx := table.Lookup(uint64(i))
		counts[idx]++
	}

	fmt.Println("maglev raw", counts)
}

func maglevHash() {
	counts := make([]int, len(servers))

	table := maglev.New(servers, maglev.BigM)
	for i := 0; i < numShard; i++ {
		idx := table.Lookup(hash(i))
		counts[idx]++
	}

	fmt.Println("maglev hash", counts)
}

func jumpRaw() {
	counts := make([]int, len(servers))

	for i := 0; i < numShard; i++ {
		idx := jump.Hash(uint64(i), len(servers))
		counts[idx]++
	}

	fmt.Println("jump raw", counts)
}

func jumpHash() {
	counts := make([]int, len(servers))

	for i := 0; i < numShard; i++ {
		idx := jump.Hash(hash(i), len(servers))
		counts[idx]++
	}

	fmt.Println("jump hash", counts)
}

func hash(i int) uint64 {
	// Hash 2 significant bytes to "improve" the result.
	ptr := unsafe.Pointer(&i)
	b := (*[2]byte)(ptr)
	return farm.Hash64((*b)[:])
}

Which produces the following result

maglev raw [39 35 12 36 36 32 31 34 29 27 33 29 31 32 34 40 34 26 28 34 32 34 36 36 18 33 40 37 31 29 31 35]
maglev hash [32 20 29 41 31 33 32 23 31 33 47 28 30 32 29 33 35 32 27 31 25 25 31 40 41 33 30 42 33 29 30 36]
jump raw [33 32 33 34 32 27 33 34 37 27 44 29 42 28 28 15 41 30 35 38 29 42 29 22 32 40 27 42 22 25 28 34]
jump hash [37 26 27 32 28 37 26 38 33 21 23 31 29 38 32 39 34 36 28 32 28 37 27 31 38 25 34 25 38 37 33 44]

So in case for maglev the best result is min=20 max=47 - there will be a server with 20 shards and a server with 47 shards. Best result for jump is min=21 max=44.

@dgryski do you have any ideas how to achieve a better result? I've tried different hashes (xxhash and wyhash) but without much luck. rendezvous and multi-probe consistent hashing are even worse...

[dgryski]

I'd be curious to see if other maglev implementations have the same problem. I.e., is it a bug in my code or more fundamental issue with the algorithm.

[dgryski]

I just did a little bit of testing, and I think you're encountering a terrible edge case with the interaction between the siphash code, the maglev code, and your choice of server names. If your server names are not just the integer values, but almost anything else (including "a" + strconv.Itoa(i)), or if you change the seed maglev passes to siphash, (0xdeadbeefcafebabe), then all your shards have a much more equal number of items.

Also, I'm not sure if mapping 1024 shards to 32 servers is enough "keys" (shards, in this case) for the statistics to even out.

[vmihailenco]

Yeah, that is my thinking as well. I hoped that I am doing something wrong or there is some hash method that can fix it all. But given that I have static set of keys I probably don't need maglev or jump hash at all. Thanks for the reply.