consistenthash

README

Consistent Hashing

A Go library that implements Consistent Hashing
This package is implemented based on golang/groupcache package with some improvements

Definitions in this README:
node: Refers to the key which is going to be stored in the hash ring or hash table
rKey: Refers to the request hash which is not going to be stored, it's used to find the upper closest node in the hash ring to the rKey

Improvements:

• Remove function added - sort and remove a node from the hash ring
• int hashes replaced with uint32
• Number of replicas is now configurable while adding new node
  Note: This is useful when capacity is not the same for all nodes

Usage

import (
    chash "github.com/mbrostami/consistenthash"
)

// Create ConsistentHash with 2 replicas
ch := chash.NewConsistentHash(2, nil)
ch.Add("127.0.0.1:1001") // node 1
ch.Add("127.0.0.1:1002") // node 2
ch.AddReplicas("127.0.0.1:1003", 4) // node3 has more capacity so possibility to get assigned request is higher than other nodes 

rKey := "something like request url"
node := ch.Get(rKey) // find upper closest node
fmt.println(node) // this will print out one of the nodes  

Test

Benchmark
go test -bench=.

Race Condition go test --race
Thanks to Mohammad Rajabloo for reporting the race issue

Tests
go test

Documentation

Overview

Package consistenthash provides an implementation of a ring hash.

Index

• type ConsistentHash
  • func NewConsistentHash(defaultReplicas int, hashFunction HashFunc) *ConsistentHash
  • func (ch *ConsistentHash) Add(key string)
  • func (ch *ConsistentHash) AddReplicas(key string, replicas int)
  • func (ch *ConsistentHash) Get(key string) string
  • func (ch *ConsistentHash) IsEmpty() bool
  • func (ch *ConsistentHash) Remove(key string) bool
• type HashFunc

Types

type ConsistentHash

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

ConsistentHash everything we need for CH

func NewConsistentHash

func NewConsistentHash(defaultReplicas int, hashFunction HashFunc) *ConsistentHash

NewConsistentHash makes new ConsistentHash

func (*ConsistentHash) Add

func (ch *ConsistentHash) Add(key string)

Add adds some keys to the hash key can be also ip:port of a replica

func (*ConsistentHash) AddReplicas

func (ch *ConsistentHash) AddReplicas(key string, replicas int)

AddReplicas adds key and generates "replicas" number of hashes in ring key can be also ip:port of a replica

func (*ConsistentHash) Get

func (ch *ConsistentHash) Get(key string) string

Get gets the closest item in the hash ring to the provided key e.g. key = "request url" O(log n)

func (*ConsistentHash) IsEmpty

func (ch *ConsistentHash) IsEmpty() bool

IsEmpty returns true if there are no items available

func (*ConsistentHash) Remove

func (ch *ConsistentHash) Remove(key string) bool

Remove removes the key from hash table

type HashFunc

type HashFunc func(data []byte) uint32

HashFunc hash function to generate random hash