布隆过滤器与海量数据处理问题¶

约 3031 个字 101 行代码 5 张图片预计阅读时间 11 分钟

介绍¶

前面学习到了位图，在处理含有大量无符号整型数据时有着格外好的性能，但是缺点就是只能处理无符号整型，但是在实际中，可能还存在大量非无符号整型数据需要处理，此时就需要使用布隆过滤器

布隆过滤器底层依旧还是位图，但是因为位图只能处理无符号整型数据，所以需要先按照一种标准将需要判断的数据通过转换变为无符号整型再存储到位图中

在布隆过滤器中，一般考虑采用哈希函数将非无符号整型的数据向无符号整型进行映射，此时就会涉及到一个问题：哈希冲突。如果只使用一位比特位作为在或者不在的判断标准，那么冲突的概率会非常大，所以一般可以考虑采用多个哈希函数计算出无符号整型分别映射到位图中，此时映射在位图的多个比特位整体是否全为1就变成了判断一个非无符号整型数据是否存在的标准

实际上，上面提到的使用多个哈希函数的方式依旧会存在哈希冲突问题导致本来不存在的数据因为哈希冲突导致错误判断为存在（后面称为误判），所以上面的方式本质上是降低冲突而不是解决冲突

布隆过滤器最大的缺点就是无法准确判断指定的数据是否存在，但是这种情况下，因为多个比特位同时为1才表示指定数据存在，而不存在只需要判断映射的位置有一个比特位为0就是不存在，而空间足够的情况下，0出现的次数肯定比1多，所以理论上可以认为布隆过滤器可以做到判定不存在是准确的，而判定存在是不准确的（即存在误判的情况）

例如，正常情况下：

而如果是下面的情况就是误判：

布隆过滤器误判率推导（了解）¶

推导过程：

Note

说明：这个比较复杂，涉及概率论、极限、对数运算，求导函数等知识

假设

\(m\)：布隆过滤器的bit长度

\(n\)：插入过滤器的元素个数

\(k\)：哈希函数的个数

布隆过滤器哈希函数等条件下某个位设置为1的概率：\(\frac{1}{m}\)

布隆过滤器哈希函数等条件下某个位设置不为1的概率：\(1 - \frac{1}{m}\)

在经过\(k\)次哈希后，某个位置依旧不为1的概率：\((1 - \frac{1}{m})^k\)

根据极限公式：\(\lim\limits_{m \to \infty}(1 - \frac{1}{m})^{-m} = e\)可以得到下面的转化：

\(\left(1 - \frac{1}{m}\right)^{k} \approx \left[\left(1 - \frac{1}{m}\right)^{m}\right]^{\frac{k}{m}} \approx e^{-\frac{k}{m}}\)

Note

上面的推导过程中的\(\left[\left(1 - \frac{1}{m}\right)^{m}\right]^{\frac{k}{m}} \approx e^{-\frac{k}{m}}\)将\(k\)转换为\(\frac{k}{m} \times m\)凑出前面的极限公式

所以可以得出：

添加\(n\)个元素某个位置不置为1的概率：\((1 - \frac{1}{m})^{kn} \approx e^{\frac{-kn}{m}}\)

添加\(n\)个元素某个位置置为1的概率：\(1 - (1 - \frac{1}{m})^{kn} \approx 1 - e^{\frac{-kn}{m}}\)

查询⼀个元素，\(k\)次哈希后误判的概率为都命中1的概率：\((1 - (1 - \frac{1}{m})^{kn})^k \approx (1 - e^{\frac{-kn}{m}}) ^ k\)

最后：

布隆过滤器的误判率为：\(f(k) = (1 - e^{\frac{-kn}{m}}) ^ k\)，可以转化为\(f(k) = (1 - \frac{1}{e^{\frac{kn}{m}}}) ^ k\)

由误判率公式可知，在\(k\)一定的情况下，当\(n\)增加时，误判率增加，\(m\)增加时，误判率减少

Note

在表达式中\(f(k) = (1 - \frac{1}{e^{\frac{kn}{m}}}) ^ k\)，在\(k\)一定的情况下，如果\(n\)大于\(m\)且\(n\)持续增大，则指数就会越来越大，此时\(e^{\frac{kn}{m}}\)就会越来越大，\(1\)作为分子除以一个越来越大的数值就会导致整体越来越小，\(1\)减去一个整体越来越小的数值就会导致减法值越来越大，再进行幂运算就是指数级增长，导致误判率增加，对于\(m\)大于\(n\)且\(m\)持续增大则刚好相反

在\(m\)和\(n\)一定，在对误判率公式求导，误判率尽可能小的情况下，可以得到哈希函数个数为\(k=\frac{m}{n} ln{2}\)时误判率最低

希望的误判率\(p\)和插入数据个数\(n\)确定的情况下，再把上面的公式代入误判率公式可以得到，通过期望的误判率和插⼊数据个数\(n\)得到需要的bit长度：\(m = -\frac{n \times ln{p}}{(ln2)^2}\)

Note

上面的具体推导过于复杂，不再展示

布隆过滤器代码实现¶

需要使用到的模版参数：

常量因子（相当于\(\frac{k}{ln2}\)）：定义为size_t X=5
插入过滤器的元素个数：定义为size_t N
待存储类型：class T = string
三个哈希函数（默认为string）：
1. 定义为class hash1 = HashFuncBKDR
2. 定义为class hash2 = HashFuncAP
3. 定义为class hash3 = HashFuncDJB

示例代码如下：

C++
#ifndef BLOOM_FILTER_H
#define BLOOM_FILTER_H
#include <iostream>
#include <bitset>
namespace BLOOM_FILTER
{
    struct HashFuncBKDR
    {
        size_t operator()(const std::string& s)
        {
            size_t hash = 0;
            for (auto ch : s)
            {
                hash *= 31;
                hash += ch;
            }
            return hash;
        }
    };

    struct HashFuncAP
    {
        size_t operator()(const std::string& s)
        {
            size_t hash = 0;
            for (size_t i = 0; i < s.size(); i++)
            {
                if ((i & 1) == 0) // 偶数位字符
                {
                    hash ^= ((hash << 7) ^ (s[i]) ^ (hash >> 3));
                }
                else              // 奇数位字符
                {
                    hash ^= (~((hash << 11) ^ (s[i]) ^ (hash >> 5)));
                }
            }
            return hash;
        }
    };

    struct HashFuncDJB
    {
        size_t operator()(const std::string& s)
        {
            size_t hash = 5381;
            for (auto ch : s)
            {
                hash = hash * 33 ^ ch;
            }
            return hash;
        }
    };

    template <size_t N, size_t X = 5, class T = std::string, class hash1 = HashFuncBKDR, class hash2 = HashFuncAP,class hash3 = HashFuncDJB>
    class Bloom_Filter
    {
    public:
        void set(const T& value)
        {
            // 计算出hash值
            // 与M取模确保hash值在布隆过滤器bit长度之内，防止越界
            size_t hs1 = hash1()(value) % M; // 匿名对象调用operator()
            size_t hs2 = hash2()(value) % M;
            size_t hs3 = hash3()(value) % M;

            // 设置标记位
            _bf.set(hs1);
            _bf.set(hs2);
            _bf.set(hs3);
        }

        bool test(const T& value)
        {
            // 计算出hash值
            // 只有有一个为0就返回false
            size_t hs1 = hash1()(value) % M;
            if(!_bf.test(hs1))
            {
                return false;
            }
            size_t hs2 = hash2()(value) % M;
            if(!_bf.test(hs2))
            {
                return false;
            }
            size_t hs3 = hash3()(value) % M;
            if(!_bf.test(hs3))
            {
                return false;
            }

            // 三个if都没走说明测试均为1
            return true;
        }
    private:
        // 长度
        const size_t M = N * X;
        std::bitset<N * X> _bf;
    };
}
#endif //BLOOM_FILTER_H

布隆过滤器删除问题¶

布隆过滤器默认是不支持删除的，因为比如"猪八戒"和"孙悟空"都映射在布隆过滤器中，他们映射的位有一个位是共同映射的（冲突的），如果把"孙悟空"删掉，那么再去查找"猪八戒"会查找不到，因为那么"猪八戒"间接被删掉了

解决方案：可以考虑计数标记的方式，一个位置用多个位标记，记录映射这个位的计数值，删除时，仅仅减减计数，那么就可以某种程度支持删除。但是这个方案也有缺陷，如果一个值不在布隆过滤器中，则在删除时，映射位的计数自减也会影响已存在的值，从而导致一个确定存在的值，可能会变成不存在。当然也有人提出可以考虑计数方式支持删除，但是定期重建一下布隆过滤器，这样也是一种思路

布隆过滤器的应用¶

首先分析一下布隆过滤器的优缺点：

优点：效率高，节省空间，相比位图，可以适用于各种类型的标记过滤

缺点：存在误判（在是不准确的，不在是准确的），不好支持删除

布隆过滤器在实际中的一些应用：

爬虫系统中URL去重：

在爬虫系统中，为了避免重复爬取相同的URL，可以使用布隆过滤器来进行URL去重。爬取到的URL可以通过布隆过滤器进行判断，已经存在的URL则可以直接忽略，避免重复的网络请求和数据处理

垃圾邮件过滤：

在垃圾邮件过滤系统中，布隆过滤器可以用来判断邮件是否是垃圾邮件系统可以将已知的垃圾邮件的特征信息存储在布隆过滤器中，当新的邮件到达时，可以通过布隆过滤器快速判断是否为垃圾邮件，从而提高过滤的效率

预防缓存穿透：

在分布式缓存系统中，布隆过滤器可以用来解决缓存穿透的问题。缓存穿透是指恶意用户请求一个不存在的数据，导致请求直接访问数据库，造成数据库压力过大。布隆过滤器可以先判断请求的数据是否存在于布隆过滤器中，如果不存在，直接返回不存在，避免对数据库的无效查询

对数据库查询提效：

在数据库中，布隆过滤器可以用来加速查询操作。例如：一个APP要快速判断一个电话号码是否注册过，可以使用布隆过滤器来判断一个用户电话号码是否存在于表中，如果不存在，可以直接返回不存在，避免对数据库进行无用的查询操作。如果在，再去数据库查询进行二次确认

海量数据处理问题¶

10亿个整数里面求最大的前100个。

经典Top-k问题，用堆解决，具体见堆
给两个文件，分别有100亿个query，我们只有1G内存，如何找到两个文件交集

解决方案1：

这个首先可以用布隆过滤器解决，一个文件中的query放进布隆过滤器，另一个文件依次查找，在的就是交集，问题就是找到交集不够准确，因为在的值可能是误判的，但是交集一定被找到了

解决方案2：

哈希切分，首先内存的访问速度远大于硬盘，大文件放到内存搞不定，那么可以考虑切分为小文件，再放进内存处理。

但是不要平均切分，因为平均切分以后，每个小文件都需要依次暴力处理，效率还是太低了。可以利用哈希切分，依次读取文件中query，i=HashFunc(query)%N，N为准备切分多少分小文件，N取决于切成多少份，内存能放下，query放进第i号小文件，这样A和B中相同的query算出的哈希值i是一样的，相同的query就进入的编号相同的小文件就可以编号相同的文件直接找交集，不用交叉找，效率就提升了。

本质是相同的query在哈希切分过程中，一定进入的同一个小文件Ai和Bi，不可能出现A中的的query进入Ai，但是B中的相同query进入了和Bj的情况，所以对Ai和Bi进行求交集即可，不需要Ai和Bj求交集。（本段表述中和j是不同的整数）

哈希切分的问题就是每个小文件不是均匀切分的，可能会导致某个小文件很大内存放不下。分析一下某个小文件很大有两种情况：
1. 这个小文件中大部分是同一个query
2. 这个小文件是有很多的不同query构成，本质是这些query冲突了
针对情况1，其实放到内存的set中是可以放下的，因为set是去重的

针对情况2，需要换个哈希函数继续二次哈希切分。所以如果遇到大于1G小文件，可以继续读到set中找交集，若set的insert时抛出了异常（set插入数据抛异常只可能是申请内存失败了，不会有其他情况），那么就说明内存放不下是情况2，换个哈希函数进行二次哈希切分后再对应找交集
给一个超过100G大小的log file，log中存着IP地址，设计算法找到出现次数最多的IP地址，查找出现次数前10的IP地址

本题的思路跟上题完全类似，依次读取文件A中IP，i=HashFunc(query)%500,query,放进Ai号小文件，然后依次用map<string,int>对每个Ai小文件统计IP次数，同时求出现次数最多的IP或者Top-k。本质是相同的IP在哈希切分过程中，一定进入的同一个小文件Ai，不可能出现同一个IP进入Ai和Aj的情况，所以对Ai进行统计次数就是准确的IP次数

Note

第2个问题和第3个问题本质就是利用相同的哈希值将相同的内容集中在相同的位置