Skip to content

算法Algorithm

Raft读屏障与ReadIndex

Raft read barrier · ReadIndex · Linearizable Raft reads

用当前任期提交、新一轮多数确认及应用位置屏障排除旧leader陈旧读,比较日志读与ReadIndex的证据和成本。

形式陈述 ​

本页沿用Raft的固定投票配置、非拜占庭节点和可靠稳定存储,网络可以丢失、乱序和任意延迟。服务采用确定性状态机复制;读取必须从一个一致的已应用版本取得全部字段。目标是线性一致:若某写已成功返回、读才被调用,读不能遗漏该写在顺序规格中应有的影响。这里只做安全保证;凑不齐多数时读可以等待或返回结果未知。

最直接的日志读屏障把read(key)也作为一个日志命令提交。它按日志顺序执行,结果在执行该条目时捕获,而不是过一会儿随便读一次内存。这样读自身得到索引,沿用写的提交和应用路径,但增加日志与稳定写成本。

ReadIndex保留同样的证据而不为每次读写一条日志。leader在收到读请求之后完成以下步骤:

  1. 确认本任期至少一个条目已按Raft规则提交。新leader通常先提交本任期no-op;只赢得选举不够
  2. 记录此刻的commitIndex为读下界r,并为本轮读生成新的上下文q
  3. 发出携带本任期和q的心跳,取得本轮有效多数确认。旧轮心跳、读调用前的确认、已知更高任期的响应不能顶替它;发现更高任期就放弃此轮leader读
  4. 等待执行层lastApplied >= r,在受保护的同一已应用版本上查询,再回复结果

每个读或已到达的一批读必须关联一次在它们调用之后发起的确认;不能把刚到的新读倒挂到已经完成的旧批次上。这里的r是最低应用位置,不是要求返回恰好索引r的历史版本。执行层若已到a > r,可在状态S_a上取一致结果。

直觉

读路径需要两种不同证据。“我拥有正确日志”不能证明“我仍有权给这次读排位置”;“刚才多数回复了我”也不能证明执行线程已经处理完日志。ReadIndex分别用新一轮多数确认和应用屏障解决这两个问题。

当前任期提交把前任遗留的已提交前缀接到本leader已知的提交位置。随后的新轮确认与任何新任期选举多数相交:若在这轮探测发出前已经有更高任期leader,交点至少已有更高任期,不会提供本轮所需的有效旧任期确认。因此不能让早已失权的leader凭一份过期心跳读旧状态。

这并不表示收到最后一份确认时leader永远不会失权。它可能随后立刻被替换。线性一致只要求为这次已经开始的读找到合法位置,并不要求它在回复瞬间仍是最新leader。若实现选择在失权时取消未回复的读,也应明确这是更保守的处理。

例子与边界

旧leader为什么能读错 ​

三副本A、B、C起初都在索引10,x=0,A是任期4的leader。先隔离A,B与C在任期5选出B;B把索引11的set(x,1)复制到B、C,提交并应用,然后客户端收到写成功。此后另一客户端才向A调用read(x)。A虽然还自认为leader、本地lastApplied=10,却只能读出0。

实时顺序要求写在读之前,顺序寄存器又要求读返回1,因此没有合法线性化。A的磁盘没有损坏、旧日志完全正确也无济于事;缺的是这次读取的权限证据。A向B、C发新轮探测时,要么收不到多数,要么看到任期5,不能返回本页承诺的成功读。

有多数,还要等应用 ​

B在任期5已提交索引11,但执行线程只到10。读到达后B取r=11,本轮q=37得到B、C两票,仍不能读。应用11后lastApplied=11,x=1,才可以返回1。若把最后一步等待删掉,即使leader真实有效,仍会返回0。

下一次读与索引12的set(x,2)重叠。若读取受保护的状态11,可返回1并放在写12之前;若已应用12,可返回2并放在其后。不能读取“x来自12、另一字段来自11”的混合版本。需要锁、不可变版本或其他一致查询接口保证一次查询对应一个前缀。

读权限与应用进度是两道门

为什么本任期no-op不能省 ​

B新当选时可能有前任已提交的条目11,却暂时只知道commitIndex=10。若此刻直接取r=10,即使它刚获得多数心跳,也可能允许执行层停在10读旧值。提交本任期no-op 12会同时提交之前的连续前缀;随后r>=12,查询便不能绕过11。no-op不是修改业务数据,而是补齐leader对于提交前缀的知识。

推论与应用

把读下界记为r后,在该读调用前已完成的写都位于它必须覆盖的前缀中;一致查询至少应用到r。与读重叠的写可按查询实际采用的前缀放在读前或读后。再结合写按日志排列、每次查询只有一个前缀版本,便得到符合实时顺序的顺序历史。不能把所有读的线性化点都机械标成“最后心跳到达”:查询若包含此后才提交的并发写,见证点也要相应后移。

Follower也可代读,但要为这批新读向leader取得按上述步骤产生的r,并在本地等待应用到r;从旧心跳缓存一个commitIndex不能代替这次读的证据。成员正在变化时,本页固定多数必须替换为当前有效配置的相应quorum,不能默默沿用旧多数。

稳定leader、无丢包、已提交本任期条目的情况下,一批ReadIndex读增加一轮多数往返、O(n)控制消息及执行层追赶等待,不新增每读日志条目。日志读则另有复制payload、日志持久化和后续压缩成本。批大小为b时可把控制消息摊到每读O(n/b),但批等待会增加延迟;这些不是固定墙钟上界。

租约读用时钟和有效期代替逐批确认,必须另证时钟漂移界、暂停处理、选举和提前移交规则。普通超时配置或“机器已经对时”不是这份证明。本页的异步安全论证不依赖租约。

参考资料
关系图谱17 个相邻概念 · 2 类关系

拖动节点调整位置。

显示关系

显示:依赖

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

使用的工具