EdmondFrank's 时光足迹

この先は暗い夜道だけかもしれない　それでも信じて進むんだ。星がその道を少しでも照らしてくれるのを。
或许前路永夜，即便如此我也要前进，因为星光即使微弱也会我为照亮前途。
——《四月は君の嘘》

基于Redis的Bloomfilter

- -

背景

url去重一直是大型分布式爬虫的主题，在一般规模比较大的的情景，去重需要考虑到两个点：

  1. 去重的数据量
  2. 去重的速度

并且，在一般情况下为了尽量降低去重对爬虫效率的影响一般选择在内存中去重。

  • 小数据：直接使用语言的逻辑判断及数据结构去重，如python的set，ruby的Set
  • 持续化去重： redis的set
  • 中型数据量去重：加密算法压缩url及长字符串在混合使用其他方法去重
  • 大型数据去重：使用bloomfilter（布隆过滤器）桉内存位去重

前言及原理简介

传统弊端

按照以往惯例来说，我们一般判断一个元素是否在一个集合内的通常做法是：先将所有元素保存下来， 然后通过比较判断它是否在集合之中。但是，这样的常规判断方法有一个很大的弊端就是，随着集合内的 元素个数变大，我们需要的空间和时间都呈线性增长，检索速度也越来越慢。

bloomfilter

而Bloom filter 采用的是哈希函数的方法，将一个元素表示为一个点并将他映射到一个长度为m的 阵列上。在检索时如果在阵列上发现对应的映射点为1时，那么这个元素在集合内，反之则不在集合内。

优点：

Bloom filter 优点在于它的插入和查询时间都是常数，另外它查询的元素不保存元素本身，具有良好的 安全性。

缺点：

最明显的一点是，当插入元素越多，查询元素被错判成“在集合内”的概率就越大。针对这个问题常用的 解决方法有：使用k个哈希函数来对应映射k个点，如果所对应的所有点都是1的话。那么元素在集合内， 如果任何一个有0的话，则元素不在集合内。另外，Bloom filter也不能删除一个元素，因为多个元素的哈希 的结果可能在bloom filter的阵列中都是占用同一个位。如果删除了一个比特位，可能会影响多个元素的检测。

简单图示

实现我们设我们的哈希函数有两个。

开始时集合内没有元素：

img

当来了一个元素a时，进行哈希计算再判断，当计算出对应的比特位上为0时，即a不在集合内，添加a的哈希值进去。

img

之后的元素，要判断是不是在集合内，也是同 a 一样的方法，只有对元素哈希后对应位置上都是 1 才认为这个元素在集合内

img

随着元素的插入，Bloom filter 中修改的值变多，出现误判的几率也随之变大，当新来一个元素时， 满足其在集合内的条件，即所有对应位都是1，这样就可能有两种情况， 一是这个元素就在集合内，没有发生误判；还有一种情况就是发生误判，出现了哈希碰撞，这个元素本不在集合内。

img

算法实现

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66

# encoding=utf-8

import redis
from hashlib import md5

class SimpleHash(object):
    def __init__(self, cap, seed):
        self.cap = cap
        self.seed = seed

    def hash(self, value):
        ret = 0
        for i in range(len(value)):
            ret += self.seed * ret + ord(value[i])
        return (self.cap - 1) & ret


class BloomFilter(object):
    def __init__(self, host='localhost', port=6379, db=0, blockNum=1, key='bloomfilter'):
        """
        :param host: the host of Redis
        :param port: the port of Redis
        :param db: witch db in Redis
        :param blockNum: one blockNum for about 90,000,000; if you have more strings for filtering, increase it.
        :param key: the key's name in Redis
        """
        self.server = redis.Redis(host=host, port=port, db=db)
        self.bit_size = 1 << 31  # Redis的String类型最大容量为512M，现使用256M
        self.seeds = [5, 7, 11, 13, 31, 37, 61]
        self.key = key
        self.blockNum = blockNum
        self.hashfunc = []
        for seed in self.seeds:
            self.hashfunc.append(SimpleHash(self.bit_size, seed))

    def isContains(self, str_input):
        if not str_input:
            return False
        m5 = md5()
        m5.update(str_input)
        str_input = m5.hexdigest()
        ret = True
        name = self.key + str(int(str_input[0:2], 16) % self.blockNum)
        for f in self.hashfunc:
            loc = f.hash(str_input)
            ret = ret & self.server.getbit(name, loc)
        return ret

    def insert(self, str_input):
        m5 = md5()
        m5.update(str_input)
        str_input = m5.hexdigest()
        name = self.key + str(int(str_input[0:2], 16) % self.blockNum)
        for f in self.hashfunc:
            loc = f.hash(str_input)
            self.server.setbit(name, loc, 1)


if __name__ == '__main__':
""" 第一次运行时会显示 not exists!，之后再运行会显示 exists! """
    bf = BloomFilter()
    if bf.isContains('http://www.baidu.com'):   # 判断字符串是否存在
        print 'exists!'
    else:
        print 'not exists!'
        bf.insert('http://www.baidu.com')