A revamped Google's jump consistent hash

Overview

Overview

This is a revamped Google's jump consistent hash. It overcomes the shortcoming of the original implementation - not being able to remove nodes. Here is the main idea behind doublejump.

Benchmark

BenchmarkDoubleJumpWithoutLock/10-nodes             50000000            27.6 ns/op
BenchmarkDoubleJumpWithoutLock/100-nodes            30000000            42.7 ns/op
BenchmarkDoubleJumpWithoutLock/1000-nodes           30000000            54.1 ns/op

BenchmarkDoubleJump/10-nodes                        20000000            72.9 ns/op
BenchmarkDoubleJump/100-nodes                       20000000            86.1 ns/op
BenchmarkDoubleJump/1000-nodes                      20000000            97.9 ns/op

BenchmarkStathatConsistent/10-nodes                  5000000           301 ns/op
BenchmarkStathatConsistent/100-nodes                 5000000           334 ns/op
BenchmarkStathatConsistent/1000-nodes                3000000           444 ns/op

BenchmarkSerialxHashring/10-nodes                    5000000           280 ns/op
BenchmarkSerialxHashring/100-nodes                   5000000           340 ns/op
BenchmarkSerialxHashring/1000-nodes                  3000000           427 ns/op

Example

h := NewHash()
for i := 0; i < 10; i++ {
    h.Add(fmt.Sprintf("node%d", i))
}

fmt.Println(h.Len())
fmt.Println(h.LooseLen())

fmt.Println(h.Get(1000))
fmt.Println(h.Get(2000))
fmt.Println(h.Get(3000))

h.Remove("node3")
fmt.Println(h.Len())
fmt.Println(h.LooseLen())

fmt.Println(h.Get(1000))
fmt.Println(h.Get(2000))
fmt.Println(h.Get(3000))

// Output:
// 10
// 10
// node9
// node2
// node3
// 9
// 10
// node9
// node2
// node0

Acknowledgements

The implementation of the original algorithm is credited to dgryski.

You might also like...
As the name says. Forges badge responses for the Defcon 29 badge and allows folks to jump straight to having completed the signal.

Defcon 29 Badge Code Generator Exactly as the title says. Will generate 7 signal keys to get you to signal then will generate 20 keys to distribute th

A simple to use SSH Jump bastion.

Kangaroo 🦘 A simple to use SSH Jump bastion. Installation Kangaroo can be installed by downloading it from apt and yum repo, more information on thos

skiptable is a jump table that mimics redis' zset using go, and implements most of the features of redis zset

skiptable is a jump table that mimics redis' zset using go, and implements most of the features of redis zset

A Jump Point Search Plus implement in Golang
A Jump Point Search Plus implement in Golang

Jump Point Search Plus 的 Golang 实现 JpsPlus 会对地图进行预处理,所以只适用于静态地图 BenchMark 两张地图,都

Jump start with the golang, start building fast REST or GraphQL API's

personalized overview and instruction for everyday use golang projects and language structure.

Gjg - Go jump goland tool

GJG go-jump-goland tool Allows you to launch quickly the Goland IDE and open pro

libketama-style consistent hashing in Go

===================================== ketama.go libketama-style consistent hashing in Go Author: Nolan Caudill ([email protected]) Date: 2011-06

Eventually consistent distributed in-memory cache Go library

bcache A Go Library to create distributed in-memory cache inside your app. Features LRU cache with configurable maximum keys Eventual Consistency sync

Consistent hashing with bounded loads in Golang

consistent This library provides a consistent hashing function which simultaneously achieves both uniformity and consistency. For detailed information

A consistent distributed data store.
A consistent distributed data store.

Doozer What Is It? Doozer is a highly-available, completely consistent store for small amounts of extremely important data. When the data changes, it

Consistent hashing with bounded loads in Golang

consistent This library provides a consistent hashing function which simultaneously achieves both uniformity and consistency. For detailed information

hego aims to provide a consistent API for several metaheuristics

hego hego aims to provide a consistent API for several metaheuristics (black box optimization algorithms) while being performant. Even though most of

Open Source (Go) implementation of "Zanzibar: Google's Consistent, Global Authorization System".

Open Source (Go) implementation of "Zanzibar: Google's Consistent, Global Authorization System". Ships gRPC, REST APIs, newSQL, and an easy and granular permission language. Supports ACL, RBAC, and other access models.

Consistent hashing hashring implementation.

hashring Consistent hashing hashring implementation. Overview This is an implementation of the consistent hashing hashring data structure. In general,

An alternative to Consistent Hashing

Weighted Rendezvous Hashing An alternative to Consistent Hashing. Evenly distributes load on node removal. ring := rendezvous.New() for _, s := range

Consistelancer - Consistent hashing load balancer for Kubernetes

Setup minikube start kubectl apply -f k8s-env.yaml skaffold dev # test locks ku

Built a causally consistent, replicated and sharded key value store with a REST API.

A causally consistent, replicated and sharded key value store built in Golang with a RESTful API. Runs through the use of a Docker container.

A demo to show clearly how Consistent Hashing works.

Consistent Hashing Demo A simple demo of consistent hashing. Features These features have been implemented: Core consistent-hashing-algorithm Consiste

Comments
  • Remove是个危险操作,使用有隐患

    Remove是个危险操作,使用有隐患

    场景: 假设有A,B,C,D,E五个节点提供服务,某时刻Remove了节点C,此时数据被hash到A,B,D,E四个节点,假设之后又过了一段时间,B发生了重启(无论B是从类似etcd中获得节点列表,还是通过其他方法发现其他存活的节点),那此时B节点对数据的hash是和其他节点完全不一致的。 假设再Remove节点C后,对A,B,D,E均调用Shrink,则Shrink之后各节点对数据的hash,和节点移除前基本是完全不一样的(测试和推理均可说明),这也是不合适的(违背了迁移数据最少的初衷) 感觉上面场景的问题,解决办法应该是,在B重启后,仍然获取A,B,C,D,E节点,然后调用Remove C节点。但这个在集群比较大时,就比较混乱了。 感觉这个实现应该是节点替换的场景比较适用,比如B节点挂了,立即添加F节点替换B。

    ====上面的推测分析是否正确,如何解决比较合适?

    opened by left2right 2
Releases(v1.0.1)
Owner
Edwin
Edwin
skiptable is a jump table that mimics redis' zset using go, and implements most of the features of redis zset

skiptable is a jump table that mimics redis' zset using go, and implements most of the features of redis zset

Qx 1 Oct 25, 2021
Consistent hashing with bounded loads in Golang

consistent This library provides a consistent hashing function which simultaneously achieves both uniformity and consistency. For detailed information

Burak Sezer 529 Nov 17, 2022
hego aims to provide a consistent API for several metaheuristics

hego hego aims to provide a consistent API for several metaheuristics (black box optimization algorithms) while being performant. Even though most of

Carl 41 Oct 7, 2022
A revamped Google's jump consistent hash

Overview This is a revamped Google's jump consistent hash. It overcomes the shortcoming of the original implementation - not being able to remove node

Edwin 81 Nov 18, 2022
Vso-hash-cuda - CUDA implementation of the BuildXL paged hash (a.k.a. VSO-Hash)

vso-hash-cuda Golang implementation of the BuildXL paged hash function (a.k.a. VSO-Hash) See https://github.com/microsoft/BuildXL/blob/master/Document

Peter Ebden 0 Jan 1, 2022
The most concise and efficient algorithm of consistent hash based on golang

consistent This package of consistent is the most concise and efficient algorithm of consistent hash based on golang. Example Quick start: package mai

null 1 Dec 28, 2021
Vso-hash - Golang implementation of the BuildXL paged hash function

vso-hash Golang implementation of the BuildXL paged hash function See https://gi

Peter Ebden 6 Jan 3, 2022
A drop-in replacement to any Writer type, which also calculates a hash using the provided hash type.

writehasher A drop-in replacement to any Writer type, which also calculates a hash using the provided hash type. Example package main import ( "fmt"

Max 0 Jan 10, 2022
Work pool channlege - An url hash retriever worker pool for getting hash digest for a collection of urls

Code challenge The aim of this project is to provide an url hash retriever worke

null 0 Feb 16, 2022
LazySSH is an SSH server that acts as a jump host only, and dynamically starts temporary virtual machines.

LazySSH is an SSH server that acts as a jump host only, and dynamically starts temporary virtual machines. If you find yourself briefly starti

Stéphan Kochen 474 Nov 9, 2022