leveldb学习记录-log文件

log文件在leveldb的主要作用是防止系统宕机的时候,数据丢失。所以在将键值对写入位于内存的memtable之前,会先写入Log文件中,保证数据的持久化。这样即使系统发生故障,memtable中的数据没有及时Dump到磁盘上,LevelDB仍然可以根据log文件恢复数据。

1.log结构

关于log的结构在leveldb源码中的doc/log_format.md中有详细的介绍。

LevelDB对于一个log文件,由以32K为单位的物理块构成,每次读取以一个Block作为基本读取单位。

下图展示的 log 文件由3个 Block 构成,所以从物理布局来讲,一个 log 文件就是由连续的 32K 大小 Block 构成的。

log文件布局

每条record的结构如下图所示:

image-20201216200910539

leveldb中存放的键值对key和value的长度是可变的,所以需要length来记录record中保存的data长度(小端对齐)。checksum记录的是type和data字段的CRC循环校验,验证数据完整性和一致性。log文件是以Block为单位进行存放的,所以会存在某个key-value对过小不能占满一个block块,或者某个key-value对过大,单个block块放不下,需要存放在多个不同的block块中,type字段则是指出每条record的逻辑结构和log文件物理分块结构的关系。在leveldb源码的db/log_format.h文件中,定义了一个RecordType的枚举类。

1
2
3
4
5
6
7
8
9
10
11
enum RecordType {
// Zero is reserved for preallocated files
kZeroType = 0,

kFullType = 1,

// For fragments
kFirstType = 2,
kMiddleType = 3,
kLastType = 4
};

主要有以下四种类型:FULL, FIRST, MIDDLE, LAST

如果一个key-value对可以存放在一个block块中,则kFullType=1

如果某个key-value对过大,单个block块放不下,如上图的Record B就占了3个block块,在block1在Block 1的剩余部分放入Record B的开头一部分,类型标识为FIRST,代表了是一个记录的起始部分;Record B剩下的内容依次放在后续的物理Block里面Block 2全部用来放Record B,且标识类型为MIDDLE,意思是这是Record B中间一段数据;还不够,需要第三个block块 ,Record B剩下的部分可以完全放在Block 3中,类型标识为LAST,代表这是Record B的末尾数据。

2.源码分析

与log日志文件相关的源码:

db/log_format.h

db/log_reader.cc

db/log_reader.h

db/log_writer.cc

db/log_writer.h

leveldb:log命名空间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

namespace leveldb {
namespace log {

enum RecordType {
// Zero is reserved for preallocated files
kZeroType = 0,

kFullType = 1,

// For fragments
kFirstType = 2,
kMiddleType = 3,
kLastType = 4
};
static const int kMaxRecordType = kLastType;

static const int kBlockSize = 32768;//32k

// Header is checksum (4 bytes), length (2 bytes), type (1 byte).
// 其中length最大为kBlockSize=0x8000 - kHeaderSize,因此只使用2个字节存储
static const int kHeaderSize = 4 + 2 + 1;

} // namespace log
} // namespace leveldb

leveldb:log下定义的Writer类,封装对log的写入操作:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
//Write负责组织数据有格式的写入,成员变量dest_负责真正写入数据到文件系统
class Writer {
public:
// Create a writer that will append data to "*dest".
// "*dest" must be initially empty.
// "*dest" must remain live while this Writer is in use.
explicit Writer(WritableFile* dest);

// Create a writer that will append data to "*dest".
// "*dest" must have initial length "dest_length".
// "*dest" must remain live while this Writer is in use.
Writer(WritableFile* dest, uint64_t dest_length);

~Writer();

//接收数据并调用dest完成写入
//实现细节:
//根据slice 及 block剩余大小,可能分成一个或者多个fragment分别写入
//对于一个fragment格式如下:
//|crc(4B) |length(2B) |type(1B) |ptr(nB)... |
//|--------------header-------------|----data----|
//其中 type 是一个枚举类型:RecordType
//{kZeroType kFullType kFirstType kMiddleType kLastType}
Status AddRecord(const Slice& slice);

private:
WritableFile* dest_;
//每kBlockSize记为一个block,block_offset_记录当前block已经写入的偏移量
int block_offset_; // Current offset in block

// crc32c values for all supported record types. These are
// pre-computed to reduce the overhead of computing the crc of the
// record type stored in the header.
uint32_t type_crc_[kMaxRecordType + 1];

Status EmitPhysicalRecord(RecordType type, const char* ptr, size_t length);

// No copying allowed
Writer(const Writer&);
void operator=(const Writer&);
};

AddRecord函数,将数据写入底层文件

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
Status Writer::AddRecord(const Slice& slice) {
const char* ptr = slice.data();
size_t left = slice.size();

// Fragment the record if necessary and emit it. Note that if slice
// is empty, we still want to iterate once to emit a single
// zero-length record
Status s;
bool begin = true;
do {
//leftover记录block当前可用大小
const int leftover = kBlockSize - block_offset_;//当前32kb块的剩余量
assert(leftover >= 0);
//如果block可用大小已经无法写入header,那么补充\x00
if (leftover < kHeaderSize) {
// Switch to a new block
if (leftover > 0) {
// Fill the trailer (literal below relies on kHeaderSize being 7)
assert(kHeaderSize == 7);
//Slice构造函数第二个参数表示字符串长度,因此效果上是leftover个'\x00'
//leftover size最大为6,因此第一个参数指定6个'\x00'
dest_->Append(Slice("\x00\x00\x00\x00\x00\x00", leftover));
}
block_offset_ = 0;//更换新快
}

// Invariant: we never leave < kHeaderSize bytes in a block.
// block还有剩余可用空间让我们写入一部分数据
// 如果 = 0,也就是剩余只能写入header,那也写入(只是此时不会写入slice里任何数据)
assert(kBlockSize - block_offset_ - kHeaderSize >= 0);

//可用大小为kBlockSize - block_offset_,减去header大小即为可写的数据大小
const size_t avail = kBlockSize - block_offset_ - kHeaderSize;
//能够全部写入则=left,否则等于可写大小
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;//下一次slice待写入位置
left -= fragment_length;//slice还有多少没有写
begin = false;
} while (s.ok() && left > 0);
return s;
}

EmitPhysicalRecord函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
//写入header data到底层文件(调用flush确保写入)
//|crc(4B) |length(2B) |type(1B) |ptr(nB)... |
//|--------------header-------------|----data----|
Status Writer::EmitPhysicalRecord(RecordType t, const char* ptr, size_t n) {
//assert这里对应n要使用buf[4, 5]存储,一共两个字节,因此大小应当<=0xffff
assert(n <= 0xffff); // Must fit in two bytes
//要写入的数据大小一定能够写入(不大于kBlockSize)
assert(block_offset_ + kHeaderSize + n <= kBlockSize);

// Format the header
char buf[kHeaderSize];
//长度使用两个字节(buf[4, 5])存储,其中4存储低两位,5存储高两位,小端序
//例如n=0x6789,则buf[4]=0x89,buf[5]=0x67
buf[4] = static_cast<char>(n & 0xff);
buf[5] = static_cast<char>(n >> 8);
//buf[6]存储类型
buf[6] = static_cast<char>(t);

//计算crc: Extend(type_crc, ptr) -> Mask -> EncodeFixed32
// Compute the crc of the record type and the payload.
uint32_t crc = crc32c::Extend(type_crc_[t], ptr, n);
crc = crc32c::Mask(crc); // Adjust for storage
EncodeFixed32(buf, crc);

// Write the header and the payload
// 首先写入header: |crc |length |type |,大小为kHeaderSize
Status s = dest_->Append(Slice(buf, kHeaderSize));
if (s.ok()) {
//接着写入数据,大小为n
s = dest_->Append(Slice(ptr, n));
if (s.ok()) {
s = dest_->Flush();
}
}
block_offset_ += kHeaderSize + n;
return s;
}

这个函数的函数体首先检查数据的大小是否小于等于2个字节,接着计算CRC,然后将header数据(|crc |length |type |,大小为kHeaderSize)写入dest_中,接着写入数据,长度为n。

3.总结

本篇博客介绍了leveldb中的log日志文件的结构、逻辑布局和物理布局,分析其源码和主要的几个函数。弄清楚一次写入操作是如何执行的。

image-20201216215542423

image-20201216215741019