hrw

package module
v0.0.0-...-d4f22a6 Latest Latest
Warning

This package is not in the latest version of its module.

Go to latest
Published: Jul 2, 2014 License: MIT Imports: 2 Imported by: 0

README

hrw

Build Status

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

Examples

Constants

This section is empty.

Variables

This section is empty.

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.

Types

This section is empty.

Notes

Bugs

  • TopN is not optimized.

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL