LevelDB源码分析-sstable的Block
sstable中的Block（table/block.h table/block.cc table/block_builder.h table/block_builder.cc） sstable中的block由Block类封装并由BlockBuilder类构建。 block的结构为： entry1 | entry2 | ... | restarts(uint32 * num_of_restarts) | num_of_restarts(uint32) | trailer 其中entry格式为： shared_bytes(varint32) | unshared_bytes(varint32) | value_bytes(varint32) | unshared_key_data(unshared_bytes) | value_data(value_bytes) shared_bytes为这个entry中的key与前一个entry的key共享的字节数，entry的key在存储时只存储不共享的部分，即采用前缀压缩的形式，并且前缀压缩是分组进行的，以避免所有查找都需要从头开始的情况。而每个组的起始entry的位置（offset）存储在restarts中，每个为uint32，数量为num_of_restarts。 trailer的格式为： type(char) | crc(uint32) type为block的压缩方式，crc为循环冗余校验码。 Block类 Block类对sstable的block中的数据进行封装，并提供了一个迭代器作为接口。Block类的声明为： class Block { public: // ... private: // ... const char *data_; size_t size_; uint32_t restart_offset_; // Offset in data_ of restart array bool owned_; // Block owns data_[] // ... class Iter; }; 其中成员变量data_为指向block中数据的指针，size_为block中数据的大小，restart_offset_为block中restarts部分数据的起始位置的offset，owned标记block是否包含data_。 而LevelDB实际上为Block类封装了一个Iter类，对Block的遍历操作需要通过Iter类提供的接口函数进行。 class Block::Iter : public Iterator { private: const Comparator *const comparator_; const char *const data_; // underlying block contents uint32_t const restarts_; // Offset of restart array (list of fixed32) uint32_t const num_restarts_; // Number of uint32_t entries in restart array // current_ is offset in data_ of current entry. >= restarts_ if !Valid uint32_t current_; uint32_t restart_index_; // Index of restart block in which current_ falls std::string key_; Slice value_; Status status_; // ... public: // ... virtual bool Valid() const { return current_ < restarts_; } virtual Status status() const { return status_; } virtual Slice key() const { // ... } virtual Slice value() const { // ... } virtual void Next() { // ... } virtual void Prev() { // ... } virtual void Seek(const Slice &target) { // 见下文分析 } virtual void SeekToFirst() { // ... } virtual void SeekToLast() { // ... } private: // ... }; 其中，前几个成员变量的含义与Block类中的成员变量的含义类似，这里不再赘述。key_、value_这两个成员变量为迭代器当前指向的entry的KV值。 在这里主要分析Seek(const Slice &target)函数，其余函数的实现比较简单，在这里就不做分析了。Seek函数首先通过二分查找算法找到target所在的前缀编码分组的位置： // Binary search in restart array to find the last restart point // with a key < target uint32_t left = 0; uint32_t right = num_restarts_ - 1; while (left < right) { uint32_t mid = (left + right + 1) / 2; 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 == nullptr || (shared != 0)) { CorruptionError(); return; } Slice mid_key(key_ptr, non_shared); if (Compare(mid_key, target) < 0) { // 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 - 1; } } 然后在该分组中遍历： // Linear search (within restart block) for first key >= target SeekToRestartPoint(left); while (true) { if (!ParseNextKey()) { return; } if (Compare(key_, target) >= 0) { return; } } 其中调用了DecodeEntry函数： static inline const char *DecodeEntry(const char *p, const char *limit, uint32_t *shared, uint32_t *non_shared, uint32_t *value_length) { // ... } 这个函数将以p为起始位置的entry解码，并且解码不会超过limit指向的位置，将key共享字节长度、key非共享字节长度、value长度存入shared，non_shared，value_length，返回指向entry中unshared_key_data起始位置的指针。 还调用了ParseNextKey函数： bool ParseNextKey() { // ... } 这个函数获取下一个entry的key和value值并存入迭代器的成员变量中。 BlockBuilder类 BlockBuilder类用于构建sstable中的block。BlockBuilder类声明为： class BlockBuilder { public: // ... // REQUIRES: Finish() has not been called since the last call to Reset(). // REQUIRES: key is larger than any previously added key void Add(const Slice &key, const Slice &value); // Finish building the block and return a slice that refers to the // block contents. The returned slice will remain valid for the // lifetime of this builder or until Reset() is called. Slice Finish(); // ... private: const Options *options_; std::string buffer_; // Destination buffer std::vector<uint32_t> restarts_; // Restart points int counter_; // Number of entries emitted since restart bool finished_; // Has Finish() been called? std::string last_key_; // ... }; 其中options_为构建选项，buffer_为实际block中的数据，restarts_存储前缀编码各个分组的起始位置，counter_记录当前前缀编码分组中已经压缩了几个entry，finished_标记Finish是否被调用，last_key_为block中上一次添加的key值。 下面我们首先看Add函数： void BlockBuilder::Add(const Slice &key, const Slice &value) Add函数首先检查当前前缀编码分组中压缩的entry个数是否已经达到上限，如果没有达到上限则计算共享的key的字节个数： Slice last_key_piece(last_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; 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++; } } 如果达到上限则重新开始一个restart： else { // Restart compression restarts_.push_back(buffer_.size()); counter_ = 0; } const size_t non_shared = key.size() - shared; 然后依次将相应的数据编码后组成一个新的entry： // 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()); 最后将数据加在buffer_的后面并更新last_key_和counter_的值： // Update state last_key_.resize(shared); last_key_.append(key.data() + shared, non_shared); assert(Slice(last_key_) == key); counter_++; 然后是Finish函数： Slice BlockBuilder::Finish() { // Append restart array for (size_t i = 0; i < restarts_.size(); i++) { PutFixed32(&buffer_, restarts_[i]); } PutFixed32(&buffer_, restarts_.size()); finished_ = true; return Slice(buffer_); } Finish函数首先将restarts_的偏移量存入buffer_，然后存入num_of_restarts，然后将buffer_封装为一个Slice返回。 228 Love u
