Redis の Bloomfilter を使用してクローラー プロセス中に重複を削除する方法

この記事の内容は、Redis の Bloomfilter を使用して重複を削除する方法についてです。Bloomfilter の大規模な重複削除機能だけでなく、Redis の永続化機能も使用しています。一定の参考値があります。必要な友人は参照できます。お役に立てば幸いです。

前書き:

「削除」は日常業務でよく使用されるスキルですが、クローラーの分野ではさらに一般的に使用されています。平均的な規模で、いずれも比較的大きい。重複排除では、重複排除するデータ量と重複排除の速度の 2 つの点を考慮する必要があります。高速な重複排除速度を維持するために、通常、重複排除はメモリ内で実行されます。

• データの量が大きくない場合は、重複排除のためにデータをメモリに直接配置できます。たとえば、Python では重複排除に set() を使用できます。

• 重複排除データを永続化する必要がある場合、redis の設定されたデータ構造を使用できます。

• データ量が大きい場合は、さまざまな暗号化アルゴリズムを使用して長い文字列を 16/32/40 文字に圧縮し、上記の 2 つの方法を使用して重複を削除できます。

• データ量が数億 (または数十億、数百億) のオーダーに達すると、メモリは限られており、重複を削除するために「ビット」を使用する必要があります。需要に応えます。ブルームフィルターは重複排除オブジェクトをいくつかのメモリ「ビット」にマッピングし、いくつかのビットの 0/1 値を使用してオブジェクトがすでに存在するかどうかを判断します。

• ただし、Bloomfilter はマシンのメモリ上で実行されるため、永続化には不便です (マシンがダウンしている場合は何もありません)。また、統合された重複排除にも不便です。分散型クローラー。 Redis 上に Bloomfilter 用のメモリを申請できれば、上記の問題は両方とも解決されます。

コード:

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

説明:

1. ブルームフィルターはどうですかアルゴリズム ビット重複排除の使用については、Baidu に多くの説明があります。簡単に言うと、いくつかのシードがあります。次に、メモリ空間のセクションに適用します。シードは文字列でハッシュされ、このメモリ上のビットにマッピングできます。いくつかのビットが 1 の場合、文字列がすでに存在していることを意味します。挿入時も同様で、マップされたすべてのビットが 1 に設定されます。

2. ブルームフィルター アルゴリズムには欠損確率があること、つまり、存在しない文字列がすでに存在すると誤って判断される一定の確率があることに注意してください。この確率のサイズは、シードの数、要求されるメモリ サイズ、および重複排除オブジェクトの数に関連します。以下の表があります。m はメモリ サイズ (ビット数)、n は重複排除オブジェクトの数、k はシードの数を表します。たとえば、コードで 256M (1

3. Redis に基づくブルームフィルター重複排除は、実際には Redis の文字列データ構造を使用しますが、Redis 文字列は最大 512M までしかできないため、重複排除データのボリュームがサイズが大きいため、複数の重複排除ブロックを適用する必要があります (コード内の blockNum は重複排除ブロックの数を表します)。

4. コードは、MD5 暗号化と圧縮を使用して文字列を 32 文字に圧縮します (hashlib.sha1() を使用して 40 文字に圧縮することもできます)。これには 2 つの機能があります。1 つ目は、ブルームフィルターは非常に長い文字列をハッシュするときにエラーを起こし、多くの場合、それがすでに存在していると誤って判断されます。この問題は圧縮後は存在しなくなりました。2 つ目は、圧縮された文字は 0 ～ f です。合計 16 の可能性があります。最初の 2 文字をインターセプトし、重複排除の blockNum に基づいてその文字列をさまざまな重複排除ブロックに割り当てました。

概要:

Redis に基づく Bloomfilter 重複排除は、Bloomfilter の大規模な重複排除機能と、Redis に基づく Redis の Persistence 機能の両方を使用し、重複排除も容易にします。分散マシン。使用中は、重複排除するデータの量を予算化し、上記の表に従ってシード数と blockNum を適切に調整する必要があります (シードが少ないほど重複排除は速くなりますが、漏洩率は高くなります)。

以上がRedis の Bloomfilter を使用してクローラー プロセス中に重複を削除する方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。