RocksDB（三）：WAL Learning
WAL Learning
Write Ahead Log
Overview
在RocksDB中每一次数据的更新都会涉及到两个结构，一个是内存中的memtable(后续会刷新到磁盘成为SST)，第二个是WAL(WriteAheadLog)。在默认情况下，RocksDB通过在每次用户写时调用flush （刷盘）WAL文件来保持一致性。
WAL主要的功能是当RocksDB异常退出后，能够恢复出错前的内存中(memtable)数据，因此RocksDB默认是每次用户写都会刷新数据到WAL。每次当当前WAL对应的内存数据(memtable)刷新到磁盘之后，都会新建一个WAL。
所有的WAL文件都是保存在WAL目录(options.wal_dir)，为了保证数据的状态，所有的WAL文件的名字都是按照顺序的(log_number)。
一个WAL记录着所有列族的写入日志。
Life Cycle of a WAL
举个例子，Rocksdb实例创建了两个column families（列族），分别是new_cf和default。一旦有db被打开，就会在磁盘上创建一个WAL来持久化所有的写操作。（WAL在所有列族之间是共享的。）
DB* db;
std::vector<ColumnFamilyDescriptor> column_families;
column_families.push_back(ColumnFamilyDescriptor(
kDefaultColumnFamilyName, ColumnFamilyOptions()));
column_families.push_back(ColumnFamilyDescriptor(
"new_cf", ColumnFamilyOptions()));
std::vector<ColumnFamilyHandle*> handles;
s = DB::Open(DBOptions(), kDBPath, column_families, &handles, &db);
在两个列族中添加一下kv对数据：
db->Put(WriteOptions(), handles[1], Slice("key1"), Slice("value1"));
db->Put(WriteOptions(), handles[0], Slice("key2"), Slice("value2"));
db->Put(WriteOptions(), handles[1], Slice("key3"), Slice("value3"));
db->Put(WriteOptions(), handles[0], Slice("key4"), Slice("value4"));
此时WAL已经记录了所有的写入操作。接着WAL会保持着打开的状态，并且持续记录将来的写入操作一直到WAL的大小达DBOptions::max_total_wal_size
为止。
如果使用者决定将列族刷新到磁盘上，会产生以下改变：
1.new_cf的数据（key1和key3）会被刷新成为一个新的SST file。
- 一个新的WAL会被创建，并且后续对于所有的列族的写入操作都会被记录在新的WAL上
- 旧的WAL将不会再记录新的写入操作但是对于旧WAL的删除会被推迟。
db->Flush(FlushOptions(), handles[1]);
// key5 and key6 will appear in a new WAL
db->Put(WriteOptions(), handles[1], Slice("key5"), Slice("value5"));
db->Put(WriteOptions(), handles[0], Slice("key6"), Slice("value6"));
此时会有两个WAL，旧的WAL包括对于key1到key4的记录，而新的WAL包括key5与key6的记录。因为旧的WAL仍然包括至少一个default列族的有效数据，所以现在它还不能被删除。只有当default列族被flush后（无论是自动的刷盘操作还是手动的刷盘操作），这个旧的WAL可以被归档并标记为删除。
db->Flush(FlushOptions(), handles[0]);
// The older WAL will be archived and purged separately
所以总结以下，一个WAL只有在下面两种情况下才会被创建：
1.当一个新的数据库被打开
2.当一个列族被flush
只有当所有的列族都被flush到SST中并超出WAL所能容纳的最大序号时，或者说，当所有WAL中的数据都已经被持久化到SST文件中时，一个WAL文件才会被删除（或者说被归档，如果启用了存档的话）。而归档的文件会被移动到一个单独的位置，后续从磁盘中删除。处于复制的目的，所以实际上的删除可能还会被延迟，详见下面关于事务日志迭代器的部分。
WAL Configurations
DBOptions::wal_dir
DBOptions::wal_dir可以设置RocksDB保存WAL文件的目录，这使得WAL的文件可以保存在与实际数据不同的目录下。
DBOptions::WAL_ttl_seconds,DBOptions::WAL_size_limit_MB
这两个选项会影响归档的WAL被删除的快慢。非零值表示触发归档的 WAL 删除的时间和磁盘空间阈值。
DBOptions::max_total_wal_size
为了限制WAL文件数目的大小，RocksDB使用DBOptions::max_total_wal_size来出发列族的flush操作。一旦WAL文数目件超出限定大小，RocksDB会开始强制将所有列族的数据都flush，以便于删除一些旧的WAL文件。当列族以非均匀的速率更新时，这个配置会很有用。如果没有大小限制的话，当不经常更新的列族一段时间没有flush时，用户可能会一直保留着旧的WAL文件。
DBOptions::avoid_flush_during_recovery
顾名思义，这个配置就是为了避免在recovery的时候进行flush。
DBOptions::manual_wal_flush
DBOptions::manual_wal_flush决定了是否每次在写操作后对WAL自动进行flush或者纯手动执行。（用户通过地爱用WALflush来触发WAL的flush）
DBOptions::wal_filter
通过DBOptions::wal_filter，用户可以提供在恢复数据期间处理WAL时所要调用的过滤器对象。(恢复数据时可以过滤某些记录)
DBOptions::wal_compression
压缩算法用于压缩WAL记录。默认是kNoCompression.
WriteOptions::disableWAL
用来打开或者关闭WAL支持。当用户依赖其他方法来记录或者不在意数据的丢失时，可以调用WriteOptions::disableWAL。
Transaction Log Iterator
事务日志迭代器提供了一种在 RocksDB 实例之间进行复制数据的方法。一旦 WAL 由于列族刷新而被归档，WAL 并不会立即删除。目的是允许事务日志迭代器继续读取 WAL 并将其发送给从节点进行重现。
WAL Recovery Modes
Introduction
每一个应用都是唯一的，都需要RocksDB
保证确定状态的一致性。RocksDB中每一次提交记录都是持久化的。没有被提交的记录被记载在WAL中。当RocksDB正常推出后，所有未提交的数据都会在关闭之前提交，因此始终可以保持一致性。当RocksDB进程被kill或者服务器重启后，RocksDB需要重新恢复到一致性状态。
kTolerateCorruptedTailRecords
在这种模式下，WAL的重现会忽略日志末尾的任何错误。这些错误主要是，在不安全的退出下，在日志的末尾可能会有一些没有完成的写操作。这是一种启发式模式，系统无法区分日志尾部的损坏和不完整的写入。任何其他 IO 错误都将被视为数据损坏。
这种模式为大部分应用所使用，这是因为该模式提在在不安全退出与数据一致性之间做出了适当权衡。
kAbsoluteConsistency
在这种模式下，WAL重现期间的任何IO错误都会被视作数据损坏。这种模式适用于以下场景：应用无法接受失去任何一条记录的风险或者应用有其他恢复未提交数据的方法。
kPointInTimeRecovery
在这种模式下，当遇到一个IO错误时，WAL的重现工作会停止。系统会恢复到一个满足一致性的时间点上。该模式适用于那些拥有副本的集群。来自另一个副本的数据可以用来恢复剩下的数据。
kSkipAnyCorruptedRecords
在这种模式下，读取日志时会忽略任何IO错误。系统尽最大努力去恢复尽可能多的数据。该模式适用于灾难性毁坏的修复。
WAL File Format
Overview
WAL将memtable的操作序列化从而持久化存储为日志文件。当db故障时，可以使用WAL文件来根据记录重建memtable，从而恢复数据库回到一致性状态。当一个memtable被安全地flush到持久化存储的文件中，相应的WAL日志会被淘汰从而归档。最终经过一段时间后，被归档的记录都会从磁盘中被清除。
WAL Manager
在WAL的目录中，WAL文件按照序列号递增的顺序命名。为了重建数据库之前的一致性状态，这些文件会按照序列号递增的顺序读取。WAL Manager 封装了读取WAL文件的操作。在封装内部，采用Reader or Writer abstraction来读取文件。
Reader/Writer
Writer将记录更新到日志文件中的相关操作进行封装。这中间具体的内部细节由WriteableFile接口来处理实现。同样的，Reader将从日志文件中顺序读取记录的操作进行封装。这中间具体的内部细节由SequentialFile接口来处理实现。
Log File Format
WAL文件时由一堆变长的record组成的，而每个record是由kBlockSize（32K）来分组（就是一个kBlockSize由多个record组成），如果某一个record大于kBlockSize的话，它就会被切分为多个record（通过type来判断）。
+-----+-------------+--+----+----------+------+-- ... ----+
File | r0 | r1 |P | r2 | r3 | r4 | |
+-----+-------------+--+----+----------+------+-- ... ----+
<--- kBlockSize ------>|<-- kBlockSize ------>|
rn = variable size records
P = Padding
- rn：代表第n个record
- p：代表当无法组成一个kBlockSize时的填充，即如果一个特定的记录不能完全适配剩余的空间，那么就会把剩余的空间补零。
Record Format
记录的格式展示如下。总共由两种记录格式，分为Legacy和Recyclable。
The Legacy Record Format
+---------+-----------+-----------+--- ... ---+
|CRC (4B) | Size (2B) | Type (1B) | Payload |
+---------+-----------+-----------+--- ... ---+
CRC = 32bit hash computed over the payload using CRC
Size = Length of the payload data
Type = Type of record
(kZeroType, kFullType, kFirstType, kLastType, kMiddleType )
The type is used to group a bunch of records together to represent
blocks that are larger than kBlockSize
Payload = Byte stream as long as specified by the payload size
- CRC：循环冗余校验码，32bit，用CRC计算在有效负载上的hash
- Size：是有效负载的数据量的长度
- Payload：由有效负载大小规定的字节流大小，其实就是承载的数据
- Type：记录的种类，种类是用来对一大堆记录进行分组从而更好的展现出来，包括kZeroType, kFullType, kFirstType, kLastType, kMiddleType这些种类。后续详细说下这些种类。
The Recyclable Record Format
+---------+-----------+-----------+----------------+--- ... ---+
|CRC (4B) | Size (2B) | Type (1B) | Log number (4B)| Payload |
+---------+-----------+-----------+----------------+--- ... ---+
Same as above, with the addition of
Log number = 32bit log file number, so that we can distinguish between
records written by the most recent log writer vs a previous one.
Log number（32bit）是文件编号，用来区别最新的log writter写的记录和之前的记录。
Record Format Details For Legacy Format
日志文件是由连续地32KB大小的block组成。唯一的例外是文件尾部数据包含一个不是完整的block。
每一个block包含连续的Records，record的格式如下：
block := record* trailer?
record :=
checksum: uint32 // crc32c of type and data[]
length: uint16
type: uint8 // One of FULL, FIRST, MIDDLE, LAST
data: uint8[length]
记录永远不会在块的最后六个字节内开始（因为它不适合）。此处的任何剩余字节构成trailer，trailer必须完全由零字节组成，并且必须被readers跳过。
如果当前块中只剩下七个字节，并且添加了一条新的非零长度记录，则writer必须发出一条 FIRST 记录（其中包含零字节的用户数据）以填充块中剩下的七个字节，然后在后续块中存放所有用户数据。
后续还会添加更多的types。因为无法识别记录的types，一些Readers可能会跳过阅读types，其他的Readers可能会报告一些数据被跳过。
FULL == 1
FIRST == 2
FIRST == 3
LAST == 4
其中FULL表示包含了全部用户record记录，FIRST、MIDDLE、LAST用户表示一个record因为太大然后拆分为多个数据片。FIRST表示是用户record的第一块数据，LAST表示最后一块数据，MID表示record中间部分的数据。举一个简单的例子：
A：length 1000
B：length 97270
C：length 8000
A会在第一个block中存储为一个完整的record。
B会因为超出了一个block的大小（32KB=32768B），所以B会被拆分为3个分片，第一个分片占用了第一个block的剩余全部空间，第二个分片占用第二个block的全部空间，第三个分片占用第三个block的前面部分空间。会在第三个block中预留6个字节作为trailer，置为空来表示结束。
C将会完整地存储在第四个block。
payload
最后是WAL的payload的格式，其实是一批操作的集合，从record中可以看出wal的写入是一批一批写入的。
// WriteBatch::rep_ :=
// sequence: fixed64
// count: fixed32
// data: record[count]
// record :=
// kTypeValue varstring varstring
// kTypeDeletion varstring
// kTypeSingleDeletion varstring
// kTypeMerge varstring varstring
// kTypeColumnFamilyValue varint32 varstring varstring
// kTypeColumnFamilyDeletion varint32 varstring varstring
// kTypeColumnFamilySingleDeletion varint32 varstring varstring
// kTypeColumnFamilyMerge varint32 varstring varstring
// kTypeBeginPrepareXID varstring
// kTypeEndPrepareXID
// kTypeCommitXID varstring
// kTypeRollbackXID varstring
// kTypeNoop
// varstring :=
// len: varint32
// data: uint8[len]
从上面的格式中可以看出有一个sequence的值，这个值主要用来表示WAL中操作的时序，这里要注意的每次sequence的更新是按照WriteBatch来更新的。
Status DBImpl::WriteToWAL(const WriteThread::WriteGroup& write_group,
log::Writer* log_writer, uint64_t* log_used,
bool need_log_sync, bool need_log_dir_sync,
SequenceNumber sequence) {
Status status;
.........................................
WriteBatchInternal::SetSequence(merged_batch, sequence);
Benefits
recordio的记录格式有以下好处：
1.我们不需要任何启发式方法进行重新同步 - 只需转到下一个block的边界并扫描即可。如果存在损坏，请跳到下一个block。作为附带好处，当一个日志文件的部分内容作为记录嵌入到另一个日志文件中时，我们并不会混淆。
2.在近似边界处拆分（例如，对于mapreduce）很简单：找到下一个block边界并跳过记录，直到我们遇到一个FULL或FIRST记录。
3.对于大型记录，我们不需要额外的缓冲。
Downsides
recordio的记录格式有以下弊端：
1.没有封装更小的记录。但这可以通过添加新的记录类型来解决，因此这是当前实现的缺点。
2.无压缩。同样，可以通过添加新的记录类型来解决此问题。
WAL Performance
Non-Sync Mode
当WriteOptions.sync = false时（默认就是false），WAL的写操作不会被同步到磁盘上。除非操作系统认为必须要进行flush（比如有太多的脏页的情况），用户不需要等待任何IO进行写入。
而希望可以减少因为写入操作系统页面缓存导致的 CPU 延迟的用户可以选择Options.manual_wal_flush = true。在这种选项下，WAL的写入甚至不会flush到文件系统的页面缓存中，但是会被保存在RocksDB中。用户可以通过调用DB::FlushWAL()来将缓存的条目转移到文件系统。
用户也可以通过调用DB::SyncWAL()来强制同步WAL文件。该函数不会阻止在其他线程中执行的写入。
在这种模式下，WAL的写在崩溃情况下时不安全的。
Sync Mode
当WriteOptions.sync = true时，前，WAL文件会在返回给用户之前被同步。
Group Commit
正如其他一些依赖日志型操作的系统一样，RocksDB支持group commit来提高WAL的写入吞吐量以及写入放大。RocksDB的group commit是用简单的方式实现的：当不同的线程同时写入同一个数据库时，所有符合组合条件的未完成写入将被组合在一起并写入 WAL 一次，只需一次同步。通过这种方式，相同数量的IO可以完成更多的写入。
然而通过不同的写入操作进行的写入可能会不可以组合。组合的最大容量时1MB。RocksDB通过主动延迟写入来避免增加组合容量的大小。
Number of I/Os per write
如果Options.recycle_log_file_num = false（默认就是false），RocksDB总会为新WAL的文段创建新文件。每一次的WAL写入都会改变数据和文件大小，因此每次同步将产生两个IO，一个用于修改数据，一个用于修改元数据。注意，RocksDB可以通过调用fallocate()来为文件预存空间，但同步时并不会阻塞元数据的IO。
Options.recycle_log_file_num = true会保留一个WAL文件池并尝试重新使用它们。当写入现有存在的日志文件时，会使用随机写入（写入的大小最小为0）。在写入到达文件末尾之前，文件大小不会更改，因此可以避免元数据产生的 I/O（也取决于文件系统装载选项）。假设大多数的WAL文件拥有差不多的大小，那么元数据产生的IO将会很小。
Write Amplification
注意对于有些实例来说，同步WAL可能会引入不小的写入放大。当写入内容很小时，因为整个block/page可能都需要更新，所以即使在写入很小的情况下，我们可能最终也需要两个4KB的写入（一个用于数据，一个用于元数据）。如果写入的内容只有40byte，将会有8KB被更新，那么写入放大就是8 KB/40 bytes ~= 200。因此，它产生的写入放大可能比LSM树带来的更大。
WAL Compression
WAL 压缩是一项将压缩记录更新到 WAL 的功能。它使用流式压缩来查找记录中的匹配短语，这比基于记录边界压缩的block具有更好的压缩率。
Overview
RocksDB中的SST文件包含的是压缩的kv键值对。然而，当用户第一次将键值对写入启用了WAL的数据库，它们写入WAL采用的是非压缩的格式。这样可能是的WAL的文件大小相对于数据库的大小更膨胀。如果数据库位于网络存储上，并且复制了 WAL，则会增加 IO 和存储开销。支持 WAL 压缩解决了这些限制。
WAL 以流式传输方式编写和读取。写入数据库的内容可以被打包成逻辑记录并更新到WAL文件中。RocksDB 以 32KB 块的形式分配并物理写入 WAL 文件，超过 32KB 边界的逻辑记录将被分解为物理记录（或片段）。压缩在逻辑记录级别完成，然后分解为物理记录。我们使用流式压缩，它允许在逻辑记录边界处刷新压缩缓冲区，但也允许后续逻辑记录引用先前记录中的匹配短语，与基于块的压缩相比，压缩因子损失最小。
这对于具有很长和重复的key的用户特别有用。这在SST文件中不是问题，但是WAL文件与key会不成比例，变得十分巨大。如果 WAL 写入很小并且更频繁地同步到磁盘，但则可能没有那么有益。
Configuration
WAL的压缩是通过设置DBOptions中的wal_compression 选项来启动的。目前仅支持ZSTD压缩。该配置无法动态改变。无论选项设置如何，RocksDB 都将能够从以前的实例中读取压缩的 WAL 文件（如果存在的话）。