一、引出布隆过滤器
现在有一个问题：
现在有50亿过个电话号码，有10万个电话号码，要快速准确判断10万个电话号码是否存在。

1.如果通过数据库查询：不能快速查询。
2.如果是将数据放入redis集合中：那么50亿个电话号码大概要占用40G的内存，内存很可能不够
3.使用hyperloglog：准确性达不到（有一定的误差率）

现实中其实也有这样的问题，例如网络爬虫重复url的检测

这个问题就可以使用到布隆过滤器

它可以用很小的空间解决上述的“在一个大数据集中过滤一个小数据集”的问题。它的优点是空间效率和查询时间都远远超过一般的算法，缺点是有一定的误识别率和删除困难。它的误识别体现在：如果检测出一个元素在集合中则这个元素实际不一定在集合中，如果检测出一个元素不在集合中，则这个元素就一定不在集合中。

二、布隆过滤器的实现原理
需要3个对象：数据，一个很长的二进制向量（长度可能有几十亿几百亿个位）和若干个哈希函数

例如，下面有一个50个长度的二进制（实际应用中肯定不只这么多个）

00000000000000000000000000000000000000000000000000

还有一个数据 136xxxx8888
还有8个哈希函数 f1~f8

将数据分别传入f1~f3这3个函数，将得到的结果（得到的结果范围只会在1~49之间）所在的位标记为1
比如，得到的结果分别是4，11和48，那么这个二进制就标记为：

00001000000100000000000000000000000000000000000010

还有另外一个数据 138xxx5555，得到的结果是3，33，48，那么这个二进制就要在之前的基础上继续标记1变成

00011000000100000000000000000000100000000000000010

什么是布隆过滤器，布隆过滤器就是将50亿个电话号码走一遍上面的流程所构建出来的这个二进制向量。

如何检验某个号码是否在这50亿个号码中？
只需将这个号码带入上面3个哈希函数得到3个位数，查看二进制向量中的这3个位数是否都是1，如果都是1就说明这个号码在这50亿个号码中。

布隆过滤器当然也是有一定的误差，但是这个误差可以通过调整哈希函数的个数和二进制向量的总长度来控制，而hyperloglog的误差是不可控的。

总结：布隆过滤器的本质是一个二进制向量，在使用布隆过滤器之前，我们先要构建出布隆过滤器。构建好之后，我们只需要存储这个二进制向量，不用存储50亿个电话这么多数据，极大的节省了内存。

三、布隆过滤器的误差率
现在有一个m个位的二进制向量，n个数据和k个哈希函数
误差率的直接因素：m/n的比率和k的个数

m/n越大，k越大，误差就越小

误差率公式为： (1-e^(-kn/m))^k

四、redis布隆过滤器的实现

下面使用redis + python实现一下布隆过滤器，布隆过滤器在redis中本质上是一个位图结构

import mmh3,redis,math

class PyBloomFilter():
    # 内置100个随机种子，一个随机种子就是一个hash函数
    SEEDS = [543, 460, 171, 876, 796, 607, 650, 81, 837, 545, 591, 946, 846, 521, 913, 636, 878, 735, 414, 372,
             344, 324, 223, 180, 327, 891, 798, 933, 493, 293, 836, 10, 6, 544, 924, 849, 438, 41, 862, 648, 338,
             465, 562, 693, 979, 52, 763, 103, 387, 374, 349, 94, 384, 680, 574, 480, 307, 580, 71, 535, 300, 53,
             481, 519, 644, 219, 686, 236, 424, 326, 244, 212, 909, 202, 951, 56, 812, 901, 926, 250, 507, 739, 371,
             63, 584, 154, 7, 284, 617, 332, 472, 140, 605, 262, 355, 526, 647, 923, 199, 518]
    
    # capacity是数据集的容量
    # error_rate是错误率
    # conn是redis的连接客户端，用于操作redis
    # key是redis布隆过滤器的key名
    def __init__(self, key, capacity=1000000000, error_rate=0.00000001, conn=None):
        self.m = math.ceil(capacity * math.log2(math.e) * math.log2(1 / error_rate))  # 计算需要的总bit位数
        self.k = math.ceil(math.log1p(2) * self.m / capacity)  #计算 需要最少的hash函数个数()
        self.mem = math.ceil(self.m / 8 / 1024 / 1024)  # 需要的多少M内存
        self.seeds = self.SEEDS[0:self.k]   # 获取随机种子
        self.N = 2 ** 31 - 1
        self.redis = conn
        self.key = "bf_" + key
        
    # 往布隆过滤器添加位（构造布隆过滤器）
    def add(self, value):
        hashs = get_hashs(value)    # 计算某个值的所有的哈希值，是一个列表
        
        print(len(hashs), hashs)
        [self.redis.setbit(self.key, hash, 1) for hash in hashs]
        
    # 判断是否存在
    def is_exist(self, value):
        hashs = get_hashs(value)
        exist = True
        while exist and len(hashs):
            exist = self.redis.getbit(self.key, hashs.pop())
        
        return exist
        
    # 获取hash值
    def get_hashs(self, value):
        hashs = []
        for seed in self.seeds:
            # 计算hash值
            hash = mmh3.hash(value, seed)
            if hash >= 0:
                hashs.append(hash)
            else:
                hash.append(self.N - hash)
        
        return hashs

在redis中，一个位图的最大空间是512MB，大概有43亿个位的容量。

 

布隆过滤器的应用除了有去重之外，还可以防止缓存穿透：
首先什么是缓存穿透，缓存穿透就是攻击者发起请求查询很多很多个redis和mysql中都不存在的key，由于这个key不存在于redis中，于是服务器会去请求mysql，但是在mysql中也找不到相应的记录。此时请求全都打在了mysql上，导致数据库压力剧增，甚至可能崩溃。

 

如何使用布隆过滤器防止缓存穿透：
例如，某个接口是通过id来查找数据的，那么可以将数据库中这个表的所有id添加都布隆过滤器中。当用户请求这个接口，传入一个id的时候，就检验这个id是否在布隆过滤器中，如果不存在说明数据库中不存在这个id，此时直接返回空即可。

 

当然，使用布隆过滤器防缓存穿透有一定的缺点：
1.误判：可能有些实际上不存在的id被布隆过滤器判定为存在。
2.删除困难：加入数据库对某条数据进行删除，此时我们无法在布隆过滤器中删除这个id元素。因为删除了这个id就会将它对应的位从1设为0，这可能会影响到其他id的位。

 

解决办法：
针对误判，我们可以通过调整哈数函数的个数和布隆过滤器的位长度来降低误判率。这样即使真的有漏网之鱼打到了DB中也不多，对DB的性能影响不大。

针对删除困难，我们可以对数据库的数据不真正删除，而是进行软删除。所谓软删除就是不从表中删除某条记录，而是增加一个状态字段，将这行记录的状态字段设为已删除状态。