consistent_choose_k/
consistent_hash.rs1use std::hash::{Hash, Hasher};
2
3pub trait HashSequence {
7 fn next(&mut self) -> u64;
8}
9
10pub trait HashSeqBuilder {
13 type Seq: HashSequence;
14
15 fn bit_mask(&self) -> u64;
17 fn hash_seq(&self, bit: u64) -> Self::Seq;
20}
21
22pub trait ManySeqBuilder {
25 type Builder: HashSeqBuilder;
26
27 fn seq_builder(&self, i: usize) -> Self::Builder;
29}
30
31impl<H: Hasher> HashSequence for H {
32 fn next(&mut self) -> u64 {
33 54387634019u64.hash(self);
34 self.finish()
35 }
36}
37
38impl<H: Hasher + Clone> HashSeqBuilder for H {
39 type Seq = H;
40
41 fn bit_mask(&self) -> u64 {
42 self.finish()
43 }
44
45 fn hash_seq(&self, bit: u64) -> Self::Seq {
46 let mut hasher = self.clone();
47 bit.hash(&mut hasher);
48 hasher
49 }
50}
51
52impl<H: Hasher + Clone> ManySeqBuilder for H {
53 type Builder = H;
54
55 fn seq_builder(&self, i: usize) -> Self::Builder {
56 let mut hasher = self.clone();
57 i.hash(&mut hasher);
58 hasher
59 }
60}
61
62#[derive(Default)]
66struct BucketIterator<H: HashSequence> {
67 hasher: H,
68 n: usize, is_first: bool,
70 bit: u64, }
72
73impl<H: HashSequence> BucketIterator<H> {
74 fn new(n: usize, bit: u64, hasher: H) -> Self {
75 Self {
76 hasher,
77 n,
78 is_first: true,
79 bit,
80 }
81 }
82}
83
84impl<H: HashSequence> Iterator for BucketIterator<H> {
85 type Item = usize;
86
87 fn next(&mut self) -> Option<Self::Item> {
88 if self.bit == 0 {
89 return None;
90 }
91 if self.is_first {
92 let res = (self.hasher.next() & (self.bit - 1)) + self.bit;
93 self.is_first = false;
94 if res < self.n as u64 {
95 self.n = res as usize;
96 return Some(self.n);
97 }
98 }
99 loop {
100 let res = self.hasher.next() & (self.bit * 2 - 1);
101 if res & self.bit == 0 {
102 return None;
103 }
104 if res < self.n as u64 {
105 self.n = res as usize;
106 return Some(self.n);
107 }
108 }
109 }
110}
111
112pub struct ConsistentHashRevIterator<H: HashSeqBuilder> {
115 builder: H,
116 bits: u64, n: usize, inner: Option<BucketIterator<H::Seq>>, }
120
121impl<H: HashSeqBuilder> ConsistentHashRevIterator<H> {
122 pub fn new(n: usize, builder: H) -> Self {
123 Self {
124 bits: builder.bit_mask() & (n.next_power_of_two() as u64 - 1),
125 builder,
126 n,
127 inner: None,
128 }
129 }
130}
131
132impl<H: HashSeqBuilder> Iterator for ConsistentHashRevIterator<H> {
133 type Item = usize;
134
135 fn next(&mut self) -> Option<Self::Item> {
136 if self.n == 0 {
137 return None;
138 }
139 if let Some(res) = self.inner.as_mut().and_then(|inner| inner.next()) {
140 return Some(res);
141 }
142 while self.bits > 0 {
143 let bit = 1 << self.bits.ilog2();
144 self.bits ^= bit;
145 let seq = self.builder.hash_seq(bit);
146 let mut iter = BucketIterator::new(self.n, bit, seq);
147 if let Some(res) = iter.next() {
148 self.inner = Some(iter);
149 return Some(res);
150 }
151 }
152 self.n = 0;
153 Some(0)
154 }
155}
156
157pub struct ConsistentHashIterator<H: HashSeqBuilder> {
160 bits: u64, n: usize, builder: H,
163 stack: Vec<usize>, }
165
166impl<H: HashSeqBuilder> ConsistentHashIterator<H> {
167 pub fn new(n: usize, builder: H) -> Self {
168 Self {
169 bits: builder.bit_mask() & !((n + 2).next_power_of_two() as u64 / 2 - 1),
170 stack: if n == 0 { vec![0] } else { vec![] },
171 builder,
172 n,
173 }
174 }
175}
176
177impl<H: HashSeqBuilder> Iterator for ConsistentHashIterator<H> {
178 type Item = usize;
179
180 fn next(&mut self) -> Option<Self::Item> {
181 if let Some(res) = self.stack.pop() {
182 return Some(res);
183 }
184 while self.bits > 0 {
185 let bit = self.bits & !(self.bits - 1);
186 self.bits &= self.bits - 1;
187 let inner = BucketIterator::new(bit as usize * 2, bit, self.builder.hash_seq(bit));
188 self.stack = inner.take_while(|x| *x >= self.n).collect();
189 if let Some(res) = self.stack.pop() {
190 return Some(res);
191 }
192 }
193 None
194 }
195}
196
197pub struct ConsistentHasher<H: HashSeqBuilder> {
200 builder: H,
201}
202
203impl<H: HashSeqBuilder> ConsistentHasher<H> {
204 pub fn new(builder: H) -> Self {
206 Self { builder }
207 }
208
209 pub fn prev(&self, n: usize) -> Option<usize>
211 where
212 H: Clone,
213 {
214 let mut sampler = ConsistentHashRevIterator::new(n, self.builder.clone());
215 sampler.next()
216 }
217
218 pub fn next(&self, n: usize) -> Option<usize>
220 where
221 H: Clone,
222 {
223 let mut sampler = ConsistentHashIterator::new(n, self.builder.clone());
224 sampler.next()
225 }
226
227 pub fn into_prev(self, n: usize) -> Option<usize> {
229 ConsistentHashRevIterator::new(n, self.builder).next()
230 }
231}
232
233#[cfg(test)]
234mod tests {
235 use std::hash::DefaultHasher;
236
237 use super::*;
238
239 fn hasher_for_key(key: u64) -> DefaultHasher {
240 let mut hasher = DefaultHasher::default();
241 key.hash(&mut hasher);
242 hasher
243 }
244
245 #[test]
246 fn test_uniform_1() {
247 for k in 0..100 {
248 let hasher = hasher_for_key(k);
249 let sampler = ConsistentHasher::new(hasher.clone());
250 for n in 0..1000 {
251 assert!(sampler.prev(n + 1) <= sampler.prev(n + 2));
252 let next = sampler.next(n).unwrap();
253 assert_eq!(next, sampler.prev(next + 1).unwrap());
254 }
255 let mut iter_rev: Vec<_> = ConsistentHashIterator::new(0, hasher.clone())
256 .take_while(|x| *x < 1000)
257 .collect();
258 iter_rev.reverse();
259 let iter: Vec<_> = ConsistentHashRevIterator::new(1000, hasher).collect();
260 assert_eq!(iter, iter_rev);
261 }
262 let mut stats = vec![0; 13];
263 for i in 0..100000 {
264 let hasher = hasher_for_key(i);
265 let sampler = ConsistentHasher::new(hasher);
266 let x = sampler.prev(stats.len()).unwrap();
267 stats[x] += 1;
268 }
269 assert_eq!(
270 stats,
271 vec![7577, 7541, 7538, 7822, 7763, 7687, 7718, 7723, 7846, 7723, 7688, 7716, 7658]
272 );
273 }
274}