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
