比特币bloomfilter

A. Bloom filter有哪些实践应用

应用样例可以参考 en.wikipedia.org/wiki/Bloom_filter

Akamai's web servers use Bloom filters to prevent "one-hit-wonders" from being stored in its disk caches.[7] One-hit-wonders are web objects requested by users just once.[7] Nearly three-quarters of urls accessed from a typical web cache are one-hit-wonders! Using a Bloom filter to detect the second request for a web object and caching that object only on its second request prevents one-hit wonders from entering the disk cache, significantly recing disk workload and increasing disk cache hit rates.[7]

Google BigTable, Apache HBase and Apache Cassandra use Bloom filters to rece the disk lookups for non-existent rows or columns. Avoiding costly disk lookups considerably increases the performance of a database query operation.[8][9]

The Google Chrome web browser used to use a Bloom filter to identify malicious URLs. Any URL was first checked against a local Bloom filter, and only if the Bloom filter returned a positive result was a full check of the URL performed (and the user warned, if that too returned a positive result).[10][11]

The Squid Web Proxy Cache uses Bloom filters for cache digests.[12]

Bitcoin uses Bloom filters to speed up wallet synchronization.[13][14]

The Venti archival storage system uses Bloom filters to detect previously stored data.[15]

The SPIN model checker uses Bloom filters to track the reachable state space for large verification problems.[16]

The Cascading analytics framework uses Bloom filters to speed up asymmetric joins, where one of the joined data sets is significantly larger than the other (often called Bloom join[17] in the database literature).[18]
The Exim mail transfer agent (MTA) uses Bloom filters in its rate-limit feature.[19]
Medium uses Bloom filters to avoid recommending articles a user has previously read.[20]

B. bitcoin bloom filter

20180901
冉小龙（xiaolong.ran）
致谢：齐巍

问题：在大数据场景下，我们如何从海量的数据池中去判断某一个东西是否存在它李毕里面？

思路：要去构建这个海量数据池，我们存储的方案无外乎这几种

一般来讲，计算机中的集合是用哈希表（hash table）来存储的。它的好处是快速准确，缺点是费存储空间。当集合比较小时，这个问题不显著，但是当集合巨大时，哈希表存储效率低的问题就显现出来了。关于这个，只需要根据元素的数量和大小简单的计算一下就知道了。虽然可以适用分布式K-V系统（如Redis）来承载，但是成本仍然高昂。布隆过滤器只需要哈希表 1/8 到 1/4 的大小就能解决同样的问题，以一定的误判率为代价。所需要的内存大小可以通过公式精确的计算出来： Bloom Filter Calculator 。

降低误判率

如果哈希函数的个数多，那么在对一个不属于集合的元素进行查询时得到0的概率就大；但另一方面，如果哈希函数的个数少，那么位数组薯扰派中的0就多。所以就需要权衡，具体怎么权衡能？ 不知道

BloomFilter中不允许有删除操作，因为删除后，可能会造成原来存在的元素返回不存在。因为假设两个hash函数hash到同一个位置的时候，看到这个位置为1，就不做处理了，所以，你删除之后，这个位置的标记1也跟着删除了。

把存储数组的每一个元素扩展一下（原来是1b）用来存储该位置被置1的次数。存储是，计数次数加一；删除的时候，计数次数减一。

观察上图，假设某个元素通过hash映射对应下标为4，5，6这3个点。虽然这3个点都为1，但是很明显这3个点是不同元素经过哈希得到的位置，因此这种情况说明元素虽然不在集合中，也可能对应的都是1，这是误判率存在的原因。

比特币中布隆过滤器是在 BIP-0037 中提到，主要是提供给spv节点使用,主要是去过滤发送给他们的交易。

Bloom Filter就是一个过滤器，用来过滤不属于钱包的UTXO ,通过bloom filter，钱包既能保护用户的隐私，还能节省存储空间和宽带。

规定bloom filter最多允许有50个hash函数，最大是3.5Kb左右

基础结构：

nflag:

序列化操作：

生成不同hash函数的操作：

按照bloom filter的算法对新增的key做几次hash然后修改位数组:

添加操作：

filter具体过滤过程

获取指定blockhash中满足bloom filter的block 内容

ProcessMessage:

load filter:

add filter:

clear filter

假设目前没有bloom filter，用户A是一个spv节点的用户，他有两个pubKey，那么用户A就只会接收跟我这两个pubKey相关的交易，因为整个网络是明文传输的，我很容易通过监控中心，直接获取到该用户的账户余额等信息；但是加入bloom filter就不一样了，bloom filter的缺点数贺恰好可以用来保护用户的隐私，因为bloom filter的假阳性是可以控制的，我可以适当的增加这个假阳性的概率，进而把不属于我这个pubKey的交易也发到我账户上，真真假假，虚虚实实，混淆有恶意行为的用户的视听。

C. 布隆过滤器既然有错误率，为什么还能应用在key-value系统中

bloom filter的特点是会出现误报，但不会漏报，也就是说对于bloom filter验证的一个数据文件，可能不包含你查找的数据项，但是包含你查找的数据项的数据文件它一定是会返回的，key-value系统中bloom filter返回的数据文件还是需要查看里面的内容才能知道是否存在所需的数据的，这就保证了执行结果的正确性和完整性。因此key-value系统不会因此而出错的，只是多访问一些数据文件而已。在数据量很大key-value系统中，建立统一的B+树索引的代价是非常大的，维护成本也很高，因此综合起来bloom filter的性能是最好的。

D. 布隆过滤器（Bloom Filter）与比特币

布隆过滤器（Bloom Filter）是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆册巧过滤器可以用于检索一个元素是否在一个集合。它的优点是空间效率和查询时间都比一般的算法要好得多，缺点是有一定的误识别率和删除困难。

如果想要判断一个元素是否在一个集合里，一般想到的是将所雹搭有元素保存起来，然后通过比较确定。数组、链表、树等数据结构都是这种思路，它们的时间复杂度为（O(n)、O(logn)）。散列表是一个能够提供更快查询速度的数据结构（时间复杂度为O(1)）。但是随着集合中元素的增加，我们需要的存储空间越来越大，特别是随着大数据的发展，我们越来越不可能将所有的数据都先加载到内存中再进行查找。
这时，我们就可以借助一种新的数据结构，也就是本文的主题：布隆过滤器（Bloom Filter）。
我们使用一段长度为m的二进制位数组，再源姿拿使用k个哈希函数，将一个值进行k次哈希，得到k个索引，并将对应的位置设置为1。

布隆过滤器主要提供两种方法：Add和Test。
Add：通过哈希函数计算，得到k个索引，并将其对应的二进制位设置为1。
Test：通过哈希函数计算，得到k个索引，判断如果任意位置上的二进制都为0，则表示该值一定不在集合中；但是如果所有位置上的二进制都为1，却并不能表示该值一定在集合中，这被称为假阳性，或是判断错误。
可以通过增大数组的长度m，以及增加哈希函数的数量k来降低假阳性的概率。

时间复杂度
由于需要计算k次的哈希，需要的时间复杂度为O(k)，而计算出对应的索引后，可以进行直接地址访问，需要的时间复杂度为O(1)，所以总的时间复杂度为O(k)。

空间复杂度
由于需要长度为m的二进制数据，所以空间复杂度为O(m)，但是由于数据的基本单位是位，假设为了处理100万条数据，为了降低假阳性的概率，我们使用长度为1000万的二进制数组，所需的内存空间为10,000,000/8/1024/1024=1.2M内存空间。

优点

缺点

E. 布隆过滤器详解

布隆过滤器 （英语：Bloom Filter）是 1970 年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。主要用于判断一个元素是否在一个集合中。

通常我们会遇到很多要判断一个元素是否在某个集合中的业务场景，一般想到的是将集合中所有元素保存起来，然后通过比较确定。链表、树源迅、散列表（又叫哈希表，Hash table）等等数据结构都是这种思路。但是随着集合中元素的增加，我们需要的存储空间也会呈现线性增长，最终达到瓶颈。同时检索速度也越来越慢，上述三种结构的检索时间复杂度分别为 ， ， 。

这个时候，布隆过滤器（Bloom Filter）就应运而生。

了解布隆过滤器原理之前，先回顾下 Hash 函数原理。

哈希函数的概念是：将任意大小的输入数据转换成特定大小的输出数据的函数，转换后的数据称为哈希值或哈希编码，也叫散列值。下面是一幅示意图：

所有散列函数都有如下基本特性：

但是用 hash表存储大数据量时，空间效率还是很低，当只有一个 hash 函数时，还很容易发生哈希碰撞。

BloomFilter 是由一个固定大小的二进制向量或者位图（bitmap）和一系列映射函数组成的。

在初始状态时，对于长度为 m 的位数组，它的所有位都被置为0，如下图所示：

当有变量被加入集合时，通过 K 个映射函数将这个变量映射成位图中的 K 个点，把它们置为 1（假定有两个变量都通过 3 个映射函数）。

查询某个变量的时候我们只要看看这些点是不是都是 1 就可以大概率知道集合中有没有它了

为什么说是可能存在，而不是一定存在呢？那是因为映射函数本身就是散列函数，散列函数是会有碰撞的。

布隆顷凳过滤器的误判是指多个输入经过哈希之后在相同的bit位置1了，这样就无法判断究竟是哪个输入产生的，因此误判的根源在于相同的 bit 位被多次映射且置 1。

这种情况也造成了布隆过滤器的删除问题，因为布隆过滤器的每一个 bit 并不是独占的，很有可能多个元素共享了某一位。如果我们直接删除这一位的话，会影响其他的元素。(比如上图中的第 3 位)

相比于其它的数据结构，布隆过滤器在空间和时间方面都有巨大的优势。布隆过滤器存储空间和插入/查询时间都是常数 ，另外，散列函数相互之间没有关系，方便由硬件并行实现。布隆过滤器不需要存储元素本身，在某些对保密要求非常严格的场合有优势。

布隆过滤器可以表示全集，其它任何数据结构都不能；

但是布隆过滤器的缺点和优点一样明显。误算率是其中之一。随着存入的元素数量增加，误算率随之增加。但是如果元素数量太少，则使用散列表足矣。

另外，一般情况下不能从布隆过滤器中删除元素。我们很容易想到把位数组变成整数数组，每插入一个元素相应的计数器雹乎此加 1, 这样删除元素时将计数器减掉就可以了。然而要保证安全地删除元素并非如此简单。首先我们必须保证删除的元素的确在布隆过滤器里面。这一点单凭这个过滤器是无法保证的。另外计数器回绕也会造成问题。

在降低误算率方面，有不少工作，使得出现了很多布隆过滤器的变种。

在程序的世界中，布隆过滤器是程序员的一把利器，利用它可以快速地解决项目中一些比较棘手的问题。

如网页 URL 去重、垃圾邮件识别、大集合中重复元素的判断和缓存穿透等问题。

布隆过滤器的典型应用有：

知道了布隆过滤去的原理和使用场景，我们可以自己实现一个简单的布隆过滤器

分布式环境中，布隆过滤器肯定还需要考虑是可以共享的资源，这时候我们会想到 Redis，是的，Redis 也实现了布隆过滤器。

当然我们也可以把布隆过滤器通过 bloomFilter.writeTo() 写入一个文件，放入OSS、S3这类对象存储中。

Redis 提供的 bitMap 可以实现布隆过滤器，但是需要自己设计映射函数和一些细节，这和我们自定义没啥区别。

Redis 官方提供的布隆过滤器到了 Redis 4.0 提供了插件功能之后才正式登场。布隆过滤器作为一个插件加载到 Redis Server 中，给 Redis 提供了强大的布隆去重功能。

在已安装 Redis 的前提下，安装 RedisBloom，有两种方式

直接编译进行安装

使用Docker进行安装

使用

布隆过滤器基本指令：

我们只有这几个参数，肯定不会有误判，当元素逐渐增多时，就会有一定的误判了，这里就不做这个实验了。

上面使用的布隆过滤器只是默认参数的布隆过滤器，它在我们第一次 add 的时候自动创建。

Redis 还提供了自定义参数的布隆过滤器， bf.reserve 过滤器名 error_rate initial_size

但是这个操作需要在 add 之前显式创建。如果对应的 key 已经存在，bf.reserve 会报错

我是一名 Javaer，肯定还要用 Java 来实现的，Java 的 Redis 客户端比较多，有些还没有提供指令扩展机制，笔者已知的 Redisson 和 lettuce 是可以使用布隆过滤器的，我们这里用 Redisson

为了解决布隆过滤器不能删除元素的问题，布谷鸟过滤器横空出世。论文《Cuckoo Filter：Better Than Bloom》作者将布谷鸟过滤器和布隆过滤器进行了深入的对比。相比布谷鸟过滤器而言布隆过滤器有以下不足：查询性能弱、空间利用效率低、不支持反向操作（删除）以及不支持计数。

由于使用较少，暂不深入。

https://www.cs.cmu.e/~dga/papers/cuckoo-conext2014.pdf

http://www.justdojava.com/2019/10/22/bloomfilter/

https://www.cnblogs.com/cpselvis/p/6265825.html

https://juejin.im/post/5cc5aa7ce51d456e431adac5

F. BloomFilter详解（布隆过滤器）

从上式中可以看出，当m增大或n减小时，都会使得误判率减小，这也符合直觉。

现在计算对于给定的m和n，k为何值时可以使得误判率最低。设误判率为k的函数为：

这说明了若想保持某固定误判率不变，布隆过滤器的bit数m与被add的元素数n应该是线性同步增加的。

三 如何设计bloomfilter

此概率为某bit位在插入n个元素后未被置位的概率。因此，想保持错误率低，布隆过滤器的空间使用率需为50%。

bloomfilter的各个参数的错误率

公式推完了，大家可以看看，里面的数学公式基本用到了指数函数 对数函数 微积分求导法则 概率论的知识，大家可以补充看下课本。

个人介绍：杜宝坤，京东联邦学习从0到1构建者，带领团队构建了京东的联邦学习解决方案，实现了电知慧局商营销领域支持超大规模的工业化联邦学习解决方案，支持超大规模样本PSI隐私对齐、安全的树模型与神经网络模型等众多模型支持，并且实现了广告搭让侧等业务领域的落地，开创了新的业务增长点，产生了显著的业务经济效益。

个人喜欢研究技术。基碧猛于从全链路思考与决策技术规划的考量，研究的领域比较多，从架构、数据到算法与算法框架均有涉及。欢迎喜欢技术的同学和我交流，邮箱： [email protected]