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 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.

Similar Resources

A Jump Point Search Plus implement in Golang

A Jump Point Search Plus implement in Golang

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

Jan 11, 2022

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.

Feb 7, 2022

Gjg - Go jump goland tool

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

Mar 14, 2022

libketama-style consistent hashing in Go

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

Sep 1, 2022

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

Dec 2, 2022

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

Dec 29, 2022

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

Jan 6, 2023

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

Dec 29, 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

Dec 24, 2022

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.

Jan 8, 2023

Consistent hashing hashring implementation.

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

Nov 11, 2022

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

Feb 12, 2022

Consistelancer - Consistent hashing load balancer for Kubernetes

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

Sep 28, 2022

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.

Feb 2, 2022

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

Nov 21, 2022

Go implementation of BLAKE2 (b) cryptographic hash function (optimized for 64-bit platforms).

Go implementation of BLAKE2b collision-resistant cryptographic hash function created by Jean-Philippe Aumasson, Samuel Neves, Zooko Wilcox-O'Hearn, an

Jul 11, 2022

ID type with marshalling to/from hash to prevent sending IDs to clients.

ID type with marshalling to/from hash to prevent sending IDs to clients.

Hide IDs Hide is a simple package to provide an ID type that is marshalled to/from a hash string. This prevents sending technical IDs to clients and c

Dec 10, 2022

Argon2 password hashing package for go with constant time hash comparison

argon2pw Argon2 password hashing package with constant time hash comparison Preface: Argon2 was selected as the winner of the Password Hashing Competi

Sep 27, 2022
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。

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

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

Dec 16, 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

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

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

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"

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

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

Dec 11, 2022
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

Aug 25, 2021
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

Jul 25, 2022
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

Oct 25, 2021