Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
JumpConsistentHash
package main
import "fmt"
type hash_function func (uint64, int32) int32
func main() {
for j := 1; j < 32; j++ {
simulate_rebalance("JumpConsistentHash", 32, int32(32 + j), JumpConsistentHash)
simulate_rebalance("ModConsistentHash", 32, int32(32 + j), ModConsistentHash)
}
}
func simulate_rebalance(name string, buckets, rebalanced_buckets int32, hash_func hash_function) {
store1 := make(map[int32]uint64, buckets)
store2 := make(map[int32]uint64, rebalanced_buckets)
moves := 0
for i := 0; i < (1<<16); i++ {
b1 := hash_func(uint64(i), buckets)
if _, exists := store1[b1]; !exists {
store1[b1] = 0
}
store1[b1]++
b2 := hash_func(uint64(i), rebalanced_buckets)
if _, exists := store2[b2]; !exists {
store2[b2] = 0
}
store2[b2]++
if b1 != b2 {
moves++
}
}
fmt.Printf("%v,%v,%v,%v\n", name, buckets, rebalanced_buckets, moves)
}
func ModConsistentHash(key uint64, num_buckets int32) int32 {
return int32(key % uint64(num_buckets))
}
func JumpConsistentHash(key uint64, num_buckets int32) int32 {
var b, j int64
b = -1
j = 0
top := float64(1<<31)
for j < int64(num_buckets) {
b = j
key = (key * 2862933555777941757) + 1
j = (b + 1) * int64(top / float64((key>>33) + 1))
}
return int32(b)
}
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.