Comment utiliser Bloomfilter de Redis pour supprimer les doublons pendant le processus du robot d'exploration

Le contenu de cet article explique comment utiliser Bloomfilter de Redis pour supprimer les doublons. Il utilise non seulement les capacités de suppression massive de doublons de Bloomfilter, mais utilise également les capacités de persistance de Redis. Il a une certaine valeur de référence. J'espère que cela vous sera utile.

Avant-propos :

Le « retrait » est une compétence souvent utilisée dans le travail quotidien, notamment dans le domaine des robots, et est d'envergure moyenne. Tous sont relativement grand. Deux points doivent être pris en compte pour la déduplication : la quantité de données à dédupliquer et la vitesse de déduplication. Afin de maintenir une vitesse de déduplication rapide, la déduplication est généralement effectuée en mémoire.

• Lorsque la quantité de données n'est pas importante, elles peuvent être directement placées dans la mémoire pour la déduplication. Par exemple, python peut utiliser set() pour la déduplication.

• Lorsque les données de déduplication doivent être conservées, la structure de données définie de Redis peut être utilisée.

• Lorsque la quantité de données est plus importante, vous pouvez utiliser différents algorithmes de cryptage pour compresser la longue chaîne en 16/32/40 caractères, puis utiliser les deux méthodes ci-dessus pour supprimer les doublons ;

• Lorsque la quantité de données atteint l'ordre de centaines de millions (voire de milliards ou de dizaines de milliards), la mémoire est limitée, et des "bits" doivent être utilisés pour dédupliquer les données afin répondre à la demande. Bloomfilter mappe les objets de déduplication sur plusieurs « bits » de mémoire et utilise les valeurs 0/1 de plusieurs bits pour déterminer si un objet existe déjà.

• Cependant, Bloomfilter fonctionne sur la mémoire d'une machine, ce qui n'est pas pratique pour la persistance (il n'y aura rien si la machine est en panne), et ce n'est pas pratique pour une déduplication unifiée de robots d'exploration distribués. Si vous pouvez demander de la mémoire sur Redis pour Bloomfilter, les deux problèmes ci-dessus seront résolus.

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

Description :

1. Bloomfilter Il existe de nombreuses explications sur Baidu sur la façon dont l'algorithme utilise la déduplication de bits. Pour faire simple, il y a plusieurs graines. Maintenant, demandez une section d'espace mémoire. Une graine peut être hachée avec une chaîne et mappée sur un bit de cette mémoire. Si plusieurs bits sont à 1, cela signifie que la chaîne existe déjà. Lors de l'insertion, les bits mappés sont mis à 1.

2. Il convient de rappeler que l'algorithme Bloomfilter a une probabilité manquante, c'est-à-dire qu'il existe une certaine probabilité qu'une chaîne inexistante soit jugée à tort comme étant déjà existante. La taille de cette probabilité est liée au nombre de valeurs de départ, à la taille de mémoire demandée et au nombre d'objets de déduplication. Il y a un tableau ci-dessous, m représente la taille de la mémoire (combien de bits), n représente le nombre d'objets de déduplication et k représente le nombre de valeurs de départ. Par exemple, j'ai demandé 256 M dans mon code, soit 1

3. La déduplication Bloomfilter basée sur Redis utilise en fait la structure de données String de Redis, mais une chaîne Redis ne peut avoir qu'un maximum de 512 Mo, donc si les données de déduplication le volume est important et vous devez demander plusieurs blocs de déduplication (blockNum dans le code représente le nombre de blocs de déduplication).

4. Le code utilise le cryptage et la compression MD5 pour compresser la chaîne à 32 caractères (hashlib.sha1() peut également être utilisé pour la compresser à 40 caractères). Il a deux fonctions : premièrement, Bloomfilter fera des erreurs lors du hachage d'une chaîne très longue, la jugeant souvent à tort comme étant déjà existante. Ce problème n'existe plus après la compression ; deuxièmement, les caractères compressés sont 0~f au total. J'ai intercepté les deux premiers caractères, puis attribué la chaîne à différents blocs de déduplication en fonction de blockNum pour la déduplication.

Résumé :

La déduplication Bloomfilter basée sur Redis utilise à la fois les capacités de déduplication massive de Bloomfilter et la capacité de persistance de Redis, basée sur Redis, facilite également la déduplication des fichiers. machines distribuées. Lors de l'utilisation, il est nécessaire de budgétiser la quantité de données à dédupliquer et d'ajuster de manière appropriée le nombre de seed et blockNum selon le tableau ci-dessus (moins il y a de seed, plus la déduplication sera rapide, mais plus le taux de fuite est élevé).

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!