LevelDB源码3SSTable

上一节提到的MemTable是内存表，当内存表增长到一定程度（memtable.size>Options::write_buffer_size）时，会持久化当前MemTable数据（在LevelDB其实有两个MemTable，后面会在LevelDB数据库备忘录中讲到）。持久文件（sst文件）称为表。LevelDB中的表分为不同的级别。当前版本最大级别为7（0-6），表中level0的数据为***，level6的数据最旧。　　Compaction动作负责触发内存表到SSTable的转换，LOG恢复时也会执行。这里不关心Compaction或者recovery的任何细节，后面会单独做笔记。　　LevelDB通过BuildTable方法完成SSTable的构建，创建SSTable文件，依次将memtable中的记录写入文件。BuildTable带了一个输出参数，FileMetaData：1structFileMetaData{2intrefs;3intallowed_seeks;//Seeksalloweduntilcompaction4uint64_tnumber;5uint64_tfile_size;//Filesizeinbytes6InternalKeysmallest;//Smallestinternalkeyservedbytable7InternalKeylargest;//Largestinternalkeyservedbytable89FileMetaData():refs(0),allowed_seeks(1<<30),file_size(0){}　　number是一个递增的序列号，用于创建文件名。allowed_seeks的作者提到它是在Compaction进入下一级之前允许当前文件Seek的次数。这个数字与文件大小有关。文件越大，Compaction前允许Seek的次数越多，这个Version也会在备忘录中提到。　　BuildTable方法实际上是在TableBuilder调用Add方法将所有记录添加到数据表中完成SSTable创建时起作用的。　　TableBuilder主要做了以下几件事：　　CreateIndexBlock：用于DataBlock的快速定位　　将数据分成DataBlocks　　如果文件需要压缩，则依次执行压缩动作　　写入DataBlock、MetaBlock、IndexBlock、FooterBlock组成一个完整的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}89//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}1819r->last_key.assign(key.data(),key.size());20r->num_entries++;21r->data_block.Add(key,value);2223constsize_estimated_block_size=r->data_block.CurrentSizeEstimate();24if(estimated_block_size>=r->options.block_size){25Flush();//超出单个数据写入文件的块大小。26}27}　　增加创建DataBlock、IndexBlock、DataBlock的方法，通过Flush刷新磁盘文件。　　再来看Finish方法：1StatusTableBuilder::Finish(){2//DataBlock3Rep*r=rep_;4Flush();56assert(!r->closed);7r->closed=true;89//MetaBlock10BlockHandlemetaindex_block_handle;11BlockHandleindex_block_handle;12if(ok())13{14BlockBuildermeta_index_block(&r->options);15//TODO(postrelease):Addstatsandothermetablocks16WriteBlock(&meta_index_block,&metaindex_block_handle);17}1819//IndexBlock20if(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}3031//Footer32if(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依次写入：最后一个DataBlock，MetaBlock，IndexBlock，还有还没有写入的Footer。MetaBlock还没有使用，Footer中存放的是metablock和indexblock的位置信息。Block　　DataBlock、MetaBlock、IndexBlock是业务划分，分别代表用户数据块、元数据块、用户数据索引块。它的存储格式是Block结构：　　　　Record代表一条数据，蓝色和红色部分（统称为“重启点”）是附加信息，这些是做什么的？两点：性能优化和空间节省。　　我们先来看Restart列表的构建列表：1voidBlockBuilder::Add(constSlice&key,constSlice&value){2Slicelast_key_piece(last_key_);3......4size_tshared=0;5if(counter_block_restart_interval){6//Seehowmuchsharingtmin_length7dowithprevious=std::min(last_key_piece.size(),key.size());8while((shared"tobuffer_22PutVarint32(&buffer_,shared);23PutVarint32(&buffer_,non_shared);24PutVarint32(&buffer_,value.size());25//Addstringdeltatobuffer_followedbyvalue26buffer_.append(key.data()+shared,non_shared);27buffer_.append(value.data(),value.size());2829//更新状态30last_key_.resize(shared);31last_key_.append(key.data()+shared,non_shared);32assert(Slice(last_key_)==key);33counter_++;34}每隔一定的时间间隔创建记录(block_restart_interval)A新的重启点，重启点的内容为当前区块的大小，即重启点在区块内的偏移量。　　每增加一个新的重启点，必须在重启点指向的Record中保存完整的key值（sharedsize=0），后续Record中保存的key值只是与之前的不同记录价值。因为键在块中是有序排列的，相邻键值重叠区域节省的空间还是很可观的。　　基于上面的实现，问题就出现了：当需要定位一条记录时，由于记录中的关键信息不完整，只包含与前一条记录的不同，而前一条记录本身只包含相同的上篇文章中的差异项，在定位一条记录时如何进行key比较？如果需要向上查找完成键值的拼接，会不会有性能损失？　　要分析这个问题，必须了解重启点的位置：BlockPrimaryindex,SSTable的secondaryindex（IndexBlock是SSTable的primaryindex）。本文将每条重启点记录位置所属的Record列表称为一个RestartBlock　　假设每条记录记录都有完整的key值，从SSTable中查找一条记录的工作流程如下：　　根据Key从IndexBlock到DataBlock的value找到　　根据Key值从“RestartPoint”列表中找到RestartBlock，从RestartBlock的起始位置开始比较key值找到正确的记录。　　在上面的过程中，我们首先要找到一个RestartPoint，然后进行key值的比较，而RestartPoint记录本身就包含了完整的key值信息，后续的key值可以根据这个key获取。　　Restart列表本身作为索引，提高了搜索性能，key-value存储技术降低了空间利用率，可以在不损害性能的情况下降低空间利用率。这是一个很好的例子。　　尽管如此，笔者还是觉得还不够，在不影响读取数据性能的情况下，还可以进一步优化空间利用率。　　的做法和Restart列表类似，都是调用IndexBlock中的FindShortestSeparator/FindShortSuccessor方法实现的。1//如果*start=*key.7//Simplecomparatorimplementationsmayreturnwith*keyunchanged,8//i.e,animplementationofthismethodthatdoesnothingiscorrect.9virtualvoidFindShortSuccessor(std::string*key)const=0;　　FindShortestSeparator查找start和limit之间最短的键值，例如“helloworld”和“hellozoomer”之间的最短键值可以是“hellox”。FindShortSuccessor更为极端。它用于查找大于键值的最小键。比如传入“helloworld”，返回的键值可能是“i”。