hash_rings/
maglev.rs

1//! Hashing ring implemented using maglev hashing.
2
3use primal::Sieve;
4use rand::{Rng, XorShiftRng};
5use siphasher::sip::SipHasher;
6use std::hash::{Hash, Hasher};
7use std::iter;
8
9/// A hashing ring implemented using maglev hashing.
10///
11/// Maglev hashing produces a lookup table that allows finding a node in constant time by
12/// generating random permutations.
13///
14/// # Examples
15/// ```
16/// use hash_rings::maglev::Ring;
17///
18/// let ring = Ring::new(vec![&"node-1", &"node-2", &"node-3"]);
19///
20/// assert_eq!(ring.get_node(&"point-1"), &"node-3");
21/// assert_eq!(ring.nodes(), 3);
22/// assert_eq!(ring.capacity(), 307);
23/// ```
24pub struct Ring<'a, T> {
25    nodes: Vec<&'a T>,
26    lookup: Vec<usize>,
27    hasher: SipHasher,
28}
29
30impl<'a, T> Ring<'a, T> {
31    fn get_hashers() -> [SipHasher; 2] {
32        let mut rng = XorShiftRng::new_unseeded();
33        [
34            SipHasher::new_with_keys(rng.next_u64(), rng.next_u64()),
35            SipHasher::new_with_keys(rng.next_u64(), rng.next_u64()),
36        ]
37    }
38
39    /// Constructs a new `Ring<T>` with a specified list of nodes.
40    ///
41    /// # Examples
42    ///
43    /// ```
44    /// use hash_rings::maglev::Ring;
45    ///
46    /// let ring = Ring::new(vec![&"node-1", &"node-2", &"node-3"]);
47    /// ```
48    pub fn new(nodes: Vec<&'a T>) -> Self
49    where
50        T: Hash,
51    {
52        assert!(!nodes.is_empty());
53        let capacity_hint = nodes.len() * 100;
54        Ring::with_capacity_hint(nodes, capacity_hint)
55    }
56
57    /// Constructs a new `Ring<T>` with a specified list of nodes and a capacity hint. The actual
58    /// capacity of the ring will always be the next prime greater than or equal to
59    /// `capacity_hint`. If nodes are removed and the ring is regenerated, the ring should be
60    /// rebuilt with the same capacity.
61    ///
62    /// # Examples
63    ///
64    /// ```
65    /// use hash_rings::maglev::Ring;
66    ///
67    /// let ring = Ring::with_capacity_hint(vec![&"node-1", &"node-2", &"node-3"], 100);
68    /// assert_eq!(ring.capacity(), 101);
69    /// ```
70    pub fn with_capacity_hint(nodes: Vec<&'a T>, capacity_hint: usize) -> Self
71    where
72        T: Hash,
73    {
74        let hashers = Self::get_hashers();
75        let lookup = Self::populate(&hashers, &nodes, capacity_hint);
76        Self {
77            nodes,
78            lookup,
79            hasher: hashers[0],
80        }
81    }
82
83    fn get_hash<U>(hasher: SipHasher, key: &U) -> usize
84    where
85        U: Hash,
86    {
87        let mut sip = hasher;
88        key.hash(&mut sip);
89        sip.finish() as usize
90    }
91
92    fn populate(hashers: &[SipHasher; 2], nodes: &[&T], capacity_hint: usize) -> Vec<usize>
93    where
94        T: 'a + Hash,
95    {
96        let m = Sieve::new(capacity_hint * 2)
97            .primes_from(capacity_hint)
98            .next()
99            .expect("Expected a prime larger than or equal to `capacity_hint`.");
100        let n = nodes.len();
101
102        let permutation: Vec<Vec<usize>> = nodes
103            .iter()
104            .map(|node| {
105                let offset = Self::get_hash(hashers[0], node) % m;
106                let skip = (Self::get_hash(hashers[1], node) % (m - 1)) + 1;
107                (0..m).map(|i| (offset + i * skip) % m).collect()
108            })
109            .collect();
110
111        let mut next: Vec<usize> = iter::repeat(0).take(n).collect();
112        let mut entry: Vec<usize> = iter::repeat(<usize>::max_value()).take(m).collect();
113
114        let mut i = 0;
115        while i < m {
116            for j in 0..n {
117                let mut c = permutation[j][next[j]];
118                while entry[c] != <usize>::max_value() {
119                    next[j] += 1;
120                    c = permutation[j][next[j]];
121                }
122                entry[c] = j;
123                next[j] += 1;
124                i += 1;
125
126                if i == m {
127                    break;
128                }
129            }
130        }
131
132        entry
133    }
134
135    /// Returns the number of nodes in the ring.
136    ///
137    /// # Examples
138    ///
139    /// ```
140    /// use hash_rings::maglev::Ring;
141    ///
142    /// let ring = Ring::new(vec![&"node-1", &"node-2", &"node-3"]);
143    /// assert_eq!(ring.nodes(), 3);
144    /// ```
145    pub fn nodes(&self) -> usize {
146        self.nodes.len()
147    }
148
149    /// Returns the capacity of the ring. If nodes are removed and the ring is regenerated, the
150    /// ring should be rebuilt with the same capacity.
151    ///
152    /// # Examples
153    ///
154    /// ```
155    /// use hash_rings::maglev::Ring;
156    ///
157    /// let ring = Ring::new(vec![&"node-1", &"node-2", &"node-3"]);
158    /// assert_eq!(ring.capacity(), 307);
159    /// ```
160    pub fn capacity(&self) -> usize {
161        self.lookup.len()
162    }
163
164    /// Returns the node associated with a key.
165    ///
166    /// # Examples
167    ///
168    /// ```
169    /// use hash_rings::maglev::Ring;
170    ///
171    /// let ring = Ring::new(vec![&"node-1", &"node-2", &"node-3"]);
172    /// assert_eq!(ring.get_node(&"point-1"), &"node-3");
173    /// ```
174    pub fn get_node<U>(&self, key: &U) -> &T
175    where
176        U: Hash,
177    {
178        let index = Self::get_hash(self.hasher, key) % self.capacity();
179        self.nodes[self.lookup[index]]
180    }
181
182    /// Returns an iterator over the ring. The iterator will yield the nodes in the ring.
183    ///
184    /// # Examples
185    ///
186    /// ```
187    /// use hash_rings::maglev::Ring;
188    ///
189    /// let ring = Ring::new(vec![&"node-1", &"node-2", &"node-3"]);
190    ///
191    /// let mut iterator = ring.iter();
192    /// assert_eq!(iterator.next(), Some(&"node-1"));
193    /// assert_eq!(iterator.next(), Some(&"node-2"));
194    /// assert_eq!(iterator.next(), Some(&"node-3"));
195    /// assert_eq!(iterator.next(), None);
196    /// ```
197    pub fn iter(&'a self) -> impl Iterator<Item = &'a T> {
198        self.nodes.iter().cloned()
199    }
200}
201
202impl<'a, T> IntoIterator for &'a Ring<'a, T>
203where
204    T: Hash + Eq,
205{
206    type IntoIter = Box<dyn Iterator<Item = &'a T> + 'a>;
207    type Item = (&'a T);
208
209    fn into_iter(self) -> Self::IntoIter {
210        Box::new(self.iter())
211    }
212}
213
214#[cfg(test)]
215mod tests {
216    use super::Ring;
217
218    #[test]
219    #[should_panic]
220    fn test_new_empty() {
221        let _ring: Ring<'_, u32> = Ring::new(vec![]);
222    }
223
224    #[test]
225    fn test_get_node() {
226        let ring = Ring::new(vec![&0, &1, &2]);
227        assert_eq!(ring.get_node(&0), &0);
228        assert_eq!(ring.get_node(&1), &1);
229
230        let ring = Ring::with_capacity_hint(vec![&0, &1], ring.capacity());
231        assert_eq!(ring.get_node(&0), &0);
232        assert_eq!(ring.get_node(&1), &1);
233    }
234
235    #[test]
236    fn test_nodes() {
237        let ring = Ring::new(vec![&0, &1, &2]);
238        assert_eq!(ring.nodes(), 3);
239    }
240
241    #[test]
242    fn test_capacity() {
243        let ring = Ring::new(vec![&0, &1, &2]);
244        assert_eq!(ring.capacity(), 307);
245
246        let ring = Ring::with_capacity_hint(vec![&0, &1], ring.capacity());
247        assert_eq!(ring.capacity(), 307);
248    }
249
250    #[test]
251    fn test_iter() {
252        let ring = Ring::new(vec![&0, &1, &2]);
253
254        let mut iterator = ring.iter();
255        assert_eq!(iterator.next(), Some(&0));
256        assert_eq!(iterator.next(), Some(&1));
257        assert_eq!(iterator.next(), Some(&2));
258        assert_eq!(iterator.next(), None);
259    }
260}
hash_rings/maglev.rs

hash_rings/
maglev.rs
