LevelDB源码解析(7) 预写日志(WAL)

背景

LevelDB每次写key-value不会直接写到文件中，而是先暂存在Memtable中，Memtable写满后再写到文件中。如果发生故障(比如宕机)，保存在Memtable中的key-value就会全部丢失。所以为了保证数据的原子性和持久性，每次写key-value要预写日志，日志落盘后才会把key-value插入Memtable。日志文件和Memtable是一一对应的，Memtable落盘后，日志文件也会被删除。日志文件的名称由6位数字编号和log后缀组成，比如000012.log。

既然每次要写一次磁盘，为什么还要放到Memtable中而不是直接把key-value写到磁盘中呢。我理解主要原因是levelDB文件内部的key是要有序的，那么每次插入直接写磁盘就需要对磁盘上的数据进行排序，这个效率不敢恭维。而放在Memtable中可以在内存中排序，最后把有序的key-value批量落到磁盘上，效率更高，也方便查找。另一个原因是，如果存放的数据不是很关注完整性，写WAL的时候也可以先缓存再一起写入，不一定真的每次都要写一次磁盘。

LevelDB实现了一个Writer类来执行预写日志，这个Writer可以理解为一个日志文件对象，名称和DBImpl::Writer重复了，但是这两个没关系。本文提到的Writer的定义在db/log_writer.h中。

日志文件的格式

leveldb日志格式

一个LOG文件由多个32KB的block组成，每个block由多少fragment组成。一条日志记录可能被拆封成多个fragment存储。一条记录的多个fragment一定是连续的，但是可能跨多个block。

Writer类定义

class Writer {
public:
  explicit Writer(WritableFile* dest);
  Writer(WritableFile* dest, uint64_t dest_length);
  Writer(const Writer&) = delete;
  Writer& operator=(const Writer&) = delete;
  ~Writer();
  Status AddRecord(const Slice& slice);

private:
  Status EmitPhysicalRecord(RecordType type, const char* ptr, size_t length);
  WritableFile* dest_;
  int block_offset_;
  uint32_t type_crc_[kMaxRecordType + 1];
};

成员变量

dest_: WritableFile这是一个文件操作的抽象类，定义在include/leveldb/env.h中，是对不同操作系统的文件操作的抽象，不同操作系统实现也不一样，提供Write、Sync等接口。
block_offset_: 写入是以Block为单位的，这个表示写入位置在当前block的偏移量，比如这个block写了100个字节了，那么block_offset_就是100。
type_crc_: 后面会讲到RecordType，每个type有一个预先计算好的crc校验值，放在数组里。这个用来辅助计算数据的crc。

EmitPhysicalRecord成员函数

EmitPhysicalRecord每次完成一个fragment的写入。

Status Writer::EmitPhysicalRecord(RecordType t, const char *ptr,
                                  size_t length)
{
  char buf[kHeaderSize];
  buf[4] = static_cast<char>(length & 0xff);
  buf[5] = static_cast<char>(length >> 8);
  buf[6] = static_cast<char>(t);

  uint32_t crc = crc32c::Extend(type_crc_[t], ptr, length);
  crc = crc32c::Mask(crc);
  EncodeFixed32(buf, crc);

  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;
  return s;
}

header放在buf中，header总共7个字节，结构如下表

4字节	2字节	1字节
crc	length	RecordType

RecordType是传入的参数，用于表示当前fragment在一条记录中的相对位置，具体含义下一小节说，这里知道是个枚举值就可以了。

crc32c::Extend计算crc值， crc32c::Mask做了一层转换。作者解释这里是因为Extend的输入字符串里包含一个嵌入的crc，直接再做crc存在问题，所以需要Mask做一层转换。这里我不是很理解，有了解的大佬欢迎指点迷津。

EncodeFixed32是编码函数，把crc编码为32bit放到buf的前4个字节。

接下来两个Append调用分别把header和data写入到文件中，最后调用Flush进行写操作，因为调用Append时，Writer并不会直接写到文件里，而是先放到缓冲区，缓冲区满了再一起写入文件，Flush会把缓冲区内容写到文件里。注意这里并没有调用Sync，没有强制写文件，此时数据可能还在IO缓存里。

AddRecord成员函数

AddRecord是提供给外部调用的的接口，参数只有一个Slice对象，一个Slice就是一条记录，AddRecord把Slice的数据写到文件中。Slice类似于std::string。

Status Writer::AddRecord(const Slice &slice)
{
  const char *ptr = slice.data();
  size_t left = slice.size();

  Status s;
  bool begin = true;
  do
  {
    const int leftover = kBlockSize - block_offset_;
    assert(leftover >= 0);

    if ( leftover < kHeaderSize )
    {
      if ( leftover > 0 )
      {
        static_assert(kHeaderSize == 7, "");
        dest_->Append(Slice("\x00\x00\x00\x00\x00\x00", leftover));
      }
      block_offset_ = 0;
    }

    assert(kBlockSize - block_offset_ - kHeaderSize >= 0);

    const size_t avail = kBlockSize - block_offset_ - kHeaderSize;
    const size_t fragment_length = (left < avail) ? left : avail;

    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;
    }

    s = EmitPhysicalRecord(type, ptr, fragment_length);
    ptr += fragment_length;
    left -= fragment_length;
    begin = false;
  } while ( s.ok() && left > 0 );
  return s;
}

AddRecord的主要功能是根据block的写入情况，把要写入的记录进行分片，分为多个fragment。为什么不直接把记录按照header|record的格式进行写入呢？虽然这样实现逻辑更简单，但是意味着每次只能读一条记录，如果每条记录的size比较小，那么一条记录就需要读一次磁盘，虽然page cache能一定程度提高读效率。但是每4KB还是会读一次磁盘，读效率相对于每次读32KB的block就低很多了。

分片是通过do…while循环来实现的。首先计算当前block剩余空间leftover。如果剩余空间小于fragment的header size，说明已经无法写入一个新的fragment了，用0填充空间。把block_offset_设置为0，即开启一个新的block。

每循环一次，就会产生一个分片，left用于保存当前记录还没有写入的size，如果left大于block的可用空间avial(leftover-kHeaderSize)，就先写入avial大小的fragment，并把left减去avail。继续循环，直到剩余可用空间足够写入left。

写入由EmitPhysicalRecord完成，EmitPhysicalRecord的第一个参数RecordType表示当前fragment在当前记录的相对位置。

  if ( begin && end )
  {
    type = kFullType;
  } else if ( begin )
  {
    type = kFirstType;
  } else if ( end )
  {
    type = kLastType;
  } else
  {
    type = kMiddleType;
  }

begin初始值为true，表示是不是第一个fragment，第一个循环结束后，begin就是false了。left的值是通过left和fragment_length来判断的，如果这两个值相等，说明left可以完整放进当前的block，那么当前fragment就是最后一个了，end为true，反之为false。

begin值	end值	RecordType	含义
true	true	kFullType	第一个也是最后一个fragment，即只有这一个fragment
true	false	kFirstType	第一个fragment
false	true	kLastType	最后一个fragment
false	false	kMiddleType	不是第一个也不是最后一个fragment，即使中间的fragment

强制写磁盘

一直到这里都没有提到强制写磁盘，事实上Writer不管写磁盘的事情，由外部根据需要决定是否强制写磁盘，也就是说Sync由外部自主调用。

源码版本

https://github.com/google/leveldb/releases/tag/1.22

背景