LevelDB源码之三SSTable

上一节提到的MemTable是内存表，而当内存表增长到一定程度时(memtable.size> Options::write_buffer_size)，会将当前的MemTable数据持久化(LevelDB中实际有两份MemTable，后面LevelDB数据库备忘时会讲)。持久化的文件(sst文件)称之为Table，LevelDB中的Table分为不同的层级，当前版本的最大层级为7(0-6),table中level0的数据最新，level6的数据最旧。

　　上一节提到的MemTable是内存表，而当内存表增长到一定程度时(memtable.size> Options::write_buffer_size)，会将当前的MemTable数据持久化(LevelDB中实际有两份MemTable，后面LevelDB数据库备忘时会讲)。持久化的文件(sst文件)称之为Table，LevelDB中的Table分为不同的层级，当前版本的***层级为7(0-6),table中level0的数据***，level6的数据最旧。

　　Compaction动作负责触发内存表到SSTable的转换，LOG恢复时也会执行，这里不关心Compaction或恢复的任何细节，后面会单独备忘。

　　LevelDB通过BuildTable方法完成SSTable的构建，其创建SSTable文件并将memtable中的记录依次写入文件。BuildTable带了一个输出参数，FileMetaData：

1structFileMetaData{
2intrefs;
3intallowed_seeks;//Seeksalloweduntilcompaction
4uint64_tnumber;
5uint64_tfile_size;//Filesizeinbytes
6InternalKeysmallest;//Smallestinternalkeyservedbytable
7InternalKeylargest;//Largestinternalkeyservedbytable
8
9FileMetaData():refs(0),allowed_seeks(1<<30),file_size(0){}

　　number为一个递增的序号，用于创建文件名，allowed_seeks作者有提到，是当前文件在Compaction到下一级之前允许Seek的次数，这个次数和文件大小相关，文件越大，Compaction之前允许Seek的次数越多，这个Version备忘时也会提。

　　BuildTable方法中真正做事的时TableBuilder，通过调用Add方法将所有记录添加到数据表中，完成SSTable创建。

　　TableBuilder主要做了如下几件事：

　　创建Index Block：用于Data Block的快速定位

　　将数据分为一个个的Data Block

　　如文件需要压缩，执行压缩动作

　　依次写入Data Block、Meta Block、Index Block、Footer Block，形成完整的SSTable文件结构

　　其中阶段1-3由Add方法完成，阶段4由Finish方法完成，先来看Add方法：

1voidTableBuilder::Add(constSlice&key,constSlice&value){
2Rep*r=rep_;
3assert(!r->closed);
4if(!ok())return;
5if(r->num_entries>0){
6assert(r->options.comparator->Compare(key,Slice(r->last_key))>0);
7}
8
9//IndexBlock：DataBlock的索引元数据。
10if(r->pending_index_entry){
11assert(r->data_block.empty());
12r->options.comparator->FindShortestSeparator(&r->last_key,key);
13std::stringhandle_encoding;
14r->pending_handle.EncodeTo(&handle_encoding);
15r->index_block.Add(r->last_key,Slice(handle_encoding));
16r->pending_index_entry=false;
17}
18
19r->last_key.assign(key.data(),key.size());
20r->num_entries++;
21r->data_block.Add(key,value);
22
23constsize_testimated_block_size=r->data_block.CurrentSizeEstimate();
24if(estimated_block_size>=r->options.block_size){
25Flush();//超过单数据块大小，写入文件。
26}
27}

　　Add方法创建Data Block、IndexBlock，DataBlcok通过Flush刷入磁盘文件。

　　再来看Finish方法：

1StatusTableBuilder::Finish(){
2//DataBlock
3Rep*r=rep_;
4Flush();
5
6assert(!r->closed);
7r->closed=true;
8
9//MetaBlock
10BlockHandlemetaindex_block_handle;
11BlockHandleindex_block_handle;
12if(ok())
13{
14BlockBuildermeta_index_block(&r->options);
15//TODO(postrelease):Addstatsandothermetablocks
16WriteBlock(&meta_index_block,&metaindex_block_handle);
17}
18
19//IndexBlock
20if(ok()){
21if(r->pending_index_entry){
22r->options.comparator->FindShortSuccessor(&r->last_key);
23std::stringhandle_encoding;
24r->pending_handle.EncodeTo(&handle_encoding);
25r->index_block.Add(r->last_key,Slice(handle_encoding));
26r->pending_index_entry=false;
27}
28WriteBlock(&r->index_block,&index_block_handle);
29}
30
31//Footer
32if(ok())
33{
34Footerfooter;
35footer.set_metaindex_handle(metaindex_block_handle);//
36footer.set_index_handle(index_block_handle);
37std::stringfooter_encoding;
38footer.EncodeTo(&footer_encoding);
39r->status=r->file->Append(footer_encoding);
40if(r->status.ok()){
41r->offset+=footer_encoding.size();
42}
43}
44returnr->status;
45}

　　Finish依次写入：尚未写入的***一块Data Block及Meta Block、Index Block、Footer。Meta Block暂未使用，Footer则保存了meta block、index block的位置信息。

　　Block

　　Data Block、Meta Block、Index Block是业务划分，分别代表用户数据块、元数据块及用户数据索引块。其存储格式均为Block结构：

　　Record代表一条数据，蓝色及红色部分(统一称作”重启点”)为附加信息，而这些是做什么的呢?两点：性能优化、节省空间。

　　我们先来看Restart列表的构建逻辑：

1voidBlockBuilder::Add(constSlice&key,constSlice&value){
2Slicelast_key_piece(last_key_);
3......
4size_tshared=0;
5if(counter_<options_->block_restart_interval){
6//Seehowmuchsharingtodowithpreviousstring
7constsize_tmin_length=std::min(last_key_piece.size(),key.size());
8while((shared<min_length)&&(last_key_piece[shared]==key[shared])){
9shared++;
10}
11}
12else{//restart时保存完整的key值
13//Restartcompression
14restarts_.push_back(buffer_.size());
15counter_=0;
16}
17constsize_tnon_shared=key.size()-shared;
18
19//Record信息
20//sharedsize|nosharedsize|valuesize|nosharedkeydata|valuedata
21//Add"<shared><non_shared><value_size>"tobuffer_
22PutVarint32(&buffer_,shared);
23PutVarint32(&buffer_,non_shared);
24PutVarint32(&buffer_,value.size());
25//Addstringdeltatobuffer_followedbyvalue
26buffer_.append(key.data()+shared,non_shared);
27buffer_.append(value.data(),value.size());
28
29//Updatestate
30last_key_.resize(shared);
31last_key_.append(key.data()+shared,non_shared);
32assert(Slice(last_key_)==key);
33counter_++;
34}

　　每隔一定间隔(block_restart_interval)Record就会创建一个新的重启点，重启点内容为当前block的大小，即重启点在block内的偏移。

　　每当添加一个新的重启点时，重启点指向位置的Record中一定保存了完整的key值(shared size = 0),随后的Record中保存的key值仅为和上一个Record的差异值。因为Key在Block中是有序排列的，所以相邻key值重叠区域节省的空间还是非常可观的。

　　基于上述实现，问题来了：当需要定位一条记录时，因为record中key的信息是不完整的，仅包含了和上一条的差异项，但上一条记录本身也只包含了和再上一条的差异项，那么定位一条记录时如何做key比较?如果需要一直向上查找完成key值拼接，性能上会不会有损伤?

　　分析这个问题就要了解重启点的定位：Block的一级索引，SSTable的二级索引(Index Block是SSTable的一级索引)。本文将每个重启点记录位置所属的Record列表称为一个Restart Block

　　假设每条record记录的都是完整的key值时，从SSTable中查找一条记录的工作流如下：

　　根据Key值从Index Block中找到所属的Data Block

　　根据Key值从“重启点”列表中找到所属的Restart Block，从Restart Block的起始位置进行key值比较，找到正确的记录。

　　在上述流程中，我们必定会先找到一个Restart Point，随后进行key值比较，而Restart Point记录本身包含了完整的key值信息，后续key值均可基于此key得到。

　　Restart列表本身做为索引，提升了查找性能，而key值存储的小技巧又降低了空间使用率，在不损伤性能的情况小降低空间利用率，这是一个很好的例子。

　　即使这样，作者觉得还不够，空间利用率还可以进一步优化，并且不损伤任何读取数据的性能。

　　做法和Restart列表的做法类似，是在Index Block中，通过调用FindShortestSeparator / FindShortSuccessor方法实现。

1//If*start<limit,changes*starttoashortstringin[start,limit).
2//Simplecomparatorimplementationsmayreturnwith*startunchanged,
3//i.e.,animplementationofthismethodthatdoesnothingiscorrect.
4virtualvoidFindShortestSeparator(std::string*start,constSlice&limit)const=0;
5
6//Changes*keytoashortstring>=*key.
7//Simplecomparatorimplementationsmayreturnwith*keyunchanged,
8//i.e.,animplementationofthismethodthatdoesnothingiscorrect.
9virtualvoidFindShortSuccessor(std::string*key)const=0;

　　FindShortestSeparator找到start、limit之间最短的key值，如“helloworld”和”hellozoomer”之间最短的key值可以是”hellox”。FindShortSuccessor则更极端，用于找到比key值大的最小key，如传入“helloworld”，返回的key值可能是“i”而已。