rfc9162_tiles/
bloom.rs

1//! A split-block Bloom filter: 256-bit blocks, one block per key, one bit in
2//! each of the block's eight 32-bit words. A probe touches one cache line.
3//! At 10 bits per key the false-positive rate is about 1 percent.
4//!
5//! Keys are hashed with SHA-256; the first eight bytes, little-endian, pick
6//! the block (high half) and the bits (low half). The bit of word `i` is
7//! `(low * SALT[i]) >> 27`, the Parquet and Impala construction.
8
9use sha2::{Digest, Sha256};
10
11use crate::error::{Error, Result};
12
13/// Bits per key the writer builds filters with.
14pub const BITS_PER_KEY: usize = 10;
15
16const SALT: [u32; 8] = [
17    0x47b6_137b,
18    0x4497_4d91,
19    0x8824_ad5b,
20    0xa2b7_289d,
21    0x7054_95c7,
22    0x2df1_424b,
23    0x9efc_4947,
24    0x5c6b_fb31,
25];
26
27/// The filter over a set of keys.
28#[derive(Debug, Clone, PartialEq, Eq)]
29pub struct Bloom {
30    blocks: Vec<[u32; 8]>,
31}
32
33impl Bloom {
34    /// A filter over `keys` at `bits_per_key`; at least one block.
35    #[must_use]
36    pub fn build<K: AsRef<[u8]>>(keys: &[K], bits_per_key: usize) -> Self {
37        let bits = keys.len().saturating_mul(bits_per_key);
38        let blocks = bits.div_ceil(256).max(1);
39        let mut filter = Self {
40            blocks: vec![[0u32; 8]; blocks],
41        };
42        for key in keys {
43            filter.insert(key.as_ref());
44        }
45        filter
46    }
47
48    fn insert(&mut self, key: &[u8]) {
49        let (block, mask) = self.locate(key);
50        for (word, bit) in self.blocks[block].iter_mut().zip(mask) {
51            *word |= bit;
52        }
53    }
54
55    /// Whether `key` may be in the set: never false for a key that is, true
56    /// for about 1 percent of keys that are not.
57    #[must_use]
58    pub fn contains(&self, key: &[u8]) -> bool {
59        let (block, mask) = self.locate(key);
60        self.blocks[block]
61            .iter()
62            .zip(mask)
63            .all(|(word, bit)| word & bit == bit)
64    }
65
66    fn locate(&self, key: &[u8]) -> (usize, [u32; 8]) {
67        let digest = Sha256::digest(key);
68        let mut first = [0u8; 8];
69        first.copy_from_slice(&digest[..8]);
70        let h = u64::from_le_bytes(first);
71        let block = (((h >> 32) * self.blocks.len() as u64) >> 32) as usize;
72        let low = h as u32;
73        let mut mask = [0u32; 8];
74        for (bit, salt) in mask.iter_mut().zip(SALT) {
75            *bit = 1u32 << (low.wrapping_mul(salt) >> 27);
76        }
77        (block, mask)
78    }
79
80    /// Blocks in the filter.
81    #[must_use]
82    pub fn blocks(&self) -> usize {
83        self.blocks.len()
84    }
85
86    /// The filter as bytes: each word little-endian, blocks in order.
87    #[must_use]
88    pub fn to_bytes(&self) -> Vec<u8> {
89        let mut out = Vec::with_capacity(self.blocks.len() * 32);
90        for block in &self.blocks {
91            for word in block {
92                out.extend_from_slice(&word.to_le_bytes());
93            }
94        }
95        out
96    }
97
98    /// The filter `to_bytes` wrote; refused unless whole blocks, at least one.
99    pub fn from_bytes(bytes: &[u8]) -> Result<Self> {
100        if bytes.is_empty() || bytes.len() % 32 != 0 {
101            return Err(Error::Format(format!(
102                "a filter of {} bytes is not whole 32-byte blocks",
103                bytes.len()
104            )));
105        }
106        let blocks = bytes
107            .chunks_exact(32)
108            .map(|chunk| {
109                let mut block = [0u32; 8];
110                for (word, raw) in block.iter_mut().zip(chunk.chunks_exact(4)) {
111                    *word = u32::from_le_bytes([raw[0], raw[1], raw[2], raw[3]]);
112                }
113                block
114            })
115            .collect();
116        Ok(Self { blocks })
117    }
118}
119
120#[cfg(test)]
121mod tests {
122    use super::*;
123
124    #[test]
125    fn every_member_is_found_and_the_bytes_round_trip() {
126        let keys: Vec<Vec<u8>> = (0..500u32).map(|i| i.to_be_bytes().to_vec()).collect();
127        let filter = Bloom::build(&keys, BITS_PER_KEY);
128        assert_eq!(filter.blocks(), (500 * 10usize).div_ceil(256));
129        assert!(keys.iter().all(|k| filter.contains(k)));
130        assert_eq!(Bloom::from_bytes(&filter.to_bytes()).unwrap(), filter);
131        assert!(Bloom::from_bytes(&[0u8; 31]).is_err());
132        let empty = Bloom::build::<&[u8]>(&[], BITS_PER_KEY);
133        assert_eq!(empty.blocks(), 1);
134        assert!(!empty.contains(b"anything"));
135    }
136
137    #[test]
138    fn false_positives_stay_near_one_percent() {
139        let keys: Vec<Vec<u8>> = (0..512u32)
140            .map(|i| format!("member-{i}").into_bytes())
141            .collect();
142        let filter = Bloom::build(&keys, BITS_PER_KEY);
143        let probes = 200_000u32;
144        let hits = (0..probes)
145            .filter(|i| filter.contains(format!("stranger-{i}").as_bytes()))
146            .count();
147        let rate = hits as f64 / f64::from(probes);
148        assert!(rate < 0.02, "false-positive rate {rate}");
149        assert!(
150            rate > 0.002,
151            "false-positive rate {rate} is too good to be a filter"
152        );
153    }
154}
rfc9162_tiles/bloom.rs

rfc9162_tiles/
bloom.rs
