faro_sharding/
lib.rs

1#![deny(missing_docs)]
2
3//! Faro Sharding is a technique for sharding keys such that adding new destinations does not move data between existing destinations. Only between existing and the new destination.
4//!
5//! For example, if we have data sharded among 10 servers, when we add an 11th, we don't want to move data from 3 to 5. Faro Sharding guarantees that won't happen.
6//!
7//! # Example
8//! ```
9//! use faro_sharding::shard_for;
10//! for locations in 4..50 {
11//!   assert_eq!(shard_for("foo", locations), 2);
12//! }
13//! assert_eq!(shard_for("foo", 50), 49);
14//! ```
15//!
16//! # Distribution
17//!
18//! Faro Sharding shows high quality even distribution among locations. With 1,000,000 keys and 100 locations, the largest has 10229 keys (1.02%) and the smallest has 9761 keys (0.98%).
19//!
20//! If you want to evaluate the distribution with your own hashing function, you can modify `examples/distribution.rs` to use your hasher.
21//!
22//! # Algorithm
23//!
24//! Inspired by [JumpHash](https://arxiv.org/abs/1406.2294), Faro Sharding sequentially hashes the initial key and then the results of those hashes. Different from JumpHash, Faro Sharding only changes the shard for a key when `hash % i == 0`.
25//!
26//! Faro Sharding can only move a key to a shard on the step corresponding to that shard number. That means that the only movement happens to shard N on step N. Additionally, approximately 1/N of keys are moved on step N, resulting in approximately even distribution.
27
28use std::hash::*;
29
30#[cfg(feature = "seahash")]
31mod with_seahash {
32    use crate::shard_with_hasher;
33    use seahash::*;
34    use std::hash::*;
35
36    /// [shard_with_hasher] using [SeaHasher].
37    pub fn shard_for(key: impl Hash, total_destinations: u64) -> u64 {
38        shard_with_hasher(key, total_destinations, &BuildSeaHasher)
39    }
40
41    struct BuildSeaHasher;
42
43    impl BuildHasher for BuildSeaHasher {
44        type Hasher = SeaHasher;
45
46        fn build_hasher(&self) -> Self::Hasher {
47            SeaHasher::new()
48        }
49    }
50}
51#[cfg(feature = "seahash")]
52pub use with_seahash::shard_for;
53
54/// Returns the index of the shard for the provided key using the hasher provided.
55///
56/// If you want a stable output, your hasher must return the exact same hash given the same input. Do not use a hasher with random state.
57///
58/// # Panics
59///
60/// If total_destinations == 0.
61pub fn shard_with_hasher(
62    key: impl Hash,
63    total_destinations: u64,
64    hasher: &impl BuildHasher,
65) -> u64 {
66    let mut final_shard = 0;
67    let mut last_hash = hasher.hash_one(key);
68
69    assert_ne!(total_destinations, 0, "total_destinations must be > 0");
70
71    for n in 1..total_destinations {
72        let hash = hasher.hash_one(last_hash);
73        if hash % (n + 1) == 0 {
74            final_shard = n;
75        }
76        last_hash = hash;
77    }
78
79    debug_assert!(final_shard < total_destinations);
80    final_shard
81}
82
83#[cfg(test)]
84mod tests {
85    use super::*;
86
87    use proptest::*;
88
89    proptest! {
90        #[test]
91        fn does_not_move_between_existing_destinations(key: String) {
92            let mut last_shard = shard_for(&key, 1);
93            for n in 2..=1024 {
94                let next_shard = shard_for(&key, n);
95                prop_assert!(next_shard == last_shard || next_shard == n - 1);
96                last_shard = next_shard;
97            }
98        }
99
100        #[test]
101        fn assigns_to_different_shards(base: String, locations in 16u64..=512u64) {
102            let base_shard = shard_for(&base, locations);
103
104            for n in 0..1024 {
105                let shard = shard_for(&format!("{base}-{n}"), locations);
106                if shard != base_shard {
107                    return Ok(());
108                }
109            }
110            prop_assert!(false);
111        }
112    }
113
114    #[test]
115    fn pinning_default_shard() {
116        // It is critical that the default `shard_for` implementation always returns the same shards for correctness of our user's systems. Do not remove or change the values here. Adding new entries is ok.
117        let shards = maplit::btreemap! {
118            "foo" => 49,
119            "bar" => 14,
120            "baz" => 9,
121            "qux" => 60,
122            "quux" => 69,
123        };
124
125        for (key, expected_shard) in shards {
126            assert_eq!(
127                shard_for(&key, 73),
128                expected_shard,
129                "Incorrect shard for {key}"
130            );
131        }
132    }
133
134    #[test]
135    fn distributes_to_every_shard() {
136        let locations = 16;
137
138        let mut shard_counts = std::collections::HashMap::<_, u64>::new();
139        for i in 0..1000 {
140            *shard_counts.entry(shard_for(i, locations)).or_default() += 1;
141        }
142
143        for l in 0..locations {
144            assert!(shard_counts.contains_key(&l), "No entries for shard {l}");
145        }
146    }
147}
faro_sharding/lib.rs

faro_sharding/
lib.rs
