Struct consistent_hash_ring::Ring

pub struct Ring<T: Hash + Eq + Clone, S = FnvBuildHasher> { /* fields omitted */ }

A consistent hash ring with support for virtual nodes and key replication.

How it works

Typical hash ring construction. See wikipedia.

Nodes are mapped onto locations on a finite ring using a hash function. Keys are likewise hashed and mapped onto the same ring; the responsible node for a given key is the first node whose hash is greater than or equal to the key's hash.

Virtual Nodes

Because node locations on the ring are only uniformly distributed when looking at the ring containing all possible nodes, we map each node to multiple vnodes to improve the statistical properties of key distribution. The probability of a node being selected for any given key scales linearly with the proportion of assigned vnodes relative to other nodes in the ring.

Replication

Keys may optionally be mapped to a set of disjoint vnodes for fault tolerance or high availability purposes. Each additional replica is located by hashing keys an extra round; the hash is then mapped in the same manner as a single key. If any duplicate nodes arise during replica resolution, a circular scan starting at the index of the offending vnode is used to select the next vnode.

Performance

Mutable and immutable operations on the ring tend toward linear and sublinear complexity respectively.

The figures given below assume that:

• n = total nodes
• k = total vnodes
• v = vnodes per node
• r = replica count

Methods

impl<T: Hash + Eq + Clone, S: BuildHasher> Ring<T, S>

pub fn len(&self) -> usize

Returns the number of nodes in the ring (not including any duplicate vnodes).

O(1)

use consistent_hash_ring::*;

let ring = RingBuilder::default()
    .nodes_iter(0..32)
    .build();
assert_eq!(32, ring.len());

pub fn is_empty(&self) -> bool

Returns whether or not the ring is empty.

O(1)

use consistent_hash_ring::*;

let mut ring = Ring::default();
assert!(ring.is_empty());
ring.insert(&());
assert!(!ring.is_empty());

pub fn vnodes(&self) -> usize

Returns the total number of vnodes in the ring, across all nodes.

O(1)

use consistent_hash_ring::*;

let ring = RingBuilder::default()
    .vnodes(4)
    .nodes_iter(0..12)
    .build();
assert_eq!(48, ring.vnodes());
assert_eq!(12, ring.len());

pub fn weight<Q: ?Sized>(&self, node: &Q) -> Option<usize> where
    T: Borrow<Q>,
    Q: Hash + Eq, 

Returns the number of vnodes for the provided node, or None if it does not exist.

O(log n)

use consistent_hash_ring::*;

let mut ring = RingBuilder::default()
    .vnodes(12)
    .nodes_iter(0..4)
    .weighted_node(42, 9)
    .build();

assert_eq!(Some(12), ring.weight(&3));
assert_eq!(Some(9), ring.weight(&42));
assert_eq!(None, ring.weight(&24));

pub fn insert(&mut self, node: T)

Insert a node into the ring with the default vnode count.

O(k * v + (v * log k) + log k + n + log n)

use consistent_hash_ring::*;

let mut ring = Ring::default();
ring.insert("hello worldo");
assert_eq!(1, ring.len());
assert_eq!(Some(10), ring.weight("hello worldo"));

pub fn insert_weight(&mut self, node: T, vnodes: usize)

Insert a node into the ring with the provided number of vnodes.

This can be used give some nodes more weight than others - nodes with more vnodes will be selected for larger proportions of keys.

If the provided node is already present in the ring, the count is updated.

O(k * v + (v * log k) + log k + n + log n)

use consistent_hash_ring::*;

let mut ring = Ring::default();
ring.insert("hello worldo");
ring.insert_weight("worldo hello", 9);
assert_eq!(2, ring.len());
assert_eq!(Some(10), ring.weight("hello worldo"));
assert_eq!(Some(9), ring.weight("worldo hello"));

pub fn remove<Q: ?Sized>(&mut self, node: &Q) where
    T: Borrow<Q>,
    Q: Hash + Eq, 

Remove a node from the ring.

Any keys that were mapped to this node will be uniformly distributed amongst nearby nodes.

O(k + n + log n)

use consistent_hash_ring::*;

let mut ring = RingBuilder::default()
    .nodes_iter(0..12)
    .build();
assert_eq!(12, ring.len());
assert_eq!(Some(10), ring.weight(&3));
ring.remove(&3);
assert_eq!(11, ring.len());
assert_eq!(None, ring.weight(&3));

pub fn try_get<K: Hash>(&self, key: K) -> Option<&T>

Returns a reference to the first node responsible for the provided key.

Any key type may be used so long as it is Hash.

Returns None if there are no nodes in the ring.

O(log k)

use consistent_hash_ring::*;

let mut ring = RingBuilder::default()
    .vnodes(12)
    .build();
assert_eq!(None, ring.try_get("none"));

ring.insert("hello worldo");
assert_eq!(Some(&"hello worldo"), ring.try_get(42));

pub fn get<K: Hash>(&self, key: K) -> &T

Returns a reference to the first node responsible for the provided key.

Any key type may be used so long as it is Hash.

Panics if there are no nodes in the ring.

O(log k)

use consistent_hash_ring::*;

let mut ring = RingBuilder::default()
    .vnodes(12)
    .nodes_iter(0..1)
    .build();

assert_eq!(&0, ring.get("by"));

Important traits for Candidates<'a, T, S>

impl<'a, T: Hash + Eq + Clone, S: BuildHasher> Iterator for Candidates<'a, T, S> type Item = &'a T;

pub fn replicas<'a, K: Hash>(&'a self, key: K) -> Candidates<'a, T, S>

Returns an iterator over replication candidates for the provided key.

Prefer Ring::get instead if only the first node will be used.

O(r * (r + log r + k + log k))

use consistent_hash_ring::*;

let ring = RingBuilder::default()
    .replicas(3)
    .nodes_iter(0..12)
    .build();

let expect = vec![&10, &2, &8];

assert_eq!(expect, ring.replicas("key").collect::<Vec<_>>());
assert_eq!(expect[0], ring.get("key"));

let ring: Ring<()> = RingBuilder::default()
    .replicas(3)
    .build();

assert_eq!(None, ring.replicas("key").next());

Trait Implementations

impl<T: Hash + Eq + Clone> Default for Ring<T>

fn default() -> Self

Returns the "default value" for a type.

impl<T: Clone + Hash + Eq, S: Clone> Clone for Ring<T, S>

fn clone(&self) -> Ring<T, S>

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<K: Hash, T: Hash + Eq + Clone, S: BuildHasher> Index<K> for Ring<T, S>

type Output = T

The returned type after indexing.

fn index(&self, index: K) -> &Self::Output

Performs the indexing (container[index]) operation.