c++ - 与使用 Iterator 相比，为什么 Get 和 MultiGet 对于大型键集要慢得多？

Question

我目前正在使用 RocksDB (C++)，并对我体验过的一些性能指标感到好奇。

出于测试目的，我的数据库键是文件路径，值是文件名。我的数据库中有大约 2M 个条目。我在 MacBook Pro 2016 (SSD) 上本地运行 RocksDB。

我的用例以读取为主。全键扫描非常常见，包括“大量”键的键扫描也是如此。 (50%+)

我对以下观察感到好奇:

<强>1。在执行全键扫描时，Iterator 比调用 Get 快得多。

当我想查看数据库中的所有键时，使用 Iterator 而不是调用 Get 时我发现性能提高了 4-8 倍每个键。 MultiGet 的使用没有区别。

在调用 Get 大约 2M 次的情况下，键已预先提取到 vector 中并按字典顺序排序。为什么反复调用 Get 比使用 Iterator 慢得多？有没有办法缩小两个 API 之间的性能差距？

<强>2。当获取大约一半的键时，使用 Iterator 和 Get 之间的性能开始变得可以忽略不计。

随着要获取的键的数量减少，多次调用 Get 开始花费与使用 Iterator 一样长的时间，因为迭代器正在付出代价扫描不在所需键集中的键。

对于大多数数据库来说，是否存在某种“神奇”的比例？例如，如果我需要扫描超过 25% 的键，则调用 Get 会更快，但如果是 75% 的键，则调用 Iterator 会更快。但这些数字只是通过粗略测试“编造”出来的。

<强>3。按排序顺序获取键似乎不会提高性能。

如果我将要获取的键预先排序为 Iterator 将返回它们的相同顺序，这似乎不会多次调用 Get任何更快。这是为什么？文档中提到建议在进行批量插入之前对键进行排序。 Get 不会受益于与 Iterator 相同的超前缓存吗？

<强>4。对于大量读取的用例，建议使用哪些设置？

最后，是否有针对可能涉及一次扫描大量键的读取密集型用例推荐的任何特定设置？

macOS 10.14.3、MacBook Pro 2016 SSD、RocksDB 5.18.3、Xcode 10.1

Answer 1

RocksDB 在内部将其数据表示为 log-structured merge tree默认情况下有几个排序层(这可以通过插件/配置更改)。保罗第一个答案的直觉是成立的，除了没有经典索引；数据实际上是在磁盘上排序的，并带有指向下一个文件的指针。查找操作具有平均对数复杂度，但在排序范围内推进迭代器是常数时间。所以对于密集的顺序读取，迭代要快得多。

成本平衡点不仅取决于您读取的键数，还取决于数据库的大小。随着数据库的增长，查找变慢，而 Next() 保持不变。最近的插入可能会被读取得非常快，因为它们可能仍在内存中(内存表)。

对键进行排序实际上只会提高您的缓存命中率。根据您的磁盘，差异可能非常小，例如，如果您有 NVMe SSD，则访问时间的差异不再像 RAM 与 HDD 时那样剧烈。如果您必须通过键顺序 (f(a-c) g(a-c) f(d-g)...) 而不是按顺序对相同或什至不同的键集执行多个操作应该会提高您的性能，因为您会有更多的缓存命中率，并且还受益于 RocksDB block 缓存。

调整指南是一个很好的起点，尤其是 video on database solutions ，但是如果 RocksDB 对你来说太慢了，你也可以考虑使用基于不同存储算法的数据库。 LSM 通常更适合写入繁重的工作负载，虽然 RocksDB 可以让您很好地控制读取与写入与空间放大，但基于 b 树或 ISAM 的解决方案对于范围读取/重复读取可能会快得多。