hashring

README

hashring-go

This is a library that provides consistent hashing with bounded loads.

Overview

The package makes sure that all the keys are distributed uniformly and we operate consistently. We offer all the standard functionality such as Add, Remove and Get operations. The user can configure what the ReplicationFactor and PartitionCount should be -- bear in mind, that these values can not be chaned after initializing the hashring object with them. Before rushing in, try to find a combination of values that suits your needs -- also make sure, that your hashing function is uniformly distributing the values around the ring for best performance.

Contributing

Before creating a pull request, create an issue first.

Install

go get github.com/odvarkadaniel/hashring-go

You can find some usage examples in the examples folder.

Documentation

To see a list of all functions, please visit /TODO: Link/.

Examples

As mentioned before, more examples can be seen in the examples folder.

package main

import (
	"fmt"
	"hash/fnv"

	"github.com/odvarkadaniel/hashring-go"
)

type Server string

func (s *Server) String() string {
	return string(*s)
}

func Sum64(data []byte) uint64 {
	h := fnv.New64()
	h.Write(data)
	return h.Sum64()
}

func main() {
	cfg := hashring.Config{
		PartitionCount:    23,
		ReplicationFactor: 20,
		Hasher:            Sum64,
	}

	buckets := []hashring.Bucket{}

    // Create our fake servers
	for i := 0; i < 8; i++ {
		b := Server(fmt.Sprintf("node%d", i))
		buckets = append(buckets, &b)
	}

    // Create a new HashRing object
	ring := hashring.New(cfg, buckets)

	key := "test-key"
    // Get a bucket that holds the key
	bucket := ring.Get(key)

	// This should print node7.
	fmt.Println(bucket.String())
}

License

This project uses MIT LICENSE, for more details, please see the LICENSE file.

Documentation

Index

• Constants
• type Bucket
• type Config
• type HashFn
• type HashRing
  • func New(config Config, buckets []Bucket) *HashRing
  • func (hr *HashRing) Add(bucket Bucket)
  • func (hr *HashRing) AvgLoad() float64
  • func (hr *HashRing) Buckets() []Bucket
  • func (hr *HashRing) Get(key string) Bucket
  • func (hr *HashRing) GetLoads() map[string]float64
  • func (hr *HashRing) GetPartitionBucket(id int) Bucket
  • func (hr *HashRing) GetPartitionID(key string) int
  • func (hr *HashRing) Remove(key string)

Constants

const (
	DefaultPartitionCount    = 71
	DefaultReplicationFactor = 20
)

Types

type Bucket

type Bucket interface {
	String() string
}

type Config

type Config struct {
	// Hasher is the hash function that we use to disribute the keys
	// in the hash ring.
	Hasher HashFn

	// ReplicationFactor determines the number of virtual nodes we
	// put into the hash ring (replication of a real node on the ring).
	ReplicationFactor int

	// PartitionCount determines how many time we want to partition the space
	// to make for more uniform distribution of keys. Select a prime number for
	// this.
	PartitionCount int
}

type HashFn

type HashFn func([]byte) uint64

type HashRing

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

func New

func New(config Config, buckets []Bucket) *HashRing

New returns a pointer a HashRing structure.

func (*HashRing) Add

func (hr *HashRing) Add(bucket Bucket)

Add adds a new bucket to the consistent hash ring.

func (*HashRing) AvgLoad

func (hr *HashRing) AvgLoad() float64

AvgLoad computes the average load. For more information, please see: https://blog.research.google/2017/04/consistent-hashing-with-bounded-loads.html

func (*HashRing) Buckets

func (hr *HashRing) Buckets() []Bucket

Buckets returns all buckets that exist in the hash ring.

func (*HashRing) Get

func (hr *HashRing) Get(key string) Bucket

Get returns a bucket that is associated to a given key.

func (*HashRing) GetLoads

func (hr *HashRing) GetLoads() map[string]float64

GetLoads returns a mapping of each bucket to it load.

func (*HashRing) GetPartitionBucket

func (hr *HashRing) GetPartitionBucket(id int) Bucket

GetPartitionBucket gets a bucket for a given partition id.

func (*HashRing) GetPartitionID

func (hr *HashRing) GetPartitionID(key string) int

GetPartitionID gets a partition id for a given key in the ring.

func (*HashRing) Remove

func (hr *HashRing) Remove(key string)

Remove removes a bucket from the consistent hash ring.