Struct ConsistentHashingRing

Source

pub struct ConsistentHashingRing<T: RingHasherTrait> {
    pub hasher: T,
    pub replication_factor: usize,
    pub hash_to_vid: BTreeMap<u64, String>,
    pub vid_to_pid: HashMap<String, String>,
    pub physicals: HashMap<String, Rc<RefCell<PhysicalNode>>>,
}

Expand description

Represents a consistent hashing ring.

This struct manages the consistent hashing ring, which is used to distribute data across multiple physical nodes. It supports features such as replication, virtual nodes, and dynamic addition/removal of nodes.

§Why `Rc<RefCell<>>` is used:

Rc (Reference Counted) is used to allow multiple ownership of PhysicalNode instances. This is necessary because multiple parts of the code may need to access the same physical node.
RefCell is used to enable interior mutability, allowing the PhysicalNode to be mutated even when it is wrapped in an Rc. This is important because there are cases that we need to borrow immutably and mutably in the same lifetime.

Fields§

§hasher: T

The hashing function used to compute hash values for keys and nodes.

§replication_factor: usize

The number of physical nodes each key is replicated to for fault tolerance.

§hash_to_vid: BTreeMap<u64, String>

A mapping of hash values to virtual node IDs.

§vid_to_pid: HashMap<String, String>

A mapping of virtual node IDs to physical node IDs.

§physicals: HashMap<String, Rc<RefCell<PhysicalNode>>>

A mapping of physical node IDs to their corresponding PhysicalNode instances.

Implementations§

Source §

impl<T: RingHasherTrait> ConsistentHashingRing<T>

Source

pub fn builder() -> ConsistentHashingRingBuilder<T>

Create an instance of ConsistentHashingRing using the builder syntax

Source §

impl<T: RingHasherTrait> ConsistentHashingRing<T>

Source

pub fn vid_to_physical(&self, vid: &str) -> Result<Rc<RefCell<PhysicalNode>>>

Source

pub fn add_physical_node(&mut self, node: PhysicalNode) -> Result<AddNodeResult>

Adds a physical node to the consistent hashing ring.

This method initializes the virtual nodes for the given physical node, calculates their hash values, and inserts them into the ring. It also redistributes data from the previous virtual nodes to the new virtual nodes based on their hash ranges.

§Steps

Initialize Virtual Nodes: Generate virtual node IDs for the physical node and compute their hash values.
Insert Physical Node: Add the physical node to the physicals map, wrapped in Rc<RefCell> for shared ownership.
Redistribute Data:
- For each virtual node, find the previous virtual node in the ring.
- Move data from the hash range [prev_hash, curr_hash] of the previous virtual node to the new virtual node.
Update Mappings:
- Update hash_to_vid to map the hash of the new virtual node to its ID.
- Update vid_to_pid to map the virtual node ID to the physical node ID.
Track Results: Record the number of keys reassigned to each virtual node in the AddNodeResult.

§Arguments

node: The physical node to be added to the ring.

§Returns

Result<AddNodeResult>: A result containing information about the virtual nodes created and the number of keys reassigned to each virtual node, or an error if the operation fails.

Source

pub fn remove_physical_node(&mut self, pid: &str) -> Result<()>

Removes a physical node from the consistent hashing ring.

This method removes all virtual nodes associated with the given physical node ID (pid). It redistributes the data stored in the virtual nodes of the removed physical node to the next virtual nodes in the ring that belong to different physical nodes.

§Steps

Check if the physicals map is empty. If so, clear all mappings and return early.
Retrieve the virtual node IDs (vids) associated with the physical node.
Remove each virtual node using the remove_vnode method.
Remove the physical node from the physicals map.

§Arguments

pid: The unique identifier of the physical node to be removed.

§Returns

Result<()>: Returns Ok(()) if the physical node is successfully removed, or an error if the physical node does not exist or if any operation fails.

Source

pub fn insert(&mut self, key: &str, value: &str) -> Result<AddKeyResult>

Inserts a key-value pair into the consistent hashing ring.

This method computes the hash of the given key, determines the virtual nodes where the key should be stored based on the replication factor, and inserts the key-value pair into the appropriate physical nodes.

§Steps

Compute the hash of the key using the hasher.
Determine the virtual nodes (vids) where the key should be stored.
For each virtual node:
- Check if the physical node has already been used for replication.
- Insert the key-value pair into the virtual node and its corresponding physical node.
- Track the virtual node and physical node in the result.
Stop once the replication factor is satisfied.

§Arguments

key: The key to be inserted into the ring.
value: The value associated with the key.

§Returns

Result<AddKeyResult>: A result containing information about the virtual nodes where the key was stored, or an error if the operation fails.

Source

pub fn insert_many(&mut self, items: &[Item]) -> Result<Vec<AddKeyResult>>

Inserts multiple key-value pairs into the consistent hashing ring.

This method iterates over a list of items, computes their hashes, and inserts each key-value pair into the appropriate virtual nodes in the ring.

§Steps

Iterate over the list of items.
For each item, call the insert method to add the key-value pair to the ring.
Collect the results of each insertion into a vector.

§Arguments

items: A slice of Item structs, each containing a key and value to be inserted.

§Returns

Result<Vec<AddKeyResult>>: A vector of results for each inserted item, or an error if any insertion fails.

Source

pub fn get_item(&self, key: &str) -> Result<Item>

Retrieves an item from the consistent hashing ring by its key.

This method computes the hash of the given key, determines the virtual nodes where the key might be stored, and retrieves the associated value if it exists.

§Steps

Compute the hash of the key using the hasher.
Iterate over the virtual nodes (vids) where the key might be stored.
Check each physical node’s data map for the key.
Return the item if found, or an error if the key does not exist.

§Arguments

key: The key to retrieve from the ring.

§Returns

Result<Item>: The item associated with the key, or an error if the key is not found.

Source

pub fn remove(&mut self, key: &str) -> Result<()>

Removes a key-value pair from the consistent hashing ring.

This method computes the hash of the given key, iterates over the virtual nodes in both clockwise and anti-clockwise directions, and removes the key-value pair from the appropriate physical nodes. The removal stops once the replication factor is satisfied.

§Steps

Compute the hash of the key using the hasher.
Iterate over the virtual nodes in both clockwise and anti-clockwise directions.
For each virtual node:
- Check if the key exists in the virtual node’s hash set.
- Remove the key-value pair from the physical node’s data map.
- Track the number of successful removals.
Stop once the replication factor is satisfied.
Return an error if the key is not found or if the replication factor is not met.

§Arguments

key: The key to be removed from the ring.

§Returns

Result<()>: Returns Ok(()) if the key is successfully removed, or an error if the key does not exist or if the replication factor is not met.

Source

pub fn get_pids_containing_key(&self, key: &str) -> Result<Vec<String>>

Retrieves the physical node IDs (pids) that contain a specific key.

This method computes the hash of the given key, determines the virtual nodes where the key might be stored, and collects the physical node IDs that store the key.

§Steps

Compute the hash of the key using the hasher.
Iterate over the virtual nodes (vids) where the key might be stored.
Check each physical node’s data map for the key.
Collect the physical node IDs that contain the key.

§Arguments

key: The key to locate in the ring.

§Returns

Result<Vec<String>>: A vector of physical node IDs that contain the key, or an error if the operation fails.

Source

pub fn remove_vnode(&mut self, vid: &str) -> Result<()>

Removes a virtual node from the consistent hashing ring.

This method removes the specified virtual node (vid) from the ring. It redistributes the data stored in the virtual node to the next virtual node in the ring that belongs to a different physical node and does not already contain the same data (due to replication).

§Steps

Retrieve the physical node associated with the virtual node.
Remove the virtual node from the physical node’s vnodes map.
Redistribute the data stored in the virtual node to the next virtual node in the ring.
Update the hash_to_vid and vid_to_pid mappings to reflect the removal.

§Arguments

vid: The unique identifier of the virtual node to be removed.

§Returns

Result<()>: Returns Ok(()) if the virtual node is successfully removed, or an error if the virtual node does not exist or if any operation fails.

Source

pub fn add_one_vnode(&mut self, pid: &str) -> Result<()>

Adds a single virtual node to a physical node in the consistent hashing ring.

This method creates a new virtual node for the specified physical node (pid), computes its hash, and redistributes data from the next virtual node in the ring to the newly added virtual node.

§Steps

Retrieve the physical node associated with the given pid.
Generate a unique virtual node ID (vid) and compute its hash.
Ensure the hash is unique and does not collide with existing virtual nodes.
Redistribute data from the next virtual node in the ring to the new virtual node.
Update the hash_to_vid and vid_to_pid mappings.
Add the new virtual node to the physical node’s vnodes map.

§Arguments

pid: The unique identifier of the physical node to which the virtual node will be added.

§Returns

Result<()>: Returns Ok(()) if the virtual node is successfully added, or an error if any operation fails.

Source

pub fn set_num_vnodes(&mut self, pid: &str, new_num_vnodes: usize) -> Result<()>

Adjusts the number of virtual nodes for a physical node in the consistent hashing ring.

This method increases or decreases the number of virtual nodes for the specified physical node (pid). If the new number of virtual nodes is zero, the physical node is removed from the ring.

§Steps

Retrieve the physical node associated with the given pid.
If new_num_vnodes is zero, remove the physical node.
If new_num_vnodes is less than the current number, remove the extra virtual nodes.
If new_num_vnodes is greater than the current number, add new virtual nodes.

§Arguments

pid: The unique identifier of the physical node.
new_num_vnodes: The desired number of virtual nodes for the physical node.

§Returns

Result<()>: Returns Ok(()) if the operation is successful, or an error if any operation fails.

Source

pub fn range_info(&self) -> Result<RangeInfo>

Retrieves information about the hash ranges in the consistent hashing ring.

This method computes the hash ranges managed by the ring, including the number of keys and the items stored within each range. It provides a detailed view of how data is distributed across the virtual nodes in the ring.

§Steps

Collect all hash values from the hash_to_vid mapping.
Handle the case where there are no hashes (empty ring).
Handle the case where there is only one hash (single virtual node).
Iterate over the hash values to compute the ranges between consecutive hashes.
For each range, collect the items stored in the corresponding virtual node.

§Returns

Result<RangeInfo>: A RangeInfo struct containing details about the hash ranges, including the start and end hashes, the number of keys, and the items in each range.

Source

pub fn key_count(&self) -> Result<usize>

Retrieves the total number of keys stored in the consistent hashing ring.

This method iterates over all physical nodes in the ring and sums up the number of keys stored in their respective data maps.

§Returns

Result<usize>: The total number of keys in the ring, or an error if any operation fails.

Source

pub fn items_by_vnode(&self) -> Result<ItemsByVNode>

Retrieves the items stored in each virtual node of the consistent hashing ring.

This method iterates over all virtual nodes in the ring and collects the items stored in each virtual node. It provides a detailed view of how data is distributed across the virtual nodes.