dablooms

Dablooms: 一个可扩展的计数型 Bloom 过滤器 --------------------------------------- _注意：此项目已经有一段时间没有维护了。

特性

除了上述功能外，dablooms还具有以下特性：

为了提高性能,低级操作使用 C 语言实现。它还具有内存映射功能,可以低成本实现异步清除和持久性。为了保持内存效率,我们不使用整数或甚至整个字节作为计数器,而是仅使用四位计数器。这些四位计数器允许最多 15 个项目共享映射中的计数器。如果超过少数几个项目共享该计数器,在任何合理的错误率下,布鲁姆过滤器都会过载(从而导致过多的假阳性结果),因此支持更大的计数器没有任何好处。

Bloom 过滤器还使用更改序列号来跟踪对 Bloom 过滤器执行的操作。这些序列号使应用程序能够确定写入操作是否仅部分完成（可能是由于崩溃），导致过滤器处于不一致状态。应用程序因此可以确定过滤器是否正常或需要重新创建。序列号可用于确定一致但过时的过滤器缺失了什么内容，并将其更新为最新状态。

有两个序列号(以及获取它们的辅助函数):"mem_seqnum"和"disk_seqnum"。如果用户确信操作系统没有崩溃,"mem"变体是有用的,如果操作系统可能自从 Bloom 过滤器上次更改以来崩溃,"disk"变体是有用的。