index/
bloom_filter.rs

1// Copyright 2023 Greptime Team
2//
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6//
7//     http://www.apache.org/licenses/LICENSE-2.0
8//
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14
15pub mod applier;
16pub mod creator;
17pub mod error;
18pub mod reader;
19
20use std::hash::{BuildHasher, BuildHasherDefault, Hasher};
21use std::sync::LazyLock;
22
23/// The seed used for the Bloom filter.
24pub const SEED: u128 = 42;
25
26static ELEMENT_HASHER: LazyLock<fastbloom::DefaultHasher> =
27    LazyLock::new(|| fastbloom::DefaultHasher::seeded(&SEED.to_be_bytes()));
28
29/// Returns the hash fastbloom derives for `elem` with the persisted [`SEED`].
30///
31/// A filter built from these hashes with [`PrehashedBuildHasher`] has exactly the same
32/// bits as one built by inserting the elements themselves, so files stay readable by
33/// both paths.
34pub fn element_hash(elem: &[u8]) -> u64 {
35    ELEMENT_HASHER.hash_one(elem)
36}
37
38/// Hasher that returns an already computed [`element_hash`] unchanged.
39#[derive(Default)]
40pub struct PrehashedHasher(u64);
41
42impl Hasher for PrehashedHasher {
43    fn finish(&self) -> u64 {
44        self.0
45    }
46
47    fn write(&mut self, _bytes: &[u8]) {
48        unreachable!("PrehashedHasher only accepts u64 hashes")
49    }
50
51    fn write_u64(&mut self, hash: u64) {
52        self.0 = hash;
53    }
54}
55
56pub type PrehashedBuildHasher = BuildHasherDefault<PrehashedHasher>;
57
58/// A persisted bloom filter probed by [`element_hash`] values.
59pub type PrehashedBloomFilter = fastbloom::BloomFilter<512, PrehashedBuildHasher>;
60
61#[cfg(test)]
62mod tests {
63    use fastbloom::BloomFilter;
64
65    use super::*;
66
67    #[test]
68    fn test_prehashed_filter_matches_seeded_filter() {
69        // Persisted filters are read back with `.seed(&SEED)`, so building them from
70        // precomputed hashes must set exactly the same bits.
71        for count in [0usize, 1, 7, 100, 5000] {
72            let elems = (0..count)
73                .map(|i| format!("elem-{i}").into_bytes())
74                .chain([Vec::new()])
75                .collect::<Vec<_>>();
76            let mut seeded = BloomFilter::with_false_pos(0.01)
77                .seed(&SEED)
78                .expected_items(elems.len());
79            let mut prehashed = BloomFilter::with_false_pos(0.01)
80                .hasher(PrehashedBuildHasher::default())
81                .expected_items(elems.len());
82            for elem in &elems {
83                seeded.insert(elem);
84                prehashed.insert(&element_hash(elem));
85            }
86            assert_eq!(seeded.as_slice(), prehashed.as_slice());
87        }
88    }
89}
index/bloom_filter.rs

index/
bloom_filter.rs
