python redis 布隆过滤器实现

布隆过滤器是什么？

如果想判断一个元素是不是在一个集合里，一般想到的是将集合中所有元素保存起来，然后通过比较确定。链表、树、散列表（又叫哈希表，Hash table）等等数据结构都是这种思路。但是随着集合中元素的增加，我们需要的存储空间越来越大。同时检索速度也越来越慢，上述三种结构的检索时间复杂度分别为 O(n),O(log n),O(1)。

原理

当一个元素被加入集合时，通过K个散列函数将这个元素映射成一个位数组中的K个点，把它们置为1。检索时，我们只要看看这些点是不是都是1就（大约）知道集合中有没有它了：如果这些点有任何一个0，则被检元素一定不在；如果都是1，则被检元素很可能在。这就是布隆过滤器的基本思想。

应用场景

布隆过滤器的用处就是，能够在节省存储空间的情况下迅速判断一个元素是否在一个集合中。举例三个使用场景：

1、网页爬虫对URL的去重，避免爬取相同的URL地址；

2、反垃圾邮件，从数十亿个垃圾邮件列表中判断某邮箱是否垃圾邮箱；

3、缓存击穿，将已存在的缓存放到布隆过滤器中，当黑客访问不存在的缓存时迅速返回避免缓存及DB挂掉。

python + redis 实现

BloomFilter仅实现两种方法：

add()- 将项目添加到布隆过滤器。
contains()- 测试过滤器中是否存在项目。
1
2
3
4

class BloomFilter(Container):
    """
    代码来自walrus中的布隆过滤取
    """
    def __init__(self, database, key, size=64 * 1024):
        super(BloomFilter, self).__init__(database, key)
        self.size = size
        self.bits = self.size * 8
        self._bf = BitField(self.database, self.key)

    def _get_seeds(self, data):
        """
        散列函数
        """
        seeds = struct.unpack('>IIII', hashlib.md5(encode(data)).digest())
        return [seed % self.bits for seed in seeds]

    def add(self, data):
        """
       添加item到 布隆过滤器
        """
        bfo = BitFieldOperation(self.database, self.key)
        for bit_index in self._get_seeds(data):
            bfo.set('u1', bit_index, 1)
        bfo.execute()

    def contains(self, data):
        """
       	检查item是否存在
        """
        bfo = BitFieldOperation(self.database, self.key)
        for bit_index in self._get_seeds(data):
            bfo.get('u1', bit_index)
        return all(bfo.execute())
    __contains__ = contains

    def __len__(self):
        return self.size
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

执行看看

bf = db.bloom_filter("bf")
for item in range(20000):
    i = f"value_{item}"
    bf.add(i)
success = 0
success2 = 0
fail = 0
fail2 = 0
for item in range(20000):
    i = f"value_{item}"
    i2 = f"value2_{item}"

    if i in bf:
        success += 1
    else:
        fail += 1

    if i2 in bf:
        success2 += 1
    else:
        fail2 += 1
print(success, fail)
print(success2, fail2)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

20000 0
8 19992
1
2

误算了8个不存在的item，误算率8/20000

优点

• 相较与其他类型，布隆过滤器在空间和时间方面都有巨大的优势，
• 布隆过滤器存储空间和插入/查询时间都是常数O(k)
• 布隆过滤器不需要存储元素本身，在某些对保密要求非常严格的场合有优势

缺点

• 存在误算
• 无法从布隆过滤器中删除元素