Skip to content

算法Algorithm

Raft快照、日志压缩与安装

Raft snapshot installation · Log compaction snapshot · InstallSnapshot

以同一前缀的业务状态、请求结果、配置和索引任期构造恢复包,明确稳定发布、后缀保留和旧快照拒绝条件。

形式陈述 ​

Raft日志压缩删除的是已被另一份完整恢复证据覆盖的物理记录,不能删除已经提交的历史含义。设已应用到k的复制服务状态为S_k。一份快照是

Snap(k,t,S_k,D_k,C_k),

其中t为日志第k项的任期,D_k为会话与结果表,C_k为截至k的配置证据。会话身份分配器、过期状态、业务内待发送outbox等凡会影响后续确定性转移的字段都属于快照内容。k <= lastApplied <= commitIndex;只见到日志却尚未应用,不能声称对应业务快照已生成。

本页采用非拜占庭crash-recovery模型,持久层提供可恢复的原子“发布一代快照根”接口;它可以由校验加双根槽、稳定影子根、持久事务或其他已经验证的方案实现。未发布的临时文件可能部分写入;崩溃后只能选择完整旧代或完整新代。具体文件系统同步责任见稳定存储顺序,这里不把一次普通rename自动当成掉电原子提交证明。

生成快照的顺序是:在同一应用截点取得各字段;写完并稳定新快照及元数据;原子发布并稳定它作为可恢复根;最后才允许回收覆盖到k的日志和旧快照。并行生成可用不可变版本或写时复制,但不能边读变动的业务表、边读取另一个时刻的结果表。

安装时先核对RPC任期和快照完整性,分块下载只是暂存,最后一块到达也不等于已经安全发布。若k <= lastApplied,本页的保守接收器忽略该旧快照,不倒退业务状态;这个策略假定本地应用位置可信且单调。若k > lastApplied,则暂停本地应用,按以下规则准备新一代恢复状态:

  • 本地日志在索引k具有相同任期t,保留k+1之后的后缀;日志匹配性质保证该后缀接在同一前缀后,但它仍可能尚未提交
  • 边界索引或任期不匹配,丢弃本地不相容尾部,由leader以后重新发送;正确Raft执行中不能丢弃一个与快照冲突的已提交历史
  • 原子发布快照状态、会话表、截点元数据及后缀选择;恢复后令应用位置为k,commitIndex至少覆盖k,再只应用已获提交证据的后续项

当前任期和投票记录属于Raft安全状态,不能随快照回滚;快照边界任期t也不是当前任期。

直觉

快照好比把前十一步计算压成一份带页码的结算单。余额是结算结果,结果表说明哪些请求已结算,索引与任期说明下一条日志应从哪里衔接,配置说明接下来该听谁的投票。只保存余额,就像撕掉所有收据却忘了哪些付款已经记账。

快照还区分三件事:生成者形成一致视图,接收者拿到完整字节,接收者把它发布为恢复入口。下载到99%不能替换当前状态;先删日志、再慢慢保存结算单,会在中途崩溃时两份证据都丢失。

例子与边界

同一个110,可能藏着不一致截点 ​

初始索引10余额100。索引11为(s,1,add(10)),应用后余额110,结果表保存(s,1)->110。索引12是相同请求的重复项,仅推进应用位置。正确快照12写B=110,a=12,D[s]=(1,add(10),110);以后再来同请求仍返回110。

错误快照若写B=110,a=12,D为空,重新注册或错误恢复会让该请求再加10;若写B=110,D为序号1,a=10,重放逻辑若无正确去重也可能重复作用。即使某种碰巧保住结果表的实现能挡住这一次重放,恢复位置与状态仍不对应同一前缀,不能据此宣布快照正确。

边界匹配才保留后缀 ​

接收者C已有(11,term5),(12,term5),(13,term6),其中只应用到10。收到Snap(12,5,...)时,索引12任期相同,保留13;恢复从快照12开始,只有得到13的提交证据后才应用13。它不是因为“文件里有13”就能执行。

若C的12是任期4,和快照任期5不同,则旧13也不能保留,因为它接在另一个前缀之后。收到快照后丢弃该未提交尾部;新leader重发它真正认可的13。若接收者已应用到14,再收到12的旧快照,本页接收器直接忽略,不能把余额和结果表倒回12。

同一截点与持久发布顺序

在三个窗口掉电 ​

窗口A:新文件只写一半。恢复仍选旧快照和旧日志。窗口B:完整新快照已稳定,但根尚未发布。仍可选旧代,临时新代可丢弃。窗口C:新根已稳定,随后只删除了一部分旧日志。恢复选新代,从k+1重放;多余旧日志可清理,不得再应用<=k。

危险顺序是先删除到12,再写快照:半文件掉电后旧快照只有10、日志11和12已无,余额无法从证据恢复。这是数据丢失,不是重试InstallSnapshot就必然可解;其他副本是否还可提供状态需要额外可用性条件。

推论与应用

恢复不变量可以写成:所选快照表示一个已提交前缀1..k,所选后缀与边界(k,t)一致,应用状态恰好等于从该快照依次执行已提交后缀至a的结果。生成时冻结同一版本建立第一项;稳定发布后再回收维持可恢复性;安装时匹配后缀且不回退应用位置维持衔接;每次只执行a+1维持顺序。

配置有双层位置:快照保存截至k的配置,但Raft决策使用本地日志最新的配置项,它可能在保留后缀中而尚未应用。安装后要以快照配置为基线,再从保留后缀恢复最新有效配置;不能把业务lastApplied当成配置生效点。具体过渡见联合配置。

设快照大小为B字节,保留后缀有m项、平均c字节,存储约为B+mc,另计未发布临时副本和写时复制脏页。全量生成和网络安装至少处理B字节,恢复还需执行m项;快照频繁会增加写放大,过稀会增加日志和重放成本。把一个GB快照塞进“一个RPC”并不会让传输成为常数时间。

本页不覆盖恶意快照、永久介质损坏、跨版本不兼容序列化或把未记录的随机/外部输入重放出来;这些必须另有验证和迁移协议。全局通道快照记录分布式一致割,本页只是同一复制状态机前缀的压缩恢复,两者不能按“快照”二字互换。

参考资料
  • Diego Ongaro and John Ousterhout,Raft论文,2014,§7、Figures12–13:边界索引/任期、配置、InstallSnapshot后缀选择
  • Diego Ongaro,博士论文,2014,§§5.1、5.1.3:客户端状态随快照保存,临时文件、稳定后发布及压缩实现问题;本文原子代际接口与三个故障窗口为教学模型
关系图谱17 个相邻概念 · 2 类关系

拖动节点调整位置。

显示关系

显示:依赖

  1. 前置三跳
  2. 前置二跳
  3. 前置一跳
  4. 当前条目
  5. 后续一跳
  6. 后续二跳
  7. 后续三跳
文字版关系按与当前条目的最短距离分组
类型化关系