hadoop - 如何构建大小无法放入 RAM 的布隆过滤器？

Question

假设我们必须在一台具有 32 GB RAM 和硬盘驱动器的机器上构建一个具有 10^12 个桶的布隆过滤器。假设密钥很小并且已经在硬盘上。我们如何以有效的方式构建它？
我的猜测是将 Bloom 过滤器分成 4 部分（125GB / 4 适合 32GB）。然后通过数据 4 次，每次散列并更新内存中的相应切片。连接 4 个切片返回完整的布隆过滤器。这个对吗？

标签： hadoopdata-structuresbigdata

Answer 1

为什么需要这么大的过滤器？您是否试图高估它以处理来自流式源的无限数据？如果是，您可以阅读有关稳定布隆过滤器和可扩展布隆过滤器的信息。两者都比经典的布隆过滤器更适合这种类型的数据。

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

您还可以搜索分布式布隆过滤器的实现示例。也许它会给您另一个问题点，或者，您无需从头开始开发您的解决方案，而是能够快速测试它在您的数据管道中的表现。

在所有情况下，如果您能在此处提供简短反馈，说明您是如何处理问题的，以及您是否最终选择了另一种解决方案，那就太好了。