consistenthash

Documentation

Overview

Package consistenthash contains helpers for mapping items to buckets using consistent hashing.

Methods (AddBucket, Assignment etc.) typically run in `log2(N*M)` time where N is the number of buckets and M is the number of virtual replicas in use (which defaults to 16). This is strictly worse than a typical map, but avoids space issues with tracking item assignments individually.

The default hash function is `crc64.ChecksumIEEE` but that can be customized. The default hash function is seeded with a constant polynomial so that assignments are stable between process starts.

A `*consistenthash.ConsistentHash` reference (the result of `New(...)`) is safe to use from multiple goroutines and will use a read/write mutex to synchronize changes to internal state.

Example usage:

    ch := consistenthash.New(
		consistenthash.OptBuckets("worker-0", "worker-1", "worker-2"),
	)
	// figure out which bucket an item maps to
	worker := ch.Assignment("item-0") // will yield `worker-0` or `worker-1` etc.

You can tune the number of virtual replicas to reduce the constant time hit of most operations at the expense of bucket to item mapping uniformity.

Example setting the replicas:

    ch := consistenthash.New(
		consistenthash.OptBuckets("worker-0", "worker-1", "worker-2"),
		consistenthash.OptReplicas(5),
	)
	// figure out which bucket an item maps to
	worker := ch.Assignment("item-0") // will yield `worker-0` or `worker-1` etc.

Index

• Constants
• func StableHash(data []byte) uint64
• type ConsistentHash
  • func New(opts ...Option) *ConsistentHash
  • func (ch *ConsistentHash) AddBuckets(newBuckets ...string) (ok bool)
  • func (ch *ConsistentHash) Assignment(item string) (bucket string)
  • func (ch *ConsistentHash) Assignments(items ...string) map[string][]string
  • func (ch *ConsistentHash) Buckets() (buckets []string)
  • func (ch *ConsistentHash) HashFunctionOrDefault() HashFunction
  • func (ch *ConsistentHash) IsAssigned(bucket, item string) (ok bool)
  • func (ch *ConsistentHash) MarshalJSON() ([]byte, error)
  • func (ch *ConsistentHash) RemoveBucket(toRemove string) (ok bool)
  • func (ch *ConsistentHash) ReplicasOrDefault() int
  • func (ch *ConsistentHash) String() string
• type HashFunction
• type HashedBucket
  • func InsertionSort(ring []HashedBucket, item HashedBucket) []HashedBucket
• type Option
  • func OptBuckets(buckets ...string) Option
  • func OptHashFunction(hashFunction HashFunction) Option
  • func OptReplicas(replicas int) Option

Constants

const (
	// DefaultReplicas is the default number of bucket virtual replicas.
	DefaultReplicas = 16
)

Functions

func StableHash

func StableHash(data []byte) uint64

StableHash implements the default hash function with a stable crc64 table checksum.

Types

type ConsistentHash

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

ConsistentHash creates hashed assignments for each bucket.

func New

func New(opts ...Option) *ConsistentHash

New returns a new consistent hash.

func (*ConsistentHash) AddBuckets

func (ch *ConsistentHash) AddBuckets(newBuckets ...string) (ok bool)

AddBuckets adds a list of buckets to the consistent hash, and returns a boolean indiciating if _any_ buckets were added.

If any of the new buckets do not exist on the hash ring the new bucket will be inserted `ReplicasOrDefault` number of times into the internal hashring.

If any of the new buckets already exist on the hash ring no action is taken for that bucket.

Calling `AddBuckets` is safe to do concurrently and acquires a write lock on the consistent hash reference.

func (*ConsistentHash) Assignment

func (ch *ConsistentHash) Assignment(item string) (bucket string)

Assignment returns the bucket assignment for a given item.

Calling `Assignment` is safe to do concurrently and acquires a read lock on the consistent hash reference.

func (*ConsistentHash) Assignments

func (ch *ConsistentHash) Assignments(items ...string) map[string][]string

Assignments returns the assignments for a given list of items organized by the name of the bucket, and an array of the assigned items.

Calling `Assignments` is safe to do concurrently and acquires a read lock on the consistent hash reference.

func (*ConsistentHash) Buckets

func (ch *ConsistentHash) Buckets() (buckets []string)

Buckets returns the buckets.

Calling `Buckets` is safe to do concurrently and acquires a read lock on the consistent hash reference.

func (*ConsistentHash) HashFunctionOrDefault

func (ch *ConsistentHash) HashFunctionOrDefault() HashFunction

HashFunctionOrDefault returns the provided hash function or a default.

func (*ConsistentHash) IsAssigned

func (ch *ConsistentHash) IsAssigned(bucket, item string) (ok bool)

IsAssigned returns if a given bucket is assigned a given item.

Calling `IsAssigned` is safe to do concurrently and acquires a read lock on the consistent hash reference.

func (*ConsistentHash) MarshalJSON

func (ch *ConsistentHash) MarshalJSON() ([]byte, error)

MarshalJSON marshals the consistent hash as json.

The form of the returned json is the underlying []HashedBucket and there is no corresponding `UnmarshalJSON` because it is uncertain on the other end what the hashfunction is because functions can't be json serialized.

You should use MarshalJSON for communicating information for debugging purposes only.

Calling `MarshalJSON` is safe to do concurrently and acquires a read lock on the consistent hash reference.

func (*ConsistentHash) RemoveBucket

func (ch *ConsistentHash) RemoveBucket(toRemove string) (ok bool)

RemoveBucket removes a bucket from the consistent hash, and returns a boolean indicating if the provided bucket was found.

If the bucket exists on the hash ring, the bucket and its replicas are removed.

If the bucket does not exist on the ring, no action is taken.

Calling `RemoveBucket` is safe to do concurrently and acquires a write lock on the consistent hash reference.

func (*ConsistentHash) ReplicasOrDefault

func (ch *ConsistentHash) ReplicasOrDefault() int

ReplicasOrDefault is the default number of bucket virtual replicas.

func (*ConsistentHash) String

func (ch *ConsistentHash) String() string

String returns a string form of the hash for debugging purposes.

Calling `String` is safe to do concurrently and acquires a read lock on the consistent hash reference.

type HashFunction

type HashFunction func([]byte) uint64

HashFunction is a function that can be used to hash items.

type HashedBucket

type HashedBucket struct {
	Hashcode uint64 `json:"hashcode"`
	Bucket   string `json:"bucket"`
	Replica  int    `json:"replica"`
}

HashedBucket is a bucket in the hashring that holds the hashcode, the bucket name (as Bucket) and the virtual replica index.

func InsertionSort

func InsertionSort(ring []HashedBucket, item HashedBucket) []HashedBucket

InsertionSort inserts an bucket into a hashring by binary searching for the index which would satisfy the overall "sorted" status of the ring returning the updated hashring.

type Option

type Option func(*ConsistentHash)

Option mutates a consistent hash.

func OptBuckets

func OptBuckets(buckets ...string) Option

OptBuckets adds buckets to the consistent hash.

It is functionally equiavalent to looping over the buckets and calling `AddBuckets(bucketsj...)` for it.

func OptHashFunction

func OptHashFunction(hashFunction HashFunction) Option

OptHashFunction sets the hash function.

The default hash function is `consistenthash.StableHash` which uses a stable crc64 hash function to preserve ordering between process restarts.

func OptReplicas

func OptReplicas(replicas int) Option

OptReplicas sets the bucket virtual replica count.

More virtual replicas can help with making item assignments more uniform, but the tradeoff is every operation takes a little longer as log2 of the number of buckets times the number of virtual replicas.

If not provided, the default (16) is used.