本文共 4834 字，大约阅读时间需要 16 分钟。
TableBuilder
将数据写入磁盘生成sstable的工作由TableBuilder类完成。顾名思义，TableBuilder负责中封装了sstable的生成格式，它对用户的接口主要是
void Add(const Slice& key, const Slice& value);
函数，从函数的形式我们也可以看到，就是将键值对逐次加入到sstable中，而至于sstable中的其他管理块，比如index block，meta data block等内容则在调用Add的过程中，在TableBuilder类内部完成构建。本文主要是研究TableBuilder的具体实现，下图是TableBuilder的UML类图
正如前面所说，TableBuilder是用于构建sstable的，而sstable里面还包含了各种block。比如data block，index block，metadata block等，不同的block可能有不同的存储格式，以及需要存储不同的信息。我们肯定不想让sstable管理所有类型的block的生成细节，那会使得TableBuilder过于臃肿，可选的解决方案是再向下封装一层Block，让Block类具体负责各种Block的生成细节。这里的rep_就是用于这个目的。
从下面的Rep的类图可以看出来
可以看到Rep中不仅接管了各种Block的生成细节，而且还会记录生成Block需要的一些统计信息。因此我们可以认为，TableBuilder只不过是对Block的一层薄薄的封装。，真正做事情的是Rep。而BuilderTable中的Add函数本质上不过是对Rep中的BlockBuilder或者FilterBlockBuilder的Add函数的调用。比如向datablock中添加数据，调用路径应该是这样的：
TableBuilder.Add -> rep_->data_block.Add
而data_block.Add会将数据写入到它的内存缓冲区中，当缓冲区的数据量达到某个阀值时，再将这个data block Flush到sstable(rep_->file)中，形成一个新的data block。当然，同时也会更新其他的block，对其他管理类的block的更新由TableBuilder协调完成，这也是TableBuilder的核心工作。
下面我们从TableBuilder.Add函数开始，一探其中奥秘。
TableBuilder.Add函数
正如前面所说，TableBuilder函数是对用户的写入接口，用户不能直接调用data Block的Add函数。
TableBuilder.Add函数的功能：向当前的data block写入一个key-value，同时更新index block，metadata block等块的内容。可以用下图直观第表示：
void TableBuilder::Add(const Slice& key, const Slice& value) { Rep* r = rep_; assert(!r->closed); if (!ok()) return; if (r->num_entries > 0) { assert(r->options.comparator->Compare(key, Slice(r->last_key)) > 0); } 这几行代码主要是确定当前的sstable是否有效，因为可能当前的sstable已经被关闭或者丢弃了，以及确定当前sstable中的最大key(last_key)比这个新加入的key小。
if (r->pending_index_entry) { assert(r->data_block.empty()); r->options.comparator->FindShortestSeparator(&r->last_key, key); std::string handle_encoding; r->pending_handle.EncodeTo(&handle_encoding); r->index_block.Add(r->last_key, Slice(handle_encoding)); r->pending_index_entry = false; } 后面的这个if主要是判断是否应该在index block中添加新的项。前面的文章讲过，每个data block对应index block中的一项。assert(r->data_block.empty())用于确定当前的data_block是新的，旧的data_block已经写入到磁盘中了，这说明现在需要为旧的，刚写入磁盘中的那个data block在index block中建一个索引项。每个索引项具有以下形式：
至于具体Block的添加函数，比如index_block->Add的实现我们后面再分析。
if (r->filter_block != NULL) { r->filter_block->AddKey(key); } 后面这个小的if语句，则是向filter block中添加一个key。filter block是一种metadata block 。filter block的含义我们后面在介绍，这里且不深究。
r->last_key.assign(key.data(), key.size()); r->num_entries++; // sst文件中总记录数 r->data_block.Add(key, value); //加入dataBlock
再往后就是向data_block中添加数据了。首先将当前添加的key设置为last_key，然后增加num_entries，这个数字是统计一共加入了多少个键值对，最后就把key-value加入到data block中。
const size_t estimated_block_size = r->data_block.CurrentSizeEstimate(); if (estimated_block_size >= r->options.block_size) { Flush(); } 最后这几行代码是检查当前的data block中包含的数据量，如果数据量大于某个阀值，则就将它写入磁盘中，形成一个真正意义上的data block。在没写如磁盘中时，它只是存在于内存中而已。
假设当前的data block已经包含了很多数据了，那就会调用Flush写入磁盘，我们看一下Flush函数的实现：
void TableBuilder::Flush() { Rep* r = rep_; assert(!r->closed); if (!ok()) return; if (r->data_block.empty()) return; assert(!r->pending_index_entry); WriteBlock(&r->data_block, &r->pending_handle); //写入到文件中，但可能还在内核缓冲中，没有真正写盘 if (ok()) { r->pending_index_entry = true; r->status = r->file->Flush(); //真正写盘了 } if (r->filter_block != NULL) { r->filter_block->StartBlock(r->offset); }} 这个函数的实现还是很简单的。首先是将data_block中的数据写入到文件中，这里需要注意的是，写入到文件中并不保证写入到磁盘中了，因为可能数据还在内核中缓冲，所以后面还要再调用r->file_Flush，这个函数将会调用fflush_unlocked，将文件的内核缓冲写入磁盘。除此之外，还要设置r->pending_index_entry，这是和Add函数中的写index bloc相对应的，因为此时一个新的data block形成，我们需要为它在index block中生成一个索引项。最后一个是处理filter block。我们且按下不提。
这样TableBuilder.Add函数基本上介绍完毕了，总的来说还是比较简单的，它的功能就是将key-value添加到sstable中，当然实际上是添加到data block中，并且负责更新index block和filter block等管理块。
TableBuilder.Finish函数
前面在介绍TableBuilder.Add函数的时候，我们看到用户通过调用Add函数向sstable中不断添加key-value，这些key-value形成一个个data block，每形成一个data block, TableBuilder都会将这个data block写盘，并同时更新内存中的index block和filter block等管理块，但是我们自始自终都没有看到除了data block之外的其他块有被写盘。那么这些管理块什么时候被写盘的呢？前面我们在介绍sstable的存储格式的时候看到，管理块在文件中的位置都是排在data block的后面，而且随着data block的不断生成管理块是需要不断更新的，因此自然可以想到应该是在不再有key-value需要被写入sstable，即sstable收尾时完成管理块的写盘工作。TableBuilder.Finish就是负责收尾工作。
Finish函数很简单，核心就是WriteBlock，将各个block写入到文件中。这里就不贴Finish的代码了。从Finish的代码结构中我们可以很清晰地看到，TableBuilder最后依次将filter block，metaindex block，index block和footer写入到sstable文件中。
总结
本篇主要介绍了leveldb是怎么将key-value键值对写入磁盘生成sstable文件的，leveldb提供的接口是TableBuilder。TableBuilder将键值对依次写入sstable，形成一个个data block，同时不断更新其他的管理型block，比如index block等。所谓通过TableBuilder的Add函数向sstable中添加数据本质上只是向data_block的缓存中添加数据，后面TableBuilder还需要将data_block的缓存中的数据真正写盘。所以写盘是以块为单位进行的。我们可以认为TableBuilder负责宏观上的sstable的存储格式，主要是以块(block)为单位，而具体的block内部是怎么存储数据的，则是由具体的Block类自己决定。当然，对TableBuilder而言，Block只不过是一个长字符串而已，TableBuilder不关心Block内部的存储细节
后面我们将看block中是怎么存储数据的，我们会看到leveldb为了提高空间效率，用到了一些技巧。