oxihuman_core/
hash_ring.rs

1#![allow(dead_code)]
2// Copyright (C) 2026 COOLJAPAN OU (Team KitaSan)
3// SPDX-License-Identifier: Apache-2.0
4
5//! Consistent hash ring for distributed key mapping.
6
7use std::collections::BTreeMap;
8
9#[allow(dead_code)]
10#[derive(Debug, Clone)]
11pub struct HashRing {
12    ring: BTreeMap<u64, String>,
13    replicas: usize,
14}
15
16#[allow(dead_code)]
17fn simple_hash(s: &str) -> u64 {
18    let mut h: u64 = 5381;
19    for b in s.bytes() {
20        h = h.wrapping_mul(33).wrapping_add(u64::from(b));
21    }
22    h
23}
24
25#[allow(dead_code)]
26pub fn new_hash_ring(replicas: usize) -> HashRing {
27    HashRing {
28        ring: BTreeMap::new(),
29        replicas: if replicas == 0 { 1 } else { replicas },
30    }
31}
32
33#[allow(dead_code)]
34pub fn add_ring_node(hr: &mut HashRing, node: &str) {
35    for i in 0..hr.replicas {
36        let key = format!("{}#{}", node, i);
37        let h = simple_hash(&key);
38        hr.ring.insert(h, node.to_string());
39    }
40}
41
42#[allow(dead_code)]
43pub fn remove_ring_node(hr: &mut HashRing, node: &str) {
44    hr.ring.retain(|_, v| v != node);
45}
46
47#[allow(dead_code)]
48pub fn get_ring_node(hr: &HashRing, key: &str) -> Option<String> {
49    if hr.ring.is_empty() {
50        return None;
51    }
52    let h = simple_hash(key);
53    let node = hr
54        .ring
55        .range(h..)
56        .next()
57        .or_else(|| hr.ring.iter().next())
58        .map(|(_, v)| v.clone());
59    node
60}
61
62#[allow(dead_code)]
63pub fn ring_node_count(hr: &HashRing) -> usize {
64    let mut nodes: Vec<&String> = hr.ring.values().collect();
65    nodes.sort();
66    nodes.dedup();
67    nodes.len()
68}
69
70#[allow(dead_code)]
71pub fn ring_to_json(hr: &HashRing) -> String {
72    format!(
73        r#"{{"nodes":{},"entries":{},"replicas":{}}}"#,
74        ring_node_count(hr),
75        hr.ring.len(),
76        hr.replicas
77    )
78}
79
80#[allow(dead_code)]
81pub fn ring_rebalance(hr: &mut HashRing) {
82    // Re-insert all nodes to ensure uniform distribution
83    let nodes: Vec<String> = {
84        let mut n: Vec<String> = hr.ring.values().cloned().collect();
85        n.sort();
86        n.dedup();
87        n
88    };
89    hr.ring.clear();
90    for node in &nodes {
91        for i in 0..hr.replicas {
92            let key = format!("{}#{}", node, i);
93            let h = simple_hash(&key);
94            hr.ring.insert(h, node.clone());
95        }
96    }
97}
98
99#[allow(dead_code)]
100pub fn ring_distribution(hr: &HashRing) -> Vec<(String, usize)> {
101    let mut counts = std::collections::HashMap::new();
102    for v in hr.ring.values() {
103        *counts.entry(v.clone()).or_insert(0usize) += 1;
104    }
105    let mut result: Vec<(String, usize)> = counts.into_iter().collect();
106    result.sort_by(|a, b| a.0.cmp(&b.0));
107    result
108}
109
110#[cfg(test)]
111mod tests {
112    use super::*;
113
114    #[test]
115    fn test_new_hash_ring() {
116        let hr = new_hash_ring(3);
117        assert_eq!(ring_node_count(&hr), 0);
118    }
119
120    #[test]
121    fn test_add_node() {
122        let mut hr = new_hash_ring(3);
123        add_ring_node(&mut hr, "node_a");
124        assert_eq!(ring_node_count(&hr), 1);
125    }
126
127    #[test]
128    fn test_remove_node() {
129        let mut hr = new_hash_ring(3);
130        add_ring_node(&mut hr, "node_a");
131        remove_ring_node(&mut hr, "node_a");
132        assert_eq!(ring_node_count(&hr), 0);
133    }
134
135    #[test]
136    fn test_get_node() {
137        let mut hr = new_hash_ring(3);
138        add_ring_node(&mut hr, "node_a");
139        let n = get_ring_node(&hr, "key1");
140        assert!(n.is_some());
141    }
142
143    #[test]
144    fn test_get_node_empty() {
145        let hr = new_hash_ring(3);
146        assert!(get_ring_node(&hr, "key").is_none());
147    }
148
149    #[test]
150    fn test_ring_to_json() {
151        let hr = new_hash_ring(2);
152        let json = ring_to_json(&hr);
153        assert!(json.contains("\"nodes\":0"));
154    }
155
156    #[test]
157    fn test_ring_rebalance() {
158        let mut hr = new_hash_ring(3);
159        add_ring_node(&mut hr, "a");
160        ring_rebalance(&mut hr);
161        assert_eq!(ring_node_count(&hr), 1);
162    }
163
164    #[test]
165    fn test_ring_distribution() {
166        let mut hr = new_hash_ring(3);
167        add_ring_node(&mut hr, "a");
168        add_ring_node(&mut hr, "b");
169        let dist = ring_distribution(&hr);
170        assert_eq!(dist.len(), 2);
171    }
172
173    #[test]
174    fn test_deterministic_lookup() {
175        let mut hr = new_hash_ring(3);
176        add_ring_node(&mut hr, "a");
177        let n1 = get_ring_node(&hr, "key");
178        let n2 = get_ring_node(&hr, "key");
179        assert_eq!(n1, n2);
180    }
181
182    #[test]
183    fn test_zero_replicas() {
184        let hr = new_hash_ring(0);
185        assert_eq!(hr.replicas, 1);
186    }
187}
oxihuman_core/hash_ring.rs

oxihuman_core/
hash_ring.rs
