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

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