English | 简体中文

chash

Consistent hashing written by Go

What is consistent hashing

Consistent hashing is a hashing technique that performs really well when operated in a dynamic environment where the distributed system scales up and scales down frequently.

Consistent Hashing allows distributing data in such a way that minimize reorganization when nodes are added or removed, hence making the system easier to scale up or down.

The key idea is that it's a distribution scheme that DOES NOT depend directly on the number of servers.

In Consistent Hashing, when the hash table is resized, in general only k / n keys need to be remapped, where k is the total number of keys and n is the total number of servers.

When a new node is added, it takes shares from a few hosts without touching other's shares When a node is removed, its shares are shared by other hosts.

Getting started

With Go module support, simply add the following import

import "github.com/werbenhu/chash"

Simple Usage

Create a group

// Create a group named "db" with 10000 virtual elements for each key
// which internally manages the group using a global singleton chash object.
dbGroup, _ := chash.CreateGroup("db", 10000)

// Insert elements (multiple MySQL servers).
dbGroup.Insert("192.168.1.100:3306", []byte("mysql0-info"))
dbGroup.Insert("192.168.1.101:3306", []byte("mysql1-info"))

// Create a second group.
webGroup, _ := chash.CreateGroup("web", 10000)

// Insert elements (multiple HTTP servers).
webGroup.Insert("192.168.2.100:80", []byte("web0-info"))
webGroup.Insert("192.168.2.101:80", []byte("web1-info"))

// Use an existing group.
dbGroup, err := chash.GetGroup("db")
if err != nil {
    log.Printf("ERROR get group failed, err:%s\n", err.Error())
}

dbGroup.Insert("192.168.1.103:3306", []byte("mysql3-info"))
host, info, err := dbGroup.Match("user-id")

Match a MySQL server for a user ID

// match an element close to where key hashes to in the circle.
host, info, err := dbGroup.Match("user-id")

Delete element from a group

// delete element
dbGroup.Delete("192.168.1.102:3306")

Get all elements of a group

elements := dbGroup.GetElemens()

Using an independent group

// A group created by chash.NewGrou() is not managed by the global chash object
// You need to manage groups yourself if there are more than one group.
group := chash.NewGroup("db", 10000)

group.Insert("192.168.1.100:3306", []byte("mysql0-info"))
group.Insert("192.168.1.101:3306", []byte("mysql1-info"))
host, info, err := group.Match("user-id")

Examples

See the example .

Contributions

Contributions and feedback are both welcomed and encouraged! Open an issue to report a bug, ask a question, or make a feature request.