本系列是在实现了绝大部分raft论文中描述的功能之后实现过程中遇到的问题，设计的决策等的记录。随着功能的增减，项目的逐渐完善，系统中的实现笔记可能会有偏差，但是基本上对于第一次实现或者想要理解raft的人来说可以作为一个参考。

本篇是针对0.1.0版本xraft，0.1.0之后的版本可能会有所变化。

日志复制是raft算法最基础的部分，实验性质的话用内存日志（xraft中的MemoryLog）就可以了，实际中采用基于文件的FileLog。

XRaft中的日志文件主要有3个

1. entries.bin
2. entries.idx
3. service.ss

分别是日志条目，日志条目索引，服务的snapshot文件。除此之外，每次重新生成snapshot之后，原有日志文件保留，生成一个新的log generation（目录）包含以上三个文件。log generation的名称中包含snapshot的last index，具体可能为

• log-0
• log-100
• log-1000

特殊的，新启动的xraft节点，会自动创建第一个log generation，即log-0。已有log generation的节点在启动时会自动选择last index最大的log generation作为存储位置。

为了防止新的log generation生成途中出现错误导致之后节点无法启动或运行，除了log-0之外，所有log generation都是在生成完之后重命名目录而来的。具体的步骤

1. 在installing或者generating目录中生成snapshot，并复制日志条目
2. 重命名installing或者generating目录为log-xxx
3. FileLog内部切换日志条目和snapshot的指向

这里installing是在收到来自leader的InstallSnapshotRpc之后用来存放数据的位置，generating是节点自身在生成snapshot时存放的位置。

通过重命名目录，可以达到以下目的

• 不会出现生成中途的log generation
• installing或者generating时出错不会影响现有日志
• installing或者generating完成之后目录不存在也就不影响下一次的installing或者generating
• 启动时如果installing或者generating存在，说明上一次生成snapshot未成功，需要删除（现阶段xraft未处理）

小结一下，xraft中生成snapshot时会新开辟一个log generation，具体是installing或者generating中生成然后重命名为一个新的log generation，保证安全处理。

BTW，现在对早期的log generation没有删除机制，如果要做的话，个人考虑是最少保留3个generation，定时或者异步执行。当然，通过cron+shell也可以做到。

接下来是日志文件的具体内容

entries.bin和entries.idx组合成日志条目序列，即xraft内部的EntrySequence。对于这两个文件，专门有两个类，EntriesFile，EntryIndexFile处理如何读写。简单来说，entries.bin单纯是日志条目的顺序存储，entries.idx则是日志条目的元信息和存储的偏移。分成两个文件的原因是raft算法中主要参与逻辑的是日志的元信息，日志条目的内容只有在catch up新节点或者日志条目冲突回退nextIndex时才被使用到。实际xraft运行中会全量加载entries.idx，但是entries.bin只有在需要的时候才会通过RandomAccessFile加载相关的内容。

日志条目结构

[(kind, int, 4) (index, int, 4) (term, int, 4) (command length, int, 4) (command, byte[], ?)] * n

如果通过hexdump看entries.bin的内容的话，就是上面这种条目的顺序表示。运行过程中，entries.bin只有两种操作

• append(Entry)
• truncate(position: long)

即commit日志条目和删除冲突的条目。后者的position由entries.idx管理。注意这里没有checksum，之后可能会增加。

日志索引结构

(min entry index, int, 4) (max entry index, int, 4)
[(entry offset, long, 8) (kind, int, 4) (term, int, 4)] * n

首先是起始条目index和结束条目index。注意，xraft对于entries.idx的空文件有额外处理：认为没有日志条目而不会尝试去读取起始和结束的index，因为下一个日志条目的index可以通过snapshot的lastIndex得到。

接下来是除去index之外日志条目的元信息和日志在entries.bin中的偏移。日志的元信息中xraft使用了一个叫做kind的字段，用来区分no-op，正常日志和group config变更日志。通过这个kind，在节点启动时，可以立马筛选出所有group config（集群配置）变更而不是遍历全部日志条目即entries.bin。

这里讲一下日志条目在commit过程中，文件部分怎么处理。

首先在日志处理中有一个pendingEntries（具体在FileEntrySequence），新增但是尚未commit的日志会追加到pendingEntries的末尾。commit时，从pendingEntries中取出相应的日志条目，追加到entries.bin并更新entries.idx的内容和缓存。

BTW，估计你也猜得到，pendingEntries会是一个链表。

接下来是snapshot文件的结构。

(header length, int, 4) (header, bytes[], ?) (data, byte[] ?)

由于snapshot存储了group config（集群配置），所以手写读写的代码比较繁琐，这里使用了protocol buffer来生成snapshot header的二进制表示。snapshot header里面包含的内容

• last term
• last index
• group config(Set<NodeEndpoint>)

至于snapshot的内容的话，由于是上层service生成，这里只是记录内容，并没有在内容前加data length之类的字段。之后加载时，data的长度可以通过文件长度减去头部来得到。

由于InstallSnapshotRpc会随机读取data的内容，所以snapshot的读取也依赖于RandomAccessFile。同时考虑到data数据比较大，运行中只会加载snapshot的头部，在生成InstallSnapshotRpc时才会读取部分的data部分。

设计上snapshot一旦生成不会有修改，所以FileSnapshot只有读操作。

代码结构上EntriesFile和EntryIndexFile构成FileEntrySequence，FileEntrySequence和FileSnapshot构成FileLog。

至此，xraft的日志存储的介绍基本完成，如果对于如何实现FileLog和FileEntrySequence感兴趣，欢迎阅读源代码。

另外，由于日志是基础部分，测试很重要。但是涉及文件的测试容易出问题，实际测试中（FileEntrySequence等的测试），抽象化RandomAccessFile，即抽取用到的方法做了一个SeekableFile的接口，然后使用了基于内存的代替。

最后，对于xraft有任何疑问和改进意见，欢迎留言，或者在github上pull request也好，开ticket等提供建议。