consistentHash

README

consistentHash

consistentHash provides a consistent hashing implementation using murmur3 with a 64bit ring space. Virtual nodes are used to provide a good distribution.

This package has an almost identical API to StatHat's consistent package at https://github.com/stathat/consistent , that packages uses a crc32 hash and a smaller number of vnodes by default.

See:
http://en.wikipedia.org/wiki/Consistent_hashing
http://en.wikipedia.org/wiki/MurmurHash

The only time an error will be returned from a Get(), Get2(), or GetN() call is if there are not enough members added.

Basic Example:

  ch := consistentHash.New()  
  ch.Add("server1")  
  ch.Add("server2")  
  ch.Add("server3")
  for _,key := range []string{"A","B","C","D","E","F","G"} {
	   server,_ := ch.Get([]byte(key)
	   fmt.Println("key=%s server=%s\n",key,server)
  }

Outputs:
key=A server=server3
key=B server=server3
key=C server=server1
key=D server=server3
key=E server=server2
key=F server=server2
key=G server=server1

Example with 3 servers and then removing a member:

    ch := consistentHash.New()
	ch.Add("server1")
	ch.Add("server2")
	ch.Add("server3")
	keys := []string{"A", "B", "C", "D", "E", "F", "G"}
	fmt.Println("3 servers")
	for _, key := range keys {
		server, _ := ch.Get([]byte(key))
		fmt.Printf("key=%s server=%s\n", key, server)
	}
	fmt.Println("Removing server3")
	ch.Remove("server3")
	for _, key := range keys {
		server, _ := ch.Get([]byte(key))
		fmt.Printf("key=%s server=%s\n", key, server)
	}

Output:
3 servers
key=A server=server3
key=B server=server3
key=C server=server1
key=D server=server3
key=E server=server2
key=F server=server2
key=G server=server1
Removing server3
key=A server=server1  // remapped from 3->1
key=B server=server2  // remapped from 3->2
key=C server=server1  // stayed in same location
key=D server=server1  // remapped from 3->1
key=E server=server2  // stayed in same location
key=F server=server2  // stayed in same location
key=G server=server1  // stayed in same location

Documentation

Overview

Package consistentHash implements a consistent hashing algorithm

Index

• Constants
• Variables
• type ConsistentHash
  • func New() *ConsistentHash
  • func (ch *ConsistentHash) Add(address string)
  • func (ch *ConsistentHash) Get(key []byte) (string, error)
  • func (ch *ConsistentHash) Get2(key []byte) (string, string, error)
  • func (ch *ConsistentHash) GetN(key []byte, count int) ([]string, error)
  • func (ch *ConsistentHash) Remove(address string)
  • func (ch *ConsistentHash) SetVnodeCount(count int) error

Constants

const (
	// DefaultVnodeCount is a tradeoff of memory and ~ log(N) speed versus how well the hash spreads
	DefaultVnodeCount = 200
)

Variables

var (
	// ErrNoMembers occurs when trying to hash before any members are added
	ErrNoMembers = errors.New("no members added")
	// ErrNotEnoughMembers occurs when more members are asked for than are available
	ErrNotEnoughMembers = errors.New("not enough members")
	// ErrNotAvailableOnceMembersAdded occurs if any attempt is made to modify the vnode account once members are added
	ErrNotAvailableOnceMembersAdded = errors.New("not available once members are added")
	// ErrInvalidVnodeCount occurs if the vnode count is set to 0 or lower
	ErrInvalidVnodeCount = errors.New("vnodeCount must be > 0")
)

Types

type ConsistentHash

type ConsistentHash struct {
	// contains filtered or unexported fields
}

ConsistentHash holds the internal data structures for the hashing

func New

func New() *ConsistentHash

New creates a new consistentHash pointer and initializes all the necessary fields

func (*ConsistentHash) Add

func (ch *ConsistentHash) Add(address string)

Add adds a server to the consistentHash

func (*ConsistentHash) Get

func (ch *ConsistentHash) Get(key []byte) (string, error)

Get finds the closest member for a given key

func (*ConsistentHash) Get2

func (ch *ConsistentHash) Get2(key []byte) (string, string, error)

Get2 finds the closest 2 members for a given key and is just a helper function calling into GetN

func (*ConsistentHash) GetN

func (ch *ConsistentHash) GetN(key []byte, count int) ([]string, error)

GetN finds the closest N members for a given key

func (*ConsistentHash) Remove

func (ch *ConsistentHash) Remove(address string)

Remove removes a server from the consistentHash

func (*ConsistentHash) SetVnodeCount

func (ch *ConsistentHash) SetVnodeCount(count int) error

SetVnodeCount sets the number of vnodes that will be added for every server This must be called before any Add() calls