java - 分布式环境中的布隆过滤器
问题描述
我有一个由几个应用程序实例组成的系统,用 Java 编写。对它们的请求是负载平衡的,以实现高可用性。每秒,这个“集群”接收数百个小数据块(每个数据块由几个简单的字符串组成),存储在数据库中,保存几天然后丢弃。除了存储这些数据之外,主要要求是快速确定给定值是否存储在数据库中。一个适当索引和分区的数据库表似乎适合这个问题,并且做得很好,至少现在是这样。
问题是,大约 80% 的搜索值没有找到,因为它们不在数据库中。因此,我想加快速度,使搜索速度更快,资源消耗更少。布隆过滤器将是显而易见的选择,如果不是因为不同的应用程序实例接收不同部分的数据,并且如果每个应用程序实例在它的布隆过滤器中只有一部分数据,那么这些布隆过滤器是无用的。
您对如何解决此问题有任何建议/想法吗?
解决方案
保存几天然后丢弃
布隆过滤器不支持删除对象,只支持插入。
如果您有多个布隆过滤器,则必须全部查询它们以检查其中一个是否包含您需要的对象。
如果布隆过滤器具有相同的结构(相同的大小、相同的哈希函数等),它们可以有效地合并。
您可以使用这个布隆过滤器: 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;
}
推荐阅读
- java - 使用java在android中的文本和整数之间迭代以显示专业的启动画面
- android-studio - 如何在 Flutter 开发中测试 Dart 代码片段?
- visual-studio-code - 无法获取开发 VS 代码扩展的工作区中的文件列表
- wordpress - 如果我更改 Wordpress 多站点 URL,如何重定向所有现有链接?
- python - 使用 rest api 从 python 应用程序创建一个 Moodle 用户
- css - 如何使用 Sass @use 导入 sass 文件
- html - gitlab页面不能直接访问,需要登录gitlab
- r - 如何在 R 中使用滚动变量构建序列
- reactjs - react-componentDidMount 方法后如何在 JSX 中使用 API 数据?
- java - 如何使用 printf 分隔多个十进制数字并将所有这些数字四舍五入到小数点后 2 位