Chinaunix首页 | 论坛 | 博客
  • 博客访问: 124342
  • 博文数量: 53
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 224
  • 用 户 组: 普通用户
  • 注册时间: 2015-06-28 01:08
文章分类
文章存档

2020年(1)

2019年(1)

2017年(1)

2016年(18)

2015年(32)

我的朋友

分类: NOSQL

2019-05-24 07:04:48

leveldb使用memtable/sstable的设计。其中sstable全称为sorted string table,顾名思义,是一组按字符串排序的sstable以分层的方式进行组织。每个level的数据量大约是上一层的10倍。由内存flush直接生成的sorted table放置于一个特殊的“young level(也称为level-0)。当young level的文件数超过某个阈值(目前是4),就会将所有overlapping【注意overlapping的含义,是指键值范围(key range)上的重叠】的young fileslevel-1 file进行merge,生成一组新的level-1文件,每个level-1文件包含2M数据level-01M的文件,其他level都是2M的文件

 

young level中不同的文件可能包含相互重叠的键值。而其他各个level中的文件key range不会重叠【层内不重叠,跨层当然会重叠】。对于特定的L(L >= 1),如果level-L的文件总大小超过10^L MB(例如lelel-1 10M, level-2 100M),那么level-L中会有一个文件,跟level-(L+1)中键值范围重叠的所有文件进行合并,生成一组新的level-(L+1)文件。这些merge操作从效果上讲,会逐步将最新的update操作从young level迁移到最大level中,这个过程只用到了bulk reads/writes,从而将磁盘操作的代价最小化。

 

level-L大小超过上限,levelDB会在后台线程中进行compact操作。该操作会选定某个level-L文件,以及level-(L+1)中所有范围与之重叠的文件。注意,即使level-Llevel-(L+1)文件的范围仅部分重合,level-(L+1)的整个文件也会用于compact操作的输入,并在操作完成后丢弃。从level-0level-1进行compact时,会有些特殊处理,因为level-0本层的文件之间相互会有overlapping。如果遇到层内范围重合的情况,level-0compact可能选定多于一个的level-0文件。

 

level-Lcompact操作将所有选定的文件(通常一个L层,若干个L+1),重新生成为一组level-(L+1)文件。levelDB生成新的文件过程中,每当current output file数据达到2M就写满,转而开始生成一个新的level-(L+1)文件。还有一个条件会触发levelDB生成新的level-(L+1)文件,即current output filekey range已经增长到可以覆盖10level-(L+2)文件。这样做是为了避免后续对level-(L+1)进行compact时,不会选中过多的level-(L+2)文件。

 

还有一个问题,leveldb确定要level-L进行compact操作之后,如何决定选择哪个文件呢?这里的策略是在整个key space循环轮流compact。具体而言,levelDB针对每一层都记录上次compact操作的ending key,下次compact操作会根据该key选定文件。

 

从上面的论述,我们可以推断level-0 compact操作最坏情况下会选定本层所有41M的文件,以及所有的level-1文件(10MB),这种情况下levelDB将需要读14M并写14M

 

level-0 compact的特殊情况不同,其他层Lcompact只选定本层一个2M的文件,最坏情况下,该文件key rangelevel-(L+1)的大约12个文件重合(L+1L层的10倍,加上两头的范围通常并不对齐,就是12个文件了)。因而该操作要读26m,写26m。假设磁盘io速率为100MB/s,则最坏情况下耗时大约0.5s

 

如果我们对后台读写进行限速,例如只能使用100MB/s10%,则compact操作大约要花费5s。这段时间新生成的level-0文件,不可以进行compact。如果用户写入的速率是10M/s,可能导致levelDB创建很多的level-0文件(5秒大约要积压大约50m,每个文件1m,就是约50个文件)。这会大幅增加read操作的代价,因为每次read要合并从大量文件读取的结果。

 

前面讲了选定level之后所进行的操作。那么leveldb 如何选定在哪层进行compact操作?leveldb会对每一层计算一个score,该值等于 current bytes / desired bytes。对于level-0score = files / desired files。然后会选定score最大的层来compact

 

选定L0进行compact的话,还有一个特殊之处,即选定了primary L0 file之后,还需要检查L0的其他文件,如果有重叠,则也要选定。通常来说,L0compact会选定所有的L0文件,但并不总是如此。

 

参考资料:

https://github.com/basho/leveldb/blob/develop/db/version_set.cc 的 PickCompaction 函数 
http://blog.sina.com.cn/s/blog_4575b5690102wny5.html





阅读(1191) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~