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:

BenchmarkSortByWeight_fnv_10-8     	 3000000	       435 ns/op	     224 B/op	       3 allocs/op
BenchmarkSortByWeight_fnv_100-8    	  200000	      7238 ns/op	    1856 B/op	       3 allocs/op
BenchmarkSortByWeight_fnv_1000-8   	   10000	    163158 ns/op	   16448 B/op	       3 allocs/op
BenchmarkSortByIndex_fnv_10-8      	 2000000	       642 ns/op	     384 B/op	       7 allocs/op
BenchmarkSortByIndex_fnv_100-8     	  200000	      8045 ns/op	    2928 B/op	       7 allocs/op
BenchmarkSortByIndex_fnv_1000-8    	   10000	    227527 ns/op	   25728 B/op	       7 allocs/op
BenchmarkSortByValue_fnv_10-8      	 1000000	      1244 ns/op	     544 B/op	      17 allocs/op
BenchmarkSortByValue_fnv_100-8     	  100000	     12397 ns/op	    4528 B/op	     107 allocs/op
BenchmarkSortByValue_fnv_1000-8    	   10000	    154278 ns/op	   41728 B/op	    1007 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 four.example.com/examples/object-key
	// trying GET three.example.com/examples/object-key
	// trying GET one.example.com/examples/object-key
	// trying GET two.example.com/examples/object-key
	// trying GET six.example.com/examples/object-key
	// trying GET five.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 four.example.com/examples/object-key
trying GET three.example.com/examples/object-key
trying GET one.example.com/examples/object-key
trying GET two.example.com/examples/object-key
trying GET six.example.com/examples/object-key
trying GET five.example.com/examples/object-key

Index

• func Hash(key []byte) uint64
• func SortByWeight(nodes []uint64, hash uint64) []uint64
• func SortSliceByIndex(slice interface{}, hash uint64)
• func SortSliceByValue(slice interface{}, hash uint64)
• type Hasher

Examples

• Package

Functions

func Hash

func Hash(key []byte) uint64

Hash uses murmur3 hash to return uint64

func SortByWeight

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

SortByWeight receive nodes and hash, and sort it by weight

func SortSliceByIndex

func SortSliceByIndex(slice interface{}, hash uint64)

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

func SortSliceByValue

func SortSliceByValue(slice interface{}, hash uint64)

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

Types

type Hasher

type Hasher interface{ Hash() uint64 }

Hasher interface used by SortSliceByValue