Crate mpchash

source ·
Expand description

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

Overview

Multi-probe consistent hashing is a variant of consistent hashing that doesn’t require virtual nodes to achieve the same load balancing properties.

Nodes are assigned randomly to positions on the ring, however the key is not assigned to the next clockwise node, but instead multiple probes (using double-hashing) are made, and attempt/position with the closest distance to some node wins – that node is considered owning the key space for the key.

This means that nodes that happen to control wide range of the key space still do not get an increased chance of being selected, as most probes for such nodes will happen to possess not the smallest distance to a key.

Main structures

HashRing is the main structure that holds the ring state. For cases where ring of the u64 size is not big enough, you will need to define your own Partitioner.

Usage

use {
    mpchash::{HashRing, RingDirection::Clockwise},
    rand::Rng,
};

// Define a node type.
#[derive(Hash, Clone, Debug, Eq, PartialEq, Ord, PartialOrd)]
struct Node {
    id: u64,
}
impl Node {
    fn random() -> Self {
        Self {
            id: rand::thread_rng().gen(),
        }
    }
}

// Create a new ring.
let mut ring = HashRing::new();

// Populate the ring with some nodes.
let node1 = Node::random();
let node2 = Node::random();
ring.add(node1.clone());
ring.add(node2);

// Get the primary key space owning node for a key.
// This will return the first node when moving clockwise from the key's position.
let node = ring.primary_node(&42).unwrap();

// Remove a node from the ring.
ring.remove(&node1);

// Iterate over the ring.
for (position, node) in ring.tokens(0, Clockwise) {
    println!("{}: {:?}", position, node);
}

Structs

  • HashRing
    Consistent hash ring.
  • KeyRange
    A (half-open) range bounded inclusively below and exclusively above i.e. [start..end).
  • Xxh3Partitioner
    A partitioner that uses a XXH3 hash function to partition data.

Enums

  • RingDirection
    Defines the direction in which the ring is traversed.

Constants

Traits

  • Partitioner
    A keyspace partitioning strategy.
  • RingNode
    Node that can be assigned a position on the ring.

Type Aliases