hrw

README

hrw

A Go implementation of Highest Random Weight hashing.

For documentation, check godoc.

Documentation

Overview

Package hrw provides an implementation of Highest Random Weight hashing, an alternative to consistent hashing which is both simple and fast.

HRW allows you to consistently select the same nodes (or sets of nodes) for a given key. When a node is removed from the set of available nodes, only the data is was responsible for is at all affected.

For more details on HRW hashing, see http://www.eecs.umich.edu/techreports/cse/96/CSE-TR-316-96.pdf or http://en.wikipedia.org/wiki/Rendezvous_hashing.

Example

// given a set of servers
servers := map[int]string{
	1: "one.example.com",
	2: "two.example.com",
	3: "three.example.com",
	4: "four.example.com",
	5: "five.example.com",
	6: "six.example.com",
}

// which can be mapped to integer values
ids := make([]int, 0, len(servers))
for id := range servers {
	ids = append(ids, id)
}

// HRW can consistently select a uniformly-distributed set of servers for
// any given key
key := []byte("/examples/object-key")
for _, id := range TopN(ids, key, 3) {
	fmt.Printf("trying GET %d %s%s\n", id, servers[id], key)
}

Output:

trying GET 1 one.example.com/examples/object-key
trying GET 3 three.example.com/examples/object-key
trying GET 5 five.example.com/examples/object-key

Index

• func SortByWeight(nodes []int, key []byte) []int
• func TopN(nodes []int, key []byte, n int) []int
• Bugs

Examples

• Package

Functions

func SortByWeight

func SortByWeight(nodes []int, key []byte) []int

SortByWeight returns the given set of nodes sorted in decreasing order of their weight for the given key.

func TopN

func TopN(nodes []int, key []byte, n int) []int

TopN returns the top N nodes in decreasing order of their weight for the given key.

Notes

Bugs

• TopN is not optimized.