暂时不要扔掉你的算法书：可以超越学习索引的经典数据结构

作者:糖果
发布时间:2024-03-29 08:34:38 (20天前)
来源:2018/01/11/index-baselines/

最近，谷歌作者提出的一项新提议引起了很多人的兴奋：通过将神经网络拟合到数据集来取代传统的索引数据结构，如 B 树和哈希图。该论文将这些学习索引与几种标准数据结构进行了比较，并报告了有希望的结果。对于范围搜索，作者报告说 B 树的速度提高了 3.2 倍，同时使用的内存减少了 9 倍，对于点查找，作者报告说哈希表内存开销减少了 80%，同时保持了相似的查询时间。
虽然学习索引是一个令人兴奋的想法，原因有很多（例如，它们可以启用自调整数据库），但有很多其他优化数据结构的文献需要考虑，因此研究人员自然一直在尝试看看这些是否可以做得更好。例如，Thomas Neumann 发表了关于在 B 树中使用样条插值进行范围搜索的文章，并表明这种易于实施的策略可以与学习索引相媲美。在这篇文章中，我们研究了论文中的第二个用例：内存高效的哈希表。我们展示了对于这个问题，一个简单而漂亮的数据结构，布谷鸟哈希, 可以实现比学习索引少 5-20 倍的空间开销，并且它在现代硬件上的速度可以惊人地快，运行速度快近 2 倍。这些结果很有趣，因为在负载平衡方面，cuckoo 哈希比简单的哈希表渐近地更好，因此使用机器学习优化哈希函数变得不那么重要：看到美丽的理论在实践中产生出色结果的案例总是很棒的。
##### 使用 Cuckoo 获取快速哈希表
让我们从了解学习索引论文中的散列用例开始。典型的散列函数在散列表中的槽之间随机分配键，导致一些槽为空，而另一些槽会发生冲突，这需要某种形式的项目链接。如果有大量内存可用，这不是问题：只需创建比表中键多得多的槽（例如 2x），冲突就很少见。但是，如果内存不足，由于更多的链接，重载的表将导致查找速度变慢。作者表明，通过学习将输入键更均匀地分布在整个表中的散列函数，他们可以生成更节省空间的表（加载了高百分比的插槽），并且仍然可以快速访问。
更详细地说，作者使用单独的碰撞链接实现了哈希表，并将标准（随机）哈希函数与学习的哈希函数进行了比较。他们报告了访问时间、空槽占用的内存以及具有不同槽数（从键数的 0.75 倍到 1.25 倍）的表的空槽百分比：

传播输入键肯定有助于简单的单独链接哈希表使用更少的空间，但我们能做得更好吗？事实上，其他数据结构在高负载下可以渐近地更好。例如，我们实现了桶化布谷鸟散列，这是一种简单而美观的技术，可以实现 99% 的占用率，并且由于两种选择的力量，只需两次内存访问即可为所有查找提供服务。与论文中学习到的索引不同，cuckoo hashing 不需要训练步骤，并且支持在运行时对密钥分布进行任意更改，使其易于在许多 系统中应用. 关键思想只是将每个键映射到两个可能的存储桶并将其放置在负载最少的存储桶中，事实证明，这样可以实现非常高的负载，同时保留分摊的 O(1) 插入和最坏情况下的 O(1) 查找. 在现代硬件上，我们发现布谷鸟哈希也可以非常快——也许令人惊讶的是，在某些情况下甚至超过了单独的链。
我们使用 32 位整数键和值（我们确认已在学习索引论文中使用）实现了一个 SIMD 友好的桶化布谷鸟哈希表，我们已将其发布在 GitHub 上。我们为每个使用 AVX2 搜索的桶存储了 8 个密钥，并使用 Murmur3 的终结步骤作为我们的哈希函数，其成本与论文中的随机哈希函数相同（2 次乘法、3 次移位和 3 次 XOR）。我们对论文中公开可用的两个数据集进行了实验：OpenStreetMap 和对数正态数据。我们使用 Intel Xeon E5-2690v4 CPU @ 2.6GHz 进行实验，但在 AWS 上的其他 CPU 上发现几乎相同的数字（c4.8xlarge、Xeon E5-2666v3 @ 2.9GHz 和 m4.16xlarge、Xeon E5-2686v4 @ 2.3GHz ）。总的来说，我们得到了以下结果：

- 地图数据：我们的表每次访问需要36 纳秒，同时仅浪费0.015GB空间（插槽的1%）。
- 对数正常数据：我们的表每次访问需要36ns，同时浪费0.015GB空间（1%的插槽）。

正如我们所见，访问时间和内存开销都得到了显着改善。特别是，即使对于每个键只有 0.75 个槽的单独链表，学习的哈希函数仍然留有 5% 到 20% 的槽为空。相反，我们的表只留下了 1% 的空槽，同时将访问时间减少了近一半。高层次的结论是，在负载平衡方面，布谷鸟哈希比单独的链渐近更好。通过链接，冲突会导致任意长的链，对于n 个键，最长的链平均为O(log n / log log n ) 。即使是学习的哈希函数似乎也没有足够均匀地传播数据来缓解这种情况。使用布谷鸟哈希，总是有每个键最多 2 次内存查找，即使使用随机哈希函数也是如此。
最后，为了确保我们的硬件没有显着不同，我们还实现了一个单独的链接哈希表，如论文中所述。当配置的槽数等于键数时，该表每次查找需要48ns，接近论文中的随机散列性能。我们能够使用我们在自己的表中使用的 Daniel Lemire 取模技巧的快速替代方法将其优化为每次查找42ns，但即便如此，它还是比我们 99% 占用的布谷鸟表慢。这种差异让我们感到惊讶，因为单独的链接表应该比 cuckoo 表平均每个键进行更少的内存访问，但它可能发生在现代硬件上的一个原因是间接访问：在单独的链接中，在每个插槽中跟踪项目的链表需要 CPU 等待读取每个节点以发现下一个指针，而在布谷鸟散列中，键映射到的两个单元的地址在执行之前是可计算的任何内存访问，因此 CPU 可能会推测性地获取两个地址。我们绝对希望处理器供应商不要拿走我们的推测执行！
##### 闭幕式
所有这些是否意味着学习索引是一个坏主意？一点也不：这篇论文很好地观察到，当周期相对于内存访问来说便宜时，计算密集型函数逼近可能有利于查找，并且 ML 模型在逼近某些函数方面可能比现有数据结构更好。自调整数据结构的想法也令人兴奋。不过，我们的主要信息是，还有许多其他想法可以创造性地解决索引问题，我们也应该确保利用这些见解。在散列的情况下，由于深刻的算法洞察力，两种选择的力量，布谷鸟散列表渐近地更好，这大大改善了负载平衡。在其他领域，诸如自适应索引之类的想法 ，数据库破解、 完美散列、数据相关散列、函数逼近和草图 也为系统设计者提供了强大的工具，例如，除了适应数据分布外，还可以适应查询分布。将这些想法与来自机器学习和最新硬件的工具进行比较和结合将是令人兴奋的。

1 条回复

动动手指，沙发就是你的了！

登录后才能参与评论