doublejump

README

Overview

Doublejump is a revamped Google's jump consistent hash. It overcomes the shortcoming of the original design - being unable to remove nodes. Here is how it works.

Benchmark

DoubleJump/10-nodes               49276861       22.3 ns/op        0 B/op      0 allocs/op
DoubleJump/100-nodes              33304191       34.9 ns/op        0 B/op      0 allocs/op
DoubleJump/1000-nodes             25261296       46.3 ns/op        0 B/op      0 allocs/op

StathatConsistent/10-nodes         4780832      273.5 ns/op       80 B/op      2 allocs/op
StathatConsistent/100-nodes        4059537      291.8 ns/op       80 B/op      2 allocs/op
StathatConsistent/1000-nodes       3132294      367.6 ns/op       80 B/op      2 allocs/op

SerialxHashring/10-nodes           2766384      455.7 ns/op      152 B/op      5 allocs/op
SerialxHashring/100-nodes          2500936      487.6 ns/op      152 B/op      5 allocs/op
SerialxHashring/1000-nodes         2254138      560.0 ns/op      152 B/op      5 allocs/op

Installation

V1

## If golang version <= 1.17
go get -u github.com/edwingeng/doublejump

V2

## If golang version >= 1.18
go get -u github.com/edwingeng/doublejump/v2

Examples

V1

// If golang version <= 1.17
import "github.com/edwingeng/doublejump"

func 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
}

V2

// If golang version >= 1.18
import "github.com/edwingeng/doublejump/v2"

func Example() {
    h := NewHash[string]()
    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 true
    // node2 true
    // node3 true
    // 9
    // 10
    // node9 true
    // node2 true
    // node0 true
}

Acknowledgements

The implementation of the original algorithm is credited to dgryski.

Documentation

Overview

Package doublejump provides a revamped Google's jump consistent hash.

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

Index

• type Hash
  • func NewHash() *Hash
  • func (h *Hash) Add(obj interface{})
  • func (h *Hash) All() []interface{}
  • func (h *Hash) Get(key uint64) interface{}
  • func (h *Hash) Len() int
  • func (h *Hash) LooseLen() int
  • func (h *Hash) Random() interface{}
  • func (h *Hash) Remove(obj interface{})
  • func (h *Hash) Shrink()

Examples

• Package

Types

type Hash

type Hash struct {
	// contains filtered or unexported fields
}

Hash is a revamped Google's jump consistent hash. It overcomes the shortcoming of the original implementation - being unable to remove nodes.

Hash is NOT thread-safe.

func NewHash

func NewHash() *Hash

NewHash creates a new doublejump hash instance.

func (*Hash) Add

func (h *Hash) Add(obj interface{})

Add adds an object to the hash.

func (*Hash) All

func (h *Hash) All() []interface{}

All returns all the objects in this Hash.

func (*Hash) Get

func (h *Hash) Get(key uint64) interface{}

Get returns the existing object for the key, or nil if there is no object in the hash.

func (*Hash) Len

func (h *Hash) Len() int

Len returns the number of objects in the hash.

func (*Hash) LooseLen

func (h *Hash) LooseLen() int

LooseLen returns the size of the inner loose object holder.

func (*Hash) Random

func (h *Hash) Random() interface{}

Random returns a random object, or nil if there is no object in the hash.

func (*Hash) Remove

func (h *Hash) Remove(obj interface{})

Remove removes an object from the hash.

func (*Hash) Shrink

func (h *Hash) Shrink()

Shrink removes all empty slots from the hash.