我计划创建一系列的博客文章，其中包括一些文献研究、各种数据结构的实现，以及我们在direcent.io中创建分布式数据存储的旅程。
在我开始写这篇文章的6天后，事实证明，假阳性概率背后的数学是错误的，长达50年之久。您可以在这里阅读详细的解释。
您可能会感到奇怪，为什么我一开始就写了一篇博客文章来解释Bloom filter，而我对如何创建分布式数据存储却毫无头绪？我的回答很简单：“我喜欢它背后的想法”。
在我详细介绍Bloom Filters之前，我想先介绍一下我们的背景故事，它将帮助您理解为什么我们开始构建一些我们在空闲时间会喜欢的东西，而这些东西永远不会投入生产。
我和我的朋友易卜拉欣(Ibrahim)总是对复杂的软件和分布式系统着迷-我们已经在一起工作了5年多(我们有个老伙计)，我们很幸运地为欧洲最大的电子商务公司工作。我们奋力拼搏，解决了分布式系统可以提供的许多不同问题。我们都搬到了英国剑桥，仍然在与分散的世界恶棍作战。
让我们通过实现Bloom过滤器来探索概率数据结构的神秘之地。
Bloom filter是一种表示n个元素(也称为键)的集合$A={a_1，a_2，\ldots，a_n}$以支持成员查询的方法。它是由Burton Bloom于1970年发明的，Marais和Bharat建议在Web上下文中使用它作为一种机制，用于识别哪些页面具有存储在CommonKnowledge服务器中的相关注释。1个。
它是一种节省空间的概率数据结构，用于回答一个非常简单的问题：该元素是集合的成员吗？Bloom过滤器不存储实际元素，它只存储这些元素的成员身份。
假阳性匹配是可能的，但假阴性是不可能的-换句话说，查询返回“可能在集合中”或“绝对不在集合中”。2不幸的是，这也意味着不能从Bloom filter中删除项(其他一些元素或元素组可能会散列到相同的索引)。
由于其概率性质，布隆过滤器以牺牲空间和性能来换取准确性。这很像CAP定理，我们选择性能而不是准确性。
Bloom过滤器有一些有趣的用例。例如，可以将它们放在数据存储区的顶部。当查询某个键是否存在，而筛选器没有该键时，我们可以完全跳过查询数据存储。
布隆过滤器背后的思想非常简单：分配一个$m$位的数组$v$，数组中的每个位最初设置为$0$，然后选择$k$独立的散列函数$h_1，h_2，…。，h_k$，每个范围为${1，…。，m}$。
当将A$中的元素$a\添加到过滤器时，位置$h_1(A)、h_2(A)、…。，$v$中的h_k(A)$被设置为$1$。简而言之，新元素由$k$个函数散列，并由$m$进行修改，导致$k$索引进入位数组。设置相应索引处的每个位。
为了查询元素$b$的成员资格，我们检查索引$h_1(B)、h_2(B)、…处的位。，h_k(B)$，单位为$v$。如果它们中的任何一个是$0$，那么$b$肯定不在集合$A$中。否则，我们假设$b$在集合中，尽管也可能有其他元素或元素组散列到相同的索引。这称为假阳性。我们可以通过为最多$n$插入选择最佳值$m$和$k$来确定特定的误报概率。
布隆过滤器最终到达所有位都已设置的点，这意味着每个查询都将指示成员身份，从而有效地使误报的概率为$1$。这样做的问题是，它需要数据集的先验知识，以便选择最佳参数并避免“过度填充”。3个。
我们可以根据$n$和选定的误报概率$P_{fp}$推导出最优的$k$和$m$。
\[K=-\frac{\ln{P_{fp}{\ln{2}}，m=-\frac{n\ln{P_{fp}{(\ln2)^2}\]如果您想了解上述公式是如何推导出来的，您可以访问此处。
终于来了！现在是写些生锈的时候了。在写这篇博客的同时，我同时实现了Bloom过滤器。如果您不相信我，请检查以下命令：
让我们继续讨论依赖项。只有一个依赖项，我们将使用它来创建$v$。
我们将声明一个新的struct StandardBloomFilter来封装必需的字段$k$(散列函数的最佳数量)、$m$(位数组的最佳大小)、$v$(位数组)、散列函数和一个标记，以告诉RUST编译器我们的结构“拥有”一个T。
Pub struct StandardBloomFilter<；T：？大小已调整>；{位图：BitVec，Optimal_m：u64，Optimal_k：u32，散列器：[DefaultHasher；2]，_marker：PhantomData<；T>；，}。
细心的读者会认为我在声明hashers数组时犯了错误，因为需要$k$独立的散列函数。这确实是故意的，原因如下：
为什么要使用两个散列函数？Kirsch和Mitzenmacher在他们的论文中证明了使用两个散列函数$h_1(X)$和$h_2(X)$来模拟形式为$g_i(X)=h_1(X)+{i}{h_2(X)}$的附加散列函数可以有效地应用于Bloom Filter。这导致了较少的计算，并且在实践中潜在地减少了对随机性的需要。4该公式可能看起来类似于成对独立散列函数的使用。不幸的是，这两种技术之间没有正式的联系。
我在前面提到过，Bloom过滤器有两个类似于标准集的操作：插入和查询。我们将使用类似构造函数的新方法实现这两个操作。
实施T：？Size>；StandardBloomFilter<；T>；{pub FN new(Items_Count：usize，FP_Rate：f64)->；self{//...snip}}。
New计算位图的大小($v$)和Optimal_k($k$)，然后实例化StandardBloomFilter。
实施T：？SIZED&gT；StandardBloomFilter<；T>；{pub FN new(Items_Count：usize，fp_rate：f64)->；self{Let Optimal_m=self：：bitmap_size(Items_count，fp_rate)；let Optimal_k=Self：：Optimal_k(Fp_Rate)；let hashers=[DefaultHasher：：New()，DefaultHasher：：New()]；StandardBloomFilter{bitmap：BitVec：：from_elem(Optimal_m as usize，false)，Optimal_m，Optimal_k，hashers，_mark：PhantomData，}}//...截取FN位图_SIZE(Items_Count：usize，FP_Rate：f64)->；usize{let LN2_2=core：：f64：：consts：：ln_2*core：：f64：consts：：((-1.0f64*Items_Count as f64*fp_rate.ln())/ln2).ceil()as usize}fn Optimal_k(fp_rate：f64)->；u32{((-1.0f64*fp_rate.ln())/core：：f64：：consts：：ln_2).ceil()as u32}//...snip}。
这看起来真的很有希望！以$0.01$的误报率表示一组$1,000,000个项目的布隆过滤器只需要$9585059$位($~1.14mathm{MB}$)和7个散列函数。
到目前为止，我们已经成功地构建了Bloom filter，现在是实现插入和包含方法的时候了。它们的实现非常简单，并且它们共享相同的代码来计算位数组的索引。
实施T：？SIZED&gT；StandardBloomFilter<；T>；{//...snip pub FN INSERT(&；mut self，Item：&；T)，其中T：hash，{let(h1，h2)=sel.hash_kernel(Item)；对于0中的k_i。Sel.Optimal_k{let index=sel.get_index(h1，h2，ki as U64)；self.bitmap.SET(index，true)；}}pub fn包含(&；mut self，item：&；T)->；bool，其中T：hash，{let(h1，h2)=sel.hash_kernel(Item)；对于0中的k_i。Sel.Optimal_k{let index=sel.get_index(h1，h2，k_i为U64)；if self.bitmap.get(Index).unwire()==false{return false；}}true}}。
上面的方法依赖于我们还没有实现的另外两个方法：hash_kernel和get_index。Hash_kernel将是实际的“散列”发生的地方。它将返回$h_1(X)$和$h_2(X)$的散列值。
实施T：？SIZED&gT；StandardBloomFilter<；T>；{//...snip FN hash_kernel(&；self，Item：&；T)->；(U64，U64)其中T：hash，{let hasher1=&；mut self.hashers[0].clone()；let hasher2=&；mut self.hashers[1].clone()；item.hash(hasher.hasher1=&；mut self.hashers[0].clone()；let hasher2=&；mut self.hashers[1].clone()；item.hash。让hash2=hasher2.Finish()；(hash1，hash2)}}
我们本可以使用$128$bit MurmurHash3，并返回较高的$64$bit作为hash1，返回较低的$64$bit作为hash2，但是为了使此实现更加简单(这就是Google Guava Bloom Filter实现目前的工作方式)，并且不依赖于任何其他依赖项，我决定继续使用DefaultHasher-参见SipHash。
现在，是时候做最后的润色了。我们将通过使用$g_i(X)=h_1(X)+{i}{h_2(X)}$来模拟两个以上的散列函数来实现get_index。
实施T：？Size>；StandardBloomFilter<；T>；{//...snip FN get_index(&；self，h1：u64，h2：u64，ki_i：u64)->；usize{(h1.wrapping_add(Ki_I).wrapping_mul(H2)%self.Optimal_m)as usize}//...snip(&；self，h1：u64，h2：u64，ki_i：u64)->；usize。
我们刚刚实现了标准Bloom filter的一个快速变体，但是还缺少一件事--我们没有编写任何测试。
#[cfg(Test)]mod test{use Super：：*；#[test]fn insert(){let mut bloom=StandardBloomFilter：：New(100，0.01)；bloom.insert("；Item"；)；assert！(Bloom.Concludes("；Item"；))；}#[test]fn check_and_insert(){let mut bloom=StandardBloomFilter：：New(100，0.01。断言！(！BLOOM.CONTAINS("；Item_1"；))；Assert！(！BLOOM.CONTAINS("；Item_2"；))；BLOOM.INSERT("；Item_1"；)；Assert！(BLOOM.CONTAINS("；Item_1"；))；}}。
用户货物测试编译PLUM v0.1.2(/Users/onat.mercan/dev/plum)在0.99秒内完成测试[未优化+调试信息]目标运行target/debug/deps/plum-6fc161db530d5b36running 2测试：：❯...。OK测试测试：：CHECK_AND_INSERT...。OK测试结果：OK。2通过；0失败；0忽略；0测量；0过滤掉。
我希望你喜欢读这篇文章，就像我喜欢写它一样！
如果您发现代码有任何错误，您可以提交问题，或者更好的做法是提交拉取请求。