hadoop - 如何构建大小不适合 RAM 的布隆过滤器？

Question

假设我们必须在一台具有 32 GB RAM 和硬盘驱动器的机器上构建一个具有 10^12 个桶的布隆过滤器。假设 key 很小并且已经在硬盘驱动器上。我们如何才能高效地构建它？
我的猜测是将布隆过滤器分成 4 个部分(125GB/4 适合 32GB)。然后将数据传递 4 次，每次散列并更新内存中的相应切片。将 4 个切片连接回去以获得完整的布隆过滤器。这是正确的吗？

Answer 1

为什么需要这么大的过滤器？您是否试图高估它以处理来自流媒体源的无限数据？如果是，您可以阅读有关 Stable Bloom filter 和 Scalable Bloom filter 的信息。两者都比经典的布隆过滤器更适合此类数据。

要回答您的问题，如果您拆分过滤器，您所说的应该有效。但要确保正确处理索引。例如，如果 4 个元素的位向量在 2 个节点上拆分，第一个将负责索引 (0, 1)，第二个将负责索引 (2, 3)。您可能会将其复杂化一点，并将范围映射存储在某个节点中，并相应地修改读取和写入部分。

您也可以搜索这样的分布式布隆过滤器的实现示例。也许它会给你另一个问题点，或者，而不是从头开始开发你的解决方案，你将能够快速测试它如何与你的数据管道一起工作。

在所有情况下，如果您能在这里就您如何处理问题以及您是否最终选择了其他解决方案提供简短反馈，那就太好了。