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