leveldb 源码分析 5¶

本系列《leveldb 源码分析》共有 22 篇文章，这是第五篇。

5.操作 Log 1¶

分析完 KV 在内存中的存储，接下来就是 操作日志。所有的写操作都必须先成功的 append 到操作日志中，然后再更新内存 memtable。这样做有两点：

可以将随机的写 IO 变成 append，极大的提高写磁盘速度；
防止在节点 down 机导致内存数据丢失，造成数据丢失，这对系统来说是个灾难。

在各种高效的存储系统中，这已经是口水技术了。

5.1 格式¶

在源码下的文档 doc/log_format.txt 中，作者详细描述了 log 格式：

The log file contents are a sequence of 32KB blocks. 
The only exception is that the tail of thefile may contain a partial block.
Each block consists of a sequence of records:
block:= record* trailer?
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]

A record never starts within the last six bytes of a block (since it won'tfit). Any leftover bytes here form thetrailer, which must consist entirely of zero bytes and must be skipped byreaders.

翻译过来就是： Leveldb 把日志文件切分成了大小为 32KB 的连续 block 块，block 由连续的 log record 组成，log record 的格式为： 注意：CRC32, Length 都是 little-endian 的。

Log Type 有 4 种：FULL = 1、FIRST = 2、MIDDLE = 3、LAST = 4。FULL 类型表明该 log record 包含了完整的 user record；而 user record 可能内容很多，超过了 block 的可用大小，就需要分成几条 log record，第一条类型为 FIRST，中间的为 MIDDLE，最后一条为 LAST。也就是：

FULL，说明该 log record 包含一个完整的 user record；
FIRST，说明是 user record 的第一条 log record
MIDDLE，说明是 user record 中间的 log record
LAST，说明是 user record 最后的一条 log record

翻一下文档上的例子，考虑到如下序列的 user records： A: length 1000 B: length 97270 C: length 8000

A 作为 FULL 类型的 record 存储在第一个 block 中；
B 将被拆分成 3 条 log record，分别存储在第 1、2、3 个 block 中，这时 block3 还剩 6byte，将被填充为 0；
C 将作为 FULL 类型的 record 存储在 block 4 中。

由于 一条 logrecord 长度最短为 7，如果一个 block 的剩余空间<=6byte，那么将被填充为*空字*符串，另外长度为 7 的 log record 是 不包括任何用户数据的。

5.2 写日志¶

写比读简单，而且写入决定了读，所以从写开始分析。有意思的是在写文件时，Leveldb 使用了内存映射文件，内存映射文件的读写效率比普通文件要高，关于内存映射文件为何更高效，这篇文章写的不错： http://blog.csdn.net/mg0832058/article/details/5890688

其中涉及到的类层次比较简单，如图 5.2-1：

注意 Write 类的成员 type_crc_ 数组，这里存放的为 Record Type 预先计算的 CRC32 值，因为 Record Type 是固定的几种，为了效率。Writer 类只有一个接口，就是 AddRecord()，传入 Slice 参数，下面来看函数实现。首先取出 slice 的字 符串指针和长度，初始化 begin=true，表明是 第一条 log record。

const char* ptr = slice.data();
size_t left = slice.size();
bool begin = true;

然后进入一个 do{}while 循环，直到写入出错，或者成功写入全部数据，如下：

1

S1 首先查看当前 block 是否<7，如果<7 则补位，并重置 block 偏移¶

dest_->Append(Slice("\x00\x00\x00\x00\x00\x00",leftover));
block_offset_ = 0;

S2 计算 block 剩余大小，以及本次 log record 可写入数据长度¶

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

S3 根据两个值，判断 log type¶

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;

S4 调用 EmitPhysicalRecord 函数，append 日志；并更新指针、剩余长度和 begin 标记¶

s = EmitPhysicalRecord(type, ptr,fragment_length);
ptr += fragment_length;
left -= fragment_length;
begin = false;

2

接下来看看 EmitPhysicalRecord 函数，这是实际写入的地方，涉及到 log 的存储格式。函数声明为：

StatusWriter::EmitPhysicalRecord(RecordType t, const char* ptr, size_t n) 参数 ptr 为用户 record 数据，参数 n 为 record 长度，不包含 log header。

S1 计算 header，并 Append 到 log 文件，共 7byte 格式为：¶

| CRC32 (4 byte) | payload length lower + high (2 byte) |   type (1byte)|
char buf[kHeaderSize];
buf[4] = static_cast<char>(n& 0xff);
buf[5] =static_cast<char>(n >> 8);
buf[6] =static_cast<char>(t);   // 计算record type和payload的CRC校验值
uint32_t crc = crc32c::Extend(type_crc_[t], ptr, n);
crc = crc32c::Mask(crc);        // 空间调整
EncodeFixed32(buf, crc);
dest_->Append(Slice(buf,kHeaderSize));

S2 写入 payload，并 Flush，更新 block 的当前偏移¶

s =dest_->Append(Slice(ptr, n));
s = dest_->Flush();
block_offset_ += kHeaderSize +n;

以上就是写日志的逻辑，很直观。