Crate rendezvous_hash

An implementation of Rendezvous (a.k.a, highest random weight) hashing algorithm.

References

• Rendezvous hashing (Wikipedia)
• [Weighted Distributed Hash Tables] (https://pdfs.semanticscholar.org/8c55/282dc37d1e3b46b15c2d97f60568ccb9c9cd.pdf)
  • This paper describes an efficient method for calculating consistent hash values for heterogeneous nodes.

Examples

For homogeneous nodes:

use rendezvous_hash::RendezvousNodes;

// Constructs a node (a.k.a., server, site, etc) set.
let mut nodes = RendezvousNodes::default();
nodes.insert("foo");
nodes.insert("bar");
nodes.insert("baz");
nodes.insert("qux");

// Finds candidate nodes for an item (a.k.a., object).
assert_eq!(nodes.calc_candidates(&1).collect::<Vec<_>>(),
           [&"bar", &"baz", &"foo", &"qux"]);
assert_eq!(nodes.calc_candidates(&"key").collect::<Vec<_>>(),
           [&"qux", &"bar", &"foo", &"baz"]);

// Update the node set.
// (The relative order between existing nodes are preserved)
nodes.remove(&"baz");
assert_eq!(nodes.calc_candidates(&1).collect::<Vec<_>>(),
           [&"bar", &"foo", &"qux"]);
assert_eq!(nodes.calc_candidates(&"key").collect::<Vec<_>>(),
           [&"qux", &"bar", &"foo"]);

For heterogeneous nodes:

use std::collections::HashMap;
use rendezvous_hash::RendezvousNodes;
use rendezvous_hash::{WeightedNode, Capacity};

let mut nodes = RendezvousNodes::default();
nodes.insert(WeightedNode::new("foo", Capacity::new(70.0).unwrap()));
nodes.insert(WeightedNode::new("bar", Capacity::new(20.0).unwrap()));
nodes.insert(WeightedNode::new("baz", Capacity::new(9.0).unwrap()));
nodes.insert(WeightedNode::new("qux", Capacity::new(1.0).unwrap()));

let mut counts = HashMap::new();
for item in 0..10000 {
    let node = nodes.calc_candidates(&item).nth(0).unwrap();
    *counts.entry(node.node.to_string()).or_insert(0) += 1;
}
assert_eq!(((counts["foo"] as f64) / 100.0).round(), 70.0);
assert_eq!(((counts["bar"] as f64) / 100.0).round(), 20.0);
assert_eq!(((counts["baz"] as f64) / 100.0).round(), 9.0);
assert_eq!(((counts["qux"] as f64) / 100.0).round(), 1.0);

Modules

types

Miscellaneous types.

Structs

Capacity

The capacity of a weighted node.

DefaultNodeHasher

The default NodeHasher implementation.

IdNode

Identity node.

KeyValueNode

Key-Value node.

RendezvousNodes

A candidate node set of a rendezvous for clients that are requiring the same item.

WeightedNode

Weighted node.

Traits

Node

This trait represents a candidate node for rendezvous.

NodeHasher

This trait allows calculating the hash value of a node for a specific item.