Write-Ahead-Log-File-Format.md

概述

WAL会把memtable的操作序列化之后以日志文件形式存储在持久化介质中。发生崩溃的时候，WAL文件可以用于重新构建memtable，帮助数据库恢复数据库到一个一致的状态。当一个memtable被安全地落盘到持久化介质之后，相关的WAL日志会变成过期的，然后被归档。最终归档的日志会在一定时间后被从硬盘上删除。

WAL管理器

WAL文件使用一个递增的序列号生成到WAL文件夹。为了重新构建数据库的状态，这些文件会被按序列号顺序读取。WAL管理器提供把WAL文件作为一个独立单元进行读取的抽象接口。内部，他使用Writer或者Reader抽象接口打开，并读取文件。

Reader/Writer

Writer提供一个抽象接口，用于在日志文件末尾增加数据。存储介质相关的内部细节信息通过WriteableFile接口处理。类似的，Reader提供一个抽象接口，用于从一个日志文件中顺序读取日志记录。内部的存储介质相关细节信息有SequentialFile接口处理。

日志文件格式

日志文件由一系列的变长记录构成。记录通过kBlockSize聚集在一起。如果某个特定记录不能放入剩余的空间，那么剩余空间将会被空数据填充。writer写而reader读数据的时候，是按照一个kBlockSize大小的块来读的

       +-----+-------------+--+----+----------+------+-- ... ----+
 File  | r0  |        r1   |P | r2 |    r3    |  r4  |           |
       +-----+-------------+--+----+----------+------+-- ... ----+
       <--- kBlockSize ------>|<-- kBlockSize ------>|

rn = 变长块记录
P = 填充数据

记录格式

记录的排列格式如下所示：

+---------+-----------+-----------+--- ... ---+
|CRC (4B) | Size (2B) | Type (1B) | Payload   |
+---------+-----------+-----------+--- ... ---+

CRC = 使用CRC算出来的payload的32bit的哈希码
Size = payload数据的长度
Type = 记录的类型
		(kZeroType, kFullType, kFirstType, kLastType, kMiddleType )
      类型用于将一系列的记录分到一组，用来表示大小大于kBlockSize的块
Payload = 长度为Size的payload数据流。

记录格式细节

日志的内容是一系列的32KB的块。唯一的例外是文件的末尾可能会包含一个分片的块。

每个块都由一系列记录构成：

block := record* trailer?
record :=
  checksum: uint32	// crc32c,覆盖 type 和 data[]
  length: uint16
  type: uint8		// FULL, FIRST, MIDDLE, LAST 的一种
  data: uint8[length]

一个记录不会在一个块的最后6个Byte开始（毕竟放不下）。任何剩下的数据都构成tailer，tailer由全0构成，读取的时候应该被跳过。

如果当前块正好剩下7个Byte，并且一个新的非0长度记录被加入进来，那么write必须加一个FIRST记录（里面不含任何用户数据）来填充剩下的7个byte，然后在下一个块再提交用户数据。

以后可能会增加更多的类型。有些Reader会跳过那些他们不能理解的记录类习惯，其他可能会报告某些数据被跳过。

FULL == 1
FIRST == 2
MIDDLE == 3
LAST == 4

FULL类型的记录保存完整的用户数据。

FIRST，MIDDLE，LAST在不得不把用户数据切分成多个分片的时候使用（大多数是因为块边界问题）。FIRST是用户数据的第一个分片用的类型，LAST是最后一个用户数据分片用的记录类型，MIDDLE则是中间那些所有的其他数据的记录类型。

例子：考虑一个用户记录的序列：

  A: 长度 1000
  B: 长度 97270
  C: 长度 8000

A会在第一个block里被存储为一个FULL记录。

B会被分成三个分片：第一个分片占据第一个块剩下的空间，第二个分片占据第二个块的完整空间，第三个分片占据第三个块的开头部分。第三个块还剩下6个Byte，作为一个tailer，留空。

C会在第四个块以FULL记录存储

优势

记录型格式的优势如下：

• 在重新同步的时候，我们不需要任何启发式操作——只要读到下一个块边界然后扫描即可。如果有错误中断，跳到下一个块。还有一个副作用，如果一个日志文件的一部分被嵌入到了另一个文件中，我们不会无法理解。
• 在大致的边界切分很简单（也许是为了做mapreduce）：找到下一个块的边界，然后跳过所有记录，直到我们命中一个FULL或者FIRST记录。我们不需要缓存大量记录。

劣势

记录型格式的劣势如下：

• 小记录没有打包方式。可能可以加入一个新的类型来解决，所以这个是当前实现导致的缺陷，不是格式本身的问题
• 无法压缩。同样的，这个可以通过加一个新的记录类型来解决。