mpchash

Consistent hashing algorithm implementation based on the Multi-probe consistent hashing paper.

Features

• Multi-probe consistent hashing.
• Balanced distribution of keys, with peak-to-average load ratio of 1 + ε with just 1 + 1/ε lookups per key.
• No virtual nodes, so no extra space required -- O(n) space complexity. The high space requirement is the main downside of the original Karger's ring.
• All conventional consistent hashing methods, like moving through the ring (in both directions), adding and removing nodes, finding the closest node to a key, finding a key range owned by a node etc.

Usage

The implementation supports all the features of the conventional consistent hashing algorithm, so it can be used as a drop-in replacement for any existing implementation.

Defining a node

Anything that implements the following traits can be placed on a ring as a node:

Hash + Clone + Debug + Eq + PartialEq + Ord + PartialOrd

Here is an example of using custom type as a node:

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

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

Creating a ring

To create a ring and populate it with nodes:

fn main() {
    use mpchash::HashRing;

    let mut ring = HashRing::new();
    ring.add(Node::new(1));
    ring.add(Node::new(2));
    ring.add(Node::new(3));
}

Finding a node that owns a key

Anything that implements Hash can be used as a key:

fn main() {
    // ... ring initialization code

    // Anything that implements `Hash` can be used as a key.
    let key = "hello world";

    // Node that owns the key.
    //
    // It is the first node when moving in CW direction from the 
    // position where key is hashed to.
    let owning_node = ring.primary_node(&key);

    // If we are interested in both ring position and owning node, 
    // we can get them with `primary_token`. 
    // 
    // A token is just a tuple of `(position, node)`.
    let token = ring.primary_token(&key);
}

In replicated settings, we want to have several replicas of a key, so need multiple destination/owning nodes.

In order to obtain such a list of replica nodes, we can traverse the ring from a given position:

fn main() {
    use mpchash::HashRing;
    use mpchash::RingDirection::Clockwise;

    let mut ring = HashRing::new();
    ring.add(Node::new(1));
    ring.add(Node::new(1));

    let key = "hello world";
    let tokens = ring
        .tokens(ring.position(&key), Clockwise)
        .collect::<Vec<_>>();

    for (pos, node) in ring.tokens(&key, Clockwise) {
        println!("node {} is at position {}", node, pos);
    }
}

Normally, you would collect/traverse replication factor number of tokens, so that you have replication factor of destination nodes.

Finding a key range owned by a node

Sometimes it is necessary to find a range of keys owned by a node. For example, when some node's data needs to be rebalanced to another node. In this case, we are moving from the node's position in the ring in CCW direction, until we find a previous node. As we are operating on a ring we need to account for the wrap-around. All this is handled by the key_range method:

fn main() {
    use mpchash::RingPosition;
    use mpchash::HashRing;

    let mut ring = HashRing::new();

    // Define nodes.
    let node1 = "SomeNode1";
    let node2 = "SomeNode2";

    // Add nodes to the ring.
    ring.add(node1);
    ring.add(node2);

    // Get the range owned by node1.
    let pos = ring.position(&node1);
    let range = ring.key_range(pos).unwrap();

    // The range starts at the position to the left of node1,
    // till (and not including) its own position.
    assert_eq!(range.start, ring.position(&node2));
    assert_eq!(range.end, ring.position(&node1));
}

License

MIT