memtable是k-v数据在内存中的存储对象，当内存中的memtable达到一定的大小时，就需要dump到磁盘中，而sstable就是数据在磁盘中的存储对象，今天看看leveldb的table对象。有关部分代码在leveldb源码文件下的table文件夹内。
其实有关sstable部分的源码剖析不好讲，最主要的是要弄清楚sstable的存储格式，在这里我就提几个理解sstable结构的要点，后面从代码中理解sstable结构：
- 因为是memtable dump到磁盘的，所以sstable的记录是有序的。
- 同Log文件一样，物理结构也是划分为固定大小的存储块
在table文件夹下：
- format：格式定义
- block/block_builder：block相关的操作
- table/table_builder：table相关的操作
- iterator_wrapper：优化的迭代器
介绍完sstable，下面来看源码，首先锁定block：
block结构
成员变量：
const char* data_;//包含了entrys、重启点数组和写在最后4bytes的重启点个数
size_t size_;//大小
uint32_t restart_offset_; // Offset in data_ of restart array
bool owned_;//block是否存有数据的标志位,析构函数delete data时会判断
这里有一个关键点：重启点
首先，你要了解，一份KV数据作为block内的一个entry（条目），考虑节省空间，leveldb对key的存储进行前缀压缩，每个entry中会记录key与前一个key前缀相同的字节（shared_bytes）和自己独有的字节（unshared_bytes），读取时，对block进行遍历，每一个key根据前一个key可以构造出来，entry存储形式如下：
然后，如果完全按照上面所述的处理，对每个key的查找，都要从block的头开始遍历，所以进一步细化粒度，对 block 内的前缀压缩分区段进行。 若干个 key 做前缀压缩之后，就重新开始下一轮。restart_offset_ 就是记录重启点信息在block的偏移量。Block::NumRestarts()返回重启点的个数。所以整个block的格式应该是（trailer先不管，放置压缩标志位和CRC校验）：
block实现
- DecodeEntry函数
static inline const char* DecodeEntry(const char* p, const char* limit,
uint32_t* shared,
uint32_t* non_shared,
uint32_t* value_length) {
if (limit - p < ) return NULL;
*shared = reinterpret_cast<const unsigned char*>(p)[];
*non_shared = reinterpret_cast<const unsigned char*>(p)[];
*value_length = reinterpret_cast<const unsigned char*>(p)[];
if ((*shared | *non_shared | *value_length) < ) {
// Fast path: all three values are encoded in one byte each
p += ;
} else {
if ((p = GetVarint32Ptr(p, limit, shared)) == NULL) return NULL;
if ((p = GetVarint32Ptr(p, limit, non_shared)) == NULL) return NULL;
if ((p = GetVarint32Ptr(p, limit, value_length)) == NULL) return NULL;
}
if (static_cast<uint32_t>(limit - p) < (*non_shared + *value_length)) {
return NULL;
}
return p;
}
如上所说，每一个entry写入block是先写入key的共享长度（shared），非共享长度（non_shared）和value长度（value _length），而对于表示长度的整型变量，前面说过leveldb是编码成varint存储的，所以首先要对这三个数解码。函数一开始假设这三个长度两都很小，编码成varint都只有一个字节，所以取出三个字节，然后通过
if ((*shared | *non_shared | *value_length) < )
判断三个数的最高位是否有置为1，因为在varint编码中，最高位为1代表后面的字节也属于这个数，而如果有一个varint的长度大于1，自然假设也就不成立了。只好一一解码：
if ((p = GetVarint32Ptr(p, limit, shared)) == NULL) return NULL;
if ((p = GetVarint32Ptr(p, limit, non_shared)) == NULL) return NULL;
if ((p = GetVarint32Ptr(p, limit, value_length)) == NULL) return NULL;
最后返回p代表此entry的key-value值首地址。GetVarint32Ptr()函数可见我前面关于varint的介绍，也看参考coding.cc文件。
-
迭代器类
为了实现在block内查找target entry，block定义了一个Iter的嵌套类，继承自虚基类Iterator
成员变量：
private:
const Comparator* const comparator_;//比较器
const char* const data_; // 数据起始点
uint32_t const restarts_; // 重启点数组在block的偏移量
uint32_t const num_restarts_; // 重启点个数
// current_ is offset in data_ of current entry. >= restarts_ if !Valid
uint32_t current_;//迭代器指向block内的数据偏移量，真实位置data_ + current_
uint32_t restart_index_; // 迭代器指向的数据所在重启区的索引，该区的重启点（起点）位置对应data_ + DecodeFixed32(data_ + restarts_ + restart_index_* sizeof(uint32_t))，如你所见，迭代器的大部分操作都是这样的底层字节移动，没有用易于明白的数组索引来实现
std::string key_;
Slice value_;//目前指向的key-value值，不包括前面的长度信息
Status status_;
迭代器的操作，就说一个seek
virtual void Seek(const Slice& target) {
// Binary search in restart array to find the last restart point
// with a key < target
uint32_t left = ;
uint32_t right = num_restarts_ - ;
while (left < right) {
uint32_t mid = (left + right + ) / ;
uint32_t region_offset = GetRestartPoint(mid);
uint32_t shared, non_shared, value_length;
const char* key_ptr = DecodeEntry(data_ + region_offset,
data_ + restarts_,
&shared, &non_shared, &value_length);
if (key_ptr == NULL || (shared != )) {
CorruptionError();
return;
}
Slice mid_key(key_ptr, non_shared);
if (Compare(mid_key, target) < ) {
// Key at "mid" is smaller than "target". Therefore all
// blocks before "mid" are uninteresting.
left = mid;
} else {
// Key at "mid" is >= "target". Therefore all blocks at or
// after "mid" are uninteresting.
right = mid - ;
}
}
这里面用的是二分查找法，在重启点数组中不停地定位到中间重启点
uint32_t mid = (left + right + ) / ;
uint32_t region_offset = GetRestartPoint(mid);
用上文的DecodeEntry函数出mid重启点的key-value值指针，然后和目标值target比较大小，更新左右点left，right。直到left < right结束循环。定位了target所在的重启区，然后深入定位target
SeekToRestartPoint(left);
while (true) {
if (!ParseNextKey()) {
return;
}
if (Compare(key_, target) >= ) {
return;
}
}
当current_的位置超过了重启点数组的位置，说明此block无所找的entry。
嗯，好了，关于sstable的block就写到这里，个人感觉block的实现代码还是值得一看的，可以去看看作者为了平衡查找速度和block大小设计出的block结构，还有迭代器的实现，作者对于每个变量的定位相当精彩，例如：
inline uint32_t NextEntryOffset() const {
return (value_.data() + value_.size()) - data_;
}
uint32_t GetRestartPoint(uint32_t index) {
assert(index < num_restarts_);
return DecodeFixed32(data_ + restarts_ + index * sizeof(uint32_t));
}
如果本博客有关内容存在偏差，欢迎大家指正。