OFilter

OFilter 是一个用 Rust 实现的快速线程安全的 Bloom 过滤器。

它实现了

• 基本 Bloom 过滤器
• 线程安全 Bloom 过滤器
• 流式 Bloom 过滤器
• 线程安全流式 Bloom 过滤器
• Bloom 过滤器参数猜测

基本 Bloom 过滤器灵感来自现有的、稳定的 bloomfilter crate，但并不直接依赖于它。API 略有不同，并做了一些有见地的修改。

• 它使用 bitlen crate 作为内部实现，并以该格式导出其内部位向量。
• 它使用 siphasher crate 作为内部哈希函数。这无法被覆盖。
• 它引入了“流式过滤器”这一概念，这在您不在批量处理并且不知道项目何时停止到来时可能很有用。在某种程度上，它是对一个简单的老化 Bloom 过滤器的实现，尽管我更喜欢“流式”这个术语。
• 从性能的角度来看，默认设置倾向于优化 CPU 使用量较少但内存占用较多。这可以通过选项进行控制，但默认情况下，过滤器可以使用比严格所需的更多内存。

实际上，我正在使用这个过滤器来实现一个自动过期的 KV 存储。

该包有 2 个可选功能

• serde 以启用对（反）序列化的 Serde 支持
• rand 以启用 随机 种子（默认启用）

状态

据我所知，虽然这没有在实际生产中使用，但它的代码库并不复杂，附带了一个相当完整的测试套件。它构建的大部分积木都是经过良好测试的、广泛使用的包。因此，使用它是应该没问题的。再次提醒，免责声明，使用风险自负。

使用方法

use ofilter::Bloom;

let mut filter: Bloom<usize> = Filter::new(100);
assert!(!filter.check(&42));
filter.set(&42);
assert!(filter.check(&42));

基准测试

来自随机CI作业

running 7 tests
test tests::bench_extern_crate_bloom       ... bench:         287 ns/iter (+/- 37)
test tests::bench_extern_crate_bloomfilter ... bench:         232 ns/iter (+/- 7)
test tests::bench_ofilter_bloom            ... bench:          81 ns/iter (+/- 5)
test tests::bench_ofilter_stream           ... bench:         257 ns/iter (+/- 39)
test tests::bench_ofilter_sync_bloom       ... bench:         101 ns/iter (+/- 1)
test tests::bench_ofilter_sync_stream      ... bench:         280 ns/iter (+/- 14)
test tests::bench_standard_hashset         ... bench:         199 ns/iter (+/- 54)
test result: ok. 0 passed; 0 failed; 0 ignored; 7 measured; 0 filtered out; finished in 16.47s

这并不是广泛的、深入的基准测试结果，只是开发历史中某个时刻的随机快照。

TL;DR -> OFilter与bloom或其他类似bloom或bloomfilter等相比表现相对较好。

流版本较慢，这是预料之中的，因为它在底层使用两个过滤器，并执行额外的检查以确定何时交换缓冲区。

值得注意的是，对于小对象，使用标准HashSet相当高效。上面的基准测试使用了isize条目。因此，如果您的集合由小元素组成且绝对数量有限，使用标准库中的简单集合可能就足够了。当然，使用Bloom过滤器除了原始CPU使用外，还有其他优势，最重要的是它确保内存使用保持低且稳定，这是一个很大的优势。但请记住您试图解决的问题。基准测试、测量、收集数据、用事实说话，而不是直觉。

运行基准测试

cd bench
rustup default nightly
cargo bench

链接

• crate在crates.io上
• doc在docs.rs上
• source在gitlab.com上
• MenhirKV，使用此包的项目
• rust-bloom-filter，此包受到了启发

许可证

OFilter采用MIT许可证。