bloomfilter笔记:基于Redis的布隆过滤器

数据过滤问题是爬虫项目开发时极为重要的一个环节

使用redis过滤的优点：速度快、可持久化

问题：当需要过滤的数据量过大（上亿）的时候即使搭配MD5（字符级）占用内存仍然比较大，

布隆过滤器优点：速度快、占用内存小（位级）

问题：不支持持久化，down机即失效

布隆过滤器的原理：https://blog.csdn.net/jiaomeng/article/details/1495500

解决方案：使用布隆过滤器的算法进行过滤，使用可持久化的redis来进行存储

bloomfilter实现代码：

#!/usr/bin/env python
# -*- coding=utf8 -*-
import redis
from hashlib import md5


class SimpleHash(object):
    """
    1.根据种子生成hash函数
    2.根据hash函数将存储对象value映射在内存范围大小（bit_size）内的一个值
    """

    def __init__(self, bit_size, seed):
        # 开辟内存的大小
        self.bit_size = bit_size
        # 种子
        self.seed = seed

    def hash(self, value):
        """
        用于将存储对象映射到存储范围内的一个值
        :param value:
        :return:
        """
        ret = 0
        for each in value:
            ret += self.seed * ret + ord(each)
        # 控制hashValue的值在这个内存空间的范围
        hash_value = (self.bit_size - 1) & ret
        # 返回映射到的值
        return hash_value


class BloomFilter(object):
    """
    在redis中初始化一个大字符串，也可以认为是在redis中开辟了一块内存空间
    """

    def __init__(self, host='localhost', port=6379, db=2, block_num=1, key='bloomfilter'):
        """
        :param host: redis主机
        :param port: redis端口
        :param db: redis的库
        :param block_num: 用来控制最大可过滤数量 每增加1(即会在redis多创建一个key)大概可扩展9000w
        :param key: 用于组成在redis中的key
        """
        self.server = redis.Redis(host=host, port=port, db=db)
        # 这是一个限制值，最大为256M，因为在redis中，字符串值可以进行伸展，伸展时，空白位置以0填充。
        self.bit_size = 1 << 31  # Redis的String类型最大容量为512M，现使用256M
        self.key = key
        # 用来控制最大可过滤数量 每增加1(即会在redis多创建一个key)大概可扩展9000w
        self.block_num = block_num
        # 种子列表
        seeds = [5, 7, 11, 13, 31, 37, 61]
        # 根据种子列表生成对应的的hash函数
        self.hash_func = [SimpleHash(self.bit_size, seed) for seed in seeds]

    def exists(self, item):
        """
        判断存储对象是否在过滤器内
        :param item: 存储对象
        :return:
        """
        item = self.create_md5(item)
        name = self.get_key(item)
        # 获取item通过hash函数列表中的每个函数映射到的位置的值,如果有一个位置的值为0即判定不存在
        pipe = self.server.pipeline()
        pipe.multi()
        list(map(lambda f: pipe.getbit(name, f.hash(item)), self.hash_func))
        result = list(filter(lambda ret: ret == 0, pipe.execute()))
        return result == list()

    def get_key(self, item):
        """
        判断数据应该映射在哪个redis key中
        :param item: 要存储数据的MD5值
        :return: redis key
        """
        # redis中对应的key
        name = self.key + str(int(item[0:2], 16) % self.block_num)
        return name

    @staticmethod
    def create_md5(item):
        if not isinstance(item, (bytes, str)):
            raise TypeError('item must be str or bytes')
        if isinstance(item, str):
            item = item.encode('utf-8')
        m5 = md5()
        m5.update(item)
        # 取存储对象的md5指纹
        ret = m5.hexdigest()
        return ret

    def insert(self, item):
        """
        将item添加到过滤器
        即将item通过 种子列表生成的hash函数 映射到的每个位置的值都置为1
        :param item: 存储对象
        :return:
        """
        item = self.create_md5(item)
        name = self.get_key(item)
        pipe = self.server.pipeline()
        pipe.multi()
        list(map(lambda f: pipe.setbit(name, f.hash(item), 1), self.hash_func))
        pipe.execute()


if __name__ == "__main__":
    bf = BloomFilter()
    url = 'https://www.baidu.com'
    if bf.exists(url):
        print('url[%s] is exist!' % url)
    else:
        print('url[%s] not exist!' % url)
        bf.insert(url)
           

代码参考：https://blog.csdn.net/bone_ace/article/details/53107018