leveldb - 为什么 LevelDB 需要两个以上的级别？

Question

我认为只有两个级别（级别 0 和级别 1）是可以的，为什么 LevelDB 需要级别 2、级别 3 等等？

Answer 1

我将为您指明有关 LevelDB 及其底层存储结构的一些文章的方向。

因此，在LevelDB 的文档中， 它讨论了级别之间的合并。

这些合并具有将新更新从年轻级别逐渐迁移到仅使用批量读取和写入的最大级别的效果（即，最大限度地减少昂贵的查找）。

LevelDB 在结构上类似于Log Structured Merge Trees。如果您有兴趣对其进行分析，本文将讨论不同的级别。如果你能理解数学，那么理解数据结构似乎是你最好的选择。

更容易阅读的 levelDB分析讨论了数据存储与 LSM 树的关系，但就您对级别的问题而言，它所说的只是：

最后，拥有数百个磁盘上的 SSTable 也不是一个好主意，因此我们将定期运行一个流程来合并磁盘上的 SSTable。

可能 LevelDB 文档提供了最好的答案：（最大化写入和读取的大小，因为 LevelDB 是磁盘上（慢速查找）数据存储）。

祝你好运！

Answer 2

我认为这主要与简单快速的关卡合并有关。

在 Leveldb 中，level-(i+1) 大约有。10 倍于 level-i 的数据。这更类似于多级缓存结构，如果数据库在键 x1 到 x2 之间有 1000 条记录，那么该范围内最常访问的 10 个记录将位于级别 1，而同一范围内的 100 个记录将是在第 2 级，在第 3 级休息（这并不准确，只是为了直观地了解关卡）。在此设置中，要合并级别-i 中的文件，我们最多需要查看级别-(i+1) 中的 10 个文件，并且可以将它们全部放入内存中，快速合并完成并写回。这些导致为每个压缩/合并操作读取相对较小的数据块。

另一方面，如果您只有 2 个级别，则一个级别 0 文件中的键范围可能与级别 1 中的 1000 个文件匹配，并且所有这些文件都需要打开以进行合并，这将非常慢。请注意，这里的一个重要假设是我们有固定大小的文件（比如 2MB）。使用级别 1 中的可变长度文件，您的想法仍然可行，我认为 HBase 和 Cassandra 等系统中使用了这种变体。

现在，如果您担心多级查找延迟，这又类似于多级缓存结构，最近写入的数据将位于更高级别以帮助典型的参考局部性。

Answer 3

级别 0 是内存中的数据，其他级别是磁盘数据。重要的部分是对级别中的数据进行排序。如果 level1 由 3 个 2Mb 文件组成，那么在 file1 中，它是 file2 150..200 和 file3 300..400 中的键 0..50（已排序）（例如）。因此，当内存级别已满时，我们需要以最有效的方式将其数据插入磁盘，即顺序写入（使用尽可能少的磁盘寻道）。想象一下，在内存中我们有 60-120 键，很酷，我们只是将它们按顺序写入文件，然后在 level1 中变成 file2。非常有效率！但是现在想象 level1 比 level0 大得多（这是合理的，因为 level0 是内存）。在这种情况下，level1 中有很多文件。现在我们在内存中的键（60-120）属于许多文件，因为 level1 中的键范围非常细。现在要将 level0 与 level1 合并，我们需要读取许多文件并进行大量随机搜索，在内存中创建新文件并写入它们。所以这就是多层次想法发挥作用的地方，我们将有很多层，每一层都比前一个（x10）大一些，但不会大很多，所以当我们必须将数据从 i-1 迁移到第 i 层时，我们有一个必须阅读最少数量的文件的好机会。

现在，由于数据可能会更改，因此可能不需要将其传播到更高更昂贵的层（它可能会被更改或删除），因此我们完全避免了昂贵的合并。最终进入最后一层的数据在统计上变化的可能性最小，因此最适合与最后一层最昂贵的合并。