Skip to main content

consistent_choose_k/
consistent_hash.rs

1use std::hash::{Hash, Hasher};
2
3/// A trait which behaves like a pseudo-random number generator.
4/// It is used to generate consistent hashes within one bucket.
5/// Note: the hasher must have been seeded with the key during construction.
6pub trait HashSequence {
7    fn next(&mut self) -> u64;
8}
9
10/// A trait for building a special bit mask and sequences of hashes for different bit positions.
11/// Note: the hasher must have been seeded with the key during construction.
12pub trait HashSeqBuilder {
13    type Seq: HashSequence;
14
15    /// Returns a bit mask indicating which buckets have at least one hash.
16    fn bit_mask(&self) -> u64;
17    /// Return a HashSequence instance which is seeded with the given bit position
18    /// and the seed of this builder.
19    fn hash_seq(&self, bit: u64) -> Self::Seq;
20}
21
22/// A trait for building multiple independent hash builders
23/// Note: the hasher must have been seeded with the key during construction.
24pub trait ManySeqBuilder {
25    type Builder: HashSeqBuilder;
26
27    /// Returns the i-th independent hash builder.
28    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/// One building block for the consistent hashing algorithm is a consistent
63/// hash iterator which enumerates all the hashes for a specific bucket.
64/// A bucket covers the range `(1<<bit)..(2<<bit)`.
65#[derive(Default)]
66struct BucketIterator<H: HashSequence> {
67    hasher: H,
68    n: usize, // Upper bound for the hash values within the bucket.
69    is_first: bool,
70    bit: u64, // A bitmask with a single bit set.
71}
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
112/// An iterator which enumerates all the consistent hashes for a given key
113/// from largest to smallest in the range `0..n`.
114pub struct ConsistentHashRevIterator<H: HashSeqBuilder> {
115    builder: H,
116    bits: u64,                             // Bitmask of unvisited buckets.
117    n: usize,                              // Exclusive upper bound for the hash values.
118    inner: Option<BucketIterator<H::Seq>>, // Iterator for the current bucket.
119}
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
157/// Same as `ConsistentHashRevIterator`, but iterates from smallest to largest
158/// for the range `n..`.
159pub struct ConsistentHashIterator<H: HashSeqBuilder> {
160    bits: u64, // Bitmasks of unvisited buckets.
161    n: usize,  // Inclusive lower bound for the hash values.
162    builder: H,
163    stack: Vec<usize>, // Stack of hashes in the current bucket.
164}
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
197/// Wrapper around `ConsistentHashIterator` and `ConsistentHashRevIterator` to compute
198/// the next or previous consistent hash for a given key for a given number of nodes `n`.
199pub struct ConsistentHasher<H: HashSeqBuilder> {
200    builder: H,
201}
202
203impl<H: HashSeqBuilder> ConsistentHasher<H> {
204    /// Construct a new ConsistentHasher with the given builder for a specific key.
205    pub fn new(builder: H) -> Self {
206        Self { builder }
207    }
208
209    /// Return the largest consistent hash smaller than `n`.
210    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    /// Return the smallest consistent hash greater than or equal to `n`.
219    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    /// Return the largest consistent hash smaller than `n`, consuming the hasher.
228    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}