Consistent hashing is a special kind of hashing such that when a hash table is resized and consistent hashing is used, only K/n keys need to be remapped on average, where K is the number of keys, and n is the number of slots. In contrast, in most traditional hash tables, a change in the number of array slots causes nearly all keys to be remapped. (cited from Wiki)
Consistent Hashing has 4 features:
- Balance
- Monotonicity
- Spread
- Load
In this application you will see:
We use virtual node to make replica for load distribution. (not all node pick the same server).
Use the hash key function, it will make sure it always pick the same server (in the same quantity of server)
Here is more detail in Chinese
go get github.com/kkdai/consistent
Following is sample code:
package main
import (
"fmt"
. "github.com/kkdai/consistent"
)
func main() {
ch := NewConsistentHashing()
ch.Add("server1")
ch.Add("server2")
ch.Add("server3")
//[server1 server2 server3]
fmt.Println(ch.ListNodes())
targetObj := []string{"client1", "client2", "client3", "client4", "client5", "client6"}
for _, v := range targetObj {
server, err := ch.Get(v)
if err == nil {
fmt.Printf("client: %s in server: %s \n", v, server)
}
}
//client: client1 in server: server1
//client: client2 in server: server3
//client: client3 in server: server1
//client: client4 in server: server3
//client: client5 in server: server1
//client: client6 in server: server3
ch.Add("server4")
ch.Add("server5")
for _, v := range targetObj {
server, err := ch.Get(v)
if err == nil {
fmt.Printf("client: %s in server: %s \n", v, server)
}
}
//client: client1 in server: server4
//client: client2 in server: server3
//client: client3 in server: server4
//client: client4 in server: server3
//client: client5 in server: server4
//client: client6 in server: server3
}- 每天进步一点点——五分钟理解一致性哈希算法(consistent hashing)
- https://github.com/stathat/consistent
- Wiki: Consistent Hashing
It is one of my project 52.
This package is licensed under MIT license. See LICENSE for details.