你的位置:首页 > 数据库

[数据库]LevelDB源码之三SSTable


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

 1   struct FileMetaData { 2     int refs; 3     int allowed_seeks;     // Seeks allowed until compaction 4     uint64_t number; 5     uint64_t file_size;     // File size in bytes 6     InternalKey smallest;    // Smallest internal key served by table 7     InternalKey largest;    // Largest internal key served by table 8  9     FileMetaData() : refs(0), allowed_seeks(1 << 30), file_size(0) { }10   };

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

 

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

TableBuilder主要做了如下几件事:

  1. 创建Index Block:用于Data Block的快速定位
  2. 将数据分为一个个的Data Block
  3. 如文件需要压缩,执行压缩动作
  4. 依次写入Data Block、Meta Block、Index Block、Footer Block,形成完整的SSTable文件结构

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

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

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

再来看Finish方法:

 1   Status TableBuilder::Finish() { 2     //Data Block 3     Rep* r = rep_; 4     Flush(); 5  6     assert(!r->closed); 7     r->closed = true; 8      9     //Meta Block10     BlockHandle metaindex_block_handle;11     BlockHandle index_block_handle;12     if (ok()) 13     {14       BlockBuilder meta_index_block(&r->options);15       // TODO(postrelease): Add stats and other meta blocks16       WriteBlock(&meta_index_block, &metaindex_block_handle);17     }18 19     //Index Block20     if (ok()) {21       if (r->pending_index_entry) {22         r->options.comparator->FindShortSuccessor(&r->last_key);23         std::string handle_encoding;24         r->pending_handle.EncodeTo(&handle_encoding);25         r->index_block.Add(r->last_key, Slice(handle_encoding));26         r->pending_index_entry = false;27       }28       WriteBlock(&r->index_block, &index_block_handle);29     }30 31     //Footer32     if (ok()) 33     {34       Footer footer;35       footer.set_metaindex_handle(metaindex_block_handle);  //36       footer.set_index_handle(index_block_handle);37       std::string footer_encoding;38       footer.EncodeTo(&footer_encoding);39       r->status = r->file->Append(footer_encoding);40       if (r->status.ok()) {41         r->offset += footer_encoding.size();42       }43     }44     return r->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列表的构建逻辑:

 

 1 void BlockBuilder::Add(const Slice& key, const Slice& value) { 2     Slice last_key_piece(last_key_); 3     ...... 4     size_t shared = 0; 5     if (counter_ < options_->block_restart_interval) { 6       // See how much sharing to do with previous string 7       const size_t min_length = std::min(last_key_piece.size(), key.size()); 8       while ((shared < min_length) && (last_key_piece[shared] == key[shared])) { 9         shared++;10       }11     }12     else {  //restart时保存完整的key值13       // Restart compression14       restarts_.push_back(buffer_.size());15       counter_ = 0;16     }17     const size_t non_shared = key.size() - shared;18 19     //Record信息20     // shared size | no shared size | value size | no shared key data | value data21     // Add "<shared><non_shared><value_size>" to buffer_22     PutVarint32(&buffer_, shared);23     PutVarint32(&buffer_, non_shared);24     PutVarint32(&buffer_, value.size());25     // Add string delta to buffer_ followed by value26     buffer_.append(key.data() + shared, non_shared);27     buffer_.append(value.data(), value.size());28 29     // Update state30     last_key_.resize(shared);31     last_key_.append(key.data() + shared, non_shared);32     assert(Slice(last_key_) == key);33     counter_++;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中查找一条记录的工作流如下:

  1. 根据Key值从Index Block中找到所属的Data Block
  2. 根据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 *start to a short string in [start,limit).2     // Simple comparator implementations may return with *start unchanged,3     // i.e., an implementation of this method that does nothing is correct.4     virtual void FindShortestSeparator(std::string* start, const Slice& limit) const = 0;5 6     // Changes *key to a short string >= *key.7     // Simple comparator implementations may return with *key unchanged,8     // i.e., an implementation of this method that does nothing is correct.9     virtual void FindShortSuccessor(std::string* key) const = 0;

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