分布式环境中的布隆过滤器

Question

我有一个由几个应用程序实例组成的系统，用 Java 编写。对它们的请求是负载平衡的以实现高可用性。每一秒，这个“集群”都会收到数百个小数据块（每个数据块由几个简单的字符串组成），存储在数据库中，保存几天然后丢弃。除了存储这些数据外，主要要求是快速确定给定的值是否存储在数据库中。一个适当索引和分区的数据库表似乎适合这个问题，并且它的工作很好，至少现在是这样。

问题是，大约 80% 的搜索值未找到，因为它们不在数据库中。因此，我想加快速度，使搜索速度更快，资源占用更少。布隆过滤器将是显而易见的选择，如果不是因为不同的应用程序实例接收不同部分的数据，并且如果每个应用程序实例的布隆过滤器中只有一部分数据，那么这些布隆过滤器就没有用了。

您对如何解决此问题有任何建议/想法吗？

Answer 1

保存几天然后丢弃

布隆过滤器不支持删除对象，只支持插入。
如果您有多个布隆过滤器，则必须查询所有过滤器以检查其中之一是否包含您需要的对象。

如果布隆过滤器具有相同的结构（相同的大小、相同的哈希函数等），则它们可以有效地合并。

您可以使用此布隆过滤器： https://github.com/odnoklassniki/apache-cassandra/blob/master/src/java/org/apache/cassandra/utils/BloomFilter.java

并像这样合并两个过滤器：

BloomFilter merge(BloomFilter dstFilter, BloomFilter srcFilter) {
    OpenBitSet dst = dstFilter.bitset;
    OpenBitSet src = srcFilter.bitset;

    for (int i = 0; i < src.getPageCount(); ++i) {
        long[] dstBits = dst.getPage(i);
        long[] srcBits = src.getPage(i);

        for (int j = 0; j < srcBits.length; ++j) {
            dstBits[j] |= srcBits[j];
        }
        dst.setPage(i, dstBits);
    }
    return dstFilter;
}