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.
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
rphysical 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
rkeys 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.