conhash-ring: Rust implementation of Consistent Hashing

Overview

This is a Rust implementation of consistent hashing, a technique used in distributed systems to distribute data across multiple nodes in a way that minimizes the amount of data that needs to be moved when nodes are added or removed.

This implementation serves as an educational example to demonstrate the concept of a consistent hash ring. It is not designed for production environments.

Features

• Support pluggable hash functions.
• Support virtual nodes: Each physical node can be represented by multiple virtual nodes to improve load balancing. Physical nodes contain real data, while virtual nodes contain key hashes.
• Support replication factor: Each key can be stored on multiple physical nodes to improve fault tolerance.

APIs

Checkout ConsistentHashingRing for more details.

Test case examples

Checkout test cases in src/lib.rs for more details. Criteria is to maintain the replication factor r.

• Adding a key: When a key is added, it is hashed to a position on the ring. The key is then stored on r physical nodes, starting from the position of the key's hash and moving clockwise around the ring. If 2 virtual nodes of the same physical are close to each other, the key will be stored on the first virtual node, then replicated to the next physical nodes

• Removing a key: Starting from the position of the key's hash, remove the r keys from both clockwise and anti-clockwise directions.

• Adding a virtual node: When a new node is added, keys are redistributed clockwise to the nearest virtual node belonging to a physical node that does not already store the key.

• Removing a virtual node: When a node is removed, keys are redistributed anti-clockwise to the nearest virtual node belonging to a physical node that does not already store the key.

1. Add keys

2. Remove a key

3. Removing node 2 (with 2 vnodes)

4. Adding 1 vnode (hash = 70) to node 1

5. Reducing node 3 vnodes to 1

6. Increasing node 1 vnodes to 3