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;
以上就是写日志的逻辑,很直观。