Struct anchorhash::AnchorHash

pub struct AnchorHash<K, R, B>where
    K: Hash,
    B: BuildHasher,{ /* private fields */ }

An AnchorHash instance consistently maps keys of type K to resources of type R using the algorithm described in AnchorHash: A Scalable Consistent Hash.

The AnchorHash algorithm uniformly balances keys across all the configured resources and performs optimal (minimal) rebalancing when existing resources are removed or new resources added. AnchorHash achieves this using only a few bytes per resource, and outperforms state-of-the-art algorithms.

Hashing Algorithm

The hashing algorithm used by default is the same as the one used by Rust’s HashMap and can be easily swapped for a more performant hashing algorithm.

AnchorHash does NOT require a cryptographic hash, but DOES require the hash to produce uniformly distributed values.

Distributed Consistency

In order for multiple AnchorHash instances to map the same keys to the same resources, all instances must reach consensus on the ordering of changes to the resource set.

Key and Resource Types

Any type can be used as a resource type, including both owned any borrowed content. Good examples include socket addresses, connection pools, API clients, etc.

Any type that implements Hash can be used as a key. All primitive types implement Hash (strings, usize, etc):

// Build an AnchorHash from a list of backends.
//
// Backends can be added and removed, but this AnchorHash instance can hold
// a maximum of 2 backends when constructed by collecting an iterator
// (capacity == iterator length).
let anchor = vec!["cache1.itsallbroken.com", "cache2.itsallbroken.com"]
    .into_iter()
    .collect::<AnchorHash<_, _, _>>();

let backend_1 = anchor.get_resource("user-A").unwrap();
let backend_2 = anchor.get_resource("user-B").unwrap();

You can also derive Hash on your types - this makes it easy to use a compound key safely and without resorting to string types:

use std::net::SocketAddr;

// A custom key type that maps to a backend based on all values
#[derive(Hash)]
struct UserSession {
    user_id: u64,
    ip_addr: SocketAddr,
}

// Initialise a AnchorHash with the capacity for 20 backend cache servers,
// and 3 active servers.
let anchor = anchorhash::Builder::default()
    .with_resources(vec![
        "cache1.itsallbroken.com",
        "cache2.itsallbroken.com",
        "cache3.itsallbroken.com",
    ])
    .build(20);

// Look up a cache backend for this user ID and requesting IP
let key = UserSession {
    user_id: 42,
    ip_addr: "127.0.0.1:4242".parse().unwrap(),
};

// Map the UserSession to a cache backend
let backend = anchor.get_resource(&key).unwrap();

println!("user mapped to: {}", backend);

Implementations

impl<K, R, B> AnchorHash<K, R, B>where
    K: Hash,
    B: BuildHasher,
    R: PartialEq,

pub fn get_resource(&self, key: K) -> Option<&R>

Consistently hash key to a configured resource.

This method will return None when self contains no resources.

pub fn add_resource(&mut self, resource: R) -> Result<(), Error>

Add resource, allowing keys to map to it.

When a new resource is added, keys immediately begin mapping to it, and the load across all the resources remains uniformly balanced. If there were 3 backends, each handling 1/3 of the load, adding a new resource (total: 4) means they all immediately become responsible for 1/4 of load.

A subset of keys from each resource is mapped to the new resource ensuring minimal disruption with optimal load sharing.

pub fn remove_resource(&mut self, resource: &R) -> Result<(), Error>

Remove the resource, preventing keys from mapping to resource.

When resource is removed, all the keys that previously mapped to it are uniformly distributed over the remaining resources. Keys that did not map to resource continue mapping to the same resource as before the removal.

Removal runs in linear time w.r.t the number of resources.

pub fn resources(&self) -> ResourceIterator<'_, R>

Returns an iterator yielding references to the configured resources in an arbitrary order.

pub fn resources_mut(&mut self) -> ResourceMutIterator<'_, R>

Returns an iterator yielding mutable references to the configured resources in an arbitrary order.

Trait Implementations

impl<K, R, B> Clone for AnchorHash<K, R, B>where
    K: Hash,
    B: BuildHasher + Clone,
    R: Clone,

Implement Clone when both the resource type (R) and the hash builder (B) implement clone.

Note the key type (K) does NOT have to implement Clone.

fn clone(&self) -> Self

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<K: Debug, R: Debug, B: Debug> Debug for AnchorHash<K, R, B>where
    K: Hash,
    B: BuildHasher,

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<R, K> FromIterator<R> for AnchorHash<K, R, RandomState>where
    K: Hash,

fn from_iter<T: IntoIterator<Item = R>>(iter: T) -> Self

Creates a value from an iterator.