“对已应用位置a,服务恢复状态应是同一已提交前缀的业务状态、请求结果表和应用索引。只恢复余额却丢去重,或只恢复位置却漏业务,都可能在一次重试后破坏刚才的历史映射。快照安装把截点索引/任期、结果…”
形式陈述
本页选用Raft原论文§6的联合配置算法,允许一次加入或移除多个成员;不混用另一套单成员变更算法。节点身份稳定且不复用,故障为crash-recovery;配置变化也要遵守Raft的任期、投票、日志新旧和持久化规则。配置由日志记录,管理者不能各自修改一份本地成员清单就宣称完成重配置。
设旧配置为O、新配置为N,单配置quorum的多数谓词为majority(X,Q) := |Q∩X| > |X|/2。过渡配置J=(O,N)的quorum条件是
joint(Q) := majority(O,Q) AND majority(N,Q)。
它同时用于选举和日志提交;不是对O∪N只数一次过半。复制目标为两者并集,共有成员的一份确认可以分别计入旧、新两次计数,但同一配置内不能重复计票。
协议按顺序推进:先让新增节点作为不投票的学习者追赶;leader追加J;J本身按联合多数提交;确认J已提交后,才能追加纯新配置N;N按新多数提交后,旧配置中被移除的节点才可作为完成移除来停用。每次只进行这一项配置变更,未完成时拒绝再嵌套另一项。
关键生效规则是:节点一旦把配置项加入本地日志,就在此后选举与提交判断中使用其日志最新配置,不等业务状态机应用,亦不等待自己获知该配置已提交。若未提交配置项被合法覆盖,有效配置退回日志中仍保留的最新项;它不是一个只增不减的独立缓存。压缩后还必须从快照配置和保留后缀共同恢复它。
直觉
旧配置的多数只保证与旧多数相交,新配置的多数只保证与新多数相交。两个成员列表虽然共享一些节点,某个旧多数仍可能完全避开某个新多数。联合阶段让每次决定都同时带上两边的证据,从而在交接期间没有一段时间允许两套配置各自独立决定。
联合多数和日志继承缺一不可。集合交点提供“见到旧证据”的地方;任期、日志新旧和领导者完整性保证不能绕过那份证据。把两组确认收齐但允许选举时丢掉联合配置,仍然没有完成安全交接。
例子与边界
3换3,交集非空仍会分叉
旧配置O={A,B,C},新配置N={C,D,E}。两套配置共有C,但旧多数{A,B}与新多数{D,E}不相交。若直接切换本地清单,分区左侧A、B仍以O选主,右侧D、E以N选主,两边各有“二票多数”,可在同一槽位确认不同值。这不是Raft本身允许的执行,而是错误成员变更规则破坏了它的共同配置前提。
联合阶段中:
{A,B}在旧侧有2票、新侧0票,失败{D,E}在旧侧0票、新侧2票,失败{A,C,D}旧侧A/C两票,新侧C/D两票,成功{A,B,D}虽然是五节点并集的3/5多数,新侧只有D一票,仍失败{A,B,D,E}没有C也满足两侧各2票,所以共有节点C不是必需的“中心”
按两条日志完成交接
A是任期7的leader,旧配置有效。D、E先复制到索引20但还不投票。A追加索引21的J=(ABC,CDE),自己立即改用联合规则。收到A、C、D对21的持久确认:旧侧2/3、新侧2/3,而且21属于任期7,因此21可以提交。
接着A才追加索引22的N=CDE,改用新配置规则。C、D对22给出两份持久确认,满足新2/3,22提交。A虽已被新配置移除,交接期间仍可负责把该配置复制完成,但不把自己算进新多数;完成后退位,之后由新成员按规则选主。不能因为22只有A和C确认就认为够了:A不是N的投票者。
leader恰在中间崩溃
若21尚未提交,系统可能仍选出只含旧配置的leader,并合法覆盖未提交21,也可能选出携带21的联合leader;这时绝不能创建纯N配置,所以新侧无法单独行动。若21已经提交,领导者完整性迫使未来leader含有21;没有后续合法N条目前,它必须遵守联合多数。若22已在某些节点出现但未提交,可能出现J与N并存,但每个J quorum和N quorum都在新侧多数相交,日志继承继续传递证据。
这些说明交接安全所需的衔接,不替代完整Raft领导者完整性证明。把21的提交条件改成“旧多数就行”,上述关键结论不再成立。
推论与应用
对于任意联合quorumQ_J,它与每个旧多数都在O内相交,与每个新多数都在N内相交。这描述的是决定证据的衔接,不是说所有副本只能同时持有两种相邻版本。沿上例让21先存到A/C/D/E并由A/C/D确认提交,再把22存到A/C/D并由C/D确认提交;此时B仍只有O,E仍只有J,A/C/D已持N,三种本地版本合法共存。可是21已经提交后,缺少它的旧候选者不能绕过日志新旧限制再获得有效多数;22的决定又经新侧交点继承21。先提交J再生成N及最新日志配置规则阻止的是旧、新两边越过这份证据独立作出冲突决定。它没有要求慢节点瞬间更新,也不允许并行发起互不知晓的配置变更。
联合阶段未必保持原来的可用性。在ABC到CDE的例子中,只有A、B可达虽然足以满足旧多数,却不能推进J;只有C、D可达足以满足新多数,却仍缺旧侧第二票。需要分别检查两边可达性,而非把“旧三副本容忍一个故障”原样搬到整个变更窗口。学习者追赶主要减少可用性空档,不能代替quorum证明。
旧节点收到“你被移除”的通知之前可能不断超时竞选。原协议还有防止被移除节点打断有效leader的处理;本页不把反复升任期造成的活性问题误写成可以忽略的运维细节,也不提供强制改票数的恢复捷径。永久丢失quorum后的数据丢失型重建是另一项管理承诺。
稳定网络下一次变更至少依次完成J和N两个配置提交,追赶的数据量由新节点缺失日志或快照决定。控制消息为每阶段O(|O∪N|)量级,必要确认等待由较慢的那一侧多数决定;状态传输字节不能藏进常数。成员交接和外部资源fencing也不同:Raft新配置完成,不会自动撤销旧进程对另一个存储系统的写权限。