mpchash 2.0.10

A space-efficient (no need for vnodes) multi-probe consistent 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
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122

use {mpchash::HashRing, rand::random, std::ops::Deref};

#[derive(Hash, Clone, Copy, Debug, Eq, PartialEq, Ord, PartialOrd)]
struct Node {
    id: u64,
}

impl Node {
    fn random() -> Self {
        Self { id: random() }
    }
}

#[test]
fn add_node() {
    let ring = HashRing::new();

    let num_nodes = 10;
    let mut nodes = Vec::with_capacity(num_nodes);
    for i in 0..num_nodes {
        nodes.insert(i, Node { id: i as u64 });
        ring.add(nodes[i]);
    }

    let num_keys = 1000;
    for i in 0..num_keys {
        let node = ring.node(&i).unwrap();
        assert!(nodes.contains(&node));
    }
}

#[test]
fn remove_node() {
    let ring = HashRing::new();
    let node1 = Node::random();
    let node2 = Node::random();

    ring.add(node1);
    ring.add(node2);

    // Make sure that node1 and node2 are assigned to the ring.
    assert_eq!(ring.len(), 2);

    // Remove node1, and make sure that it is no longer assigned to the ring.
    ring.remove(&node1);
    assert_eq!(ring.len(), 1);
    assert_eq!(ring.node(&0).as_deref(), Some(&node2));
}

#[test]
fn duplicate_peer() {
    let ring = HashRing::new();
    let node = Node::random();
    ring.add(node);
    ring.add(node);
    assert_eq!(ring.len(), 1);
    assert_eq!(ring.node(&0).as_deref(), Some(&node));
}

#[test]
fn walkthrough() {
    // Anything that implements `Hash + Send` can be used as a node.
    // Other traits used here are derived for testing purposes.
    #[derive(Hash, Debug, PartialEq, Clone, Copy)]
    struct MyNode(u64);

    // Create a new ring, and add nodes to it.
    let ring = HashRing::new();
    (1..=5).for_each(|i| {
        ring.add(MyNode(i));
    });

    // Anything that implements `Hash` can be used as a key.
    // To find which node should own a key:
    let key = "hello world";

    // Token is a thin wrapper holding reference to node itself
    // and to its position on the ring.
    let token = ring.node(&key).expect("empty ring");
    assert_eq!(token.position(), 1242564280540428107);
    assert_eq!(token.node(), &MyNode(2));

    // In replicated settings, we want to have several replicas
    // of a key to be stored redundantly, therefore we need multiple
    // destination/owning nodes.
    //
    // Assuming a replication factor of 3, we can do:
    let tokens = ring.replicas(&key, 3);
    assert_eq!(tokens, vec![&MyNode(1), &MyNode(2), &MyNode(3)]);

    let tokens = ring.replicas(&key, 3);
    assert_eq!(tokens.iter().map(|e| e.node()).collect::<Vec<_>>(), vec![
        &MyNode(1),
        &MyNode(2),
        &MyNode(3)
    ]);
    assert_eq!(tokens.iter().map(Deref::deref).collect::<Vec<_>>(), vec![
        &MyNode(1),
        &MyNode(2),
        &MyNode(3)
    ]);

    // Before node removal we probably need to move its data.
    // To find out range of keys owned by a node:
    let ranges = ring.intervals(&token).expect("empty ring");
    assert_eq!(ranges.len(), 1);

    // The range starts at the position where previous node ends,
    // and ends at the position of the owning node.
    assert_eq!(ranges[0].start, ring.position(&MyNode(1)));
    assert_eq!(ranges[0].end, ring.position(&token.node()));

    // Remove node and check the owning nodes again.
    ring.remove(&MyNode(2));

    // `MyNode(2)` is removed, `MyNode(4)` takes its place now.
    let token = ring.node(&key).expect("empty ring");
    assert_eq!(token.node(), &MyNode(4));

    let tokens = ring.replicas(&key, 3);
    assert_eq!(tokens, vec![&MyNode(1), &MyNode(3), &MyNode(4)]);
}