hrw

README

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

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

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

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

	hrw.SortSliceByValue(servers, h)
	for id := range servers {
		fmt.Printf("trying GET %s%s\n", servers[id], 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
}

Documentation

Overview

Package hrw implements Rendezvous hashing. http://en.wikipedia.org/wiki/Rendezvous_hashing.

Example

// given a set of servers
servers := []string{
	"one.example.com",
	"two.example.com",
	"three.example.com",
	"four.example.com",
	"five.example.com",
	"six.example.com",
}

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

SortSliceByValue(servers, h)
for id := range servers {
	fmt.Printf("trying GET %s%s\n", servers[id], 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

Index

• Constants
• func Hash(key []byte) uint64
• func Sort(nodes []uint64, hash uint64) []uint64
• func SortByWeight(nodes []uint64, weights []float64, hash uint64) []uint64
• func SortSliceByIndex(slice interface{}, hash uint64)
• func SortSliceByValue(slice interface{}, hash uint64)
• func SortSliceByWeightIndex(slice interface{}, weights []float64, hash uint64)
• func SortSliceByWeightValue(slice interface{}, weights []float64, hash uint64)
• func ValidateWeights(weights []float64) error
• type Hasher

Examples

• Package

Constants

const (
	NormalizedMaxWeight = 1.0
	NormalizedMinWeight = 0.0
)

Boundaries of valid normalized weights

Functions

func Hash

func Hash(key []byte) uint64

Hash uses murmur3 hash to return uint64

func Sort

func Sort(nodes []uint64, hash uint64) []uint64

Sort receive nodes and hash, and sort it by distance

func SortByWeight

func SortByWeight(nodes []uint64, weights []float64, hash uint64) []uint64

SortByWeight receive nodes, weights and hash, and sort it by distance * weight

func SortSliceByIndex

func SortSliceByIndex(slice interface{}, hash uint64)

SortSliceByIndex received []T and hash to sort by index-distance

func SortSliceByValue

func SortSliceByValue(slice interface{}, hash uint64)

SortSliceByValue received []T and hash to sort by value-distance

func SortSliceByWeightIndex

func SortSliceByWeightIndex(slice interface{}, weights []float64, hash uint64)

SortSliceByWeightIndex received []T, weights and hash to sort by index-distance * weights

func SortSliceByWeightValue

func SortSliceByWeightValue(slice interface{}, weights []float64, hash uint64)

SortSliceByWeightValue received []T, weights and hash to sort by value-distance * weights

func ValidateWeights

func ValidateWeights(weights []float64) error

ValidateWeights checks if weights are normalized between 0.0 and 1.0

Types

type Hasher

type Hasher interface{ Hash() uint64 }

Hasher interface used by SortSliceByValue