为什么LevelDB需要两个以上的关卡?

  • 本文关键字:两个 LevelDB leveldb okvs
  • 更新时间 :
  • 英文 :


我认为只有两个级别(0级和1级)是可以的,为什么LevelDB需要2级,3级,甚至更多?

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

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

这些合并的效果是将新的更新从年轻层逐渐迁移到最大层,只使用批量读写(即最小化昂贵的查找)。

LevelDB在结构上类似于Log Structured Merge Trees。如果你对它的分析感兴趣,这篇文章讨论了不同的层次。如果你能理解数学,这似乎是你理解数据结构的最佳选择。

一个更容易阅读的levelDB分析讨论了数据存储与LSM树的关系,但就你关于级别的问题而言,它所说的只是:

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

可能LevelDB文档提供了最好的答案:(最大化写和读的大小,因为LevelDB是在磁盘上(慢速查找)数据存储)。

祝你好运!

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

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

另一方面,如果你只有2个级别,一个0级文件中的键范围可能会匹配1000个1级文件,所有这些文件都需要打开合并,这将是相当缓慢的。注意,这里有一个重要的假设,即我们有固定大小的文件(比如2MB)。在level-1中使用可变长度文件,你的想法仍然可以工作,我认为它的一个变体在HBase和Cassandra等系统中使用。

现在如果你关心的是多级查询延迟,这就像一个多级缓存结构,最近写入的数据将在更高的级别,以帮助典型的引用局部性

级别0是内存中的数据,其他级别是磁盘数据。重要的部分是,关卡中的数据是排序的。如果level1包含3个2Mb的文件,那么在file1中它的键是0..50(排序)在文件e2 150…200和300…400(作为例子)。因此,当内存级别满时,我们需要以最有效的方式将它的数据插入磁盘,这是顺序写入(使用尽可能少的磁盘查找)。想象一下,在内存中,我们有60-120键,很酷,我们把它们顺序写入文件,在level1中变成file2。非常有效!但是现在想象level1比level0大得多(这是合理的,因为level0是内存)。在本例中,level1中有许多文件。现在内存中的键(60-120)属于许多文件,因为级别1中的键范围非常细粒度。现在,为了合并level0和level1,我们需要读取许多文件并进行大量随机查找,在内存中创建新文件并写入它们。所以这就是多级思想开始的地方,我们将有许多层,每一层都比前一层大一些(x10),但不会大很多,所以当我们必须将数据从i-1层迁移到i-1层时,我们很有可能必须读取最少数量的文件。

现在,由于数据可能会改变,可能不需要将其传播到更高更昂贵的层(它可能被更改或删除),因此我们完全避免了昂贵的合并。在最后一层结束的数据在统计上是最不可能改变的,所以最适合最昂贵的最后一层。

相关内容

  • 没有找到相关文章

最新更新