So verwenden Sie den Bloomfilter von Redis, um Duplikate während des Crawler-Prozesses zu entfernen

Der Inhalt dieses Artikels befasst sich mit der Verwendung des Bloomfilters zum Entfernen von Duplikaten. Er nutzt nicht nur die umfangreichen Duplikatentfernungsfunktionen, sondern auch die Persistenzfunktionen von Redis. Freunde in Not können sich darauf beziehen. Ich hoffe, es wird Ihnen hilfreich sein.

Vorwort:

„Entfernen“ ist eine Fähigkeit, die in der täglichen Arbeit, insbesondere im Raupenbereich, häufig zum Einsatz kommt und von durchschnittlichem Ausmaß ist sind relativ groß. Bei der Deduplizierung müssen zwei Punkte berücksichtigt werden: die Menge der zu deduplizierenden Daten und die Geschwindigkeit der Deduplizierung. Um eine schnelle Deduplizierungsgeschwindigkeit aufrechtzuerhalten, wird die Deduplizierung im Allgemeinen im Speicher durchgeführt.

• Wenn die Datenmenge nicht groß ist, kann sie zur Deduplizierung direkt im Speicher abgelegt werden. Beispielsweise kann Python set() zur Deduplizierung verwenden.

• Wenn Deduplizierungsdaten beibehalten werden müssen, kann die festgelegte Datenstruktur von Redis verwendet werden.

• Wenn die Datenmenge größer ist, können Sie verschiedene Verschlüsselungsalgorithmen verwenden, um die lange Zeichenfolge auf 16/32/40 Zeichen zu komprimieren, und dann die beiden oben genannten Methoden verwenden, um Duplikate zu entfernen;

• Wenn die Datenmenge die Größenordnung von Hunderten von Millionen (oder sogar Milliarden oder Dutzenden von Milliarden) erreicht, ist der Speicher begrenzt und es müssen „Bits“ verwendet werden, um Daten zu deduplizieren den Bedarf decken. Bloomfilter ordnet Deduplizierungsobjekte mehreren Speicher-„Bits“ zu und ermittelt anhand der 0/1-Werte mehrerer Bits, ob ein Objekt bereits vorhanden ist.

• Bloomfilter wird jedoch im Speicher einer Maschine ausgeführt, was für die Persistenz nicht geeignet ist (wenn die Maschine ausfällt, erfolgt nichts) und für die einheitliche Deduplizierung von nicht geeignet ist Verteilte Crawler. Wenn Sie Speicher auf Redis für Bloomfilter beantragen können, werden beide oben genannten Probleme gelöst.

Code:

# 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;)

Erklärung:

1. Wie funktioniert Bloomfilter Der Algorithmus verwendet Bit-Deduplizierung. Es gibt viele Erklärungen zu Baidu. Vereinfacht ausgedrückt gibt es mehrere Seeds, die mit einem String gehasht und einem Bit in diesem Speicher zugeordnet werden können. Dies bedeutet, dass der String bereits vorhanden ist. Beim Einfügen werden die gemappten Bits auf 1 gesetzt.

2. Es sollte daran erinnert werden, dass der Bloomfilter-Algorithmus eine fehlende Wahrscheinlichkeit aufweist, das heißt, es besteht eine gewisse Wahrscheinlichkeit, dass eine nicht vorhandene Zeichenfolge fälschlicherweise als bereits vorhanden eingeschätzt wird. Die Größe dieser Wahrscheinlichkeit hängt von der Anzahl der Seeds, der angeforderten Speichergröße und der Anzahl der Deduplizierungsobjekte ab. Unten finden Sie eine Tabelle, m stellt die Speichergröße dar (wie viele Bits), n stellt die Anzahl der Deduplizierungsobjekte dar und k stellt die Anzahl der Seeds dar. Zum Beispiel habe ich in meinem Code 256 Millionen beantragt, was 1

3. Die auf Redis basierende Bloomfilter-Deduplizierung verwendet tatsächlich die String-Datenstruktur von Redis, aber ein Redis-String kann nur maximal 512 MB haben. Wenn also die Deduplizierungsdaten vorhanden sind Das Volumen ist groß und Sie müssen mehrere Deduplizierungsblöcke beantragen (blockNum im Code stellt die Anzahl der Deduplizierungsblöcke dar).

4. Der Code verwendet MD5-Verschlüsselung und -Komprimierung, um die Zeichenfolge auf 32 Zeichen zu komprimieren (hashlib.sha1() kann auch verwendet werden, um sie auf 40 Zeichen zu komprimieren). Es hat zwei Funktionen: Bloomfilter macht beim Hashen einer sehr langen Zeichenfolge häufig Fehler, da dieses Problem nach der Komprimierung nicht mehr besteht. Es gibt insgesamt 16 Möglichkeiten. Ich habe die ersten beiden Zeichen abgefangen und die Zeichenfolge dann basierend auf blockNum verschiedenen Deduplizierungsblöcken für die Deduplizierung zugewiesen.

Zusammenfassung:

Die auf Redis basierende Bloomfilter-Deduplizierung nutzt sowohl die umfangreichen Deduplizierungsfunktionen von Bloomfilter als auch die Persistenzfunktion von Redis, die auf Redis basiert und auch die Deduplizierung erleichtert verteilte Maschinen. Während der Verwendung ist es notwendig, die zu deduplizierende Datenmenge zu budgetieren und die Anzahl der Seeds und BlockNum gemäß der obigen Tabelle entsprechend anzupassen (je weniger Seeds, desto schneller erfolgt die Deduplizierung, aber desto höher ist die Leckagerate).

Das obige ist der detaillierte Inhalt vonSo verwenden Sie den Bloomfilter von Redis, um Duplikate während des Crawler-Prozesses zu entfernen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!