Skip to content

方法Method

复制会话、请求序号与结果去重

Replicated client session · Request deduplication · Session sequence number

用显式注册会话、严格请求序号和同前缀结果表处理重试,复算响应丢失、乱序、结果回收及会话过期边界。

形式陈述 ​

RPC成功响应在没有去重合同时只证明某一次尝试完成,其他在途尝试仍可能生效。本页给同一逻辑请求加上更强的服务合同:稳定身份在重试间不变;所有尝试至多产生一次本状态机内的业务效果;在结果仍受保留合约保护时,重试可取得原结果。这不保证客户端最终收到响应,也不约束状态机之外的付款或发信。

教学协议先固定串行会话:每个客户端在得到请求q的结果后才发下一个逻辑请求q+1,但同一请求可有多份在途尝试。客户端先提交Register得到全局不复用的会话标识s,业务请求为(s,q,command),q从1严格递增。Register的重复可能多建空会话,但不执行业务;身份分配器和活跃会话集合也是复制状态。客户端在重启后若要续试,必须保留同一s,q,command,不能把一项未知业务自动换成新身份。

复制状态机在每个副本的已应用状态为(B,D,a):B是业务状态,a是应用日志索引,D[s]=(h,command_h,result_h)保存活跃会话最近完成的序号及结果。这里保存完整规范化命令以精确比较;若改存摘要,就额外承担碰撞假设。提交日志中的请求被串行应用时:

  • 会话不存在:返回SESSION_EXPIRED_OR_UNKNOWN,不执行业务,不隐式注册
  • q=h+1:执行确定性业务转移,保存该命令和结果,把h推进到q
  • q=h且命令相同:返回保存的原结果,不再执行业务;同身份不同命令返回IDENTITY_CONFLICT
  • q<h:返回RESULT_FORGOTTEN,不再执行业务;不能把最新结果错当成这个旧请求的结果
  • q>h+1:返回SEQUENCE_GAP,不执行业务;客户端须补齐前序或按已批准的另一种并发协议处理

每条已提交日志都推进a,包括重复条目和无业务效果的拒绝。一次持久恢复单位必须同时包含B,D,a,或能够从同一一致快照加日志确定性重建三者。不能把去重表当成可丢弃的leader缓存。

直觉

日志槽位与逻辑请求是两种编号。索引21和24可以装着同一(s,7)的两份尝试;Raft保证所有副本对这两个槽位内容一致,去重状态机才规定只有第一次真正改变余额。

保存结果与保存“做过”也不同。withdraw(10)最初成功并返回余额90,重试时余额可能已经是75。如果仅跳过扣款、却按当前余额生成新结果,客户端就拿不到第一次调用的输出。结果表把业务效果和它对应的答案绑在一起。

这项责任在消息传递和事务旧页已有两个相反崩溃窗口。本页不另证同一个局部结论,而把它落实为复制会话、序号状态、恢复和回收的完整协议。

例子与边界

110只出现一次业务增量 ​

初始B=100,D[s]=(0,空,空),a=10。日志11是(s,1,add(10)),应用后成为B=110,D[s]=(1,add(10),110),a=11,响应丢失。换leader后同请求重试进入日志12。再次应用只把a推到12,返回110,余额仍为110;索引12不是第二次业务操作。

客户端收到110后发(s,2,add(5)),日志13应用得115并保存序号2结果。极慢的序号1尝试到达,协议给RESULT_FORGOTTEN且不增加余额。该错误只说明旧结果已经不在本会话的一格结果槽中,不能证明序号1从未执行;客户端在串行合同下早已收到过它。

若允许同会话并发发1与2,而2先到,天真“序号大于最大已见就执行”会先执行2,再把1误判为重复,丢掉一项业务。严格h+1规则在这里拒绝2;若要支持乱序并发,须把D扩展为按序号索引的结果集合,决定业务执行顺序,并使用客户端确认的连续回收水位。maxSeen=2不等于“1和2都已执行”。

恢复必须找回同一前缀 ​

把余额110和a=11稳定保存,却完全丢失D[s],本协议会把重试拒绝为未知会话,不能再取回原结果。若错误恢复把s重新建成活跃会话且h=0,下一份序号1才会再次加10。反过来,仅保存去重结果110而业务余额仍是100,会让重试得到110但账户未入账。若余额稳定而a落后,正确结果表可能挡住这次重复效果;若结果表也落后,重放就会再次作用。无论碰巧有无重复,三者不对应同一前缀都已违反恢复不变量。

可以在一个本地持久事务中发布(B,D,a);也可以持久化完整快照,从其截点后严格重放。内存执行本身不是必须每条都落盘:若崩溃会丢弃整份内存状态,并且保留了共同持久日志和一致快照,重建后仍满足同一前缀不变量。外部副作用不能靠这种内存重建撤回。

过期是合同终点,不是“从未做过” ​

会话回收也必须是所有副本一致的状态转移,例如提交Expire(s)。每台机器各自按墙钟删除结果会令副本对同一重试作出不同执行决定。过期后,所有业务请求只查活跃集合;未知身份一律拒绝。注册只发放从不复用的新s,因此可以删除整份旧记录而无需为每个旧身份无限保存墓碑,前提是身份分配与“未知即拒绝”的规则永久保留。

若改为允许任意客户端自选旧身份并自动新建会话,这个前提就消失,必须保留拒绝旧身份所需的代际或墓碑等证据。客户端拿新会话重发一项旧的未知扣款也不受旧去重保护,应先查业务状态或按业务唯一键处理;SESSION_EXPIRED不能把未知改成“未执行”。

推论与应用

归纳不变量是:对于仍有效的s,每个已完成序号至多使B转移一次,保留的结果对应那次转移;(B,D,a)恰好来自同一已提交前缀。初始成立。首次请求同时修改业务和结果,重复请求不改业务,旧序号和gap拒绝,过期删除授权且禁止复活,因此各分支保持不变量。快照必须保存这些状态,见快照安装。

“至多一次效果”是安全性;重试最终成功还需要稳定leader、可达quorum、最终交付、客户端继续尝试,以及会话在所需期间不被过期。有限保留不能承诺无限久以后还返回原答案。业务失败也可成为已完成结果,例如余额不足后原样返回失败,而不是等账户充值后把同一身份重试改成成功。

串行协议每个活跃会话保存一条命令和结果,空间为O(S)条记录,另计payload与结果的字节长度;无限新会话会使S增长,需要显式配额、回收或拒绝注册。支持每会话w个并发未确认请求时,结果表通常增到O(Sw)条,不能保留同样的一格空间却暗中承诺任意乱序并发。

本页允许每份重复尝试进入日志以简化证明。leader可缓存命中并直接回复,但缓存必须来自可信已应用结果,且缓存缺失不能当作未执行证据。查询“是否执行过”本身也需要合法读路径;陈旧副本查不到记录时,无权保证可以重新执行。

参考资料
  • Diego Ongaro,Consensus: Bridging Theory and Practice,2014,§6.3,pp.69–72:序号/响应、并发请求集合、会话过期与显式注册;§5.1要求快照包含客户端线性化状态
  • Diego Ongaro and John Ousterhout,Raft论文,2014,§8:提交后响应丢失所致重复及结果缓存;本文严格串行序号分支、命令冲突检查和110/115轨迹为教学细化
关系图谱10 个相邻概念 · 2 类关系

拖动节点调整位置。

显示关系

显示:依赖

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