1. Devon O'Dell
  2. roundabout

Overview

Roundabout

Roundabout is a simple library implementing a consistent hashing algorithm. Such algorithms are typically used in determining where to store and how to find data in fault-tolerant, distributed systems.

Using Roundabout

Example usage is also provided in the godocs for this package.

package main
import (
    "crypto/sha256"
    "fmt"
    "bitbucket.org/dhobsd/roundabout"
)

func main() {
    hash := sha256.New()
    r := roundabout.New(hash, 256)

    r.Add("node1")
    r.Add("node2")
    r.Add("node3")

    fmt.Println(r.Get("data1"))
    fmt.Println(r.Get("data2"))
    fmt.Println(r.Get("data3"))

    r.Remove("node1")

    fmt.Println(r.Get("data1"))
    fmt.Println(r.Get("data2"))
    fmt.Println(r.Get("data3"))

    r.Add("node1")

    fmt.Println(r.Get("data1"))
    fmt.Println(r.Get("data2"))
    fmt.Println(r.Get("data3"))
}

It is generally recommended to use a large number of replicas to statistically mitigate a single node receiving a disproportionate amount of data. Good values for replication are generally around 200-300

Implementation Details

Inserts are generally O(n log n), as the underlying array needs to be sorted after an insertion.

Removals are O(n), as we do not need to re-sort after performing a removal.

Searches are O(log n).

The datastructure implemented in this package is not thread-safe, and the API makes no attempt to synchronize access to the data. When implementing this in a threaded environment, calls to roundabout.Get must be synchronized with respect to calls to Add and Remove.

The roundabout datastructure implements sort.Interface, but use of these functions outside of the package is discouraged.