LSM-Tree - LevelDb 源码解析（一）（下）

log部分

了解完写入的大致操作流程之后，下面来看看LevelDb的日志管理也就是AddRecord()函数的操作：

但是日志的核心部分并不在AddRecord()内部，因为内部只有一些简单的字符串拼接操作，这里将核心放到了RecordType的部分，可以看到这里通过当前日志字符长度判断不同的类型，RecordType标识当前记录在块里面的位置：

//....
  enum RecordType {
    // Zero is reserved for preallocated files
    kZeroType = 0,
    kFullType = 1,
    // For fragments
    kFirstType = 2,
    kMiddleType = 3,
    kLastType = 4
  };
  //....
  RecordType type;
  const bool end = (left == fragment_length);
  if (begin && end) {
    type = kFullType;
  } else if (begin) {
    type = kFirstType;
  } else if (end) {
    type = kLastType;
  } else {
    type = kMiddleType;
  }

First：是用户记录第一个片段的类型， Last：是用户记录的最后一个片段的类型。

Middle：是一个用户记录的所有内部片段的类型。

从RecordType内部的定义可以看到日志固定为32KB大小，在日志文件中将分为多部分，但是一个日志只包含一个chunk：

• 前面4个字节用于CRC校验
• 接着两个字节是chuck数据长度
• 接着是一个字节的类型标识（标识当前日志记录在块中位置）
• 最后是数据payload部分

32kb大小选择也是有考究的，主要考虑日志记录行的磁盘对齐和日志读写，针对日志写的速度也非常快，通过fdatasync(...)方法将缓冲区fflush到磁盘中并且持久化。最后通过日志完成故障恢复的操作。

需要注意如果一个日志记录较大可能存在于多个block块中。

需要注意一个记录永远不会在一个块的最后六个字节内开始，理由是一个记录前面需要一些其他部分占用空间（也就是记录行的校验和数据长度标识信息等），为了保持单个日志块被拆分到多个文件以及压缩考虑，这种“浪费”是可以被接受。 如果读者非要清楚最后几个字节存储的是什么可以看下面的代码：dest_->Append(Slice("\x00\x00\x00\x00\x00\x00", leftover));

如果看不懂源代码，可以根据作者的md文档介绍也可以大致了解日志文件结构

record :=
      checksum: uint32     // crc32c of type and data[] ; little-endian
      length: uint16       // little-endian
      type: uint8          // One of FULL, FIRST, MIDDLE, LAST
      data: uint8[length]

我们可以根据描述简单画一个图：

日志写流程图：

日志写的流程比较简单，主要分歧点是当前块剩余空间是否够写入一个header，并且最后6个字节将会填充空格进行补齐。在日志写入的过程中通过一个while(ture)不断判断buffer大小，如果大小超过32KB，则需要停止写入并且把开始写入到现在位置为一个chunk。

日志读流程图：

既然一个block大小为32kb，那么一次日志的读写也应该是32kb，接着便是扫描chunk，在扫描chunk的时候如果发现CRC校验不通过则返回错误信息， 如果数据破损则丢弃当前chunk。

整个读取通过while(true)循环read，直到读取到类型为Last的chunk，日志记录读取完成。

memtable比较有意思的特点是无论插入还是删除都是通过“新增”的方式实现的（你没有看错），内部通过Mainfest维护状态，同时根据版本号和序列号维护一条记录是新增还是删除并且保证读取到的内容是最新值，具体介绍同样在上一节[[LSM-Tree - LevelDb了解和实现]]中解释了对于记录的写入来说即使写入日志也是不能查询的（因为中间有可能存在断电故障导致真实记录没有写入），日志仅作为故障恢复，只有数据写入到mem新增数据才会被访问到。

关于mem新增和删除的代码如下：

namespace {
class MemTableInserter : public WriteBatch::Handler {
public:
  SequenceNumber sequence_;
  MemTable* mem_;
  void Put(const Slice& key, const Slice& value) override {
    mem_->Add(sequence_, kTypeValue, key, value);
    sequence_++;
  }
  void Delete(const Slice& key) override {
    mem_->Add(sequence_, kTypeDeletion, key, Slice());
    sequence_++;
  }
  };
} // namespace

在Add()函数的内部通过一个[[skiplist 跳表]]完成数据的插入，在数据的node中包含了记录键值，为了保证读取的数据永远是最新的，记录需要在skiplist内部进行排序，节点排序使用的是比较常见的比较器Compare，如果用户想要自定义排序（例如处理不同的字符编码等）可以编写自己的比较器实现。

对于一条记录的结构我们也可以从Add()函数中看到作者的注释：

// Format of an entry is concatenation of:
  //  key_size     : varint32 of internal_key.size()
  //  key bytes    : char[internal_key.size()]
  //  tag          : uint64((sequence << 8) | type)
  //  value_size   : varint32 of value.size()
  //  value bytes  : char[value.size()]

[[VarInt32编码]]：在这里虽然是变长整型类型但是实际使用4个字节表示。 uint64((sequence << 8) | type：运算之后实际为7个字节的sequence长度 注意在tag和value_size中间有一个ValueType标记来标记记录是新增还是删除。

根据get()代码内部通过valueType进行区分，valuetype占用一个字节的空间进行判断新增还是删除记录，默认比较器判断新增或者删除记录逻辑如下：

if (comparator_.comparator.user_comparator()->Compare(
  Slice(key_ptr, key_length - 8), key.user_key()) == 0) {
  // Correct user key
  const uint64_t tag = DecodeFixed64(key_ptr + key_length - 8);
  switch (static_cast<ValueType>(tag & 0xff)) {
  case kTypeValue: {
    Slice v = GetLengthPrefixedSlice(key_ptr + key_length);
    value->assign(v.data(), v.size());
    return true;
  }
  case kTypeDeletion:
    *s = Status::NotFound(Slice());
    return true;
  }
}

根据代码定义和上面的描述画出下面的结构图：

Compare键排序

LevelDb的memtable通过跳表维护了键，内部默认情况下使用InternalKeyComparator对于键进行比较，下面是比较内部逻辑： 比较器通过 user_key 和 sequence_number 进行排序，同时按照user_key进行升序排序，序列号通过插入的时间递增，以此来保证无论是增加还是删除都是获取到最新的信息。

/*
 一个用于内部键的比较器，它使用一个指定的比较器用于用户键部分比较，并通过递减序列号来打破平衡。
*/
int InternalKeyComparator::Compare(const Slice& akey, const Slice& bkey) const {
  // Order by:
  // 增加用户密钥（根据用户提供的比较器）。
  // 递减序列号
  // 递减类型（尽管序列号应该足以消除歧义）。
  int r = user_comparator_->Compare(ExtractUserKey(akey), ExtractUserKey(bkey));
  if (r == 0) {
    const uint64_t anum = DecodeFixed64(akey.data() + akey.size() - 8);
    const uint64_t bnum = DecodeFixed64(bkey.data() + bkey.size() - 8);
    if (anum > bnum) {
      r = -1;
    } else if (anum < bnum) {
      r = +1;
    }
  }
  return r;
}

需要注意被比较key可能包含完全不同的内容，这里读者肯定会有疑问对于key获取值进行提取信是否会有影响，然而从get的逻辑来看它可以通过键长度，和序列号等信息进行获取Key，并且获取是header的头部信息，所以key是任何类型都没有英雄。

记录查询

现在我们再回过头来看一下memtable是如何读取的，从memtable和imumemble的关系可以看出有点类似缓存，当memtable写满之后转为imumem并且等待同步至磁盘。

我们可以回顾一下上一节提到的读取等步骤：读取的步骤：

• 在memtable中获取指定Key，如果数据符合条件则结束查找。
• 在Imumemtable中查找指定Key，如果数据符合条件则结束查找。
• 按低层至高层的顺序在level i层的sstable文件中查找指定的key，若搜索到符合条件的数据项就会结束查找，否则返回Not Found错误，表示数据库中不存在指定的数据。

记录查询按照下面的层级关系进行搜索，首先是从当前内存中正在写入的memtable搜索，接着是imumemtable，再接着是存在于磁盘不同层级的SSTable，SSTable通过*.ldb的形式进行处理。

最终我们可以把LevelDb的查询看作下面的形式：

小结：

这一部分我们了解了LevelDB源代码部分等基础结构DB，介绍了LevelDB的基础对外接口，其实LevelDB和map的接口十分类似，同时重点讲述了读写操作等源代码，以及内部合并压缩的一些细节。

另外记录查询等动作和之前介绍LevelDB等读写流程大致类似，当然代码简化了很多的内容，读者可以根据自己感兴趣的内容研究。