本任务连接复制修复路线。下载标准库参考器,普通Python和python -O分别运行,比较stdout JSON。它不接触实际节点或磁盘;稳定提交与崩溃是明示的模型动作。
你要区分三项证据:本次写已有多少物理持久者、哪一份hint可以安全退场、哪两份快照的信息已被吸收。三个成功标志不互相替代。
一、先把两份响应集合写出来
固定A/B/C/D/E/F,首选按此顺序,家副本H={A,B,C},N3、W2、R2。键3初为版本0/old。版本7/v7写入时只有D/E/F可达,三个替补分别代A/B/C。
D先持久保存hint7,重复两次D的ACK仍只有一个物理身份,不能完成W2。E也持久保存并确认后,写返回;F的消息尚未完成。随后只从A/B读,仍获得0。
交出替补写的两集合:写确认{D,E}、后继读响应{A,B}。它们交集为空;4>3不是错误算式,错误是把六节点中的集合当成同一三节点宇宙里的quorum。别把未交付F或重复D计成额外成功副本。
把D的ACK换成“仅进入易失暂存”重做预测。正确接口没有这种持久ACK;如果强行计入,掉电后该份数据可以消失。未完成写不等于远端均未生效,也不能用一次超时替代结果查询。
二、交接7时,写9可以继续到来
从D持有(home=A,key3,tag7)开始,逐步填写:
| 步骤 | A的稳定版本 | D的稳定hint | 应做什么 |
|---|---|---|---|
| A仅暂存交接7后崩溃 | 0 | 7 | 不确认,保留hint |
| 重试7在A稳定提交,ACK丢失 | 7 | 7 | 可以再发7 |
| 第三次7产生ACK,ACK在途 | 7 | 7 | 重复合并无副作用 |
| D收到并稳定保存9 | 7 | 9 | 当前责任提升为9 |
| 旧ACK7到D | 7 | 9 | 身份不符,不删除9 |
| A稳定吸收9并回匹配ACK9 | 9 | 9 | 可以提交退场 |
| D稳定删9后双方重启 | 9 | 无 | 交接证据仍在A |
分别模拟D在退场提交前、提交后崩溃。前者留下重复待发责任,后者已经有A的持久下界;不能出现仅因本次删除而让双方都没有9的窗口。
再令A先有11,D重送9。A仍为11,但可以ACK“至少9”;这份ACK可让相同hint9退场。不是非要接收者覆盖成更旧值才算交付。
篡改ACK的接收者、epoch、键或内容身份,必须拒绝或判为陈旧。多个版本的hint可按每键最大值合并,是因为本任务选择LWW;多值冲突不能先丢其余版本再假称复制完整。
三、逐坐标找到三片差异桶
独立开始范围修复,不用上一小节已变成11的数据。范围[0,16)、树深3,叶号i覆盖键2i和2i+1。A/C同epoch并冻结:
A: 0:(1,a), 3:(2,c), 8:(4,h), 14:(6,n)
C: 0:(1,a), 3:(1,old), 9:(3,i), 14:(7,DELETE)
叶1、4、7不同,其余对应叶相同。先手画树,写出实际深度优先比较坐标:
(3,0), (2,0), (1,0), (0,0), (0,1), (1,1),
(2,1), (1,2), (0,4), (0,5), (1,3), (0,6), (0,7)
13个坐标中的相等停止点为(0,0)、(1,1)、(0,5)、(0,6)。其中(1,1)一次跳过叶2和3,因此不是把八片叶逐个扫一遍。h3、d3的粗界1+2dh=19,整树界15,实际13均与公式相容。
本地已保存树时,取得13个远端SHA256摘要,共416字节。三片差异桶双向传送六条记录出现次数;每份桶有4字节记录数,每条记录固定头为4+8+1+4=17字节,六条payload长度合计7,所以这些桶内容共6×4+6×17+7=133字节。416和133都没有包含会话/坐标字段、请求头及其他网络开销。
按完整编码计算,两旧快照根分别为:
A: cdd1c02a9347b60260368a82b57f95e9b3bfb2895bd1e1114d26ce11bd956c0f
C: 7787903021d63e96d2d244c5a096c514367c8b16bb1f03ba24be1e127b49d407
逐键取较大版本后,两端完整记录相同:0/1、3/2、8/4、9/3,以及14的删除7。可见键只有0、3、8、9。不要把保留的删除记录漏出校验输入。
四、快照完成与当前数据相等的反例
重建同样两快照,但在开始下探前,A的活动表把键3写成9/new。本轮所有树回答仍来自旧快照;A收到C的旧3/1后保留9,C收到A快照的3/2后升到2。
所以第一轮返回SNAPSHOTS_ABSORBED时,A/C当前键3仍为9与2。这个出口是真的:两份快照中的信息都已吸收;“两活动表现在相同”却是假的。
再取新快照,只差叶1,访问(3,0)、(2,0)、(1,0)、(0,0)、(0,1)、(1,1)、(2,1),共7个节点对。第二轮C才到9,完整状态相等。把第一轮安装写成“把旧快照整份赋回A”的错误版本,会让9倒退成2,应立即被版本单调性检查发现。
五、三种失败不是相等
- 根来自C快照s₁,孩子回复却标s₂:身份不符拒绝,即使各自都是正常生成的消息
- 将叶1的完整记录当作叶4回复:桶位置、原键范围及重算摘要均需匹配,不能只相信payload字段
- 把C改成四键一桶,或改成员epoch,再比较空树或根:先拒绝描述符不一致,不等到内容比较才猜含义
从C中直接删掉14的删除记录,再修复,会让A带来的旧14/6成为赢家。解释这是删除证据丢失,而不是哈希算法漏报:缺键没有表达“禁止旧版本回来”。本任务保留墓碑,安全回收另按已有成员/稳定前沿合同。
最后换成d0单桶:只比一次根,但若不同就传整个范围内容。这个迁移展示定位开销与实际数据流量的区别,不能从一份摘要判断总代价常数。
六、交付证书与实际费用
提交两份物理响应集合、操作ID去重结果、暂存/稳定/ACK/退场的全部窗口、旧ACK7与新hint9、两快照根和13坐标、完整六记录字节账、活动新写反例及第二轮7坐标。
还须说明:首选表扫描按P收费;H个hint的批量重试按H收费;构树先排序/扫描节点源表n项,并支付L片空桶及编码字节B;已有树上的比较按C收费,差异桶传完整内容。快照复制、审计排序和持久存储步骤都不能由“只发一个根”省略。
本例使用固定诚实身份、可靠稳定存储接口和每键总序合并。网络可以丢失、重复、乱序;永久分区、全部持有者永久丢盘、跨epoch重配置,以及真实业务并发冲突解决都需要另外的合同。有限Python核验不替这些假设提供认证。