Part 1 – 预写式日志
在计算机科学中，预写式日志[1]（Write-Ahead logging，缩写 WAL）是关系数据库系统中用于提供原子性和持久性（事务 ACID 属性中的 A 与 D）的一系列技术。在应用 WAL 的零碎中，所有的批改在失效之前都要先写入 log 文件中。log 文件中通常包含 redo 和 undo 信息。假如一个程序在执行某些操作的过程中机器掉电了。在重新启动时，程序可能须要晓得过后执行的操作是胜利了还是局部胜利或者是失败了。如果应用了 WAL，程序就能够查看 log 文件，并对忽然掉电时打算执行的操作内容跟实际上执行的操作内容进行比拟。在这个比拟的根底上，程序就能够决定是撤销已做的操作还是持续实现已做的操作，或者是放弃原样。
WAL 容许用 in-place 形式更新数据库。另一种用来实现原子更新的办法是 shadowpaging。用 in-place 形式做更新的次要长处是缩小索引和块列表的批改。ARIES[2]是 WAL 系列技术罕用的算法，其外围策略为：1）Write ahead logging，对于对象的任何变更都要首先记入日志，同时日志必须要先于对象被写入磁盘；2）Repeating history during Redo，在 crash 之后重启时，ARIES 通过从新执行数据库在 crash 之前的行为，使数据库复原到它 crash 之前那一刻的状态，而后 undo 掉 crash 时还在执行的事务；3）Logging changes during Undo，将在 undo 事务时对数据库所做的变更记录日志，保障在反复重启时不会重做。在文件系统中，WAL 通常称为 journaling[3]。
RocksDB[4]中的每个更新操作都会写到两个中央：1)写到磁盘上的 WAL 日志；2)一个名为 memtable 的内存数据结构，后续会被刷盘到 SST 文件。WAL 会把 memtable 的操作序列化之后以日志文件模式存储在长久化介质中。在数据库呈现解体的时候，WAL 文件能够用于从新构建 memtable，帮忙数据库复原数据库到一个统一的状态。当一个 memtable 被平安地落盘到长久化介质之后，相干的 WAL 日志会变成过期的，而后被归档，最终归档的日志会在肯定工夫后被从硬盘上删除。
1.1 WAL 管理器
WAL 文件应用一个递增的序列号生成到 WAL 文件夹。为了从新构建数据库的状态，这些文件会被按序列号程序读取。WAL 管理器提供把 WAL 文件作为一个可独立进行读取的形象接口。外部应用 Writer 或者 Reader 形象接口打开，并读取文件。
Writer 提供一个形象接口，用于在日志文件开端减少数据。存储介质相干的外部细节信息通过 WriteableFile 接口解决。相似的，Reader 提供一个形象接口，用于从一个日志文件中程序读取日志记录。外部的存储介质相干细节信息有 SequentialFile 接口解决。
1.2 WAL 文件格式
WAL 文件由一系列的变长记录形成。记录通过 kBlockSize（默认为 32KB）汇集在一起。如果某个特定记录不能放入残余的空间，那么残余空间将会被空数据填充。writer 写而 reader 读数据的时候，是依照一个 kBlockSize 大小的块来读的。
记录的排列格局如下所示：
WAL 文件蕴含一系列的大小为 32KB 的块，惟一的例外是文件的开端可能会蕴含一个分片的块。每个块都由一系列记录形成，一个记录不会在一个块的最初 6 个 Byte 开始（毕竟放不下）。任何剩下的数据都形成 tailer，tailer 由全 0 形成，读取的时候应该被跳过。如果以后块正好剩下 7 个 Byte，并且一个新的非 0 长度记录被退出进来，那么 write 必须加一个 FIRST 记录（外面不含任何用户数据）来填充剩下的 7 个 byte，而后在下一个块再提交用户数据。
FULL 类型的记录保留残缺的用户数据。FIRST，MIDDLE，LAST 在不得不把用户数据切分成多个分片的时候应用（大多数是因为块边界问题）。FIRST 是用户数据的第一个分片用的类型，LAST 是最初一个用户数据分片用的记录类型，MIDDLE 则是两头那些所有的其余数据的记录类型。
例子：思考一个用户记录的序列：
A 会在第一个 block 里被存储为一个 FULL 记录。B 会被分成三个分片：第一个分片占据第一个块剩下的空间，第二个分片占据第二个块的残缺空间，第三个分片占据第三个块的结尾局部。第三个块还剩下 6 个 Byte，作为一个 tailer，留空。C 会在第四个块以 FULL 记录存储。
1.3 WAL 的生命周期
用一个例子来阐明一个 WAL 的生命周期。一个 RocksDB 的 db 实例创立了两个列族：”new_cf” 和 ”default”。一旦 db 被关上，一个新的 WAL 会在磁盘上被创立，以保障写持久性。
往列族中退出一些数据：
这时 WAL 须要记录所有的写操作。WAL 会放弃关上，并一直跟踪后续的写操作，直到大小达到 DBOptions::max_total_wal_size 设定阈值。
如果用户决定把列族 ”new_cf” 的数据落盘，以下的事件会产生：
new_cf 的数据 (key1 和 key3) 会被落盘到一个新的 SST 文件；
一个新的 WAL 会被创立，当初后续的写操作都会写到新的 WAL 了；
旧的 WAL 不再承受新的写入，然而删除操作会被延后。
这时，会有两个 WAL 文件，旧的保留有从 key1 到 key4 的内容，新的保留 key5 和 key6。因为旧的还有线上数据，就是 ”defalut” 列族的，还不能被删除。只有当用户最初决定把 ”default” 列族的数据落盘，旧的 WAL 能力被归档，而后主动从磁盘上删除。
总的来说一个 WAL 文件会在以下机会被创立：
DB 关上的时候；
一个列族落盘数据的时候。
一个 WAL 会在他持有的所有列族的数据的最大申请序列号落盘后被删除（或者归档，如果容许归档），换句话说所有的 WAL 里的数据都被固定到 SST 文件。归档 WAL 会被移到一个独立的地位，而后再从存储设备上革除。理论的删除动作可能会因为拷贝的起因被延后。
1.4 WAL 配置
这些配置能够在 options.h 中找到。
DBOptions::wal_dir：用于设置 RocksDB 存储 WAL 文件的目录，这容许用户把 WAL 和理论数据离开存储（云溪数据库默认两者保留在同一个目录）；
DBOptions::WAL_ttl_seconds,DBOptions::WAL_size_limit_MB：这两个选项影响 WAL 文件删除的工夫。非 0 参数示意工夫和硬盘空间的阈值，超过这个阀值，会触发删除归档的 WAL 文件（云溪数据库中默认 0）；
DBOptions::max_total_wal_size：如果心愿限度 WAL 的大小，RocksDB 应用其作为列族落盘的触发器。一旦 WAL 超过这个大小，RocksDB 会开始强制列族落盘，以保障删除最老的 WAL 文件。这个配置在列族以不固定频率更新的时候十分有用。如果没有大小限度，如果这个 WAL 中有一些十分低频更新的列族的数据没有落盘，用户可能会须要保留十分老的 WAL 文件（云溪数据库中默认 0）。
DBOptions::avoid_flush_during_recovery：选项名曾经阐明了他的用处（复原过程中防止落盘）（云溪数据库中默认 false）；
DBOptions::manual_wal_flush：决定 WAL 是每次写操作之后主动 flush 还是纯人工 flush（用户必须调用 FlushWAL 来触发一个 WALflush）（云溪数据库中默认 false）；
DBOptions::wal_filter：通过改参数用户能够提供一个在复原过程中解决 WAL 文件时被调用的 filter 对象（云溪数据库中默认 Disabled）；
WriteOptions::disableWAL：如果用户依赖于其余写日志形式，或者不放心数据失落，该参数就十分有用了（云溪数据库中默认 false）。
1.5 WAL 过滤器
事务日志迭代器提供一种办法，用来在 RocksDB 实例间复制数据。一旦一个 WAL 因为列族被落盘而被归档，WAL 不会马上被删掉。这是为了容许事务日志迭代器能够持续读取 WAL 文件，再发送给从节点。事务日志迭代器提供一种办法，用来在 RocksDB 实例间复制数据。一旦一个 WAL 因为列族被落盘而被归档，WAL 不会马上被删掉。这是为了容许事务日志迭代器能够持续读取 WAL 文件，再发送给从节点。
Part 2 – WAL 的实现
2.1 etcd[5]
etcd 整体架构如下图所示：
etcd 的写申请流程大抵能够总结为如下过程：1）首先 client 端通过负载平衡算法抉择一个 etcd 节点，发动 gRPC 调用；2）而后 etcd 节点收到申请后通过 gRPC 拦截器、Quota 模块后，进入 KVServer 模块；3）KVServer 模块向 Raft 模块提交一个提案；4）随后此提案通过 RaftHTTP 网络模块转发集群中各个节点；5）通过集群少数节点长久化后，状态会变成已提交；6）etcdserver 从 Raft 模块获取已提交的日志条目，7）传递给 Apply 模块；8）Apply 模块通过 MVCC 模块执行提案内容；9）更新状态机。
在流程 5 中，Raft 模块收到提案后，如果以后节点是 Follower，它会转发给 Leader，只有 Leader 能力解决写申请。Leader 收到提案后，通过 Raft 模块输入待转发给 Follower 节点的音讯和待长久化的日志条目，日志条目则封装了提案内容。etcdserver 从 Raft 模块获取到以上音讯和日志条目后，作为 Leader，它会将 put 提案音讯播送给集群各个节点，同时须要把集群 Leader 任期号、投票信息、已提交索引、提案内容长久化到一个 WAL（Write Ahead Log）日志文件中，用于保障集群的一致性、可恢复性。
上图是 WAL 构造，它由多种类型的 WAL 记录程序追加写入组成，每个记录由类型、数据、循环冗余校验码组成。不同类型的记录通过 Type 字段辨别，Data 为对应记录内容，CRC 为循环校验码信息。WAL 记录类型目前反对 5 种，别离是文件元数据记录、日志条目记录、状态信息记录、CRC 记录、快照记录。文件元数据记录蕴含节点 ID、集群 ID 信息，它在 WAL 文件创建的时候写入；日志条目记录蕴含 Raft 日志信息，如 put 提案内容；状态信息记录，蕴含集群的任期号、节点投票信息等，一个日志文件中会有多条，以最初的记录为准；CRC 记录蕴含上一个 WAL 文件的最初的 CRC（循环冗余校验码）信息，在创立、切割 WAL 文件时，作为第一条记录写入到新的 WAL 文件，用于校验数据文件的完整性、准确性等；快照记录蕴含快照的任期号、日志索引信息，用于查看快照文件的准确性。
WAL 模块又是如何长久化一个 put 提案的日志条目类型记录呢？首先看看 put 写申请如何封装在 Raft 日志条目外面。上面是 Raft 日志条目标数据结构信息，它由以下字段组成：Term 是 Leader 任期号，随着 Leader 选举减少；Index 是日志条目标索引，枯燥递增减少；Type 是日志类型，比方是一般的命令日志（EntryNormal）还是集群配置变更日志（EntryConfChange）；Data 保留述的 put 提案内容。
理解完 Raft 日志条目数据结构后，再看 WAL 模块如何长久化 Raft 日志条目。它首先将 Raft 日志条目内容（含任期号、索引、提案内容）序列化后保留到 WAL 记录的 Data 字段，而后计算 Data 的 CRC 值，设置 Type 为 Entry Type，以上信息就组成了一个残缺的 WAL 记录。最初计算 WAL 记录的长度，程序先写入 WAL 长度（Len Field），而后写入记录内容，调用 fsync 长久化到磁盘，实现将日志条目保留到长久化存储中。当一半以上节点长久化此日志条目后，Raft 模块就会通过 channel 告知 etcdserver 模块，put 提案曾经被集群少数节点确认，提案状态为已提交，能够执行此提案内容了。于是进入流程 6，etcdserver 模块从 channel 取出提案内容，增加到先进先出（FIFO）调度队列，随后通过 Apply 模块按入队程序，异步、顺次执行提案内容。
[1] https://zh.wikipedia.org/wiki…
[2] https://en.wikipedia.org/wiki…
[3] https://en.wikipedia.org/wiki…
[4] https://rocksdb.org.cn/doc/Wr…
[5] https://github.com/etcd-io/et…