hash_rings/rendezvous.rs
1//! Hashing ring implemented using rendezvous hashing.
2
3use crate::util;
4use std::collections::hash_map::RandomState;
5use std::collections::{HashMap, HashSet};
6use std::hash::{BuildHasher, Hash};
7use std::vec::Vec;
8
9/// A hashing ring implemented using rendezvous hashing.
10///
11/// Rendezvous hashing is based on based on assigning a pseudorandom value to node-point pair.
12/// A point is mapped to the node that yields the greatest value associated with the node-point
13/// pair. By mapping the weights to `[0, 1)` using logarithms, rendezvous hashing can be modified
14/// to handle weighted nodes.
15///
16/// # Examples
17/// ```
18/// use hash_rings::rendezvous::Ring;
19/// use std::collections::hash_map::DefaultHasher;
20/// use std::hash::BuildHasherDefault;
21///
22/// type DefaultBuildHasher = BuildHasherDefault<DefaultHasher>;
23///
24/// let mut ring = Ring::with_hasher(DefaultBuildHasher::default());
25///
26/// ring.insert_node(&"node-1", 1);
27/// ring.insert_node(&"node-2", 3);
28///
29/// ring.remove_node(&"node-1");
30///
31/// assert_eq!(ring.get_node(&"point-1"), &"node-2");
32/// assert_eq!(ring.len(), 1);
33///
34/// let mut iterator = ring.iter();
35/// assert_eq!(iterator.next(), Some((&"node-2", 3)));
36/// assert_eq!(iterator.next(), None);
37/// ```
38pub struct Ring<'a, T, H = RandomState> {
39 nodes: HashMap<&'a T, Vec<u64>>,
40 hash_builder: H,
41}
42
43impl<'a, T> Ring<'a, T, RandomState> {
44 /// Constructs a new, empty `Ring<T>`.
45 ///
46 /// # Examples
47 ///
48 /// ```
49 /// use hash_rings::rendezvous::Ring;
50 ///
51 /// let mut ring: Ring<&str> = Ring::new();
52 /// ```
53 pub fn new() -> Self
54 where
55 T: Hash + Eq,
56 {
57 Self::default()
58 }
59}
60
61impl<'a, T, H> Ring<'a, T, H> {
62 /// Constructs a new, empty `Ring<T>` with a specified hash builder.
63 ///
64 /// # Examples
65 ///
66 /// ```
67 /// use hash_rings::rendezvous::Ring;
68 /// use std::collections::hash_map::DefaultHasher;
69 /// use std::hash::BuildHasherDefault;
70 ///
71 /// type DefaultBuildHasher = BuildHasherDefault<DefaultHasher>;
72 ///
73 /// let mut ring: Ring<&str, _> = Ring::with_hasher(DefaultBuildHasher::default());
74 /// ```
75 pub fn with_hasher(hash_builder: H) -> Self
76 where
77 T: Hash + Eq,
78 H: BuildHasher,
79 {
80 Self {
81 nodes: HashMap::new(),
82 hash_builder,
83 }
84 }
85
86 /// Inserts a node into the ring with a number of replicas.
87 ///
88 /// Increasing the number of replicas will increase the number of expected points mapped to the
89 /// node. For example, a node with three replicas will receive approximately three times more
90 /// points than a node with one replica.
91 ///
92 /// # Examples
93 ///
94 /// ```
95 /// use hash_rings::rendezvous::Ring;
96 ///
97 /// let mut ring: Ring<&str> = Ring::new();
98 ///
99 /// // "node-2" will receive three times more points than "node-1"
100 /// ring.insert_node(&"node-1", 1);
101 /// ring.insert_node(&"node-2", 3);
102 /// ```
103 pub fn insert_node(&mut self, id: &'a T, replicas: usize)
104 where
105 T: Hash + Eq,
106 H: BuildHasher,
107 {
108 let hashes = (0..replicas)
109 .map(|index| {
110 util::combine_hash(
111 &self.hash_builder,
112 util::gen_hash(&self.hash_builder, id),
113 util::gen_hash(&self.hash_builder, &index),
114 )
115 })
116 .collect();
117 self.nodes.insert(id, hashes);
118 }
119
120 /// Removes a node and all its replicas from the ring.
121 ///
122 /// # Examples
123 ///
124 /// ```
125 /// use hash_rings::rendezvous::Ring;
126 ///
127 /// let mut ring: Ring<&str> = Ring::new();
128 ///
129 /// ring.insert_node(&"node-1", 1);
130 /// ring.insert_node(&"node-2", 1);
131 /// ring.remove_node(&"node-2");
132 /// ```
133 pub fn remove_node(&mut self, id: &T)
134 where
135 T: Hash + Eq,
136 {
137 self.nodes.remove(id);
138 }
139
140 /// Returns the node associated with a point.
141 ///
142 /// # Panics
143 ///
144 /// Panics if the ring is empty.
145 ///
146 /// # Examples
147 ///
148 /// ```
149 /// use hash_rings::rendezvous::Ring;
150 ///
151 /// let mut ring: Ring<&str> = Ring::new();
152 ///
153 /// ring.insert_node(&"node-1", 1);
154 /// assert_eq!(ring.get_node(&"point-1"), &"node-1");
155 /// ```
156 pub fn get_node<U>(&self, id: &U) -> &'a T
157 where
158 T: Hash + Ord,
159 U: Hash,
160 H: BuildHasher,
161 {
162 let point_hash = util::gen_hash(&self.hash_builder, id);
163 self.nodes
164 .iter()
165 .map(|entry| {
166 (
167 entry
168 .1
169 .iter()
170 .map(|hash| util::combine_hash(&self.hash_builder, *hash, point_hash))
171 .max()
172 .expect("Expected non-zero number of replicas."),
173 entry.0,
174 )
175 })
176 .max()
177 .expect("Expected non-empty ring.")
178 .1
179 }
180
181 fn get_hashes(&self, id: &T) -> Vec<u64>
182 where
183 T: Hash + Eq,
184 {
185 self.nodes[id].clone()
186 }
187
188 /// Returns the number of nodes in the ring.
189 ///
190 /// # Examples
191 ///
192 /// ```
193 /// use hash_rings::rendezvous::Ring;
194 ///
195 /// let mut ring: Ring<&str> = Ring::new();
196 ///
197 /// ring.insert_node(&"node-1", 3);
198 /// assert_eq!(ring.len(), 1);
199 /// ```
200 pub fn len(&self) -> usize
201 where
202 T: Hash + Eq,
203 {
204 self.nodes.len()
205 }
206
207 /// Returns `true` if the ring is empty.
208 ///
209 /// # Examples
210 ///
211 /// ```
212 /// use hash_rings::rendezvous::Ring;
213 ///
214 /// let mut ring: Ring<&str> = Ring::new();
215 ///
216 /// assert!(ring.is_empty());
217 /// ring.insert_node(&"node-1", 3);
218 /// assert!(!ring.is_empty());
219 /// ```
220 pub fn is_empty(&self) -> bool
221 where
222 T: Hash + Eq,
223 {
224 self.nodes.is_empty()
225 }
226
227 /// Returns an iterator over the ring. The iterator will yield nodes and the replica count in
228 /// no particular order.
229 ///
230 /// # Examples
231 ///
232 /// ```
233 /// use hash_rings::rendezvous::Ring;
234 ///
235 /// let mut ring = Ring::new();
236 /// ring.insert_node(&"node-1", 1);
237 ///
238 /// let mut iterator = ring.iter();
239 /// assert_eq!(iterator.next(), Some((&"node-1", 1)));
240 /// assert_eq!(iterator.next(), None);
241 /// ```
242 pub fn iter(&'a self) -> impl Iterator<Item = (&'a T, usize)>
243 where
244 T: Hash + Eq,
245 {
246 self.nodes.iter().map(|node_entry| {
247 let (id, hashes) = node_entry;
248 (&**id, hashes.len())
249 })
250 }
251}
252
253impl<'a, T, H> IntoIterator for &'a Ring<'a, T, H>
254where
255 T: Hash + Eq,
256{
257 type IntoIter = Box<dyn Iterator<Item = (&'a T, usize)> + 'a>;
258 type Item = (&'a T, usize);
259
260 fn into_iter(self) -> Self::IntoIter {
261 Box::new(self.iter())
262 }
263}
264
265impl<'a, T, H> Default for Ring<'a, T, H>
266where
267 T: Hash + Eq,
268 H: BuildHasher + Default,
269{
270 fn default() -> Self {
271 Self::with_hasher(Default::default())
272 }
273}
274
275/// A client that uses `Ring<T>`.
276///
277/// # Examples
278/// ```
279/// use hash_rings::rendezvous::Client;
280///
281/// let mut client = Client::new();
282/// client.insert_node(&"node-1", 3);
283/// client.insert_point(&"point-1");
284/// client.insert_point(&"point-2");
285///
286/// assert_eq!(client.len(), 1);
287/// assert_eq!(client.get_node(&"point-1"), &"node-1");
288///
289/// client.remove_point(&"point-2");
290/// assert_eq!(client.get_points(&"node-1"), [&"point-1"]);
291/// ```
292pub struct Client<'a, T, U, H = RandomState> {
293 ring: Ring<'a, T, H>,
294 nodes: HashMap<&'a T, HashSet<&'a U>>,
295 points: HashMap<&'a U, (&'a T, u64)>,
296 hash_builder: H,
297}
298
299impl<'a, T, U> Client<'a, T, U, RandomState> {
300 /// Constructs a new, empty `Client<T, U>`.
301 ///
302 /// # Examples
303 ///
304 /// ```
305 /// use hash_rings::rendezvous::Client;
306 ///
307 /// let mut client: Client<&str, &str> = Client::new();
308 /// ```
309 pub fn new() -> Self
310 where
311 T: Hash + Eq,
312 U: Hash + Eq,
313 {
314 Self::default()
315 }
316}
317
318impl<'a, T, U, H> Client<'a, T, U, H> {
319 /// Constructs a new, empty `Client<T, U>` with a specified hash builder.
320 ///
321 /// # Examples
322 ///
323 /// ```
324 /// use hash_rings::rendezvous::Client;
325 /// use std::collections::hash_map::DefaultHasher;
326 /// use std::hash::BuildHasherDefault;
327 ///
328 /// type DefaultBuildHasher = BuildHasherDefault<DefaultHasher>;
329 ///
330 /// let mut client: Client<&str, &str, _> = Client::with_hasher(DefaultBuildHasher::default());
331 /// ```
332 pub fn with_hasher(hash_builder: H) -> Self
333 where
334 T: Hash + Eq,
335 U: Hash + Eq,
336 H: BuildHasher + Clone,
337 {
338 Self {
339 ring: Ring::with_hasher(hash_builder.clone()),
340 nodes: HashMap::new(),
341 points: HashMap::new(),
342 hash_builder,
343 }
344 }
345
346 /// Inserts a node into the ring with a number of replicas.
347 ///
348 /// Increasing the number of replicas will increase the number of expected points mapped to the
349 /// node. For example, a node with three replicas will receive approximately three times more
350 /// points than a node with one replica.
351 ///
352 /// # Examples
353 ///
354 /// ```
355 /// use hash_rings::rendezvous::Client;
356 ///
357 /// let mut client: Client<&str, &str> = Client::new();
358 ///
359 /// // "node-2" will receive three times more points than "node-1"
360 /// client.insert_node(&"node-1", 1);
361 /// client.insert_node(&"node-2", 3);
362 /// ```
363 pub fn insert_node(&mut self, id: &'a T, replicas: usize)
364 where
365 T: Hash + Eq,
366 U: Hash + Eq,
367 H: BuildHasher,
368 {
369 self.ring.insert_node(id, replicas);
370 let hashes = self.ring.get_hashes(id);
371
372 let mut new_points = HashSet::new();
373
374 let Client {
375 ref mut points,
376 ref mut nodes,
377 ref hash_builder,
378 ..
379 } = self;
380 for (point, node_entry) in points {
381 let (ref mut original_node, ref mut original_score) = node_entry;
382 let point_hash = util::gen_hash(hash_builder, point);
383 let max_score = hashes
384 .iter()
385 .map(|hash| util::combine_hash(hash_builder, *hash, point_hash))
386 .max()
387 .expect("Expected non-zero number of replicas.");
388
389 if max_score > *original_score {
390 nodes
391 .get_mut(original_node)
392 .expect("Expected node to exist.")
393 .remove(point);
394 new_points.insert(*point);
395 *original_score = max_score;
396 *original_node = id;
397 }
398 }
399
400 self.nodes.insert(id, new_points);
401 }
402
403 /// Removes a node and all its replicas from the ring.
404 ///
405 /// # Panics
406 ///
407 /// Panics if the ring is empty after removal of a node or if the node does not exist.
408 ///
409 /// # Examples
410 ///
411 /// ```
412 /// use hash_rings::rendezvous::Client;
413 ///
414 /// let mut client: Client<&str, &str> = Client::new();
415 ///
416 /// client.insert_node(&"node-1", 1);
417 /// client.insert_node(&"node-2", 1);
418 /// client.remove_node(&"node-1");
419 /// ```
420 pub fn remove_node(&mut self, id: &T)
421 where
422 T: Hash + Ord,
423 U: Hash + Eq,
424 H: BuildHasher,
425 {
426 self.ring.remove_node(id);
427 if self.ring.is_empty() {
428 panic!("Error: empty ring after deletion.");
429 }
430 if let Some(points) = self.nodes.remove(id) {
431 for point in points {
432 let new_node = self.ring.get_node(point);
433 let hashes = self.ring.get_hashes(new_node);
434 let point_hash = util::gen_hash(&self.hash_builder, point);
435 let max_score = hashes
436 .iter()
437 .map(|hash| util::combine_hash(&self.hash_builder, *hash, point_hash))
438 .max()
439 .expect("Expected non-zero number of replicas");
440
441 self.nodes
442 .get_mut(new_node)
443 .expect("Expected node to exist.")
444 .insert(point);
445 self.points.insert(point, (new_node, max_score));
446 }
447 }
448 }
449
450 /// Returns the points associated with a node and its replicas.
451 ///
452 /// # Panics
453 ///
454 /// Panics if the node does not exist.
455 ///
456 /// # Examples
457 ///
458 /// ```
459 /// use hash_rings::rendezvous::Client;
460 ///
461 /// let mut client: Client<&str, &str> = Client::new();
462 ///
463 /// client.insert_node(&"node-1", 1);
464 /// client.insert_point(&"point-1");
465 /// assert_eq!(client.get_points(&"node-1"), [&"point-1"]);
466 /// ```
467 pub fn get_points(&self, id: &T) -> Vec<&U>
468 where
469 T: Hash + Eq,
470 U: Hash + Eq,
471 {
472 self.nodes[id].iter().cloned().collect()
473 }
474
475 /// Returns the node associated with a point.
476 ///
477 /// # Panics
478 ///
479 /// Panics if the ring is empty.
480 ///
481 /// # Examples
482 ///
483 /// ```
484 /// use hash_rings::rendezvous::Client;
485 ///
486 /// let mut client: Client<&str, &str> = Client::new();
487 ///
488 /// client.insert_node(&"node-1", 1);
489 /// client.insert_point(&"point-1");
490 /// assert_eq!(client.get_node(&"point-1"), &"node-1");
491 /// ```
492 pub fn get_node(&self, point: &U) -> &T
493 where
494 T: Hash + Ord,
495 U: Hash + Eq,
496 H: BuildHasher,
497 {
498 self.ring.get_node(point)
499 }
500
501 /// Inserts a point into the ring and returns the node associated with the inserted point.
502 ///
503 /// # Panics
504 ///
505 /// Panics if the ring is empty.
506 ///
507 /// # Examples
508 ///
509 /// ```
510 /// use hash_rings::rendezvous::Client;
511 ///
512 /// let mut client = Client::new();
513 /// client.insert_node(&"node-1", 1);
514 /// client.insert_point(&"point-1");
515 /// ```
516 pub fn insert_point(&mut self, point: &'a U) -> &T
517 where
518 T: Hash + Ord,
519 U: Hash + Eq,
520 H: BuildHasher,
521 {
522 let node = self.ring.get_node(point);
523 let hashes = self.ring.get_hashes(node);
524 let point_hash = util::gen_hash(&self.hash_builder, point);
525 let max_score = hashes
526 .iter()
527 .map(|hash| util::combine_hash(&self.hash_builder, *hash, point_hash))
528 .max()
529 .expect("Expected non-zero number of replicas.");
530 self.nodes
531 .get_mut(node)
532 .expect("Expected node to exist.")
533 .insert(point);
534 self.points.insert(point, (node, max_score));
535 node
536 }
537
538 /// Removes a point from the ring.
539 ///
540 /// # Panics
541 ///
542 /// Panics if the ring is empty.
543 ///
544 /// # Examples
545 ///
546 /// ```
547 /// use hash_rings::rendezvous::Client;
548 ///
549 /// let mut client = Client::new();
550 /// client.insert_node(&"node-1", 1);
551 /// client.insert_point(&"point-1");
552 /// client.remove_point(&"point-1");
553 /// ```
554 pub fn remove_point(&mut self, point: &U)
555 where
556 T: Hash + Ord,
557 U: Hash + Eq,
558 H: BuildHasher,
559 {
560 let node = self.ring.get_node(point);
561 self.nodes
562 .get_mut(node)
563 .expect("Expected node to exist.")
564 .remove(point);
565 self.points.remove(point);
566 }
567
568 /// Returns the number of nodes in the ring.
569 ///
570 /// # Examples
571 ///
572 /// ```
573 /// use hash_rings::rendezvous::Client;
574 ///
575 /// let mut client: Client<&str, &str> = Client::new();
576 ///
577 /// client.insert_node(&"node-1", 3);
578 /// assert_eq!(client.len(), 1);
579 /// ```
580 pub fn len(&self) -> usize
581 where
582 T: Hash + Eq,
583 {
584 self.nodes.len()
585 }
586
587 /// Returns `true` if the ring is empty.
588 ///
589 /// # Examples
590 ///
591 /// ```
592 /// use hash_rings::rendezvous::Client;
593 ///
594 /// let mut client: Client<&str, &str> = Client::new();
595 ///
596 /// assert!(client.is_empty());
597 /// client.insert_node(&"node-1", 3);
598 /// assert!(!client.is_empty());
599 /// ```
600 pub fn is_empty(&self) -> bool
601 where
602 T: Hash + Eq,
603 {
604 self.ring.is_empty()
605 }
606
607 /// Returns an iterator over the ring. The iterator will yield nodes and points in no
608 /// particular order.
609 ///
610 /// # Examples
611 ///
612 /// ```
613 /// use hash_rings::rendezvous::Client;
614 ///
615 /// let mut client = Client::new();
616 /// client.insert_node(&"node-1", 1);
617 /// client.insert_point(&"point-1");
618 ///
619 /// let mut iterator = client.iter();
620 /// assert_eq!(iterator.next(), Some((&"node-1", vec![&"point-1"])));
621 /// assert_eq!(iterator.next(), None);
622 /// ```
623 pub fn iter(&'a self) -> impl Iterator<Item = (&'a T, Vec<&'a U>)>
624 where
625 T: Hash + Eq,
626 U: Hash + Eq,
627 {
628 self.nodes.iter().map(move |node_entry| {
629 let (node_id, points) = node_entry;
630 (&**node_id, points.iter().cloned().collect())
631 })
632 }
633}
634
635impl<'a, T, U, H> IntoIterator for &'a Client<'a, T, U, H>
636where
637 T: Hash + Eq,
638 U: Hash + Eq,
639{
640 type IntoIter = Box<dyn Iterator<Item = (&'a T, Vec<&'a U>)> + 'a>;
641 type Item = (&'a T, Vec<&'a U>);
642
643 fn into_iter(self) -> Self::IntoIter {
644 Box::new(self.iter())
645 }
646}
647
648impl<'a, T, U, H> Default for Client<'a, T, U, H>
649where
650 T: Hash + Eq,
651 U: Hash + Eq,
652 H: BuildHasher + Default + Clone,
653{
654 fn default() -> Self {
655 Self::with_hasher(Default::default())
656 }
657}
658
659#[cfg(test)]
660mod tests {
661 use super::{Client, Ring};
662 use crate::test_util::BuildDefaultHasher;
663
664 #[test]
665 fn test_size_empty() {
666 let client: Client<'_, u32, u32, BuildDefaultHasher> = Client::default();
667 assert!(client.is_empty());
668 assert_eq!(client.len(), 0);
669 }
670
671 #[test]
672 #[should_panic]
673 fn test_panic_remove_node_empty_client() {
674 let mut client: Client<'_, u32, u32, BuildDefaultHasher> = Client::default();
675 client.insert_node(&0, 1);
676 client.remove_node(&0);
677 }
678
679 #[test]
680 #[should_panic]
681 fn test_panic_remove_node_non_existent_node() {
682 let mut client: Client<'_, u32, u32, BuildDefaultHasher> = Client::default();
683 client.remove_node(&0);
684 }
685
686 #[test]
687 #[should_panic]
688 fn test_panic_get_node_empty_client() {
689 let mut client: Client<'_, u32, u32, BuildDefaultHasher> = Client::default();
690 client.get_node(&0);
691 }
692
693 #[test]
694 #[should_panic]
695 fn test_panic_insert_point_empty_client() {
696 let mut client: Client<'_, u32, u32, BuildDefaultHasher> = Client::default();
697 client.insert_point(&0);
698 }
699
700 #[test]
701 #[should_panic]
702 fn test_panic_remove_point_empty_client() {
703 let mut client: Client<'_, u32, u32, BuildDefaultHasher> = Client::default();
704 client.remove_point(&0);
705 }
706
707 #[test]
708 fn test_insert_node() {
709 let mut client: Client<'_, u32, u32, BuildDefaultHasher> = Client::default();
710 client.insert_node(&1, 1);
711 client.insert_point(&0);
712 client.insert_node(&0, 1);
713 assert_eq!(client.get_points(&0), [&0u32]);
714 }
715
716 #[test]
717 fn test_remove_node() {
718 let mut client: Client<'_, u32, u32, BuildDefaultHasher> = Client::default();
719 client.insert_node(&0, 1);
720 client.insert_point(&0);
721 client.insert_point(&1);
722 client.insert_point(&2);
723 client.insert_node(&1, 1);
724 client.remove_node(&1);
725
726 let points = client.get_points(&0);
727
728 assert!(points.contains(&&0u32));
729 assert!(points.contains(&&1u32));
730 assert!(points.contains(&&2u32));
731 }
732
733 #[test]
734 fn test_get_node() {
735 let mut client: Client<'_, u32, u32, BuildDefaultHasher> = Client::default();
736 client.insert_node(&0, 3);
737 assert_eq!(client.get_node(&0), &0);
738 }
739
740 #[test]
741 fn test_insert_point() {
742 let mut client: Client<'_, u32, u32, BuildDefaultHasher> = Client::default();
743 client.insert_node(&0, 3);
744 client.insert_point(&0);
745 assert_eq!(client.get_points(&0), [&0u32]);
746 }
747
748 #[test]
749 fn test_remove_point() {
750 let mut client: Client<'_, u32, u32, BuildDefaultHasher> = Client::default();
751 client.insert_node(&0, 3);
752 client.insert_point(&0);
753 client.remove_point(&0);
754 let expected: [&u32; 0] = [];
755 assert_eq!(client.get_points(&0), expected);
756 }
757
758 #[test]
759 fn test_iter() {
760 let mut client: Client<'_, u32, u32, BuildDefaultHasher> = Client::default();
761 client.insert_node(&0, 3);
762 client.insert_point(&1);
763 client.insert_point(&2);
764 client.insert_point(&3);
765 client.insert_point(&4);
766 client.insert_point(&5);
767 let mut actual: Vec<(&u32, Vec<&u32>)> = client.iter().collect();
768 actual[0].1.sort();
769 assert_eq!(actual[0].0, &0);
770 assert_eq!(actual[0].1, [&1, &2, &3, &4, &5]);
771 }
772
773 #[test]
774 fn test_ring_len() {
775 let mut ring = Ring::with_hasher(BuildDefaultHasher::default());
776
777 ring.insert_node(&0, 1);
778 assert_eq!(ring.len(), 1);
779 }
780
781 #[test]
782 fn test_ring_iter() {
783 let mut ring = Ring::with_hasher(BuildDefaultHasher::default());
784
785 ring.insert_node(&0, 1);
786 let mut iterator = ring.iter();
787 assert_eq!(iterator.next(), Some((&0, 1)));
788 assert_eq!(iterator.next(), None);
789 }
790}