β

Raft实现笔记-日志结构

箱猫日和 32 阅读

本系列是在实现了绝大部分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,具体可能为

特殊的,新启动的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时存放的位置。

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

小结一下,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只有两种操作

即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里面包含的内容

至于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等提供建议。

作者:箱猫日和
Box Cat Happy Day
原文地址:Raft实现笔记-日志结构, 感谢原作者分享。

发表评论