scylla/routing/locator/
token_ring.rs

1use crate::routing::Token;
2
3/// A token ring is a continuous hash ring. It defines association by hashing a key
4/// onto the ring and then walking the ring in one direction.
5/// Cassandra and Scylla use it for determining data ownership which allows for efficient load balancing.
6/// The token ring is used by the driver to find the replicas for a given token.
7/// Each ring member has a token (i64 number) which defines the member's position on the ring.
8/// The ring is circular and can be traversed in the order of increasing tokens.
9/// `TokenRing` makes it easy and efficient to traverse the ring starting at a given token.
10#[derive(Debug, Clone)]
11pub struct TokenRing<ElemT> {
12    ring: Vec<(Token, ElemT)>,
13}
14
15impl<ElemT> TokenRing<ElemT> {
16    pub(crate) const fn new_empty() -> TokenRing<ElemT> {
17        Self { ring: Vec::new() }
18    }
19
20    pub(crate) fn new(ring_iter: impl Iterator<Item = (Token, ElemT)>) -> TokenRing<ElemT> {
21        let mut ring: Vec<(Token, ElemT)> = ring_iter.collect();
22        ring.sort_by(|a, b| a.0.cmp(&b.0));
23        TokenRing { ring }
24    }
25
26    /// Iterates over all members of the ring starting at the lowest token.
27    pub fn iter(&self) -> impl Iterator<Item = &(Token, ElemT)> {
28        self.ring.iter()
29    }
30
31    /// Provides an iterator over the ring members starting at the given token.
32    /// The iterator traverses the whole ring in the direction of increasing tokens.
33    /// After reaching the maximum token it wraps around and continues from the lowest one.
34    /// The iterator visits each member once, it doesn't have infinite length.
35    pub fn ring_range_full(&self, token: Token) -> impl Iterator<Item = &(Token, ElemT)> {
36        let binary_search_index: usize = match self.ring.binary_search_by(|e| e.0.cmp(&token)) {
37            Ok(exact_match_index) => exact_match_index,
38            Err(first_greater_index) => first_greater_index,
39        };
40
41        self.ring[binary_search_index..]
42            .iter()
43            .chain(self.ring.iter())
44            .take(self.ring.len())
45    }
46
47    /// Provides an iterator over the ring's elements starting at the given token.
48    /// The iterator traverses the whole ring in the direction of increasing tokens.
49    /// After reaching the maximum token it wraps around and continues from the lowest one.
50    /// The iterator visits each member once, it doesn't have an infinite length.
51    /// To access the token along with the element you can use `ring_range_full`.
52    pub fn ring_range(&self, token: Token) -> impl Iterator<Item = &ElemT> {
53        self.ring_range_full(token).map(|(_t, e)| e)
54    }
55
56    /// Traverses the ring starting at the given token and returns the first ring member encountered.
57    pub fn get_elem_for_token(&self, token: Token) -> Option<&ElemT> {
58        self.ring_range(token).next()
59    }
60
61    /// Get the total number of members in the ring.
62    pub fn len(&self) -> usize {
63        self.ring.len()
64    }
65
66    /// Returns `true` if the token ring contains no elements.
67    pub fn is_empty(&self) -> bool {
68        self.ring.is_empty()
69    }
70}
71
72#[cfg(test)]
73mod tests {
74    use super::TokenRing;
75    use crate::{routing::Token, test_utils::setup_tracing};
76
77    #[test]
78    fn test_token_ring() {
79        setup_tracing();
80        let ring_data = [
81            (Token::new(-30), -3),
82            (Token::new(-20), -2),
83            (Token::new(-10), -1),
84            (Token::new(0), 0),
85            (Token::new(10), 1),
86            (Token::new(20), 2),
87            (Token::new(30), 3),
88        ];
89
90        let ring: TokenRing<i32> = TokenRing::new(ring_data.into_iter());
91
92        assert_eq!(
93            ring.ring_range(Token::new(-35))
94                .cloned()
95                .collect::<Vec<i32>>(),
96            vec![-3, -2, -1, 0, 1, 2, 3]
97        );
98
99        assert_eq!(
100            ring.ring_range(Token::new(-30))
101                .cloned()
102                .collect::<Vec<i32>>(),
103            vec![-3, -2, -1, 0, 1, 2, 3]
104        );
105
106        assert_eq!(
107            ring.ring_range(Token::new(-25))
108                .cloned()
109                .collect::<Vec<i32>>(),
110            vec![-2, -1, 0, 1, 2, 3, -3]
111        );
112
113        assert_eq!(
114            ring.ring_range(Token::new(-20))
115                .cloned()
116                .collect::<Vec<i32>>(),
117            vec![-2, -1, 0, 1, 2, 3, -3]
118        );
119
120        assert_eq!(
121            ring.ring_range(Token::new(-15))
122                .cloned()
123                .collect::<Vec<i32>>(),
124            vec![-1, 0, 1, 2, 3, -3, -2]
125        );
126
127        assert_eq!(
128            ring.ring_range(Token::new(-10))
129                .cloned()
130                .collect::<Vec<i32>>(),
131            vec![-1, 0, 1, 2, 3, -3, -2]
132        );
133
134        assert_eq!(
135            ring.ring_range(Token::new(-5))
136                .cloned()
137                .collect::<Vec<i32>>(),
138            vec![0, 1, 2, 3, -3, -2, -1]
139        );
140
141        assert_eq!(
142            ring.ring_range(Token::new(0))
143                .cloned()
144                .collect::<Vec<i32>>(),
145            vec![0, 1, 2, 3, -3, -2, -1]
146        );
147
148        assert_eq!(
149            ring.ring_range(Token::new(5))
150                .cloned()
151                .collect::<Vec<i32>>(),
152            vec![1, 2, 3, -3, -2, -1, 0]
153        );
154
155        assert_eq!(
156            ring.ring_range(Token::new(10))
157                .cloned()
158                .collect::<Vec<i32>>(),
159            vec![1, 2, 3, -3, -2, -1, 0]
160        );
161
162        assert_eq!(
163            ring.ring_range(Token::new(15))
164                .cloned()
165                .collect::<Vec<i32>>(),
166            vec![2, 3, -3, -2, -1, 0, 1]
167        );
168
169        assert_eq!(
170            ring.ring_range(Token::new(20))
171                .cloned()
172                .collect::<Vec<i32>>(),
173            vec![2, 3, -3, -2, -1, 0, 1]
174        );
175
176        assert_eq!(
177            ring.ring_range(Token::new(25))
178                .cloned()
179                .collect::<Vec<i32>>(),
180            vec![3, -3, -2, -1, 0, 1, 2]
181        );
182
183        assert_eq!(
184            ring.ring_range(Token::new(30))
185                .cloned()
186                .collect::<Vec<i32>>(),
187            vec![3, -3, -2, -1, 0, 1, 2]
188        );
189
190        assert_eq!(
191            ring.ring_range(Token::new(35))
192                .cloned()
193                .collect::<Vec<i32>>(),
194            vec![-3, -2, -1, 0, 1, 2, 3]
195        );
196    }
197}
scylla/routing/locator/token_ring.rs

scylla/routing/locator/
token_ring.rs
