rendezvous

README

go-rendezvous

This package provides a simplistic implementation of Rendezvous Hashing with a pluggable hash.Hash function.

From Wikipedia:

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.

Rendezvous Hashing is simple in principle, but wide-reaching in application.

For example, to determine ownership of an item:

h := rendezvous.NewHasher(
    rendezvous.WithMembers("node1", "node2", "node3", "node4", "node5"),
)

fmt.Printf("The owner of item is %s\n", h.Owner("item"))
// Output: The owner of item is node3

Or to fairly place replicas of a file in a storage cluster:

h := rendezvous.NewHasher(
    rendezvous.WithMembers("node1", "node2", "node3", "node4", "node5"),
)

fmt.Printf("the nodes to replicate data to are: %v\n", h.Place("item", 3))
// Output: the nodes to replicate data to are: [node3 node5 node1]

Or maybe to implement a priority list:

h := rendezvous.NewHasher(
    rendezvous.WithMembers("node1", "node2", "node3", "node4", "node5"),
)

fmt.Printf("priority list: %v\n", h.Prioritise("item"))
// Output: priority list: [node3 node5 node1 node2 node4]

Documentation

Index

• type Hasher
  • func NewHasher(opts ...HasherOption) *Hasher
  • func (h *Hasher) AddMembers(members ...string)
  • func (h *Hasher) Members() []string
  • func (h *Hasher) Owner(key string) string
  • func (h *Hasher) Place(key string, n int) []string
  • func (h *Hasher) Prioritise(key string) []string
  • func (h *Hasher) RemoveMembers(members ...string)
  • func (h *Hasher) SetMembers(members ...string)
• type HasherOption
  • func WithHashImplementation(h hash.Hash) HasherOption
  • func WithMembers(members ...string) HasherOption
  • func WithSortOrder(order SortOrder) HasherOption
• type SortOrder

Examples

• Hasher (Ownership)
• Hasher (PriorityList)
• Hasher (Replication)

Types

type Hasher

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

Example (Ownership)

h := rendezvous.NewHasher(
	rendezvous.WithMembers("node1", "node2", "node3", "node4", "node5"),
)

fmt.Printf("The owner of item is %s\n", h.Owner("item"))

Output:

The owner of item is node3

Example (PriorityList)

h := rendezvous.NewHasher(
	rendezvous.WithMembers("node1", "node2", "node3", "node4", "node5"),
)

fmt.Printf("priority list: %v\n", h.Prioritise("item"))

Output:

priority list: [node3 node5 node1 node2 node4]

Example (Replication)

h := rendezvous.NewHasher(
	rendezvous.WithMembers("node1", "node2", "node3", "node4", "node5"),
)

fmt.Printf("the nodes to replicate data to are: %v\n", h.Place("item", 3))

Output:

the nodes to replicate data to are: [node3 node5 node1]

func NewHasher

func NewHasher(opts ...HasherOption) *Hasher

func (*Hasher) AddMembers

func (h *Hasher) AddMembers(members ...string)

AddMembers adds the given members to the member list

func (*Hasher) Members

func (h *Hasher) Members() []string

Member returns the current member list

func (*Hasher) Owner

func (h *Hasher) Owner(key string) string

Owner returns the best member for the given key sorted by their rendezvous hash value.

func (*Hasher) Place

func (h *Hasher) Place(key string, n int) []string

Place returns the top n members for the given key sorted by their rendezvous hash value.

func (*Hasher) Prioritise

func (h *Hasher) Prioritise(key string) []string

PriorityList returns all the placement members sorted by their rendezvous hash value for the given key.

func (*Hasher) RemoveMembers

func (h *Hasher) RemoveMembers(members ...string)

RemoveMembers removes the given members from the member list

func (*Hasher) SetMembers

func (h *Hasher) SetMembers(members ...string)

SetMembers replaces the current member list with the members provided

type HasherOption

type HasherOption func(*Hasher)

func WithHashImplementation

func WithHashImplementation(h hash.Hash) HasherOption

func WithMembers

func WithMembers(members ...string) HasherOption

func WithSortOrder

func WithSortOrder(order SortOrder) HasherOption

type SortOrder

type SortOrder bool

const (
	LowestFirst  SortOrder = true
	HighestFirst SortOrder = false
)