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…
发表回复