[−][src]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 |
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. |