hashring

Documentation

Overview

Package hashring implements a thread-safe consistent hashring with a pluggable hashing algorithm.

This package was developed for use in a gRPC balancer, but nothing precludes it from being used for any other purpose.

Index

• Variables
• type HashFunc
• type Member
• type Ring
  • func MustNew(hasher HashFunc, replicationFactor uint16) *Ring
  • func New(hashfn HashFunc, replicationFactor uint16) (*Ring, error)
  • func (h *Ring) Add(member Member) error
  • func (h *Ring) FindN(key []byte, num uint8) ([]Member, error)
  • func (h *Ring) Members() []Member
  • func (h *Ring) Remove(member Member) error

Variables

var (
	ErrMemberAlreadyExists      = errors.New("member node already exists")
	ErrMemberNotFound           = errors.New("member node not found")
	ErrNotEnoughMembers         = errors.New("not enough member nodes to satisfy request")
	ErrInvalidReplicationFactor = errors.New("replication factor must be at least 1")
	ErrVnodeNotFound            = errors.New("vnode not found")
	ErrUnexpectedVnodeCount     = errors.New("found a different number of vnodes than replication factor")
)

Types

type HashFunc

type HashFunc func([]byte) uint64

HashFunc is the signature for any hashing function that can be leveraged by the hashring.

type Member

type Member interface {
	Key() string
}

Member represents a participating member of the hashring. In most use cases, you can think of a member as a node or backend.

type Ring

type Ring struct {
	sync.RWMutex
	// contains filtered or unexported fields
}

Ring provides a thread-safe consistent hashring implementation with a configurable number of virtual nodes.

func MustNew

func MustNew(hasher HashFunc, replicationFactor uint16) *Ring

MustNew creates a new Hashring with the specified hasher function and replication factor.

If the provided replication factor is less than 1, this function will panic.

func New

func New(hashfn HashFunc, replicationFactor uint16) (*Ring, error)

New allocates a Ring with the specified hash function and replication factor.

The replication factor must be greater than 0 and ideally be at least 20 or higher for quality key distribution. At 100, the standard distribution of key->member mapping will be about 10% of the mean. At 1000, it will be about 3.2%. This value should be chosen very carefully because a higher value will require more memory and decrease member selection performance.

func (*Ring) Add

func (h *Ring) Add(member Member) error

Add inserts a member into the hashring.

If a member with the same key is already in the hashring, ErrMemberAlreadyExists is returned.

func (*Ring) FindN

func (h *Ring) FindN(key []byte, num uint8) ([]Member, error)

FindN finds the first N members after the specified key.

If there are not enough members to satisfy the request, ErrNotEnoughMembers is returned.

func (*Ring) Members

func (h *Ring) Members() []Member

Members enumerates the full set of hashring members.

func (*Ring) Remove

func (h *Ring) Remove(member Member) error

Remove finds and removes the specified member from the hashring.

If no member can be found, ErrMemberNotFound is returned.