hrw-hash 0.2.2

A minimalistic implementation of the Highest Random Weight (HRW) aka Rendezvous hashing algorithm
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96

# hrw-hash

[![crates.io](https://img.shields.io/crates/d/hrw-hash.svg)](https://crates.io/crates/hrw-hash)
[![docs.rs](https://docs.rs/hrw-hash/badge.svg)](https://docs.rs/hrw-hash)
[![unsafe forbidden](https://img.shields.io/badge/unsafe-forbidden-success.svg)](https://github.com/rust-secure-code/safety-dance/)
[![dependencies](https://deps.rs/repo/github/farazdagi/hrw-hash/status.svg)](https://deps.rs/repo/github/farazdagi/mpchash)

A minimalistic implementation of the Highest Random Weight (HRW) aka Rendezvous hashing algorithm as
described in the
["A name-based mapping scheme for Rendezvous"](https://www.eecs.umich.edu/techreports/cse/96/CSE-TR-316-96.pdf),
by Thaler and Ravishankar (1996).

The weighted variant of the HRW algorithm is implemented using Logarithmic Method as described in
["Weighted distributed hash tables"](https://dl.acm.org/doi/10.1145/1073970.1074008), by
Schindelhauer and Schomaker (2005).

To constrain the number of hashing operations, the implementation hashes nodes and keys only once
(instead of `nodes * keys` hashes). This optimization idea is well presented in the
["Rendezvous Hashing: The Path to Faster Hashes Calculation"](https://www.npiontko.pro/2024/12/23/computation-efficient-rendezvous-hashing)
blog.

## Features

- [x] Absolutely minimalistic implementation with sane defaults.
- [x] Allow weighted nodes.
- [ ] Allow massive number of nodes (`O(log(n))` lookup time, instead of `O(n)`).
- [x] Optimized for performance and memory usage. No wasted re-hashing.

## Usage

For non-weighted nodes:

``` rust
use hrw_hash::HrwNodes;

// Anything that implements `IntoIterator<Item = Hash + Eq>` can
// be used as list of target nodes.
let hrw = HrwNodes::new((0..10).map(|i| format!("node{}", i)));

// For a given key, get the iterator to node references
// (sorted by their weight).
let shard_id = 0;
let replicas: Vec<&String> = hrw.sorted(&shard_id)
                                .take(3).collect();
assert_eq!(replicas, vec!["node1", "node6", "node4"]);
```

For weighted nodes, which can have different capacities:

``` rust
use hrw_hash::{WeightedHrwNodes, WeightedNode};

// Define node
// (anything that implements `Hash + Eq` can be used as node).
#[derive(Debug, PartialEq, Eq, Hash)]
struct Node {
    id: u64,
    capacity: usize,
}

impl Node {
    fn new(id: u64, capacity: usize) -> Self {
        Self { id, capacity }
    }
}

// Implement `WeightedNode` trait for the node.
impl WeightedNode for Node {
    fn capacity(&self) -> usize {
        self.capacity
    }
}

let mut nodes = Vec::new();
for i in 0..100 {
    // Regular nodes, have the same capacity.
    nodes.push(Node::new(i, 1));
}
// Add some nodes with higher capacities.
nodes.push(Node::new(100, 50));
nodes.push(Node::new(101, 20));

let hrw = WeightedHrwNodes::new(nodes);

// Nodes `100` and `101` have higher capacity, so they will be
// selected more often -- even though there are many other nodes.
assert_eq!(hrw.sorted(&"foobar1").next(), Some(&Node::new(29, 1)));
assert_eq!(hrw.sorted(&"foobar2").next(), Some(&Node::new(78, 1)));
assert_eq!(hrw.sorted(&"foobar3").next(), Some(&Node::new(100, 50)));
assert_eq!(hrw.sorted(&"foobar4").next(), Some(&Node::new(101, 20)));
assert_eq!(hrw.sorted(&"foobar5").next(), Some(&Node::new(100, 50)));
```

## License

MIT