JumpConsistentHash

hash_test.go

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)
}