Jenner's Blog

不变秃,也要变强!

0%

布隆过滤器

引例

算法题目

如果一个黑名单网站包含100亿个黑名单网页,每个网页最多占64B,设计一个系统,判断当前的URL是否在这个黑名单当中,要求额外空间不超过30GB,允许误差率为万分之一。

解题思路

布隆过滤器

基础介绍

布隆过滤器(Bloom Filter)是1970年由布隆提出的。它实际上是一个很长的二进制向量(位图)和一系列随机映射函数(哈希函数)。

布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都远远超过一般的算法,缺点是有一定的误识别率和删除困难。
实际工程的应用实际上,布隆过滤器广泛应用于网页黑名单系统、垃圾邮件过滤系统、爬虫网址判重系统等,有人会想,我直接将网页URL存入数据库进行查找不就好了,或者建立一个哈希表进行查找不就OK了。当数据量小的时候,这么思考是对的,但如果整个网页黑名单系统包含100亿个网页URL,在数据库查找是很费时的,并且如果每个URL空间为64B,那么需要内存为640GB,一般的服务器很难达到这个需求。那么,在这种内存不够且检索速度慢的情况下,不妨考虑下布隆过滤器,但业务上要可以忍受判断失误率。
46ce58dd1b5437be76f0a0a7996d78e6.jpeg

位图(bitmap)布隆过滤器其中重要的实现就是位图的实现,也就是位数组,并且在这个数组中每一个位置只占有1个bit,而每个bit只有0和1两种状态。如上图bitarray所示!bitarray也叫bitmap,大小也就是布隆过滤器的大小。假设一种有k个哈希函数,且每个哈希函数的输出范围都大于m,接着将输出值对k取余(%m),就会得到k个[0, m-1]的值,由于每个哈希函数之间相互独立,因此这k个数也相互独立,最后将这k个数对应到bitarray上并标记为1(涂黑)。等判断时,将输入对象经过这k个哈希函数计算得到k个值,然后判断对应bitarray的k个位置是否都为1(是否标黑),如果有一个不为黑,那么这个输入对象则不在这个集合中,也就不是黑名单了!如果都是黑,那说明在集合中,但有可能会误,由于当输入对象过多,而集合也就是bitarray过小,则会出现大部分为黑的情况,那样就容易发生误判!因此使用布隆过滤器是需要容忍错误率的,即使很低很低!

布隆过滤器重要参数计算

通过上面的描述,我们可以知道,如果输入量过大,而bitarray空间的大小又很小,那么误判率就会上升。那么bitarray空间大小怎么确定呢?不要慌,已经有人通过数据推倒出公式了!假设输入对象个数为n,bitarray大小(也就是布隆过滤器大小)为m,所容忍的误判率p和哈希函数的个数k。计算公式如下:(小数向上取整)
fc1fb96508a363b17d1bb7737dc51e54.jpeg

注意:由于我们计算的m和k可能是小数,那么需要经过向上取整,此时需要重新计算误判率p!假设一个网页黑名单有URL为100亿,每个样本为64B,失误率为0.01%,经过上述公式计算后,需要布隆过滤器大小为25GB,这远远小于使用哈希表的640GB的空间。并且由于是通过hash进行查找的,所以基本都可以在O(1)的时间完成!

在比特币中的应用

比特币中布隆过滤器是在BIP-0037中提到。下面我们通过“比特币钱包如何知道有多少钱”的问题来介绍布隆过滤器在比特币中的应用。这个问题其实就是“比特币钱包如何知道有多少UTXO”。
比特币网络中主要有两种节点类型:

  • 全节点:存放所有区块数据和交易
  • SPV节点:只存放区块头(Block Header)

我们假设,比特币钱包最开始值存储了私钥,没有任何其他数据。那么它要获取跟自己地址相关的UTXO,只能向比特币网络中相邻的全节点询问,询问的方式有3种:

  • 方法一:下载完整的区块链账本,自己查找
    这种方法很简单,也能隐藏用户的隐私(全节点无法知道SPV节点关联的钱包的地址)。但是在手机端是不现实的,每次用户需要下载上百G的区块链数据,才能知道自己钱包有多少钱,虽然保护了用户隐私,但是浪费了存储空间和带宽。所以这种方法不行,而这也是为什么有SPV的概念存在,中本聪也是考虑到移动支付的场景的。
  • 方法二:直接告诉全节点自己钱包的所有地址,全节点返回所有跟钱包地址相关的UTXO
    这种方法直接等于是泄露了用户隐私,其他全节点就知道SPV节点所关联的钱包地址。但是好处是所要下载的数据少了很多,也更精确了。
  • 方法三:告诉全节点部分自己钱包的地址信息,全节点返回可能相关的UTXO这种方法实际上就是采用布隆过滤器的方法隐藏用户隐私,从而做到即保护用户隐私,又节省存储空间和带宽。
    布隆过滤器的两个特点:只能告诉你某个元素可能存在集合中以及某个元素一定不存在集合中。这里可以简单理解Bloom Filter就是一个过滤器,用来过滤不属于钱包的UTXO。钱包节点(SPV节点)会以布隆过滤器的形式告诉相邻全节点自己地址信息,那么根据布隆过滤器的特性,会有两种结果:没有通过布隆过滤器过滤出来的UTXO,就【一定】不属于钱包地址通过布隆过滤器过滤出来的UTXO,【可能】属于钱包地址这种方法虽然在一定程度上保护用户隐私,节省了存储空间和带宽,但是根据布隆过滤器的特点,我们知道,随着钱包交易的UTXO越多,布隆过滤器误报率会越高,也就是相邻全节点返回正确的UTXO概率越低。

参考

数学之美:布隆过滤器 - TeddyZhang的文章 - 知乎
比特币原理分析(三)

点击下方打赏按钮,获得支付宝二维码