与使用 Iterator 相比，为什么 Get 和 MultiGet 对于大型键集要慢得多？
Why are Get and MultiGet significantly slower for large key sets compared to using an Iterator?
我目前正在使用 RocksDB (C++)，并且对我体验过的一些性能指标感到好奇。
出于测试目的，我的数据库键是文件路径，值是文件名。我的数据库中有大约 2M 个条目。我在 MacBook Pro 2016 (SSD) 上本地 运行 RocksDB。
我的用例以读取为主。全键扫描非常常见，包括 "significant" 个键的键扫描也是如此。 (50%+)
我对以下观察感到好奇：
1.在执行全键扫描时，Iterator 比调用 Get 快得多。
当我想查看数据库中的所有键时，使用 Iterator 而不是为每个键调用 Get 时，性能提高了 4-8 倍。使用 MultiGet 没有区别。
在调用 Get 大约 2M 次的情况下，键已预先提取到向量中并按字典顺序排序。为什么重复调用 Get 比使用 Iterator 慢得多？有没有办法缩小两个 API 之间的性能差距？
2。当获取大约一半的键时，使用 Iterator 和 Get 之间的性能开始变得可以忽略不计。
随着要获取的键的数量减少，然后多次调用 Get 开始花费与使用 Iterator 一样长的时间，因为迭代器正在支付扫描键的代价不在所需的键集中。
是否有一些 "magic" 比率可以使大多数数据库成为现实？例如，如果我需要扫描超过 25% 的键，那么调用 Get 会更快，但如果它是 75% 的键，那么调用 Iterator 会更快。但这些数字只是 "made up" 通过粗略测试。
3。按排序顺序获取键似乎不会提高性能。
如果我将要获取的键预先排序为 Iterator 将 return 放入的相同顺序，那似乎不会多次调用 Get任何更快。这是为什么？文档中提到建议在进行批量插入之前对键进行排序。 Get 是否受益于与 Iterator 相同的超前缓存？
4.对于大量读取的用例，建议使用哪些设置？
最后，是否有针对可能涉及一次扫描大量键的读取密集型用例推荐的任何特定设置？
macOS 10.14.3、MacBook Pro 2016 固态硬盘、RocksDB 5.18.3、Xcode10.1
我对 RocksDB 本身一无所知，但我可以从第一原则回答很多问题。
An Iterator is dramatically faster than calling Get when performing full key scans.
这可能是因为 Get 必须在基础索引中进行完整查找（从顶部开始），而推进迭代器可以通过从当前节点移动到下一个节点来实现。假设索引实现为红黑树或类似树，则第二种方法比第一种方法少很多工作。
When fetching around half the keys, the performance between using an Iterator and Get starts to become negligible.
所以您是通过多次调用 iterator->Next () 来跳过条目？如果是这样，那么就会有一点，为每个键调用 Get 会更便宜，是的。具体何时发生将取决于索引中的条目数（因为这决定了树中的级别数）。
Fetching keys in sorted order does not appear to improve performance.
不，我不希望如此。 Get 是（大概）无国籍的。
What settings are recommended for a read-heavy use case?
抱歉，我不知道，但你可能会读到：
https://github.com/facebook/rocksdb/wiki/RocksDB-Tuning-Guide
RocksDB 在内部将其数据表示为 log-structured merge tree，默认情况下有多个排序层（这可以用 plugins/config 更改）。保罗第一个答案的直觉是成立的，除了没有经典索引；数据实际上是在磁盘上排序的，并带有指向下一个文件的指针。查找操作具有平均对数复杂度，但在排序范围内推进迭代器是常数时间。所以对于密集的顺序读取，迭代要快得多。
成本平衡点不仅取决于您读取的键数，还取决于数据库的大小。随着数据库的增长，查找变慢，而 Next() 保持不变。最近的插入可能会被读取得非常快，因为它们可能仍在内存中 (memtables)。
对键进行排序实际上只会提高缓存命中率。根据您的磁盘，差异可能非常小，例如，如果您有 NVMe SSD，则访问时间的差异不再像 RAM 与 HDD 时那样剧烈。如果您必须通过键顺序 (f(a-c) g(a-c) f(d-g)...) 而不是按顺序对相同或什至不同的键集执行多个操作应该会提高您的性能，因为您会有更多的缓存命中，也受益于 RocksDB 块缓存。
调优指南是一个很好的起点，尤其是 video on database solutions，但如果 RocksDB 对您来说太慢，您也可以考虑使用基于不同存储算法的数据库。 LSM 通常更适合写入繁重的工作负载，虽然 RocksDB 可以让您很好地控制读取与写入与 space 放大，但基于 b 树或 ISAM 的解决方案对于 range-reads/repeated 来说可能要快得多阅读。
我目前正在使用 RocksDB (C++)，并且对我体验过的一些性能指标感到好奇。
出于测试目的，我的数据库键是文件路径，值是文件名。我的数据库中有大约 2M 个条目。我在 MacBook Pro 2016 (SSD) 上本地 运行 RocksDB。
我的用例以读取为主。全键扫描非常常见，包括 "significant" 个键的键扫描也是如此。 (50%+)
我对以下观察感到好奇：
1.在执行全键扫描时，Iterator 比调用 Get 快得多。
当我想查看数据库中的所有键时，使用 Iterator 而不是为每个键调用 Get 时，性能提高了 4-8 倍。使用 MultiGet 没有区别。
在调用 Get 大约 2M 次的情况下，键已预先提取到向量中并按字典顺序排序。为什么重复调用 Get 比使用 Iterator 慢得多？有没有办法缩小两个 API 之间的性能差距？
2。当获取大约一半的键时，使用 Iterator 和 Get 之间的性能开始变得可以忽略不计。
随着要获取的键的数量减少，然后多次调用 Get 开始花费与使用 Iterator 一样长的时间，因为迭代器正在支付扫描键的代价不在所需的键集中。
是否有一些 "magic" 比率可以使大多数数据库成为现实？例如，如果我需要扫描超过 25% 的键，那么调用 Get 会更快，但如果它是 75% 的键，那么调用 Iterator 会更快。但这些数字只是 "made up" 通过粗略测试。
3。按排序顺序获取键似乎不会提高性能。
如果我将要获取的键预先排序为 Iterator 将 return 放入的相同顺序，那似乎不会多次调用 Get任何更快。这是为什么？文档中提到建议在进行批量插入之前对键进行排序。 Get 是否受益于与 Iterator 相同的超前缓存？
4.对于大量读取的用例，建议使用哪些设置？
最后，是否有针对可能涉及一次扫描大量键的读取密集型用例推荐的任何特定设置？
macOS 10.14.3、MacBook Pro 2016 固态硬盘、RocksDB 5.18.3、Xcode10.1
我对 RocksDB 本身一无所知，但我可以从第一原则回答很多问题。
An Iterator is dramatically faster than calling Get when performing full key scans.
这可能是因为 Get 必须在基础索引中进行完整查找（从顶部开始），而推进迭代器可以通过从当前节点移动到下一个节点来实现。假设索引实现为红黑树或类似树，则第二种方法比第一种方法少很多工作。
When fetching around half the keys, the performance between using an Iterator and Get starts to become negligible.
所以您是通过多次调用 iterator->Next () 来跳过条目？如果是这样，那么就会有一点，为每个键调用 Get 会更便宜，是的。具体何时发生将取决于索引中的条目数（因为这决定了树中的级别数）。
Fetching keys in sorted order does not appear to improve performance.
不，我不希望如此。 Get 是（大概）无国籍的。
What settings are recommended for a read-heavy use case?
抱歉，我不知道，但你可能会读到：
https://github.com/facebook/rocksdb/wiki/RocksDB-Tuning-Guide
RocksDB 在内部将其数据表示为 log-structured merge tree，默认情况下有多个排序层（这可以用 plugins/config 更改）。保罗第一个答案的直觉是成立的，除了没有经典索引；数据实际上是在磁盘上排序的，并带有指向下一个文件的指针。查找操作具有平均对数复杂度，但在排序范围内推进迭代器是常数时间。所以对于密集的顺序读取，迭代要快得多。
成本平衡点不仅取决于您读取的键数，还取决于数据库的大小。随着数据库的增长，查找变慢，而 Next() 保持不变。最近的插入可能会被读取得非常快，因为它们可能仍在内存中 (memtables)。
对键进行排序实际上只会提高缓存命中率。根据您的磁盘，差异可能非常小，例如，如果您有 NVMe SSD，则访问时间的差异不再像 RAM 与 HDD 时那样剧烈。如果您必须通过键顺序 (f(a-c) g(a-c) f(d-g)...) 而不是按顺序对相同或什至不同的键集执行多个操作应该会提高您的性能，因为您会有更多的缓存命中，也受益于 RocksDB 块缓存。
调优指南是一个很好的起点，尤其是 video on database solutions，但如果 RocksDB 对您来说太慢，您也可以考虑使用基于不同存储算法的数据库。 LSM 通常更适合写入繁重的工作负载，虽然 RocksDB 可以让您很好地控制读取与写入与 space 放大，但基于 b 树或 ISAM 的解决方案对于 range-reads/repeated 来说可能要快得多阅读。