linux文件删除原理

1 什么是bloom filter?

bloom filter是一种空间效率很高的随机数据结构，基本原理是：
当一个元素加入集合时，通过$k$个hash函数将这个元素映射成一个位数组(bit array)中的$k$个点，将$k$个点均置为1。
检索时只需要查看这些点是否为1，如果这些点存在0，则被检索元素一定不存在；如果都为1，则被检索元素很可能存在。

2 集合表示和元素查询

初始状态，bloom filter是一个$m$位的位数组$A$，初始值均为0：

对于$n$个元素的集合$S={x_1,x_2,...,x_n}$，bloom filter使用$k$个相互独立的hash函数，分别将集合中每个元素映射到$A$的索引${ 1,2,...,m }$。对任意一个元素$x$，第$i$个hash函数映射的位置$h_i(x)$被置为1($1 \leq k$)，如果一个位置多次被置为1，则只有第一次会起作用，后面几次保持1即可。下图中，$k=3$且有两个hash函数选中同一个位置：

判断$y$是否属于这个集合时，对$y$应用$k$次hash函数，如果$h_i(y)$位置都是1($1 \leq k$)，则认为$y$是集合中的元素，否则$y$不是集合中的元素，下图中$y_1$就不是集合中的元素，$y_2$可能属于这个集合，或恰好为一个false positive。

3 错误率估计

bloom filter在判断元素是否属于集合时，会有一定的错误率false positive rate，下面我们来估计错误率的大小。为了简化模型，假设$kn<m$且各hash函数完全随机，当集合$S={x_1,x_2,...,x_n}$的所有元素都被$k$个hash函数映射到$m$位数组中时，数组某一位仍然0的概率是：
$p' = (1 - \frac{1}{m})^{kn} \approx e^{-\frac{kn}{m}}$
其中$\frac{1}{m}$表示任意一个hash函数选中这一位的概率(hash函数完全随机)，$1 - \frac{1}{m}$表示hash一次没有选中这一位的概率，要将$S$映射到位数组中，需要做$kn$次hash，某一位还是0意味着$kn$次hash都没有选中，因此这个概率为$1 - \frac{1}{m}$的$kn$次方。令$p = e^{-\frac{kn}{m}}$是为了简化运算，这里用到了$e$的常用近似：
$\lim_{x\rightarrow+\infty}(1 - \frac{1}{x})^{-x} = e$

令$\rho$为数组中0的比例，则$\rho$的数学期望$E(\rho) = p'$，在$\rho$已知的情况下，要求的错误率false positive rate为：
$(1 - \rho)^k \approx (1 - p')^k \approx (1 - p)^k$
$1 - \rho$为数组中1的比例，$(1 - \rho)^k$表示$k$次hash恰好选中1的概率，即false positive rate。上式中第二步近似前面已经提到，现在来看第一步近似：$p'$只是$\rho$的数学期望，实际中$\rho$的值可能偏离它的期望值，M.Mitzenmacher已经证明，位数组中0的比例非常集中地分布在它的数学期望值附近，因此第一步的近似得以成立。分别将$p$和$p'$代入上式中得：
$f' = (1 - (1 - \frac{1}{m})^{kn})^k = (1 - p')^k$
$f = (1 - e^{-\frac{kn}{m}})^k = (1 - p)^k$
相比$p'$和$f'$，使用$p$和$f$通常在分析中更为方便。

4 最优的哈希函数个数

既然bloom filter要靠多个哈希函数将集合映射到位数组中，那么应该选择几个哈希函数才能使元素查询时的错误率降到最低呢？这里有两个互斥的理由：如果哈希函数的个数多，那么在对一个不属于集合的元素进行查询时得到0的概率就大；但另一方面，如果哈希函数的个数少，那么位数组中的0就多，为了得到最优的哈希函数个数，我们需要根据上一小节中的错误率公式进行计算。

先用$p$和$f$进行计算，注意到$f = e^{kln(1 - e^{\frac{-kn}{m}})}$，令$g = kln(1 - e^{\frac{-kn}{m}})$，只要让$g$取到最小，$f$自然也取到最小，由于$p = e^{\frac{-kn}{m}}$，我们可以将$g$写为：
$g = -\frac{m}{n}ln(p)ln(1-p)$
根据对称性法则可以得到当$p=\frac{1}{2}$，即$k = \frac{m}{n}ln2$时，$g$取最小值，在这种情况下，最小错误率
$f = (\frac{1}{2})^k \approx (0.6185)^{\frac{m}{n}}$。另外，注意到$p$是位数组中某一位仍为0的概率，所以$p=\frac{1}{2}$对应这位数组中0和1各一半，换句话说，要想保持错误率低，最好让位数组有一半空着。

需要强调的一点是，$p=\frac{1}{2}$时错误率最小这个结果并不依赖于近似值$p$和$f$，同样对于
$f'=e^{kln(1-(1-\frac{1}{m})^{kn})}$，$g'=kln(1-(1-\frac{1}{m})^{kn})$，$p'=(1-\frac{1}{m})^{kn}$，我们可以将$g'$写为：
$g'=\frac{1}{nln(1-1/m)}ln(p')ln(1-p')$
同样根据对称性法则可以得到当$p'=\frac{1}{2}$时，$g'$取得最小值。

5 位数组的大小

下面我们来看看，在不超过一定错误率的情况下，bloom filter至少需要多少位才能表示全集中任意$n$个元素的集合。假设全集中共有$u$个元素，允许的最大错误率为$\epsilon$，下面我们来求位数组的位数$m$。

假设$X$为全集中任取$n$个元素的集合，$F(X)$表示$X$的位数组，那么对于集合$X$中任意一个元素$x$，在$S=F(x)$中查询$x$都能得到肯定的结果，即$S$能够接受$x$，显然由于bloom filter引入了错误，$S$能够接受的不仅仅是$X$中的元素，它还能够接受$\epsilon(u - n)$个false positive。因此对于一个确定的位数组来说，它能够接受总共$n + \epsilon(u -n)$个元素。在$n + \epsilon(u -n)$个元素中，$S$真正表示的只有其中$n$个，所以一个确定的位数组可以表示为：
${n + \epsilon(u - n) \choose n}$
个集合，$m$位的位数组共有$2^m$个不同的组合，进而可以推出，$m$位的位数组可以表示为：
$2^m{n + \epsilon(u - n) \choose n}$
个集合，全集中$n$个元素的集合总共有：
${u \choose n}$
个，因此要让$m$位的位数组能够表示所有$n$个元素的集合，必须有：
$2^m{n + \epsilon(u - n) \choose n} \geq {u \choose n}$
即：
$m \geq \log_2{\frac{u \choose n}{n + \epsilon(u - n) \choose n}} \approx \log_2{\frac{u \choose n}{\epsilon u \choose n}} \geq \log_2{\epsilon^{-n}} = n\log_2{\frac{1}{\epsilon}}$
上式中的近似前提是$n$和$\epsilon u$相比很小，这也是在实际情况中常常发生的，根据上式我们得出结论：在错误率不大于$\epsilon$的情况下，$m$至少要等于$n\log_2{\frac{1}{\epsilon}}$才能表示任意$n$个元素的集合。

上一小节中我们曾算出当$k = ln2(\frac{m}{n})$时错误率$f$最小，这时$f={\frac{1}{2}^k={\frac{1}{2}}^{mln2/n}}$。现在令$f\leq\epsilon$，可以推出：
$m\geq n{\frac{\log_2{\frac{1}{\epsilon}}}{ln2}}=n\log_2e\log_2{\frac{1}{\epsilon}}$
这个结果比前面算的下界$n\log_2{\frac{1}{\epsilon}}$大了$\log_2{e} \approx 1.44$倍，这说明hash函数的个数取到最优时，要让错误率不超过$\epsilon$，$m$至少需要取到最小值的1.44倍。

6 总结

实际问题中常常会碰到时间换空间或空间换时间的情况，bloom filter在时间空间这两个因素之外又引入了另一个因素：错误率，在使用bloom filter判断一个元素是否属于某个集合时，会有一定的错误率，也就是说，有可能把不属于这个集合的元素误认为属于这个集合(False Positive)，但不会把属于这个集合的元素误认为不属于这个集合(False Negative)。在增加了错误率这个因素之后，bloom filter通过允许少量的错误来节省大量的存储空间。自从Burton Bloom在70年代提出bloom filter之后，bloom filter就被广泛用于拼写检查和数据库系统。

7 适用范围

数据字典，数据的判重，集合求交集；
网页爬虫对URL去重，避免爬取相同URL地址；
反垃圾邮件，从数十亿个垃圾邮件列表中判断某邮箱是否垃圾邮箱；
Google Chrome使用布隆过滤器识别恶意URL；
Medium使用布隆过滤器避免推荐给用户已经阅读过的文章；
Google BigTable，Apache HBbase和Apache Cassandra使用布隆过滤器减少对不存在的行和列的查找；

除了上述的应用场景之外，布隆过滤器还有一个应用场景就是解决缓存穿透的问题，所谓缓存穿透就是服务调用方每次都查询不在缓存中的数据，这样每次服务调用都会到数据库中进行查询，如果这类请求比较多的话，就会导致数据库压力增大，缓存就失去了意义。利用布隆过滤器我们可以预先把数据查询的主键，比如用户ID或文章ID缓存到过滤器中，当根据ID进行查询的时候，先判断该ID是否存在，若存在，则进行下一步处理；若不存在，直接返回。这样就不会触发后续的数据库查询，需要注意的是缓存穿透不能完全解决，我们只能将其控制在一个可以容忍的范围。

8 要点

原理来说很简单，位数组 + $k$个独立hash函数，将hash函数对应的值的位数组置1，查找时如果发现所有hash函数对应位都是1说明存在，这个过程并不保证查找结果是100%正确，同时也不支持删除一个已经插入的关键字，因为该关键字对应的位会牵动到其他的关键字，一个简单的改进是counting bloom filter，用一个counter数组代替位数组，就可以支持删除。

还有一个比较重要的问题，如何根据输入元素个数n，确定位数组m的大小及hash函数个数，当hash函数个数$k=\frac{m}{n}ln2$时错误率最小，在错误率不大于$\epsilon$的情况下，$m$至少要等于$n\log_2{\frac{1}{\epsilon}}$才能表示任意$n$个元素的集合，但m还应该更大些，因为还要保证bit数组里至少一半为0，则$m\geq n\log_2{\frac{1}{\epsilon}}\log_2{e}$，大概为$n\log_2{\frac{1}{\epsilon}}$的1.44倍。

举个例子我们假设错误率为0.01，则$m$应大概是$n$的13倍，这样$k$大概是8个，注意这里$m$与$n$的单位不同，$m$是bit为单位，而$n$则是以元素个数为单位(准确的说是不同元素的个数)，通常单个元素的长度都是有很多bit的，所以使用bloom filter内存上都是很节省的。

9 扩展

Bloom filter将集合中的元素映射到位数组中，用$k$($k$为哈希函数个数)个映射位是否全1表示元素在不在这个集合中。Counting bloom filter(CBF)将位数组中的每一位扩展为一个counter，从而支持了元素的删除操作。Spectral Bloom Filter(SBF)将其与集合元素的出现次数关联，SBF采用counter中的最小值来近似表示元素的出现频率。

10 问题实例

给你A，B两个文件，各存放50亿条URL，每条URL占用64字节，内存限制是4G，找出A，B文件共同的URL；如果是三个乃至n个文件呢？
我们来计算下内存的占用，4G=2^32大概是40亿*8，约为340亿，n=50亿，如果按出错率0.01算需要大概480亿个bit。现在可用的是340亿，相差不大，不过可能会使出错率上升些。另外，如果这些url ip是一一对应的，就可以先转换成ip。

11 源码

PostgreSQL src/backend/lib/bloomfilter.c

---

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至yj.mapple@gmail.com