Redis의 Bloomfilter를 사용하여 크롤러 프로세스 중에 중복을 제거하는 방법

이 글의 내용은 Redis의 Bloomfilter를 사용하여 중복을 제거하는 방법에 대한 것입니다. Bloomfilter의 대규모 중복 제거 기능을 사용할 뿐만 아니라 Redis의 지속성 기능도 사용하므로 친구들이 참조할 수 있습니다. 그것이 당신에게 도움이 되기를 바랍니다.

서문:

"제거"는 일상 작업, 특히 크롤러 분야에서 자주 사용되는 기술이며 일반적으로 규모가 비교적 큽니다. 중복 제거에는 중복 제거할 데이터의 양과 중복 제거 속도라는 두 가지 사항을 고려해야 합니다. 빠른 중복 제거 속도를 유지하기 위해 일반적으로 중복 제거는 메모리에서 수행됩니다.

• 데이터의 양이 크지 않은 경우 중복 제거를 위해 메모리에 직접 배치할 수 있습니다. 예를 들어 Python에서는 중복 제거를 위해 set()을 사용할 수 있습니다.

• 중복 제거 데이터를 유지해야 하는 경우 Redis의 설정된 데이터 구조를 사용할 수 있습니다.

• 데이터 양이 더 많은 경우 다양한 암호화 알고리즘을 사용하여 긴 문자열을 16/32/40자로 압축한 다음 위의 두 가지 방법을 사용하여 중복을 제거할 수 있습니다. 데이터 도달 메모리가 수십억(심지어 수십억 또는 수백억)에 이르면 메모리가 제한되며 수요를 충족하려면 중복을 제거하는 데 "비트"를 사용해야 합니다. Bloomfilter는 중복 제거 개체를 여러 메모리 "비트"에 매핑하고 여러 비트의 0/1 값을 사용하여 개체가 이미 존재하는지 확인합니다.

• 블룸필터는 머신의 메모리에서 실행되기 때문에 지속성 측면에서 편리하지 않으며(머신이 다운되면 아무 일도 일어나지 않음) 분산 크롤러의 통합 중복 제거에도 편리하지 않습니다. Bloomfilter를 위해 Redis에서 메모리를 신청할 수 있다면 위의 두 가지 문제는 모두 해결될 것입니다.

• 코드:

# encoding=utf-8import redisfrom hashlib import md5class 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) & retclass 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__ == &#39;__main__&#39;:""" 第一次运行时会显示 not exists!，之后再运行会显示 exists! """
    bf = BloomFilter()    if bf.isContains(&#39;http://www.baidu.com&#39;):   # 判断字符串是否存在
        print &#39;exists!&#39;
    else:        print &#39;not exists!&#39;
        bf.insert(&#39;http://www.baidu.com&#39;)

설명:

블룸필터 알고리즘이 비트 중복 제거를 사용하는 방법은 Baidu에 많은 설명이 있습니다. 간단히 말해서, 여러 개의 시드가 있는데, 이제 메모리 공간을 신청하세요. 시드는 문자열로 해시되어 이 메모리의 비트에 매핑될 수 있습니다. 이는 해당 문자열이 이미 존재한다는 의미입니다. 삽입할 때도 마찬가지이며 매핑된 모든 비트를 1로 설정합니다.

1. 블룸필터 알고리즘에는 누락 확률이 있다는 점, 즉 존재하지 않는 문자열이 이미 존재하는 것으로 잘못 판단될 특정 확률이 있다는 점을 기억해야 합니다. 이 확률의 크기는 시드 수, 요청된 메모리 크기 및 중복 제거 개체 수와 관련됩니다. 아래 표가 있는데, m은 메모리 크기(비트 수), n은 중복 제거 개체 수, k는 시드 수를 나타냅니다. 예를 들어 내 코드에는 1

2. 
   Redis 기반의 Bloomfilter 중복제거는 실제로 Redis의 String 데이터 구조를 사용하지만 Redis String은 최대 512M까지만 가능하므로 중복제거할 데이터량이 많은 경우 다중 중복제거를 신청해야 합니다. 블록(코드 blockNum은 중복 제거 블록 수를 나타냄)

3. 코드는 MD5 암호화 및 압축을 사용하여 문자열을 32자로 압축합니다(hashlib.sha1()을 사용하여 40자로 압축할 수도 있음). 두 가지 기능이 있습니다. 첫째, Bloomfilter는 매우 긴 문자열을 해싱할 때 오류를 발생시키며, 압축 후에는 이 문제가 더 이상 존재하지 않습니다. 둘째, 압축된 문자는 총 16가지입니다. 처음 두 문자를 가로채서 중복 제거를 위해 blockNum을 기반으로 다른 중복 제거 블록에 문자열을 할당했습니다.

4. 요약:

Redis 기반 Bloomfilter 중복 제거는 Bloomfilter의 대규모 중복 제거 기능을 사용할 뿐만 아니라 Redis 기반의 지속성 기능도 사용하여 분산 시스템의 중복 제거를 용이하게 합니다. 사용 중에는 중복 제거할 데이터 양에 대한 예산을 책정하고 위 표에 따라 시드 수와 blockNum을 적절하게 조정해야 합니다(시드 수가 적을수록 중복 제거 속도는 빨라지지만 누출률은 높아집니다).

위 내용은 Redis의 Bloomfilter를 사용하여 크롤러 프로세스 중에 중복을 제거하는 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!