为什么Get和MultiGet对于大密钥集要比使用Iterator慢得多？

Question

目前，我正在使用RocksDB (C++)，并且对我所经历的一些性能指标感到好奇。

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

我的用例主要是读。全键扫描和包含“大量”键的键扫描一样非常常见。(50%+)

我对以下的观察很好奇：

Iterator 1.在执行全键扫描时，比调用要快得多。

当我想查看数据库中的所有键时，我看到在使用Iterator而不是为每个键调用Get时，性能提高了4-8倍。MultiGet的使用没有什么不同。

在调用Get大约200万次的情况下，键以前已经被提取到一个向量中，并按字典顺序排序。为什么反复调用Get比使用Iterator慢得多？有办法缩小这两个API之间的性能差距吗？

当获取大约一半的密钥时，使用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内部将其数据表示为一个日志结构合并树，默认情况下它有多个排序层(这可以通过plugins/config进行更改)。Paul第一个答案的直觉是成立的，只是没有经典的索引；数据实际上是用指向下一个文件的指针在磁盘上排序的。查找操作平均具有对数复杂度，但在排序范围内推进迭代器是恒定的时间。因此，对于密集的顺序读取，迭代要快得多。

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

对密钥进行排序实际上只会提高缓存命中率。取决于您的磁盘，差异可能非常小，例如，如果您有一个NVMe SSD，访问时间上的差异不再像在RAM和HDD时那么大。如果您必须在同一甚至不同的键集上执行多个操作，则按键顺序(f(A)g(A)f(D).)而不是顺序地提高您的性能，因为您将有更多的缓存命中，并且还受益于RocksDB块缓存。

调优指南是一个很好的起点，特别是关于数据库解决方案的视频，但是如果RocksDB太慢，您也可以考虑使用基于不同存储算法的DB。LSM通常更适合于令人头痛的工作负载，虽然RocksDB允许您很好地控制读写和空间放大，但是基于b树或ISAM的解决方案对于范围读取/重复读取来说可能要快得多。

Answer 2

我对RocksDB本身一无所知，但我可以从基本原则中回答很多问题。

在执行全键扫描时，Iterator比调用Get要快得多。

这很可能是因为Get必须对底层索引进行全面查找(从顶部开始)，而提升迭代器则可以通过从当前节点转移到下一个节点来实现。假设索引是以红黑树或类似的方式实现的，那么第二种方法的工作量要比第一种方法少得多。

当获取大约一半的密钥时，使用Iterator和Get之间的性能开始变得微不足道。

那么，您是通过多次调用iterator->Next ()跳过条目的吗？如果是这样的话，那么就会出现这样的情况:为每个密钥调用Get会更便宜，是的。这种情况发生的确切时间将取决于索引中的条目数(因为这决定了树中的级别数)。

按排序顺序取键似乎不会提高性能。

不，我不希望这样。Get (大概)是无状态的。

对于读重的用例，建议设置哪些设置？

我不知道，对不起，但你可能会读到：

https://github.com/facebook/rocksdb/wiki/RocksDB-Tuning-Guide