hrw

Golang HRW implementation

Rendezvous or highest random weight (HRW) hashing is an algorithm that allows clients to achieve distributed agreement on a set of k options out of a possible set of n options. A typical application is when clients need to agree on which sites (or proxies) objects are assigned to. When k is 1, it subsumes the goals of consistent hashing, using an entirely different method.

Install

go get github.com/nspcc-dev/hrw/v2

Benchmark:

BenchmarkSort_fnv_10-8                           5000000               365 ns/op             224 B/op          3 allocs/op
BenchmarkSort_fnv_100-8                           300000              5261 ns/op            1856 B/op          3 allocs/op
BenchmarkSort_fnv_1000-8                           10000            119462 ns/op           16448 B/op          3 allocs/op
BenchmarkSortByIndex_fnv_10-8                    3000000               546 ns/op             384 B/op          7 allocs/op
BenchmarkSortByIndex_fnv_100-8                    200000              5965 ns/op            2928 B/op          7 allocs/op
BenchmarkSortByIndex_fnv_1000-8                    10000            127732 ns/op           25728 B/op          7 allocs/op
BenchmarkSortByValue_fnv_10-8                    2000000               962 ns/op             544 B/op         17 allocs/op
BenchmarkSortByValue_fnv_100-8                    200000              9604 ns/op            4528 B/op        107 allocs/op
BenchmarkSortByValue_fnv_1000-8                    10000            111741 ns/op           41728 B/op       1007 allocs/op

BenchmarkSortByWeight_fnv_10-8                   3000000               501 ns/op             320 B/op          4 allocs/op
BenchmarkSortByWeight_fnv_100-8                   200000              8495 ns/op            2768 B/op          4 allocs/op
BenchmarkSortByWeight_fnv_1000-8                   10000            197880 ns/op           24656 B/op          4 allocs/op
BenchmarkSortByWeightIndex_fnv_10-8              2000000               702 ns/op             480 B/op          8 allocs/op
BenchmarkSortByWeightIndex_fnv_100-8              200000              9338 ns/op            3840 B/op          8 allocs/op
BenchmarkSortByWeightIndex_fnv_1000-8              10000            204669 ns/op           33936 B/op          8 allocs/op
BenchmarkSortByWeightValue_fnv_10-8              1000000              1083 ns/op             640 B/op         18 allocs/op
BenchmarkSortByWeightValue_fnv_100-8              200000             11444 ns/op            5440 B/op        108 allocs/op
BenchmarkSortByWeightValue_fnv_1000-8              10000            148471 ns/op           49936 B/op       1008 allocs/op

Example

package main

import (
	"fmt"
	
	"github.com/nspcc-dev/hrw/v2"
)

type hashString string

func (h hashString) Hash() uint64 {
	return hrw.WrapBytes([]byte(h)).Hash()
}

func main() {
	// given a set of servers
	servers := []hrw.Hashable{
		hashString("one.example.com"),
		hashString("two.example.com"),
		hashString("three.example.com"),
		hashString("four.example.com"),
		hashString("five.example.com"),
		hashString("six.example.com"),
	}

	// HRW can consistently select a uniformly-distributed set of servers for
	// any given key
	var key = []byte("/examples/object-key")

	hrw.Sort(servers, hrw.WrapBytes(key))
	for id := range servers {
		fmt.Printf("trying GET %s%s\n", servers[id], string(key))
	}

	// Output:
	// trying GET three.example.com/examples/object-key
	// trying GET two.example.com/examples/object-key
	// trying GET five.example.com/examples/object-key
	// trying GET six.example.com/examples/object-key
	// trying GET one.example.com/examples/object-key
	// trying GET four.example.com/examples/object-key
}