levelDB源码剖析(8)--Block和SSTable的构建

Block和SSTable的构建

我们在之前提到了SSTable和内部的各类Block的结构，也初步分析了其在源码中的类级别的组织结构，但是我们也能注意到类结构和实际写入文件的结构是存在明显差异的，所以我们现在就需要进一步了解levelDB是如何构建这些Block与SSTable的。

源码位置与说明:

table/block_builder.cc table/block_builder.h : Block构建相关
include/leveldb/table_builder.h table/table_builder.cc : table构建相关
include/leveldb/table.h table/table.cc : 读取一个Table的内容，产生迭代器，或者根据一个键读取一个值

Block的构建--BlockBuilder

我们之前看到的Block的类其实只有存储的数据类型、迭代器和查询相关的东西，那么Block获取到的数据是哪里来的呢？也就是哪个类来负责把一个一个kv插入到data_中呢？其实这个类就是BlockBuilder。

class BlockBuilder
{
private:
    const Options *options_;         // Options选项
    std::string buffer_;             // 缓冲区，是存放kv的位置
    std::vector<uint32_t> restarts_; // Restart points
    int counter_;                    // 将此类重启后的元素数目
    bool finished_;                  // 是否构建完成
    std::string last_key_;           //上一个key

public:
    // 构造析构函数相关
    explicit BlockBuilder(const Options *options);
    BlockBuilder(const BlockBuilder &) = delete;
    BlockBuilder &operator=(const BlockBuilder &) = delete;

    // 重启此类，其实就是开启新的构建，因为每个Block内的数据大小是有限制的
    // 但是不需要为每个Block都创建一个BlockBuilder
    void Reset();

    // 把key-value加入，要求构建过程没有结束且key比之前加入的key要大
    void Add(const Slice &key, const Slice &value);

    // 结束此次构建，返回一个构建结果，即data_，包含数据区和偏执区两部分
    // 返回的字符串一直到下次Finish()被调用前都有效
    Slice Finish();

    // 返回构建的Block大小
    size_t CurrentSizeEstimate() const;

    // 当前构建是否为空
    bool empty() const { return buffer_.empty(); }
};

我们可以看到一个BlockBuilder的作用其实就是不断把key-value添加到缓冲区中，然后在完成构建时返回这个缓冲区。由于没有必须要为每个Block都生成一个BlockBuilder类，所以BlockBuilder类是可以复用的。

下面我们来看一下具体的实现。

BlockBuilder::BlockBuilder(const Options *options)
    : options_(options), restarts_(), counter_(0), finished_(false)
{
    assert(options->block_restart_interval >= 1);
    restarts_.push_back(0); // 第一个重启点就是0偏置位置
}

// 重启BlockBuilder类
void BlockBuilder::Reset()
{
    buffer_.clear();
    restarts_.clear();
    restarts_.push_back(0); // 第一个重启点就是0偏置位置
    counter_ = 0;
    finished_ = false;
    last_key_.clear();
}

// 返回当前的构建大小，包含三部分组成：data_[] restart_[] restart_num
size_t BlockBuilder::CurrentSizeEstimate() const
{
    return (buffer_.size() +                      // Raw data buffer
            restarts_.size() * sizeof(uint32_t) + // Restart array
            sizeof(uint32_t));                    // Restart array length
}

// 结束当次构建
Slice BlockBuilder::Finish()
{
    // 需要把所有的重启点插入到数据后面
    for (size_t i = 0; i < restarts_.size(); i++)
    {
        PutFixed32(&buffer_, restarts_[i]);
    }
    PutFixed32(&buffer_, restarts_.size());
    finished_ = true;
    return Slice(buffer_);
}

// 插入key-value
void BlockBuilder::Add(const Slice &key, const Slice &value)
{
    Slice last_key_piece(last_key_); // 获取上一个key，需要保证当前key大于上一个key
    assert(!finished_);
    assert(counter_ <= options_->block_restart_interval);
    assert(buffer_.empty() // No values yet?
           || options_->comparator->Compare(key, last_key_piece) > 0);
    size_t shared = 0;

    // 计算出与上一个key之间的前缀长度
    if (counter_ < options_->block_restart_interval)
    {
        // See how much sharing to do with previous string
        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
    {
        // 如果某个重启点后共享key数目到达预定值就新建重启点
        restarts_.push_back(buffer_.size());
        counter_ = 0;
    }
    const size_t non_shared = key.size() - shared; // 非共享key长度

    // 下面就是按照key的格式插入到data_中
    // Add "<shared><non_shared><value_size>" to buffer_
    PutVarint32(&buffer_, shared);
    PutVarint32(&buffer_, non_shared);
    PutVarint32(&buffer_, value.size());

    // Add string delta to buffer_ followed by value
    buffer_.append(key.data() + shared, non_shared);
    buffer_.append(value.data(), value.size());

    // 更新类内数据
    last_key_.resize(shared);
    last_key_.append(key.data() + shared, non_shared);
    assert(Slice(last_key_) == key);
    counter_++;
}

我们可以看到，BlockBuilder还是很简单的，主要就是创建重启点、插入key-value，不过需要注意的是这个插入key-value的时候需要保证keys是有序的。

Table类

在之前我们讲述SSTable的时候，我们其实是没有提到Table这个类的，因为前面的内容有点多，下面我们就来具体看一下这个类。

class LEVELDB_EXPORT Table
{
private:
    friend class TableCache; // 友元缓存类
    struct Rep;              // 这个是一个结构体，存放xxxhandler、Block之类的

    // 把xxxindex Block中的内容给提取出来
    static Iterator *BlockReader(void *, const ReadOptions &, const Slice &);

    // 关闭构造函数
    explicit Table(Rep *rep) : rep_(rep) {}

    // Calls (*handle_result)(arg, ...) with the entry found after a call
    // to Seek(key).  May not make such a call if filter policy says
    // that key is not present.
    Status InternalGet(const ReadOptions &, const Slice &key, void *arg,
                       void (*handle_result)(void *arg, const Slice &k,
                                             const Slice &v));

    // 读取Meta Block和Filter Block
    void ReadMeta(const Footer &footer);
    void ReadFilter(const Slice &filter_handle_value);

    Rep *const rep_;

public:
    // Attempt to open the table that is stored in bytes [0..file_size)
    // of "file", and read the metadata entries necessary to allow
    // retrieving data from the table.
    //
    // If successful, returns ok and sets "*table" to the newly opened
    // table.  The client should delete "*table" when no longer needed.
    // If there was an error while initializing the table, sets "*table"
    // to nullptr and returns a non-ok status.  Does not take ownership of
    // "*source", but the client must ensure that "source" remains live
    // for the duration of the returned table's lifetime.
    //
    // *file must remain live while this Table is in use.

    // 打开一个可以随机读取的SSTable文件，并返回从这个文件中读取的Table类
    // RandomAccessFile可以看成是一个随机读写迭代器
    // 这里的原文我保留下来，写的很详细
    static Status Open(const Options &options, RandomAccessFile *file,
                       uint64_t file_size, Table **table);

    // 构造析构函数相关
    Table(const Table &) = delete;
    Table &operator=(const Table &) = delete;
    ~Table();

    // 返回一个指向Table内的数据的迭代器，初始生成的迭代器不可用，需要手动初始化
    Iterator *NewIterator(const ReadOptions &) const;

    // 用于估算key值所在记录的偏移，目前作用不是很清楚
    uint64_t ApproximateOffsetOf(const Slice &key) const;
};

头文件中定义了缓存用的友元类、迭代器这些，说明Table类其实也没有定义怎么构建SSTable，而主要的目的是从文件中读取一个SSTable出来。

由于这其中涉及到了迭代器和缓存类，所以具体的实现我们就先略过，等到后面再详细看。

Table的构建--TableBuilder

Block的构建是通过BlockBuilder类来完成的，而Table的构建则是通过TableBuilder类来完成的。我们先来看一下其头文件

class LEVELDB_EXPORT TableBuilder
{
private:
    // 返回构建器状态
    bool ok() const { return status().ok(); }
    // 写入Block的封装函数，对WriteRawBlock的封装
    void WriteBlock(BlockBuilder *block, BlockHandle *handle);
    // 将Block实际写入文件的函数，包含压缩类型
    void WriteRawBlock(const Slice &data, CompressionType, BlockHandle *handle);

    struct Rep; // 这个Rep与Table类中的Rep不一样，其声明位置是不同的
    Rep *rep_;

public:
    // 创建一个Builder类来完成文件的写入
    TableBuilder(const Options &options, WritableFile *file);
    TableBuilder(const TableBuilder &) = delete;
    TableBuilder &operator=(const TableBuilder &) = delete;
    ~TableBuilder();

    // 改变Builder类的Options，只有部分选项可以被更改
    Status ChangeOptions(const Options &options);

    // 添加一个key-value需要保证key比之前的都大
    void Add(const Slice &key, const Slice &value);

    // 这个函数的作用是把缓存区中的key-value持久化到磁盘中
    void Flush();

    // 返回构建器的状态
    Status status() const;

    // 结束当前构建，和BlockTable中一样
    Status Finish();

    // 抛弃掉当前构建器
    void Abandon();

    // Add的次数
    uint64_t NumEntries() const;

    // 返回构建的文件大小
    uint64_t FileSize() const;
};

我们可以看到TableBuilder的头文件中定义了将Key写入文件的部分。以及，虽然这个类中也存在一个类型为Req的东西，但是和Table类中的不是同一个东西，我们看一下其定义。

struct TableBuilder::Rep
{
    Rep(const Options &opt, WritableFile *f)
        : options(opt),
          index_block_options(opt),
          file(f),
          offset(0),
          data_block(&options),
          index_block(&index_block_options),
          num_entries(0),
          closed(false),
          filter_block(opt.filter_policy == nullptr
                           ? nullptr
                           : new FilterBlockBuilder(opt.filter_policy)),
          pending_index_entry(false)
    {
        index_block_options.block_restart_interval = 1;
    }

    Options options;                  // 选项
    Options index_block_options;      // index_block的选项
    WritableFile *file;               // 写入的文件
    uint64_t offset;                  // 偏移值
    Status status;                    // 状态
    BlockBuilder data_block;          // data_block构建器
    BlockBuilder index_block;         // index_block构建器
    std::string last_key;             // 上一个写入的key
    int64_t num_entries;              // 写入的key次数
    bool closed;                      // Table构建器是否关闭
    FilterBlockBuilder *filter_block; // 过滤器block

    // We do not emit the index entry for a block until we have seen the
    // first key for the next data block.  This allows us to use shorter
    // keys in the index block.  For example, consider a block boundary
    // between the keys "the quick brown fox" and "the who".  We can use
    // "the r" as the key for the index block entry since it is >= all
    // entries in the first block and < all entries in subsequent
    // blocks.
    // 这里的原注释可以好好看一下
    // Invariant: r->pending_index_entry is true only if data_block is empty.
    bool pending_index_entry;   // 当data_block为空时是true否则为false
    BlockHandle pending_handle; // 是一个为index_block添加数据时使用的handler

    std::string compressed_output; // 压缩输出
};

这个结构体中定义了table中包含的各个部分，这些部分没有直接在Table类中定义，是因为那样就会让Table类十分冗长，使用类内的一个结构体会清晰很多。实际上，TableBuilder类在进行构建的时候也是直接处理这个结构体的。

下面我们来看一下TableBuiler类的具体实现。

// 构造函数
TableBuilder::TableBuilder(const Options &options, WritableFile *file)
    : rep_(new Rep(options, file))
{
    if (rep_->filter_block != nullptr)
    {
        rep_->filter_block->StartBlock(0);
    }
}

// 析构函数
TableBuilder::~TableBuilder()
{
    assert(rep_->closed); // Catch errors where caller forgot to call Finish()
    delete rep_->filter_block;
    delete rep_;
}

// 改变TableBudiler类的选项
Status TableBuilder::ChangeOptions(const Options &options)
{
    if (options.comparator != rep_->options.comparator)
    {
        return Status::InvalidArgument("changing comparator while building table");
    }

    rep_->options = options;
    rep_->index_block_options = options;
    rep_->index_block_options.block_restart_interval = 1;
    return Status::OK();
}

// 添加一个key-value
void TableBuilder::Add(const Slice &key, const Slice &value)
{
    Rep *r = rep_;
    assert(!r->closed);
    if (!ok())
        return;

    // 如果之前有添加过，则需要保证现在的key比之前的key要大
    if (r->num_entries > 0)
    {
        assert(r->options.comparator->Compare(key, Slice(r->last_key)) > 0);
    }

    // pending_index_entry当data_block为空时是true，其实就是标识出重启点
    // 目的是把block加入index中
    if (r->pending_index_entry)
    {
        assert(r->data_block.empty());
        // 压缩一下key长度，这个压缩与重启点的压缩其实不冲突
        r->options.comparator->FindShortestSeparator(&r->last_key, key);
        std::string handle_encoding;
        r->pending_handle.EncodeTo(&handle_encoding);
        // 把block中的起始位置和偏移编码后存入index，因为每个重启点处相当于datablock起点
        r->index_block.Add(r->last_key, Slice(handle_encoding));
        r->pending_index_entry = false;
    }

    if (r->filter_block != nullptr)
    {
        r->filter_block->AddKey(key);
    }

    // 更新一下参数并把key-value加入到data_block中
    r->last_key.assign(key.data(), key.size());
    r->num_entries++;
    r->data_block.Add(key, value);

    // 如果目前缓冲区数据长度比较长就持久化到文件
    const size_t estimated_block_size = r->data_block.CurrentSizeEstimate();
    if (estimated_block_size >= r->options.block_size)
    {
        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); // 调用TableBuilder写入文件的函数
    if (ok())
    {
        r->pending_index_entry = true;
        r->status = r->file->Flush(); // 调用文件的持久化函数
    }
    if (r->filter_block != nullptr)
    {
        r->filter_block->StartBlock(r->offset); // 布隆过滤器
    }
}

// 把Table中的Block写入文件，只是这个函数是一层封装，内部只执行了压缩步骤
void TableBuilder::WriteBlock(BlockBuilder *block, BlockHandle *handle)
{
    // 写入文件的格式block_data, type, crc
    assert(ok());
    Rep *r = rep_;
    Slice raw = block->Finish(); // 拿出Block的数据

    Slice block_contents;
    CompressionType type = r->options.compression; // 压缩类型
    switch (type)                                  // 根据压缩类型来执行压缩
    {
    case kNoCompression: // 不压缩
        block_contents = raw;
        break;

    case kSnappyCompression: // Snappy压缩
    {
        std::string *compressed = &r->compressed_output;
        if (port::Snappy_Compress(raw.data(), raw.size(), compressed) &&
            compressed->size() < raw.size() - (raw.size() / 8u))
        {
            block_contents = *compressed;
        }
        else
        {
            // Snappy not supported, or compressed less than 12.5%, so just
            // store uncompressed form
            block_contents = raw;
            type = kNoCompression;
        }
        break;
    }
    }
    // 调用WriteRawBlock来真正写入文件中
    WriteRawBlock(block_contents, type, handle);
    r->compressed_output.clear();
    block->Reset();
}

// 写入文件的函数
void TableBuilder::WriteRawBlock(const Slice &block_contents,
                                 CompressionType type, BlockHandle *handle)
{
    Rep *r = rep_;
    handle->set_offset(r->offset);
    handle->set_size(block_contents.size());
    r->status = r->file->Append(block_contents); // 调用文件写入的函数
    if (r->status.ok())
    {
        char trailer[kBlockTrailerSize]; // block的尾部由压缩类型与crc组成
        trailer[0] = type;
        uint32_t crc = crc32c::Value(block_contents.data(), block_contents.size());
        crc = crc32c::Extend(crc, trailer, 1); // Extend crc to cover block type
        EncodeFixed32(trailer + 1, crc32c::Mask(crc));
        // 然后把尾部添加进文件中
        r->status = r->file->Append(Slice(trailer, kBlockTrailerSize));
        if (r->status.ok())
        {
            r->offset += block_contents.size() + kBlockTrailerSize;
        }
    }
}

// 返回状态
Status TableBuilder::status() const { return rep_->status; }

// 结束构建
Status TableBuilder::Finish()
{
    Rep *r = rep_;
    Flush();
    assert(!r->closed);
    r->closed = true;

    BlockHandle filter_block_handle, metaindex_block_handle, index_block_handle;

    // 写入filter_block
    if (ok() && r->filter_block != nullptr)
    {
        WriteRawBlock(r->filter_block->Finish(), kNoCompression,
                      &filter_block_handle);
    }

    // 写入metaindex_block
    if (ok())
    {
        BlockBuilder meta_index_block(&r->options);
        if (r->filter_block != nullptr)
        {
            std::string key = "filter.";
            key.append(r->options.filter_policy->Name());
            std::string handle_encoding;
            filter_block_handle.EncodeTo(&handle_encoding);
            meta_index_block.Add(key, handle_encoding);
        }
        WriteBlock(&meta_index_block, &metaindex_block_handle);
    }

    // 写入index_block
    if (ok())
    {
        if (r->pending_index_entry)
        {
            r->options.comparator->FindShortSuccessor(&r->last_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;
        }
        WriteBlock(&r->index_block, &index_block_handle);
    }

    // 写入table的Footer
    if (ok())
    {
        Footer footer;
        footer.set_metaindex_handle(metaindex_block_handle);
        footer.set_index_handle(index_block_handle);
        std::string footer_encoding;
        footer.EncodeTo(&footer_encoding);
        r->status = r->file->Append(footer_encoding);
        if (r->status.ok())
        {
            r->offset += footer_encoding.size();
        }
    }
    return r->status;
}

// 放弃构建
void TableBuilder::Abandon()
{
    Rep *r = rep_;
    assert(!r->closed);
    r->closed = true;
}

// Add的次数
uint64_t TableBuilder::NumEntries() const { return rep_->num_entries; }

// 文件的大小
uint64_t TableBuilder::FileSize() const { return rep_->offset; }

通过这个TableBuilder类，我们就可以很清晰地看出一个Table是怎么构建的了。下面给出构建一个Table的流程。

• TableBuilder类首先在类内创建出各类BlockBuilder，包括dataBlock，metadataBlock，filterBlock等等。
• 然后当每次需要插入一个key时就会调用TableBuilder的add方法，这个方法会自动负责处理index_block、重启点、filter_block以及对每个key进行长度压缩(这个压缩不是共享key，而是调用comparator中的FindShortestSeparator方法)。另外TableBuilder类插入key-value会首先写入内存中，只有当内存部分的大小超过一定长度才会写持久化到硬盘。
• Flush函数负责将目前的数据区追加写到磁盘中，它会调用WriteBlock函数，注意Flush不会把非data_block的block持久化。
• WriteBlock函数是对WriteRawBlock函数的封装。它主要是处理了数据压缩的部分，然后把压缩后的数据和压缩类型以及数据的crc校验码传递给WriteRawBlock函数。
• WriteRawBlock函数是真正写入数据的函数，每个Block都由数据区和偏置区、压缩类型以及crc校验组成。
• 当一个table完成构建时就会调用finish函数，这个函数会负责追加写filter_block、metaindex_block、index_block和Footer。其中写入每个Block时会调用对应handler的encode函数来将每个block编码成字符串。

我们继续来审视一下SSTable和Block的结构图，这样我们会更加清楚其结构。

总结

不得不说，Block的统一的设计还是非常的巧妙，所有的Block结构都是一样的，只是提供了统一的接口(Add)，内部设计包含了key的前缀压缩、偏置区、重启点等等优化设计。而filterBlock和IndexBlock等等也是包含这些偏置区和重启点的，可能会感觉有些奇怪，因为这些存储的都是过滤器或者是索引。但是由于我们不需要关心这些内部的细节，所以可以看成是数据结构内部优化即可。