pub mod hash;
use std::collections::{BTreeMap, HashMap, HashSet};
use std::fmt;
use std::mem::size_of;
use bytes::Bytes;
use self::hash::HashFn;
pub trait Member<P> {
fn inner(&self) -> &Bytes;
fn make_virtual(&self, password: P) -> Self;
fn physical_from_virtual(&self) -> Self;
fn new_physical(key: &str) -> Self;
}
pub trait Ring<P: Clone, M: Member<P>> {
fn add_node(&mut self, member: M, replicas: usize);
fn delete_node(&mut self, member: M);
fn get_node(&self, key: &[u8]) -> Option<M>;
fn get_nodes(&self, key: &[u8], k: usize) -> Vec<M>;
fn contains_node(&self, member: &M) -> bool;
fn nodes(&self) -> impl Iterator<Item = &Bytes>;
fn prune(&mut self);
fn len(&self) -> usize;
fn is_empty(&self) -> bool;
}
#[derive(Clone)]
pub enum RingMember {
Physical(Bytes),
Virtual(Bytes),
}
impl Member<usize> for RingMember {
fn inner(&self) -> &Bytes {
match self {
RingMember::Physical(b) | RingMember::Virtual(b) => b,
}
}
fn make_virtual(&self, virtual_pass: usize) -> RingMember {
match self {
RingMember::Physical(_) => {
let inner = self.inner().as_ref();
let v = [inner, &virtual_pass.to_be_bytes()].concat();
RingMember::Virtual(Bytes::from(v))
}
RingMember::Virtual(_) => self.clone(), }
}
fn physical_from_virtual(&self) -> RingMember {
match self {
RingMember::Physical(_) => self.clone(),
RingMember::Virtual(b) => {
let int_size = size_of::<usize>();
let name = if b.len() >= int_size {
b.slice(..b.len() - int_size)
} else {
b.clone()
};
RingMember::Physical(name)
}
}
}
fn new_physical(key: &str) -> RingMember {
RingMember::Physical(Bytes::copy_from_slice(key.as_bytes()))
}
}
impl fmt::Display for RingMember {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
match self {
RingMember::Physical(b) => {
let text = String::from_utf8_lossy(b);
write!(f, "{}", text)
}
RingMember::Virtual(b) => {
let int_size = size_of::<usize>();
if b.len() >= int_size {
let (name_bytes, int_bytes) = b.split_at(b.len() - int_size);
let name = String::from_utf8_lossy(name_bytes);
let index = usize::from_be_bytes(
int_bytes.try_into().unwrap_or([0u8; size_of::<usize>()]),
);
write!(f, "{}-{}", name, index)
} else {
write!(f, "{}", String::from_utf8_lossy(b))
}
}
}
}
}
pub struct ConsistentHashRing<V, M: Member<usize>> {
ring: BTreeMap<V, M>,
hasher: HashFn<V>,
replica_counts: HashMap<Bytes, usize>,
}
impl<V, M: Member<usize>> ConsistentHashRing<V, M> {
pub fn new(hasher: HashFn<V>) -> Self {
ConsistentHashRing {
ring: BTreeMap::new(),
hasher,
replica_counts: Default::default(),
}
}
}
impl<H: Ord + Clone, M: Member<usize>> Ring<usize, M> for ConsistentHashRing<H, M> {
fn add_node(&mut self, member_def: M, replicas: usize) {
assert!(replicas > 0, "replicas must be at least 1");
let name = member_def.inner().clone();
if let Some(&existing) = self.replica_counts.get(&name) {
for i in 0..existing {
let v = member_def.make_virtual(i);
let hash = (self.hasher)(v.inner().as_ref());
self.ring.remove(&hash);
}
}
for i in 0..replicas {
let v = member_def.make_virtual(i);
let hash = (self.hasher)(v.inner().as_ref());
self.ring.insert(hash, v);
}
self.replica_counts.insert(name, replicas);
}
fn delete_node(&mut self, member_def: M) {
let name = member_def.inner().clone();
let Some(&replicas) = self.replica_counts.get(&name) else {
return; };
for i in 0..replicas {
let v = member_def.make_virtual(i);
let hash = (self.hasher)(v.inner().as_ref());
self.ring.remove(&hash);
}
self.replica_counts.remove(&name);
}
fn get_node(&self, key: &[u8]) -> Option<M> {
if self.ring.is_empty() {
return None;
}
let hash = (self.hasher)(key);
self.ring
.range(hash..)
.next()
.or_else(|| self.ring.iter().next())
.map(|(_, v)| v.physical_from_virtual())
}
fn get_nodes(&self, key: &[u8], k: usize) -> Vec<M> {
if k == 0 || self.ring.is_empty() {
return Vec::new();
}
let hash = (self.hasher)(key);
let mut out = Vec::with_capacity(k.min(self.replica_counts.len()));
let mut seen = HashSet::new();
for (_, v) in self
.ring
.range(hash.clone()..)
.chain(self.ring.range(..hash))
{
let physical = v.physical_from_virtual();
if seen.insert(physical.inner().clone()) {
out.push(physical);
if out.len() == k {
break;
}
}
}
out
}
fn contains_node(&self, member: &M) -> bool {
self.replica_counts.contains_key(member.inner())
}
fn nodes(&self) -> impl Iterator<Item = &Bytes> {
self.replica_counts.keys()
}
fn prune(&mut self) {
self.ring.clear();
self.replica_counts.clear();
}
fn len(&self) -> usize {
self.ring.len()
}
fn is_empty(&self) -> bool {
self.ring.is_empty()
}
}
#[cfg(test)]
mod tests {
use super::hash::hash128;
use super::*;
fn physical(name: &str) -> RingMember {
RingMember::Physical(Bytes::copy_from_slice(name.as_bytes()))
}
#[test]
fn test_ring() {
let mut ring = ConsistentHashRing::new(hash128);
ring.add_node(physical("node-a"), 32);
ring.add_node(physical("node-b"), 32);
assert_eq!(ring.len(), 64);
let key = Bytes::from_static(b"some-key");
let resolved = ring
.get_node(&key)
.map(|v| v.to_string())
.expect("ring is not empty");
assert!(resolved == "node-a" || resolved == "node-b");
let again = ring.get_node(&key).map(|v| v.to_string()).unwrap();
assert_eq!(resolved, again);
ring.delete_node(physical("node-a"));
ring.delete_node(physical("node-b"));
assert!(ring.is_empty());
assert!(ring.get_node(&key).is_none());
}
#[test]
fn per_node_replicas_and_idempotent_readd() {
let mut ring = ConsistentHashRing::new(hash128);
ring.add_node(physical("heavy"), 40);
ring.add_node(physical("light"), 8);
assert_eq!(ring.len(), 48);
ring.add_node(physical("heavy"), 40);
assert_eq!(ring.len(), 48);
ring.delete_node(physical("ghost"));
assert_eq!(ring.len(), 48);
}
#[test]
fn prune_clears_the_ring() {
let mut ring = ConsistentHashRing::new(hash128);
ring.add_node(physical("node-a"), 8);
ring.prune();
assert!(ring.is_empty());
}
#[test]
fn lookup_wraps_around_past_the_last_node() {
let mut ring = ConsistentHashRing::new(hash128);
ring.add_node(physical("node-a"), 1);
ring.add_node(physical("node-b"), 1);
let key = (0..100_000u32)
.map(|i| i.to_be_bytes())
.find(|bytes| {
let h = hash128(bytes);
ring.ring.range(h..).next().is_none()
})
.expect("a wrap-around key must exist");
let got = ring
.get_node(&key)
.map(|v| v.to_string())
.expect("ring is not empty");
assert!(got == "node-a" || got == "node-b");
}
#[test]
fn get_nodes_returns_distinct_physical_successors() {
let mut ring = ConsistentHashRing::new(hash128);
ring.add_node(physical("node-a"), 8);
ring.add_node(physical("node-b"), 8);
ring.add_node(physical("node-c"), 8);
let two = ring.get_nodes(b"some-key", 2);
assert_eq!(two.len(), 2);
let names: Vec<String> = two.iter().map(|m| m.to_string()).collect();
assert_ne!(names[0], names[1]);
assert_eq!(ring.get_nodes(b"some-key", 10).len(), 3);
assert!(ring.get_nodes(b"some-key", 0).is_empty());
ring.prune();
assert!(ring.get_nodes(b"some-key", 3).is_empty());
}
#[test]
fn accessors_report_membership_and_nodes() {
let mut ring = ConsistentHashRing::new(hash128);
ring.add_node(physical("node-a"), 4);
ring.add_node(physical("node-b"), 4);
assert!(ring.contains_node(&physical("node-a")));
assert!(!ring.contains_node(&physical("ghost")));
let mut names: Vec<&str> = ring
.nodes()
.map(|b| std::str::from_utf8(b).unwrap())
.collect();
names.sort_unstable();
assert_eq!(names, ["node-a", "node-b"]);
ring.delete_node(physical("node-a"));
assert!(!ring.contains_node(&physical("node-a")));
assert_eq!(ring.nodes().count(), 1);
}
}