leveldb 源码分析

Arch

image.png

lsm-tree 存储引擎

1. WriteBatch的数据格式

// writeBatch rep format: 8byte sequence number 4byte count
void WriteBatch::Put(const Slice& key, const Slice& value) {
  WriteBatchInternal::SetCount(this, WriteBatchInternal::Count(this) + 1);

  // 这里实际copy了key value的值
  rep_.push_back(static_cast<char>(kTypeValue));
  PutLengthPrefixedSlice(&rep_, key);
  PutLengthPrefixedSlice(&rep_, value);
}

    // 从队列中根据sync条件和kv大小找出适合加入本次WriteBatch的
    WriteBatch* updates = BuildBatchGroup(&last_writer);

    printf("Write header:seq=%llu count=%d\n",last_sequence+1,WriteBatchInternal::Count(updates));

    WriteBatchInternal::SetSequence(updates, last_sequence + 1);
    last_sequence += WriteBatchInternal::Count(updates);

image.png
image.png

2. WAL的数据格式

enum RecordType {
  // Zero is reserved for preallocated files
  kZeroType = 0,
  kFullType = 1,
  // For fragments
  kFirstType = 2,
  kMiddleType = 3,
  kLastType = 4
};
// 单个Block 32KB 因此写入操作可能被切分成几块，依次顺序写入文件
static const int kBlockSize = 32768;
// 每个分块的Header
static const int kHeaderSize = 4 + 2 + 1;

  // Write the header and the payload
  // 调用了flush将数据刷到了page cache
  Status s = dest_->Append(Slice(buf, kHeaderSize));
  if (s.ok()) {
    s = dest_->Append(Slice(ptr, length));
    if (s.ok()) {
      s = dest_->Flush();
    }
  }
  block_offset_ += kHeaderSize + length;

image.png

3. SST数据格式

   
   image.png

• DataBlock

  
  image.png

• SST

  
  image.png

4. FilterBlock
   提供快速判断一个key是否存在于某个datablock中，以加速查找的过滤器

参考

https://blog.csdn.net/u012432778/article/details/46494105