fastbloom

Rust 中最快的 Bloom filter。不牺牲准确性。支持完全并发，并兼容任意 hasher。

Overview

fastbloom 是一个用 Rust 实现的快速、灵活且准确的 Bloom filter。fastbloom 的默认 hasher 是使用随机化密钥的 SipHash-1-3，但可以进行种子设置或配置为使用任意 hasher。fastbloom 比现有的 Bloom filter 实现快 2-20 倍，且准确度高出数个数量级。fastbloom 的 AtomicBloomFilter 是一种并发 Bloom filter，可避免锁竞争。

Usage

由于 0.17.x 中采用了不同的（改进的！）算法，Bloomfilter 与之前版本的序列化/反序列化不兼容。

# Cargo.toml
[dependencies]
fastbloom = "0.17.0"

基本用法：

use fastbloom::BloomFilter;

let mut filter = BloomFilter::with_num_bits(1024).expected_items(2);
filter.insert("42");
filter.insert("🦀");

使用目标假阳性率进行实例化：

use fastbloom::BloomFilter;

let filter = BloomFilter::with_false_pos(0.001).items(["42", "🦀"].iter());
assert!(filter.contains("42"));
assert!(filter.contains("🦀"));

使用任意 hasher：

use fastbloom::BloomFilter;
use foldhash::fast::RandomState;

let filter = BloomFilter::with_num_bits(1024)
    .hasher(RandomState::default())
    .items(["42", "🦀"].iter());

支持完全并发。AtomicBloomFilter 是 RwLock<OtherBloomFilter> 的直接替代品，因为所有方法都接受 &self：

use fastbloom::AtomicBloomFilter;

let filter = AtomicBloomFilter::with_num_bits(1024).expected_items(2);
filter.insert("42");
filter.insert("🦀");

Background

Bloom filter 是一种空间高效的近似成员集合数据结构，由底层位数组支持以跟踪项目成员资格。为了插入/检查成员资格，会根据项目的哈希值在相应位置设置/检查若干位。成员资格检查可能出现假阳性，但不会出现假阴性。一旦构建完成，Bloom filter 的底层内存使用量或每个项目的位数均不会改变。查看更多。

hash(4) ──────┬─────┬───────────────┐
              ↓     ↓               ↓
0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 1 0
  ↑           ↑           ↑
  └───────────┴───────────┴──── hash(3) (not in the set)

实现

fastbloom 之所以速度极快，是因为它仅通过每个项目的一次真实哈希即可高效地推导出许多索引位，并利用了关于布隆过滤器的其他研究成果。fastbloom 对原始 64 位哈希的两个 32 位半部分采用“哈希组合”。每个后续哈希都是通过模运算和位运算将原始哈希值与不同的常量组合而得出的。这产生了一组实际上相互独立且均匀分布的哈希函数，尽管它们源自同一个原始哈希函数。计算两个原始哈希的组合比使用不同的种子重新计算哈希更快。此技术在这篇论文中有深入解释。

速度

AMD Ryzen 9 5900X 12-Core Processor (3.70 GHz)
64 位操作系统，基于 x64 的处理器

perf-non-member perf-member

使用的哈希器：

xxhash: sbbf

Sip1-3: bloom, bloomfilter, probabilistic-collections

foldhash: fastbloom

基准测试来源

准确性

fastbloom 不会牺牲准确性。以下是与其他布隆过滤器 crate 的误报率比较：

Benchmark 来源

可用特性

rand - 默认启用，此特性使用 thread_rng() 而非硬件源来为 DefaultHasher 源提供随机状态。从用户空间源获取熵的速度明显更快，但需要额外的依赖项来实现。通过使用 default-features = false 禁用此特性，将使 DefaultHasher 使用 foldhash 来提供其熵，这将以速度为代价换取更简单的代码占用。
serde - 在可能的情况下，BloomFilter 实现了 Serialize 和 Deserialize。
loom - AtomicBloomFilter 使用 loom 原子操作，使其与 loom 测试兼容。

参考

许可证

根据以下任一许可证授权：

Apache License, Version 2.0 (LICENSE-APACHE 或 http://www.apache.org/licenses/LICENSE-2.0)
MIT license (LICENSE-MIT 或 http://opensource.org/licenses/MIT)

供您选择。

贡献

除非您明确声明其他情况，否则您有意提交以包含在作品中的任何贡献，如 Apache-2.0 许可证所定义，将按照上述双重许可，不附加任何额外条款或条件。