跳转至

leveldb 源码分析 7

本系列《leveldb 源码分析》共有 22 篇文章，这是第七篇。

6. SSTable 之一

SSTable 是 Leveldb 的核心之一，是表数据最终在磁盘上的物理存储。也是体量比较大的模块。

6.1 SSTable 的文件组织

作者在文档 doc/table_format.txt 中描述了表的逻辑结构，如图 6.1-1 所示。逻辑上可分为两大块，数据存储区 Data Block，以及各种 Meta 信息。

  1. 文件中的 k/v 对 是有序存储的，并且被划分到连续排列的 Data Block 里面，这些 Data Block 从文件头开始顺序存储，Data Block 的存储格式代码在 block_builder.cc 中；
  2. 紧跟在 Data Block 之后的是 Meta Block，其格式代码也在 block_builder.cc 中；Meta Block 存储的是 Filter 信息，比如 Bloom 过滤器，用于快速定位 key 是否在 data block 中。
  3. MetaIndex Block 是对 Meta Block 的索引，它只有一条记录，key 是 meta index 的名字（也就是 Filter 的名字），value 为指向 meta index 的 BlockHandle；BlockHandle 是一个结构体，成员 offset_ 是 Block 在文件中的偏移，成员 size_ 是 block 的大小；

  4. Index block 是对 Data Block 的索引，对于其中的每个记录，其 key >=Data Block 最后一条记录的 key，同时<其后 Data Block 的第一条记录的 key；value 是指向 data index 的 BlockHandle；

  5. Footer，文件的最后，大小固定，其格式如图 6.1-2 所示。

  6. 成员 metaindex_handle 指出了 meta index block 的起始位置和大小；

  7. 成员 index_handle 指出了 index block 的起始地址和大小；

这两个字段都是 BlockHandle 对象，可以理解为索引的索引，通过 Footer 可以直接定位到 metaindex 和 index block。再后面是一个 填充区和魔数（0xdb4775248b80fb57）。

6.2 Block 存储格式

6.2.1 Block 的逻辑存储

Data Block 是具体的 k/v 数据对存储区域，此外还有存储 meta 的 metaIndex Block，存储 data block 索引信息的 Index Block 等等，他们都是以 Block 的方式存储的。来看看 Block 是如何组织的。每个 Block 有三部分构成：block data, type, crc32，如图 6.2-1 所示。

类型 type 指明使用的是哪种压缩方式，当前支持 none 和 snappy 压缩。

虽然 block 有好几种，但是 Block Data 都是有序的 k/v 对，因此写入、读取 BlockData 的接口都是统一的，对于 Block Data 的管理也都是相同的。

对 Block 的写入、读取将在创建、读取 sstable 时分析，知道了格式之后，其读取写入代码都是很直观的。

由于 sstable 对数据的存储格式都是 Block，因此在分析 sstable 的读取和写入逻辑之前，我们先来分析下 Leveldb 对 Block Data 的管理。

Leveldb 对 Block Data 的管理是读写分离的，读取后的遍历查询操作由 Block 类实现，BlockData 的构建则由 BlockBuilder 类实现。

6.2.2 重启点 -restartpoint

BlockBuilder 对 key 的存储是前缀压缩的，对于有序的字符串来讲，这能极大的减少存储空间。但是却增加了查找的时间复杂度，为了兼顾查找效率，每隔 K 个 key，leveldb 就不使用前缀压缩，而是存储整个 key，这就是 重启点（restartpoint）。

在构建 Block 时，有参数 Options::block_restart_interval 定每隔几个 key 就直接存储一个重启点 key。

Block 在结尾记录所有重启点的偏移，可以二分查找指定的 key。Value 直接存储在 key 的后面，无压缩。

对于一个 k/v 对，其在 block 中的存储格式为：

  • 共享前缀长度 shared_bytes: varint32
  • 前缀之后的字符串长度 unshared_bytes: varint32
  • 值的长度 value_length: varint32
  • 前缀之后的字符串 key_delta: char[unshared_bytes]
  • 值 value: char[value_length]

对于重启点，shared_bytes= 0

Block 的结尾段格式是：

  • > restarts: uint32[num_restarts]

  • > num_restarts: uint32 // 重启点个数

元素 restarts[i]存储的是 block 的第 i 个重启点的偏移。很明显第一个 k/v 对，总是第一个重启点，也就是 restarts[0] = 0;

图 6.2-2 给出了 block 的存储示意图。

总体来看 Block 可分为 k/v 存储区和后面的重启点存储区两部分，其中 k/v 的存储格式如前面所讲，可看做 4 部分：

前缀压缩的 key 长度信息 + value 长度 + key 前缀之后的字符串 + value

最后一个 4byte 为重启点的个数。

对 Block 的存储格式了解之后，对 Block 的构建和读取代码分析就是很直观的事情了。见下面的分析。

6.3 Block 的构建与读取

6.3.1 BlockBuilder 的接口

首先从 Block 的构建开始，这就是 BlockBuilder 类，来看下 BlockBuilder 的函数接口，一共有 5 个：

void Reset(); // 重设内容，通常在Finish之后调用已构建新的block

//添加k/v，要求：Reset()之后没有调用过Finish()；Key > 任何已加入的key

void Add(const Slice& key,const Slice& value);

// 结束构建block，并返回指向block内容的指针

Slice Finish();// 返回Slice的生存周期：Builder的生存周期，or直到Reset()被调用

size_t CurrentSizeEstimate()const; // 返回正在构建block的未压缩大小—估计值

bool empty() const { returnbuffer_.empty();} // 没有entry则返回true

主要成员变量如下：

std::string            buffer_;    // block的内容

std::vector<uint32_t>  restarts_;  // 重启点-后面会分析到

int                    counter_;   // 重启后生成的entry数

std::string            last_key_;  // 记录最后添加的key

6.3.2 BlockBuilder::Add()

调用 Add 函数 向当前 Block 中新加入一个 k/v 对 {key, value}。函数处理逻辑如下：

S1 保证新加入的 key > 已加入的任何一个 key；
assert(!finished_);  

assert(counter_ <= options_->block_restart_interval);

assert(buffer_.empty() || options_->comparator->Compare(key,last_key_piece) > 0);
S2 如果计数器 counter < opions->block_restart_interval，则使用前缀算法压缩 key，否则就把 key 作为一个重启点，无压缩存储；
Slice last_key_piece(last_key_);

if (counter_ < options_->block_restart_interval) { //前缀压缩

    // 计算key与last_key_的公共前缀

    const size_t min_length= std::min(last_key_piece.size(), key.size());

    while ((shared < min_length)&& (last_key_piece[shared] == key[shared])) {

    shared++;

} else { // 新的重启点

    restarts_.push_back(buffer_.size());

    counter_ = 0;

}



Slice last_key_piece(last_key_);

if (counter_ < options_->block_restart_interval) { //前缀压缩

    // 计算key与last_key_的公共前缀

    const size_t min_length= std::min(last_key_piece.size(), key.size());

    while ((shared < min_length)&& (last_key_piece[shared] == key[shared])) {

    shared++;

} else { // 新的重启点

    restarts_.push_back(buffer_.size());

    counter_ = 0;

}
S3 根据上面的数据格式存储 k/v 对，追加到 buffer 中，并更新 block 状态。
const size_t non_shared = key.size() - shared; // key前缀之后的字符串长度

// append"<shared><non_shared><value_size>" 到buffer_  

PutVarint32(&buffer_, shared); 

PutVarint32(&buffer_, non_shared); 

PutVarint32(&buffer_, value.size());  

// 其后是前缀之后的字符串 + value 

buffer_.append(key.data() + shared, non_shared);  

buffer_.append(value.data(), value.size());  

// 更新状态 ，last_key_ = key及计数器counter_

last_key_.resize(shared);   // 连一个string的赋值都要照顾到，使内存copy最小化

last_key_.append(key.data() + shared, non_shared); 

assert(Slice(last_key_) == key);  

counter_++;

6.3.3 BlockBuilder::Finish()

调用该函数完成 Block 的构建，很简单，压入重启点信息，并返回 buffer_，设置结束标记 finished_:

for (size_t i = 0; i < restarts_.size(); i++) {  // 重启点  

      PutFixed32(&buffer_, restarts_[i]);  

}  

PutFixed32(&buffer_, restarts_.size());    // 重启点数量  

finished_ = true;  

return Slice(buffer_);

6.3.4 BlockBuilder::Reset() & 大小

还有 Reset 和 CurrentSizeEstimate 两个函数，Reset 复位函数，清空各个信息；函数 CurrentSizeEstimate 返回 block 的预计大小，从函数实现来看，应该在调用 Finish 之前调用该函数。

void BlockBuilder::Reset() {  

   buffer_.clear();  restarts_.clear();  last_key_.clear();  

   restarts_.push_back(0);       // 第一个重启点位置总是 0  

   counter_ = 0;  

   finished_ = false;  

}  



size_t BlockBuilder::CurrentSizeEstimate () const {  

   // buffer大小 +重启点数组长度 + 重启点长度(uint32)

  return (buffer_.size() +  restarts_.size() * sizeof(uint32_t) + sizeof(uint32_t)); 

}

Block 的构建就这些内容了，下面开始分析 Block 的读取，就是类 Block。

6.3.5 Block 类接口

对 Block 的读取 是由类 Block 完成的，先来看看其函数接口和关键成员变量。

Block 只有两个函数接口，通过 Iterator 对象，调用者就可以遍历访问 Block 的存储的 k/v 对了；以及几个成员变量，如下：

size_t size() const { returnsize_; }

Iterator* NewIterator(constComparator* comparator);



const char* data_;        // block数据指针

size_t size_;             // block数据大小

uint32_t restart_offset_; // 重启点数组在data_中的偏移

bool owned_;              //data_[]是否是Block拥有的

6.3.6 Block 初始化

Block 的构造函数接受一个 BlockContents 对象 contents 初始化，BlockContents 是一个有 3 个成员的结构体。

  • >data = Slice();
  • >cachable = false; // 无 cache
  • >heap_allocated = false; // 非 heap 分配

根据 contents 为成员赋值

data_ = contents.data.data(), size_ =contents.data.size(),owned_ = contents.heap_allocated;

然后 从 data 中解析出重启点数组，如果数据太小，或者重启点计算出错，就设置 size_=0，表明该 block data 解析失败。

if (size_ < sizeof(uint32_t)){

  size_ = 0;  // 出错了

} else {

  restart_offset_ = size_ - (1 +NumRestarts()) * sizeof(uint32_t);

  if (restart_offset_ > size_- sizeof(uint32_t)) size_ = 0;

}

NumRestarts() 函数 就是从最后的 uint32 解析出重启点的个数，并返回:

return DecodeFixed32(data_ +size_ - sizeof(uint32_t))

6.3.7 Block::Iter

这是一个用以遍历 Block 内部数据的内部类，它继承了 Iterator 接口。函数 NewIterator 返回 Block::Iter 对象：

return new Iter(cmp, data_,restart_offset_, num_restarts);

下面我们就 分析 Iter 的实现。

主要成员变量有：

const Comparator* constcomparator_; // key比较器

const char* const data_;      // block内容

uint32_t const restarts_;     // 重启点(uint32数组)在data中的偏移

uint32_t const num_restarts_; // 重启点个数

uint32_t current_; // 当前entry在data中的偏移.  >= restarts_表明非法

uint32_t restart_index_;  // current_所在的重启点的index

下面来看看对 Iterator 接口的实现，简单函数略过。

首先是 Next() 函数，直接调用 private 函数 ParseNextKey() 跳到下一个 k/v 对，函数实现如下：

S1 跳到下一个 entry，其位置紧邻在当前 value_ 之后。如果已经是最后一个 entry 了，返回 false，标记 current_ 为 invalid。

current_ = NextEntryOffset(); // (value_.data() + value_.size()) - data_

const char* p = data_ +current_;

const char* limit = data_ +restarts_; // Restarts come right after data

if (p >= limit) { // entry到头了，标记为invalid.

  current_ = restarts_;

  restart_index_ =num_restarts_;

  return false;

}

S2 解析出 entry，解析出错则设置错误状态，记录错误并返回 false。解析成功则根据信息组成 key 和 value，并更新重启点 index。

uint32_t shared, non_shared,value_length;

p = DecodeEntry(p, limit,&shared, &non_shared, &value_length);

if (p == NULL || key_.size()< shared) {

  CorruptionError();

  return false;

} else { // 成功

  key_.resize(shared);

  key_.append(p, non_shared);

  value_ = Slice(p +non_shared, value_length);

  while (restart_index_ + 1< num_restarts_ && GetRestartPoint(restart_index_ + 1) < current_) {

       ++restart_index_; //更新重启点index

  }

  return true;

}
  • 函数 DecodeEntry 从 字符串 [p, limit) 解析出 key 的前缀长度、key 前缀之后的字符串长度和 value 的长度这三个 vint32 值，代码很简单。
  • 函数 CorruptionError 将 current_ 和 restart_index_ 都设置为 invalid 状态，并在 status 中设置错误状态。
  • 函数 GetRestartPoint 从 data 中读取指定 restart index 的偏移值 restart[index]，并返回：
DecodeFixed32(data_ + restarts_ +index * sizeof(uint32_t);

接下来看看 Prev 函数，Previous 操作分为两步：首先回到 current_ 之前的重启点，然后再向后直到 current_，实现如下：

S1 首先向前回跳到在 current_ 前面的那个重启点，并定位到重启点的 k/v 对开始位置。

const uint32_t original =current_;

while (GetRestartPoint(restart_index_)>= original) {
        // 到第一个entry了，标记invalid状态
        if (restart_index_ == 0) { 

            current_ = restarts_;

            restart_index_ =num_restarts_;

            return;

      }

      restart_index_--;

}
 //根据restart index定位到重启点的k/v对

SeekToRestartPoint(restart_index_);

S2 第二步，从重启点位置开始向后遍历，直到遇到 original 前面的那个 k/v 对。

do {} while (ParseNextKey() &&NextEntryOffset() < original);

说说上面遇到的 SeekToRestartPoint 函数，它只是设置了几个有限的状态，其它值将在函数 ParseNextKey() 中设置。感觉这有点 tricky，这里的 value_ 并不是 k/v 对的 value，而只是一个指向 k/v 对起始位置的 0 长度指针，这样后面的 ParseNextKey 函数将会取出重启点的 k/v 值。

void SeekToRestartPoint(uint32_tindex) {

  key_.clear();

  restart_index_ = index;

  // ParseNextKey()会设置current_;

  //ParseNextKey()从value_结尾开始, 因此需要相应的设置value_

  uint32_t offset =GetRestartPoint(index);

  value_ = Slice(data_ + offset,0); // value长度设置为0，字符串指针是data_+offset

}

SeekToFirst/Last，这两个函数都很简单，借助于前面的 SeekToResartPoint 函数就可以完成。

virtual void SeekToFirst() {

  SeekToRestartPoint(0);

  ParseNextKey();

}



virtual void SeekToLast() {

  SeekToRestartPoint(num_restarts_ - 1);

  while (ParseNextKey()&& NextEntryOffset() < restarts_) {} //Keep skipping

}

最后一个 Seek 函数，跳到指定的 target(Slice)，函数逻辑如下：

S1 二分查找，找到 key < target 的最后一个重启点，典型的二分查找算法，代码就不再贴了。
S2 找到后，跳转到重启点，其索引由 left 指定，这是前面二分查找到的结果。如前面所分析的，value_ 指向重启点的地址，而 size_ 指定为 0，这样 ParseNextKey 函数将会取出重启点的 k/v 值。
SeekToRestartPoint(left);
S3 自重启点线性向下，直到遇到 key>= target 的 k/v 对。
while (true) {

   if (!ParseNextKey()) return;

   if (Compare(key_, target)>= 0) return;

}

上面就是 Block::Iter 的全部实现逻辑，这样 Block 的创建和读取遍历都已经分析完毕。