Crate conhash_ring 

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

Structs

AddKeyResult

Represents the result of adding a key-value pair to the consistent hashing ring.

AddKeyResultBuilder

Use builder syntax to set the inputs and finish with build().

AddKeyResultLocation

AddKeyResultLocationBuilder

Use builder syntax to set the inputs and finish with build().

AddNodeResult

Represents the result of adding a physical node to the consistent hashing ring.

AddNodeResultBuilder

Use builder syntax to set the inputs and finish with build().

AddNodeResultValue

AddNodeResultValueBuilder

Use builder syntax to set the inputs and finish with build().

ConsistentHashingRing

Represents a consistent hashing ring.

ConsistentHashingRingBuilder

HashItem

HashItemBuilder

Use builder syntax to set the inputs and finish with build().

Item

ItemBuilder

Use builder syntax to set the inputs and finish with build().

ItemsByVNode

ItemsByVNodeBuilder

Use builder syntax to set the inputs and finish with build().

ItemsByVNodeValue

ItemsByVNodeValueBuilder

Use builder syntax to set the inputs and finish with build().

PhysicalNode

Represents a physical node in the consistent hashing ring.

PhysicalNodeBuilder

Use builder syntax to set the inputs and finish with build().

Range

RangeBuilder

Use builder syntax to set the inputs and finish with build().

RangeInfo

Represents information about hash ranges in the consistent hashing ring.

RangeInfoBuilder

Use builder syntax to set the inputs and finish with build().

VirtualNode

VirtualNodeBuilder

Use builder syntax to set the inputs and finish with build().

Enums

RingHasher

Traits

RingHasherTrait

A trait that defines the behavior of a hashing function used in the consistent hashing ring.