use std::{
collections::HashSet,
hash::{BuildHasher, Hash},
};
mod cluster_manager;
pub use cluster_manager::ClusterManager;
#[derive(Debug, Clone)]
pub struct VirtualRingNode {
hash: u64,
physical_node_index: usize,
}
#[derive(Debug, Clone)]
pub struct PhysicalRingNode<'a, T> {
identifier: String,
value: &'a T,
weight: usize,
}
impl<'a, T> PhysicalRingNode<'a, T> {
pub fn identifier(&self) -> &str {
&self.identifier
}
pub fn value(&self) -> &T {
self.value
}
pub fn weight(&self) -> usize {
self.weight
}
}
#[derive(Debug, Clone)]
pub struct TokenRangeMigration<T> {
pub start_hash: u64,
pub end_hash: u64,
pub from_node: T,
pub to_node: T,
}
#[derive(Clone)]
pub struct RingConfig<BH: BuildHasher> {
pub virtual_node_base_count: usize,
pub build_hasher: BH,
}
#[derive(Clone)]
pub struct ConsistentRing<'a, T, BH: BuildHasher> {
nodes: Vec<VirtualRingNode>,
physical_nodes: Vec<PhysicalRingNode<'a, T>>,
virtual_node_base_count: usize,
build_hasher: BH,
}
#[derive(Debug, Clone)]
pub enum RingError {
EmptyRing(&'static str),
ZeroWeight(&'static str),
NodeAlreadyExists(String),
NodeNotFound(String),
}
impl<'a, T, BH: BuildHasher> ConsistentRing<'a, T, BH> {
pub fn try_new(config: RingConfig<BH>) -> Result<Self, RingError> {
if config.virtual_node_base_count == 0 {
return Err(RingError::EmptyRing("Virtual nodes count must be > 0"));
}
Ok(Self {
nodes: Vec::new(),
physical_nodes: Vec::new(),
virtual_node_base_count: config.virtual_node_base_count,
build_hasher: config.build_hasher,
})
}
fn hash_key<K: Hash>(&self, key: &K) -> u64 {
self.build_hasher.hash_one(key)
}
fn format_virtual_node_key(&self, identifier: &str, i: usize) -> String {
format!("{identifier}#virtual-node-{i}")
}
pub fn add_node(
&mut self,
node: &'a T,
identifier: &str,
replica_multiplier: usize,
) -> Result<String, RingError> {
if replica_multiplier == 0 {
return Err(RingError::ZeroWeight("Replica multiplier must be > 0"));
}
if self.contains_identifier(identifier) {
return Err(RingError::NodeAlreadyExists(identifier.to_owned()));
}
let virtual_nodes_count = self.virtual_node_base_count * replica_multiplier;
let physical_node_index = self.physical_nodes.len();
for i in 0..virtual_nodes_count {
let virtual_node_key = self.format_virtual_node_key(identifier, i);
let hash = self.hash_key(&virtual_node_key);
self.nodes.push(VirtualRingNode {
hash,
physical_node_index,
});
}
self.nodes.sort_unstable_by_key(|ring_node| ring_node.hash);
self.physical_nodes.push(PhysicalRingNode {
identifier: identifier.to_owned(),
value: node,
weight: replica_multiplier,
});
Ok(identifier.to_string())
}
pub fn remove_node(&mut self, identifier: &str) {
if let Some(index) = self.physical_node_index(identifier) {
self.nodes.retain(|node| node.physical_node_index != index);
for node in &mut self.nodes {
if node.physical_node_index > index {
node.physical_node_index -= 1;
}
}
self.physical_nodes.remove(index);
}
}
fn physical_node_index(&self, identifier: &str) -> Option<usize> {
self.physical_nodes
.iter()
.position(|node| node.identifier == identifier)
}
pub fn contains_identifier(&self, identifier: &str) -> bool {
self.physical_node_index(identifier).is_some()
}
pub fn physical_nodes(&self) -> &[PhysicalRingNode<'a, T>] {
&self.physical_nodes
}
fn get_node_by_hash(&self, hash: u64) -> Option<&'a T> {
if self.nodes.is_empty() {
return None;
}
let start_index = self.find_start_index(hash);
Some(self.physical_nodes[self.nodes[start_index].physical_node_index].value)
}
pub fn find_start_index(&self, target_hash: u64) -> usize {
match self
.nodes
.binary_search_by(|ring_node| ring_node.hash.cmp(&target_hash))
{
Ok(exact_match) => exact_match,
Err(some_position) => {
if some_position == self.nodes.len() {
0
} else {
some_position
}
}
}
}
pub fn get_nodes<K: Hash>(&self, key: &K, count: usize) -> Vec<&'a T> {
if self.is_empty() || count == 0 {
return Vec::new();
}
let target_hash = self.hash_key(key);
let start_index = self.find_start_index(target_hash);
let mut result = Vec::new();
let mut seen_indices = HashSet::new();
for i in 0..self.len() {
let current_index = (start_index + i) % self.len();
let ring_node = &self.nodes[current_index];
if seen_indices.insert(ring_node.physical_node_index) {
result.push(self.physical_nodes[ring_node.physical_node_index].value);
if result.len() == count {
break;
}
}
}
result
}
pub fn calculate_migration_on_add(
&self,
new_node: &'a T,
new_identifier: &str,
new_replica_multiplier: usize,
) -> Result<Vec<TokenRangeMigration<T>>, RingError>
where
T: Clone,
BH: Clone,
{
let mut future_ring = self.clone();
future_ring.add_node(new_node, new_identifier, new_replica_multiplier)?;
let new_index = future_ring.physical_nodes.len() - 1;
let mut migrations = Vec::new();
for i in 0..future_ring.len() {
let current_virtual_node = &future_ring.nodes[i];
if current_virtual_node.physical_node_index == new_index {
let old_node = self.get_node_by_hash(current_virtual_node.hash);
if let Some(from_node) = old_node {
let previous_virtual_node = if i == 0 { future_ring.len() - 1 } else { i - 1 };
let start_hash = future_ring.nodes[previous_virtual_node].hash;
let end_hash = current_virtual_node.hash;
migrations.push(TokenRangeMigration {
start_hash,
end_hash,
from_node: from_node.clone(),
to_node: new_node.clone(),
});
}
}
}
Ok(migrations)
}
pub fn calculate_migration_on_remove(&self, identifier: &str) -> Vec<TokenRangeMigration<T>>
where
T: Clone,
BH: Clone,
{
if self.nodes.is_empty() {
return Vec::new();
}
let mut future_ring = self.clone();
future_ring.remove_node(identifier);
if future_ring.is_empty() {
return Vec::new();
}
let Some(removed_index) = self.physical_node_index(identifier) else {
return Vec::new();
};
self.nodes
.iter()
.enumerate()
.filter(|(_, node)| node.physical_node_index == removed_index)
.map(|(index, node)| {
let previous_index = if index == 0 {
self.nodes.len() - 1
} else {
index - 1
};
TokenRangeMigration {
start_hash: self.nodes[previous_index].hash,
end_hash: node.hash,
from_node: self.physical_nodes[removed_index].value.clone(),
to_node: future_ring
.get_node_by_hash(node.hash)
.expect("a destination exists after removal")
.clone(),
}
})
.collect()
}
pub fn get_node<K: Hash>(&self, key: &K) -> Option<&'a T> {
self.get_nodes(key, 1).into_iter().next()
}
pub fn len(&self) -> usize {
self.nodes.len()
}
pub fn is_empty(&self) -> bool {
self.nodes.is_empty()
}
}