当前位置: 首页 > 科技观察

LevelDB源码3SSTable

时间:2023-03-12 16:18:43 科技观察

上一节提到的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”。