我从大学得知Bloom过滤器，这是一种以Burton Bloom命名的概率数据结构。但是我没有机会使用它。上个月，这样的机会出现了-这种结构使我着迷。但是，我很快发现了她的一些缺陷。本文是关于我与Bloom过滤器的短暂恋情的故事。

在研究IP欺骗的过程中，有必要检查传入数据包中的IP地址，并将其与我们数据中心的地理位置进行比较。例如，来自意大利的包裹不应送到巴西的数据中心。这个问题看似简单，但是在不断变化的Internet环境中，它远非简单易行。可以说，最后我积累了很多大的文本文件，它们的内容大致如下：

这意味着来自解析的IP地址192.0.2.1的请求记录在Cloudflare数据中心编号107中。这些数据来自许多来源，包括我们的主动和被动样本，我们拥有的某些域的日志（例如，cloudflare.com），开放源代码（例如BGP表）等。同一行通常在几个文件中重复。

最后，我得到了一个巨大的此类数据集。在某个时候，在所有收集的资源中，我计算了10亿行。通常，我编写bash脚本来预处理输入数据，但是在这种规模下，这种方法不起作用。例如，从600 MIB和40万行的这个小文件删除重复发生...永恒：

我只想说，与该类型的普通命令是重复数据删除线sort在各种配置（见--parallel，--buffer-size和--unique）不是最好的这样一个大的数据集。

布隆过滤器

大卫·爱泼斯坦（David Epstein）在公共领域的插图

然后，我突然意识到：不要对台词进行排序！您需要删除重复项，因此某种“设置”数据结构会更快地工作。另外，我大致知道输入文件的大小（唯一行数），并且某些数据的丢失并不重要，也就是说，概率数据结构非常合适。

这非常适合Bloom过滤器！

在阅读有关Bloom过滤器的Wikipedia时，这就是我看待此数据结构的方式。

您将如何实现多元化？给定理想的哈希函数和无限内存，我们可以简单地创建无限位图并为每个元素设置位数hash(item)。这为“众多”提供了理想的数据结构。对？琐碎的。不幸的是，哈希函数相撞，并且无限内存不存在，因此在我们的现实中我们必须妥协。但是我们可以计算碰撞的可能性并管理该值。例如，我们有一个很好的哈希函数和128 GB的内存。我们可以计算出每个新元素的碰撞概率为1到1099511627776。当您添加更多元素时，该概率随着位图的填充而增加。

此外，我们可以应用多个哈希函数并获得更密集的位图。这是Bloom过滤器运作良好的地方，它是一组具有四个变量的数学数据：

n -插入的元素数（基数）
m -位图使用的内存
k -为每个输入计算的哈希函数数
p -误报的可能性

给定基数n和所需的误报率p，Bloom过滤器返回所需的内存m和所需的哈希函数数量k。

查看一下出色的 Thomas Hurst 可视化，了解参数如何相互影响。

mmuniq-bloom

在直觉的指导下，我将概率工具mmuniq-bloom添加到我的武器库中，该工具使用输入STDIN并仅在STDOUT中返回唯一行。它应该比sort+ 的组合要快得多uniq！

他在那：

mmuniq-bloom.c

为了简化和提高速度，我最初设置了一些参数。首先，除非另有说明，否则mmuniq-bloom使用八个哈希函数k = 8。对于我们的数据大小，这似乎接近最佳数目，并且散列函数可以快速产生八个像样的散列。然后，我们将m位图中的内存对齐到2的幂，以免进行昂贵的操作%modulo，而该操作在汇编器中会变慢div。如果数组等于2的幂，我们可以简单地使用按位与（有趣的是，阅读编译器如何通过乘以魔术常数来优化某些除法运算）。

现在，我们可以在之前使用的同一数据文件上运行它：

哦，那好多了！ 12秒而不是2分钟。该程序使用优化的数据结构，相对有限的内存，优化的行解析和良好的输出缓冲...而且，与工具相比，这12秒钟似乎是永恒wc -l：

发生了什么？我知道算入字符串wc比计算唯一字符串要容易，但是26倍的时差真的合理吗？ CPU需要mmuniq-bloom什么？

必须用于计算哈希。该实用程序wc不会花费处理器，而是为4000万行中的每行执行所有这些奇怪的数学运算。我使用了一个相当平凡的哈希函数siphash24，可以肯定它会烧坏处理器，对吗？让我们通过仅运行哈希函数而不是哈希来进行验证不使用Bloom过滤器执行任何操作：

这很奇怪。尽管上一次运行的整个程序执行了12秒，但哈希函数的计算仅花费了大约2秒钟。一个Bloom过滤器能否工作10秒钟？这怎么可能？这是如此简单的数据结构...

秘密武器-探查器

现在是时候为该任务应用正确的工具了-让我们运行分析器，看看处理器在做什么。首先，让我们运行strace以验证没有意外的系统调用：

一切看起来不错。十个调用mmap每个4 ms（3971μs）都很有趣，但这很好。我们使用来预填充内存MAP_POPULATE，以防止由于缺少页面而导致的错误。

你下一步怎么做？当然是perf！

然后让我们看一下结果：

因此，我们实际上在主代码中消耗了87.2％的周期。让我们看看确切的位置。团队perf annotate process_line --source立即显示出意外情况。

我们看到26.90％的处理器在mov，但这还不是全部！编译器正确插入函数并扩展循环。事实证明，大多数循环都转到此行mov或行uint64_t v = *p！

显然perf是错误的，如此简单的字符串如何占用这么多资源？但是，使用其他任何探查器重复测试都会显示相同的问题。例如，由于彩色图表，我喜欢将google-perftools与kcachegrind一起使用：

可视化的结果如下：

让我总结一下到目前为止已经发现的内容。

标准实用wc程序在0.45 s的处理器时间内处理600 MiB文件。我们优化的工具mmuniq-bloom可以运行12秒。处理器在一条指令上烧毁mov，从而取消了对内存的引用...

Jose Nicdao的图像，CC BY / 2.0

哦！我怎么会忘记随机访问内存真的很慢！非常非常非常慢！

根据每个程序员应该知道的数字，一次访问RAM大约需要100 ns。让我们数一下：4000万行，每行8个散列。由于我们的Bloom过滤器的大小为128 MiB，因此在我们的旧硬件上，它不适合L3缓存！散列均匀分布在广泛的内存中-每个散列都会产生高速缓存未命中。全部放在一起，结果...

事实证明，仅在访问内存时32秒就会耗尽。真正的程序仅用了12秒，因为Bloom筛选器仍然受益于缓存。这很容易看到perf stat -d：

是的，我们应该至少有3.2亿个高速缓存未命中（LLC-load-misses），但是只有2.8亿个发生：这仍然不能解释为什么程序在短短的12秒钟内就能工作。但是这没关系。重要的是，缓存未命中的数量是一个实际问题，我们只能通过减少内存访问的数量来解决它。让我们尝试配置布隆过滤器只使用一个哈希函数：

好哦！真的很痛！为了使每10,000条线发生碰撞的可能性为1，Bloom过滤器需要64 GB的内存。这太糟糕了！

另外，似乎速度没有显着提高。操作系统为我们准备内存需要22秒，但是我们仍然在用户空间上花了11秒。我认为，由于显着增加的内存大小，现在访问缓存的可能性较低，从而弥补了对内存进行罕见访问的所有优势。早期，对于Bloom过滤器，128 MiB就足够了！

拒绝布隆过滤器

这太荒谬了。为了减少误报的可能性，您必须在Bloom过滤器中使用大量的哈希（例如，八个）并进行大量的内存访问，或者保留一个哈希函数，但要使用大量的内存。

我们实际上没有内存限制，我们想最大程度地减少对其的调用。我们需要一个数据结构，该数据结构每个元素最多损失一个高速缓存未命中，并使用少于64 GB的RAM。

当然，您可以实现复杂的数据结构，例如布谷鸟过滤器，但是肯定有一个更简单的选择。好的老式线性探测哈希表又如何呢？Vadims Podans的

插图 

认识mmuniq哈希

这是使用哈希表的mmuniq-bloom的新版本：

mmuniq-hash.c

现在，我们将存储来自'siphash24'函数的 64位哈希值，而不是Bloom过滤器的位。这样可以更好地防止哈希冲突：比每10,000行一个更好。

我们来数数。将一个新项目添加到一个哈希表中，比如说有4000万个条目，则有可能发生哈希冲突40 000 000/2^64。这大约是4610亿中的1-可能性很小。但是，我们不会在预填充集中添加一个元素！相反，我们将4,000万行添加到最初为空的集合中。根据生日悖论，这大大增加了碰撞的可能性。一个合理的近似值是一个估计值'~n^2/2m，在我们的例子中是~(40M^2)/(2*(2^64))。原来，在23,000个元素中有一个机会，换句话说，有了良好的哈希函数，我们期望在4000万个元素的23,000个随机集合之一中发生碰撞。这是一个非零的概率，但仍然比Bloom过滤器中的概率要好，并且对于我们的用例来说是完全可以容忍的。

带有哈希表的代码比Bloom过滤器中的工作更快，具有更好的内存访问模式和更低的误报率。

不必担心“哈希冲突”这一行，它仅显示哈希表的填充量。我们使用线性感应，因此当我们进入全套时，我们只取下一个空的。在我们的例子中，我们必须平均跳过0.7组才能在表中找到一个空白点。这个是正常的。由于我们以线性顺序遍历集合，因此存储器必须在质量上已满。

从前面的示例中，我们知道哈希函数大约需要两秒钟。我们得出的结论是，4000万次内存访问大约需要四秒钟。

得到教训

当可以预测采样模式时，现代处理器确实擅长顺序访问内存（请参阅缓存预取）。另一方面，随机访问内存非常昂贵。

高级数据结构非常有趣，但是要小心。现代计算机要求使用缓存优化算法。当使用不适用于L3的大型数据集时，优先选择命中数，而不是优化所使用的内存量。

可以公平地说，布隆过滤器放在L3缓存中时表现出色。但是，如果没有，那么它们将是可怕的。这不是新闻：Bloom筛选器针对内存量（而不是对其的调用次数）进行了优化。例如，请参阅关于杜鹃过滤器的科学文章。

另一件事是关于哈希函数的无休止的讨论。老实说，在大多数情况下，这并不重要。siphash24与随机访问内存的成本相比，计算甚至复杂的哈希函数的成本似乎也很小。在我们的案例中，简化哈希函数只会带来很小的好处。 CPU时间只是浪费在其他地方-等待内存！

一位同事经常说：“可以假设现代处理器是无限快的。它们以无限的速度工作，直到它们紧贴记忆墙为止。”

最后，不要重复我的错误。您总是需要首先使用perf stat -d并查看IPC计数器（每个周期的指令）。如果小于1，通常意味着程序在等待内存时被卡住。最佳值在两个以上。这意味着工作负载主要在CPU上。不幸的是，在我的任务中，IPC仍然很低...

高级mmuniq

在同事的帮助下，我基于哈希表编写了mmuniq工具的改进版本。这是代码：

mmuniq.c

它可以动态更改哈希表的大小，支持带有任意基数的输入。然后，它有效地利用prefetchCPU中的提示来处理数据包中的数据，从而使程序速度提高了35-40％。请注意，prefetch在代码中大量使用很少能发挥作用。为了使用此功能，我专门对算法进行了重新排序。经过所有改进，执行时间减少到2.1秒：

结束

试图超越“ sort / uniq”组合的基本工具的创建揭示了现代计算的一些隐藏功能。经过一番汗水，我们将程序从两分钟多缩短到了两秒。在开发过程中，我们了解了对内存的随机访问的延迟以及缓存友好型数据结构的功能。奇异的数据结构吸引了人们的注意，但是在实践中，减少对内存的随机访问次数通常更为有效。

当布隆过滤器不合适时