chash

README

CHash

A lightweight library for load distribution.

Description

Combines modular hashing and consistent hashing. The algorithm distributes partitions between nodes using consistent hashing, then uses modular hashing to determine partition for key (and thus the node for key).

The algorithm limits the load on a node, which makes distribution more or less even as you can see in the table below.

Nodes	Next	Median Partitions	Min Partitions	Max Partitions	Partitions Moved
16	17	753	704	754	6.49%
17	18	708	674	709	6.42%
18	19	669	625	670	5.69%
19	20	634	595	635	5.53%
20	21	602	556	603	5.53%
...	...	...	...	...	...
66	67	182	164	183	2.22%
67	68	180	159	181	2.30%
68	69	177	159	178	2.38%
69	70	174	161	175	2.37%
70	71	172	154	173	2.05%

Documentation

Index

• Variables
• type CHash
  • func New(c Config) (CHash, error)
• type Config
  • func (c Config) Validate() (err error)
• type Hasher
• type Member

Variables

var (
	ErrMemberExists       = errors.New("member exists")
	ErrMemberNotExists    = errors.New("member not exists")
	ErrPartitionNotExists = errors.New("partition not exists")
	ErrInvalidCapacity    = errors.New("member capacity must be > 0")
)

Types

type CHash

type CHash interface {
	// AddMembers adds one or more members to the cluster
	// May return ErrInvalidCapacity if member capacity less or equal 0
	// May return ErrMemberExists if member was added before
	AddMembers(members ...Member) error
	// RemoveMembers removes members with given ids
	RemoveMembers(memberIds ...string) error
	// Reconfigure replaces all members list
	Reconfigure(members []Member) error
	// GetMembers returns list of members for given key
	// Members count will be equal replication factor or total members count (if it is less than the replication factor)
	GetMembers(key string) []Member
	// GetPartition returns partition number for given key
	GetPartition(key string) int
	// GetPartitionMembers return members by partition number
	GetPartitionMembers(partId int) ([]Member, error)
	// Distribute members by partitions
	// Must be called if you changed members' capacity
	Distribute()
	// PartitionCount returns configured partitions count
	PartitionCount() int
}

func New

func New(c Config) (CHash, error)

type Config

type Config struct {
	// Hasher implementation (optional), by default, will be used xxhash
	Hasher Hasher
	// PartitionCount - how many virtual partitions will be distributed by nodes, reasonable values from 100 to 10k
	PartitionCount uint64
	// ReplicationFactor - how many nodes expected for GetMembers
	ReplicationFactor int
	// Multiply Factor (optional) - this value multiplied for member capacity means how many times a member will be added to the hash ring. The default value is 2000.
	MultiplyFactor int
}

func (Config) Validate

func (c Config) Validate() (err error)

type Hasher

type Hasher interface {
	Sum64([]byte) uint64
}

type Member

type Member interface {
	Id() string
	Capacity() float64
}