Python中的现代高性能Bloom过滤器？

Question

我正在寻找一个生产质量的Python布隆过滤器实现来处理相当大量的项目（比如100M到10亿个项目，误报率为0.01%）。

Pybloom是一种选择，但它似乎因为在Python 2.5上经常抛出DeprecationWarning错误而显得有些陈旧。Joe Gregorio也有一种实现。

要求快速查询性能和稳定性。我也可以创建Python接口到特别好的c/c++实现，甚至到Jython如果有一个好的Java实现。

如果没有这样的实现，有没有关于位数组/位向量表示的建议，可以处理约16亿个位？

- Parand

---

出于兴趣，你能解释一下现有实现（特别是PyBloom）有什么问题吗？虽然它可能“老旧”，但如果它能正常工作且不需要修复，那听起来像是一个优点。 - Oddthinking

Oddthinking，附加了一些解释更新。 - Parand

Answer 1

我最近也走了这条路，尽管听起来我的应用程序略有不同。我对大量字符串的集合操作进行了近似。

你确实做出了重要的观察，即需要一个快速的比特向量。根据你想要放入布隆过滤器的内容，你还需要考虑所使用的哈希算法的速度。你可能会发现这个库有用。你可能还想调整下面使用的随机数技术，只对你的密钥进行一次哈希处理。

关于非Java比特数组实现：

• Boost有dynamic_bitset
• Java内建BitSet

我使用BitVector构建了我的布隆过滤器。我花了一些时间对该库进行性能分析和优化，并将我的补丁贡献给了Avi。请访问BitVector链接并在v1.5的致谢部分向下滚动以了解详细信息。最后，我意识到性能不是这个项目的目标，因此决定不使用它。

这里有一些我之前写的代码。我可能会在python-bloom上发布这个代码。欢迎提出建议。

from BitVector import BitVector
from random import Random
# get hashes from http://www.partow.net/programming/hashfunctions/index.html
from hashes import RSHash, JSHash, PJWHash, ELFHash, DJBHash


#
# [e-mail] / www.asciiarmor.com
#
# copyright (c) 2008, ryan cox
# all rights reserved 
# BSD license: http://www.opensource.org/licenses/bsd-license.php
#

class BloomFilter(object):
    def __init__(self, n=None, m=None, k=None, p=None, bits=None ):
        self.m = m
        if k > 4 or k < 1:
            raise Exception('Must specify value of k between 1 and 4')
        self.k = k
        if bits:
            self.bits = bits
        else:
            self.bits = BitVector( size=m )
        self.rand = Random()
        self.hashes = []
        self.hashes.append(RSHash)
        self.hashes.append(JSHash)
        self.hashes.append(PJWHash)
        self.hashes.append(DJBHash)

        # switch between hashing techniques
        self._indexes = self._rand_indexes
        #self._indexes = self._hash_indexes

    def __contains__(self, key):
        for i in self._indexes(key): 
            if not self.bits[i]:
                return False    
        return True 

    def add(self, key):
        dupe = True 
        bits = []
        for i in self._indexes(key): 
            if dupe and not self.bits[i]:
                dupe = False
            self.bits[i] = 1
            bits.append(i)
        return dupe

    def __and__(self, filter):
        if (self.k != filter.k) or (self.m != filter.m): 
            raise Exception('Must use bloom filters created with equal k / m paramters for bitwise AND')
        return BloomFilter(m=self.m,k=self.k,bits=(self.bits & filter.bits))

    def __or__(self, filter):
        if (self.k != filter.k) or (self.m != filter.m): 
            raise Exception('Must use bloom filters created with equal k / m paramters for bitwise OR')
        return BloomFilter(m=self.m,k=self.k,bits=(self.bits | filter.bits))

    def _hash_indexes(self,key):
        ret = []
        for i in range(self.k):
            ret.append(self.hashes[i](key) % self.m)
        return ret

    def _rand_indexes(self,key):
        self.rand.seed(hash(key))
        ret = []
        for i in range(self.k):
            ret.append(self.rand.randint(0,self.m-1))
        return ret

if __name__ == '__main__':
    e = BloomFilter(m=100, k=4)
    e.add('one')
    e.add('two')
    e.add('three')
    e.add('four')
    e.add('five')        

    f = BloomFilter(m=100, k=4)
    f.add('three')
    f.add('four')
    f.add('five')
    f.add('six')
    f.add('seven')
    f.add('eight')
    f.add('nine')
    f.add("ten")        

    # test check for dupe on add
    assert not f.add('eleven') 
    assert f.add('eleven') 

    # test membership operations
    assert 'ten' in f 
    assert 'one' in e 
    assert 'ten' not in e 
    assert 'one' not in f         

    # test set based operations
    union = f | e
    intersection = f & e

    assert 'ten' in union
    assert 'one' in union 
    assert 'three' in intersection
    assert 'ten' not in intersection
    assert 'one' not in intersection

此外，在我的情况下，我发现为BitVector编写一个更快的count_bits函数非常有用。将以下代码插入到BitVector 1.5中，它应该会为您提供更高效的位计数方法：

def fast_count_bits( self, v ):
    bits = (
            0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
            1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
            1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
            2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
            1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
            2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
            2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
            3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
            1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
            2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
            2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
            3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
            2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
            3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
            3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
            4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8 )

    return bits[v & 0xff] + bits[(v >> 8) & 0xff] + bits[(v >> 16) & 0xff] + bits[v >> 24]

- Ryan Cox

---

谢谢Ryan，非常有启发性。关于BitVector的性能，你找到了更快的替代方案吗？此外，我注意到你只使用了4个哈希，这似乎有点少。对此有什么想法吗？一种常见的做法是使用类似SHA1的算法并拆分位以形成多个哈希值。 - Parand

Hashcount的计算依赖于元素数量和可接受的误判率。我有一个改进版的代码将要提交。虽然我想象中可能会有本地实现更快的方法，但目前还没有找到比这更快的方法。 - Ryan Cox

你能添加一个文档字符串吗？这些值 n=None, m=None, k=None, p=None, bits=None 用于什么？ - Ahmed

Answer 2

作为对 Parand 的回应，他说“通常的做法似乎是使用类似 SHA1 的东西并分割比特以形成多个哈希值”，虽然这在某种意义上是常见的做法（PyBloom 也使用它），但这仍然并不意味着这是正确的事情要做 ;-)

对于 Bloom 过滤器，哈希函数唯一的要求是其输出空间必须在预期输入下均匀分布。虽然密码哈希肯定满足这个要求，但它有点像用大炮打苍蝇。

相反，尝试使用 FNV Hash，它只使用一个 XOR 和一个乘法来处理每个输入字节，我估计它比 SHA1 快几百倍：）

FNV 哈希不是密码安全的，但你不需要它是安全的。它具有略微 不完美的雪崩行为，但你也不会将其用于完整性检查。

关于一致性，需要注意的是第二个链接仅对32位FNV哈希进行了卡方检验。最好使用更多的比特和FNV-1变体，它交换了XOR和MUL步骤以获得更好的比特分散。对于Bloom过滤器，还有一些更多的细节需要注意，例如将输出均匀映射到位数组的索引范围内。如果可能的话，建议将位数组的大小向上舍入到最接近的2的幂，并相应地调整k。这样可以获得更高的准确性，并且可以使用简单的XOR折叠来映射范围。

此外，这里有一个参考文献，解释了为什么在需要通用哈希时不要使用SHA1（或任何加密哈希）。

- Kazeng

---

+1，好答案。而且，对新用户发布链接的限制真的很愚蠢。 - Scott Griffiths

谢谢，伙计。我知道收藏这个两年前的问题总有一天会有回报！ - drxzcl

感谢你的完美答案。目前我还没有使用布隆过滤器，但如果有机会使用，我会尝试将FNV替换成SHA1。 - Parand

Answer 3

最终我发现了pybloomfiltermap。虽然我没有使用过它，但看起来似乎符合要求。

- Parand

---

请告诉我这个库对您是否有用！ - Mike Axiak

这是我能找到的最快的一个。测试了pybloom_live、pyprobables和pybloof。也比cuckoopy更快。顺便说一句，pyprobables非常慢。这里有非常粗糙的代码：https://gist.github.com/fjsj/f7f544ebcedb1ad931a4d31cdc9d2fb5 - fjsj

我一直在使用目前版本的模块pybloomfiltermmap3。该模块适用于Python 3.5及以上版本，采用MurmurHash3，由Cython编写，并带有设置操作。 - Hbar

Answer 4

看一下数组模块。

class Bit( object ):
    def __init__( self, size ):
        self.bits= array.array('B',[0 for i in range((size+7)//8)] )
    def set( self, bit ):
        b= self.bits[bit//8]
        self.bits[bit//8] = b | 1 << (bit % 8)
    def get( self, bit ):
        b= self.bits[bit//8]
        return (b >> (bit % 8)) & 1

值得一提的是，所有的//8和% 8操作可以被替换为>>3和&0x07。这样做可能会在稍微牺牲一些可读性的前提下，提高代码运行速度。

此外，在大多数硬件上，将'B'和8更改为'L'和32应该会更快。[将其更改为'H'和16在某些硬件上可能会更快，但这是有疑虑的。]

- S.Lott

Answer 5

离上次回答这个问题已经接近十年了，时代在变化。

看起来2019年末最受欢迎的维护布隆过滤器包现在是这个：https://github.com/joseph-fox/python-bloomfilter，可以在PyPi上作为pybloom_live获得: https://pypi.org/project/pybloom_live/

- Graham Lea

Answer 6

我已经在 http://stromberg.dnsalias.org/~strombrg/drs-bloom-filter/ 上放置了一个Python布隆过滤器实现。 这是纯Python编写的，具有良好的哈希函数和自动化测试，支持多种后端（磁盘、数组、内存映射等），并且在__init__方法中具有更直观的参数，因此您可以指定理想的元素数量和所需的最大误差率，而不是某些存在于数据结构中的可调参数。

- user1277476