Crate anchorhash
source · [−]Expand description
A consistent hashing algorithm that outperforms state-of-the-art algorithms.
This crate provides an implementation of the algorithm described in AnchorHash: A Scalable Consistent Hash.
AnchorHash
consistently hashes keys onto resources under arbitrary
working set changes. It does this with a low memory footprint, fast key
lookups (10s to 100s of millions of lookups per second), optimal disruption
and uniform balancing of load across resources.
This implementation also makes use of Daniel Lemire’s fast range mapping algorithm presented in Fast Random Integer Generation in an Interval.
Example
// 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);
// Map an input key to one of the backends
let backend = anchor.get_resource("user-A").unwrap();
println!("user mapped to: {}", backend);
Features
This crate has several compile-time features:
simd
: use SIMD operations to hash data internally (enabled by default onx86_64
platforms with support for SSE4.2)fastmod
: efficient range mapping from Fast Random Integer Generation in an Interval (enabled by default on 64-bit platforms)
Structs
An
AnchorHash
instance consistently maps keys of type K
to resources
of type R
using the algorithm described in AnchorHash: A Scalable Consistent Hash
.Initialise a new
AnchorHash
instance.An iterator yielding resources assigned to an
AnchorHash
instance in
an arbitrary order.An iterator yielding mutable references to the resources assigned to an
AnchorHash
instance in an arbitrary order.Enums
Errors returned when operating on an
AnchorHash
instance.Functions
A hash function producing a 32 bit hash for
k
, using seed
as the initial
hasher state.A 32-bit replacement for Daniel Lemire’s
Fast Random Integer Generation in an Interval
used on 64-bit CPUs.