consist/
lib.rs

1//! consist: An implementation of consistent hashing in Rust.
2//! The goal of consistent hashing is to partition entries in such a way that the addition or
3//! removal of buckets minimizes the number of items that must be shifted between buckets, i.e. it
4//! optimizes the rehashing stage that is usually needed for hash tables.
5//! The algorithm was originally put forth by David Karger et al. in their 1997 paper
6//! "Consistent Hashing and Random Trees".
7//! As of version 0.3.0, we use CRC64 with ECMA polynomial, so that updating the rust version does
8//! not change behavior.
9#![feature(btree_range, collections_bound)]
10
11extern crate crc;
12
13use crc::crc64::{ECMA, Digest, Hasher64};
14
15use std::collections::BTreeMap;
16use std::hash::{Hash, Hasher};
17use std::collections::Bound::{Included, Excluded, Unbounded};
18
19/// A newtype that wraps a Hasher64 and provides implementation of std::hash::Hasher methods.
20struct Hasher64StdHashHasher<T: Hasher64>(T);
21
22impl<T> Hasher for Hasher64StdHashHasher<T>
23    where T: Hasher64
24{
25    fn write(&mut self, bytes: &[u8]) {
26        self.0.write(bytes);
27    }
28
29    fn finish(&self) -> u64 {
30        self.0.sum64()
31    }
32}
33
34/// HashRing is a type that tracks a set of buckets corresponding to a collection of resources,
35/// usually servers. Items are hashed to these buckets in such a way that few items change their
36/// bucket mapping when one is eliminated.
37pub struct HashRing<B: Hash> {
38    buckets: BTreeMap<u64, B>,
39}
40
41impl<B> HashRing<B>
42    where B: Hash
43{
44    /// Get a new HashRing.
45    pub fn new() -> HashRing<B> {
46        HashRing::<B> { buckets: BTreeMap::new() }
47    }
48
49    /// Adds the specified bucket to the hash ring.
50    pub fn add_bucket(&mut self, bucket: B) {
51        let hash_code = HashRing::<B>::get_hash_code(&bucket);
52        self.buckets.insert(hash_code, bucket);
53    }
54
55    /// Finds the corresponding bucket for this item.
56    pub fn get_bucket<T>(&self, item: &T) -> Option<&B>
57        where T: Hash
58    {
59        let hash_code = HashRing::<B>::get_hash_code(item);
60        // If there are no buckets in the end of the circle from here to the end, we wrap around
61        // and try from the beginning.
62        let back_half = self.buckets.range((Included(&hash_code), Unbounded)).next().map(|val| val.1);
63        let front_half = self.buckets
64                             .range((Included(&0), Excluded(&hash_code)))
65                             .next()
66                             .map(|val| val.1);
67        back_half.or(front_half)
68    }
69
70    /// Eliminate a bucket from the ring. All items mapped to this bucket will be mapped to the
71    /// next bucket in hash order (with wraparound).
72    /// Returns true if removal is successful, or false if the removal has no effect.
73    pub fn remove_bucket(&mut self, bucket: &B) -> bool {
74        let code = HashRing::<B>::get_hash_code(bucket);
75        match self.buckets.remove(&code) {
76            None => false,
77            Some(..) => true,
78        }
79    }
80
81    fn get_hash_code<H>(value: &H) -> u64
82        where H: Hash
83    {
84        let mut hasher = Hasher64StdHashHasher(Digest::new(ECMA));
85        value.hash(&mut hasher);
86        hasher.finish()
87    }
88}
consist/lib.rs

consist/
lib.rs
