前提

网上大部分python实现的布隆过滤器库如：pybloomfilter、pybloom 但都是基于py2且哈希函数用的都是sha1类、md5类，效率不如mmh3.所以决定自己实现，

git地址：https://github.com/Sssmeb/BloomFilter

觉得有帮助的可以star~~ 也欢迎讨论、指教！！

Bloom Filter（布隆过滤器）

布隆过滤器是一种多哈希函数映射的快速查找算法，通常应用在一些需要快速判断某个元素是否属于集合，但并不严格要求100%正确的场合。

本质上是一种数据结构，比较巧妙的概率型数据结构。

布隆过滤器可能会出现误判，但不会漏判。即，如果过滤器判断该元素不在集合中，则元素一定不在集合中，但如果过滤器判断该元素在集合中，有一定的概率判断错误（在合适的参数情况下，误判率可以降低到0.000级别甚至更低）。

因此，Bloom Filter不适合那些“零错误”的应用场合。而在能容忍低错误率的应用场合下，Bloom Filter相比于其他常见的算法极大节省了空间（相较于直接存储，可节省上千倍的空间）。它的优点是空间效率和查询时间都远远超过一般的算法，缺点是存在误识别率和删除困难。

应用

常见适用的场景主要利用布隆过滤器减少磁盘io或网络请求等：

1. 黑名单

   • 例如 邮件黑名单过滤器，判断邮件地址是否存在黑名单中

2. 网络爬虫去重

3. K-V系统快速判断某个key是否存在

   • 例如 Hbase每个Region都包含一个BloomFilter，用于快速判断某个key在该region中是否存在

4. 缓解缓存穿透

   • 大量查询不存在数据的请求，越过redis缓存后，全部打到数据库中

   • 可以在服务器内存中搭建一个布隆过滤器缓解

去重背景

一般将数据存储用做去重判断的方法有：

1. 将数据直接存储到数据库中

2. 用HashSet（字典结构）/redis的set 将数据存储起来，实现O(1)时间复杂度的查询

3. 经过MD5 或 SHA-1等 单向哈希后再保存到HashSet或数据库

4. Bit-Map。建立一个BitSet，将每份数据通过哈希函数映射到某一位（bit）。

当数据量较小时，前3种方法都是不错的选择。但是当数据量非常大时（几G、甚至几十G）会出现存储瓶颈。

当数据量较大时，上述四种方法的表现：

1. 查询效率非常低，每检查一个数据是否存在时都需要扫描全表。

2. 占用大量的内存空间（内存较昂贵）

3. 由于字符串经过MD5或SHA-1处理后，长度只有128bit或160bit，所以当数据本身长度较大时，比方法2节省内存。

4. 消耗内存少，但单一哈希函数发生冲突的概率太高。若要冲突率降到1%，就要将Bitset的长度设置为数据个数的100倍。

Bloom Filter原理

基于以上的背景，可以看到：当数据量非常大时，方法4是较好的选择。但该较大的问题是冲突率高，为了降低冲突，Bloom Filter使用多个哈希函数，而不是一个。

总结BloomFilter的核心思想：

1. 多个hash，增大随机性，减少hash碰撞的概率

2. 扩大数组范围，使hash值均匀分布，进一步减少hash碰撞的概率

算法实现

1. 创建一个m位的BitSet，先将所有位初始化为0
   image

2. 插入数据流程：

   1. 加入字符串，经过k个哈希函数，分别计算出k个范围是0 - m-1的值

   2. 将k个值对应的BitSet位 置1

image

检查流程：

1. 将数据经过k个哈希函数，分别计算出k个值

2. 若k个位都为1，则判断存在。（可能误判）

3. 有任意1位是0，则肯定不存在。

通过上述流程也得，布隆过滤器需要提前预定位数组的大小。

删除操作？

经典的布隆过滤器可以支持 add 和 isExist操作。但是不支持delete操作。

例如，有两个值共同覆盖了一个位，当需要删除其中一个值时，会导致另一个值的该位也被删除，最终导致错判。

可以使用计数删除解决这个问题。即不再使用bit位，而存储一个数值。插入操作时不再是置1，而是加1操作。判断时不再判断0、1，而是判断是否大于0。但是这种做法明显增大了占用的内存，这里不展开。

参数选择

哈希函数选择

简单总结经典哈希函数的5个特点：

1. 输入域无穷

2. 输出域有固定范围

3. 相同的输入，输出一定相同

4. 不同的输入，可能相同

   • 产生哈希碰撞的原因

5. 数据足够多的情况下，输出域近乎均匀

   • 离散性

   • 用来评判哈希函数优劣的关键。哈希函数越好，离散性越好（输出值分布越均匀）。

   • 将其返回值对m取余(%m),得到的返回值可以认为也会均匀的分布在0~m-1位置上

哈希函数的选择对性能影响较大，一个好（离散性高）的哈希函数能近似等概率的将字符串映射到各个bit。选择k个不同的哈希函数比较麻烦，一种简单的方法是选择一个哈希函数，然后送入k个不同的参数。

哈希函数个数和位数组大小的确定

显然，哈希函数个数越少、位数组越小误报率就越高，效率越低。

image

取自：https://www.jianshu.com/p/2104d11ee0a2

哈希函数的个数k、位数组大小m、加入的字符串数量n、误报率p 的关系。

通过简单的数学推导可以得出以下结论：

image

image

哈希函数个数k取10，位数组大小m设为字符串个数n的20倍时，false positive发生的概率是0.0000889 ，即10万次的判断中，会存在9次误判，对于一天1亿次的查询，误判的次数为9000次。可见在参数良好的情况下，误报率在可接受的范围内。

公式推导

哈希函数的个数k、位数组大小m、加入的字符串数量n、误报率p 的关系。

在已得误报率p、数据量的情况下（通过用户输入），我们来建立关于p的表达式。

image

image

image

标明某个元素是否在集合中所需的 k 个位置都按照如上的方法设置为 1，但是该方法可能会使算法错误的认为某一原本不在集合中的元素却被检测为在该集合中（False Positives），该概率由以下公式确定

image

image

image

image

取自：https://blog.csdn.net/wh_springer/article/details/52193110

进阶优化

性能很低的哈希函数不是个好选择，推荐 MurmurHash、Fnv 这些。

Redis 因其支持 setbit 和 getbit 操作，且纯内存性能高等特点，因此天然就可以作为布隆过滤器来使用。可以通过redis实现分布式的持久化去重。但是需要注意redis的bitmap是用字符串来实现的，而redis规定字符串最长为512MB（40多亿位），因此生产环境中建议对体积庞大的布隆过滤器进行拆分。

Bloom Filter具体实现（redis、python）

限于文章篇幅，以下仅使用简单实现说明。具体实现代码：

https://github.com/Sssmeb/BloomFilter/tree/master

求星星求start！！ 也非常欢迎讨论、指点~

python实现

基于以上分析，通过python实现一个简单的版本，核心函数add和contains都很好理解。初始化参数仅是数组大小和哈希函数个数。常见的实现是误判率（根据误判率来调整函数的个数）。

取自：https://blog.csdn.net/happytofly/article/details/80124542

    from bitarray import bitarray

    # 3rd party
    import mmh3


    class BloomFilter(set):

        def __init__(self, size, hash_count):
            super(BloomFilter, self).__init__()
            self.bit_array = bitarray(size)
            self.bit_array.setall(0)
            self.size = size
            self.hash_count = hash_count

        def __len__(self):
            return self.size

        def __iter__(self):
            return iter(self.bit_array)

        def add(self, item):
            for ii in range(self.hash_count):
                index = mmh3.hash(item, ii) % self.size
                self.bit_array[index] = 1

            return self

        def __contains__(self, item):
            out = True
            for ii in range(self.hash_count):
                index = mmh3.hash(item, ii) % self.size
                if self.bit_array[index] == 0:
                    out = False

            return out

哈希函数 - Murmur hash3

murmur hash是一种非加密型哈希函数，适用于一般的哈希检索操作。对于规律性较强的key，murmurhash的随机分布特征表现更良好。

redis在实现字典时用到了两种不同的哈希算法，murmur hash就是其中一种（另一种是djb）。
redis中数据库、集群、哈希键、阻塞操作等功能都用到了这个算法。

相比于md5，murmur hash在万次测试中，性能高4-5倍。

redis

简单的实现把数据放在本地内存中，无法实现布隆过滤器的共享，我们可以把数据放在redis中，用redis实现布隆过滤器。

思路是将布隆过滤器的位数组用redis的bitmap代替，由于redis最大申请空间为512MB，可以通过多个键来扩充位数组。

由于redis自带setbit、getbit，所以实现起来更加便捷。

具体实现参看git：https://github.com/Sssmeb/BloomFilter/tree/master

scrapy中的去重

scrapy自带了去重的功能，主要是通过fingerprint（指纹）标志过滤，用set实现去重功能。

在源码中的实现

class RFPDupeFilter(BaseDupeFilter):
    def __init__(self, path=None, debug=False):
        self.file = None
        self.fingerprints = set()   # 集合
        xxx # 省略
    
    # 通过request_fingerprint计算出请求的fp
    # 根据是否存在于fingerprints集合中判断
    def request_seen(self, request):
        fp = self.request_fingerprint(request)
        if fp in self.fingerprints:
            return True
        self.fingerprints.add(fp)
        if self.file:
            self.file.write(fp + os.linesep)

request_fingerprint方法用于计算请求的指纹（fp）。去重指纹是sha1(method + url + body + header)

    # 计算请求fp函数
    def request_fingerprint(request, include_headers=None):
        # 判断是否带请求头信息
        if include_headers:
            include_headers = tuple([h.lower() for h in sorted(include_headers)])
        # 获取该请求的缓存
        cache = _fingerprint_cache.setdefault(request, {}) 
        # 如果是新请求头信息
        if include_headers not in cache:
              # sha1算法
              fp = hashlib.sha1()
              fp.update(request.method)
              fp.update(canonicalize_url(request.url))
              fp.update(request.body or '') 
              if include_headers:
                for hdr in include_headers:
                      if hdr in request.headers:
                        fp.update(hdr)
                        for v in request.headers.getlist(hdr):
                              fp.update(v)
              cache[include_headers] = fp.hexdigest()
        return cache[include_headers]

如果想自定义Filter，可以通过继承，重写request_seen

from scrapy.dupefilter import RFPDupeFilter
class SeenURLFilter(RFPDupeFilter):
      """A dupe filter that considers the URL"""
      def __init__(self, path=None):
        self.urls_seen = set()
        RFPDupeFilter.__init__(self, path)
      def request_seen(self, request):
        if request.url in self.urls_seen:
              return True
        else:
              self.urls_seen.add(request.url)


# 修改settings设置
DUPEFILTER_CLASS ='scraper.custom_filters.SeenURLFilter'

scrapy-redis中的去重策略

scrapy-redis的策略基本和scrapy相同，只是所用的数据结构不同。

去重结构使用的是redis中的集合，键名为XX:dupefilter。该结构中存储了已爬取的请求。

另外， 请求队列使用的是redis中的有序集合， 键名为XX:request， 存储了待爬取的请求
        items数据使用的是redis中的列表， 键名为XX:items， 存储了爬取到的数据

存在的问题

redis是内存数据库，也就是说以上的三块数据：所有待爬取的请求、爬取到的items数据、去重的集合，都会存在内存中。

请求队列会随着爬取的进行，动态的出入，不会无限的叠加。爬取到的items数据一般会转移到其他的数据库中（mysql、mongodb），也不会无限的叠加。但是去重集合会随着爬取的进行，添加新的指纹，导致占用的内存空间越来越大，最终可能成为运行瓶颈。

改用布隆过滤器流程

以下只介绍修改流程，布隆过滤器实现见git：https://github.com/Sssmeb/BloomFilter/tree/master

1. 加入文件

（可以先复制一份scrapy_redis源码文件到当前scrapy工作目录下）将自己编写的bloomfilter.py文件加入scrapy_redis源码中

2. 修改源码，加入布隆过滤器

dupefilter.py（去重相关）文件中 导入布隆过滤器文件

from .bloomfilter import BloomFilter

在init函数中，加入实例化

self.bf = BloomFilter(server, key)

修改request_seen方法的去重规则

fp = self.request_fingerprint(request)
if self.bf.is_exist(fp):
    return True
else:
    self.bf.add(fp)
    return False

3. 修改配置

像正常使用scrapy_redis一样修改即可。

DUPEFILTER_CLASS = "scrapy_redis.dupefilter.RFPDupeFilter"
SCHEDULER = "scrapy_redis.scheduler.Scheduler"

如果想标识这个特别的scrapy_redis，可以修改scrapy_redis目录名称，在导入时修改对应的文件名即可

DUPEFILTER_CLASS = "scrapy_redis_blommfilter.dupefilter.RFPDupeFilter"
SCHEDULER = "scrapy_redis_blommfilter.scheduler.Scheduler"

引用

https://piaosanlang.gitbooks.io/spiders/content/09day/section9.1.html
https://blog.csdn.net/xinzhongtianxia/article/details/81294922
https://zhuanlan.zhihu.com/p/50587308