hashring

README

hashring

Consistent hashing hashring implementation.

Overview

This is an implementation of the consistent hashing hashring data structure.

In general, consistent hashing is all about mapping objects from a very big set of values (e.g., request id) to objects from a quite small set (e.g., server address). The word "consistent" means that it can produce consistent mapping on different machines or processes without additional state exchange and communication.

For more theory about the subject please see this great document.

For more info about the package please read the docs.

The Why?

This is an approach for load distribution across servers which I found convinient to be used in a few projects I had worked on in the past.

I think it is good to implement it from scratch to synthesize all my experience working with it and share it with the community in hope it will help to build something good.

The key points of the package:

1. Efficient concurrent read operations
2. Correct handling of write operations (order of insertions on different processes doesn't matter; hash collisions are handled carefully).

Installation

go get github.com/gobwas/hashring

Usage

package main

import (
	"strings"
	"io"

	"github.com/gobwas/hashring"
)

func main() {
	var ring hashring.Ring
	_ = ring.Insert(StringItem("server01"))
	_ = ring.Insert(StringItem("server02"))
	_ = ring.Insert(StringItem("server03"))
	_ = ring.Insert(StringItem("server04"))

	ring.Get(StringItem("user01")) // server04
	ring.Get(StringItem("user02")) // server04
	ring.Get(StringItem("user03")) // server02
	ring.Get(StringItem("user04")) // server01
}

type StringItem string

func (s StringItem) WriteTo(w io.Writer) (int64, error) {
	n, err := io.WriteString(w, string(s))
	return int64(n), err
}

Contributing

If you find some bug or want to improve this package in any way feel free to file an issue to discuss your findings or ideas.

Debugging

Note that this package comes with built in debug tracing (which only takes place if you pass hashring_trace build tag, thanks to gtrace zero-cost tracing).

This means that you can make hashring to print out each meaningful step it does to understand better what's happening under the hood.

It also consumes hashring_debug build tag, which allows you to hook into hash calculation process and override the value it returns. For example, this was useful to test hash collisions.

Magic factor

Magic factor is a number of "virtual" nodes each item gets on a ring. The higher this number, the more equal distribution of objects this ring produces and the more time is needed to update the ring.

The default value is picked through testing different sets of servers and objects, however, for some datasets it may be enough to have smaller (or higher) value of magic factor. There is a branch called magic which contains code used to generate statistics on distribution of objects depending on magic factor value.

Here is the sample result of distribution of 10M objects across 10 servers with different magic factor values:

Documentation

Overview

Package hashring implements consistent hashing hashring data structure.

In general, consistent hashing is all about mapping of object from a very big set of values (e.g. request id) to object from a quite small set (e.g. server address). The word "consistent" means that it can produce consistent mapping on different machines or processes without additional state exchange and communication.

For more theory about the subject please see this great document: https://theory.stanford.edu/~tim/s16/l/l1.pdf

There are two goals for this hashring implementation: 1) To be efficient in highly concurrent applications by blocking read operations for the least possible time. 2) To correctly handle very rare but yet possible hash collisions, which may break all your eventually consistent application.

To reach the first goal hashring uses immutable AVL tree internally, making read operations (getting item for object) blocked only for a tiny amount of time needed to swap the ring's tree root after some write operation (insertion or deletion).

The second goal is reached by using ring of size 2^64-1 points, which dramatically reduces the probability of hash collisions (the greater the number of items on the ring, the higher the probability of collisions) and implementation that covers collisions.

Index

• Constants
• type Item
• type Ring
  • func (r *Ring) Delete(x Item) error
  • func (r *Ring) Get(v Item) Item
  • func (r *Ring) Has(x Item) bool
  • func (r *Ring) Insert(x Item, w float64) error
  • func (r *Ring) Update(x Item, w float64) error

Examples

• Ring

Constants

const DefaultMagicFactor = 1020

Types

type Item

type Item interface {
	io.WriterTo
}

type Ring

type Ring struct {
	// Hash is an optional function used to build up a new 64-bit hash function
	// for further hash values calculation.
	Hash func() hash.Hash64

	// MagicFactor is an optional number of "virtual" points on the ring per
	// item. The higher this number, the more equal distribution of objects
	// this ring produces and the more time is needed to update the ring.
	//
	// MagicFactor is the maximum number of points which can be placed on ring
	// for a single item. That is, item having max weight will have this amount
	// of points.
	//
	// If MagicFactor is zero, then the DefaultMagicFactor is used. For most
	// applications the default value is fine enough.
	MagicFactor int
	// contains filtered or unexported fields
}

Ring is a consistent hashing hashring. It is goroutine safe. Ring instances must not be copied. The zero value for Ring is an empty ring ready to use.

Example

var ring Ring

// Insert four servers on the ring with equal weight.
ring.Insert(StringItem("server01"), 1)
ring.Insert(StringItem("server02"), 1)
ring.Insert(StringItem("server03"), 1)
ring.Insert(StringItem("server04"), 1)

// Calculate distribution of 1M requests across four servers.
distribution := make(map[string]int)
for i := 0; i < 1000000; i++ {
	x := ring.Get(StringItem(strconv.Itoa(i)))
	s := string(x.(StringItem))
	distribution[s]++
}

fmt.Println(distribution["server01"])
fmt.Println(distribution["server02"])
fmt.Println(distribution["server03"])
fmt.Println(distribution["server04"])

Output:

254240
253479
246126
246155

func (*Ring) Delete

func (r *Ring) Delete(x Item) error

Delete removes item x from the ring. It returns non-nil error when x doesn't exist on the ring.

func (*Ring) Get

func (r *Ring) Get(v Item) Item

Get returns mapping of v to previously inserted item. Returned item is nil only when ring is empty.

func (*Ring) Has

func (r *Ring) Has(x Item) bool

func (*Ring) Insert

func (r *Ring) Insert(x Item, w float64) error

Insert puts item x with weight w onto the ring. It returns non-nil error when x already exists on the ring. If weight is less or equal to zero Insert() panics.

func (*Ring) Update

func (r *Ring) Update(x Item, w float64) error

Update updates item's x weight on the ring. It returns non-nil error when x doesn't exist on the ring. If weight is less or equal to zero Update() panics.