Skip to content

会话读取终结任务:迁移收据与两轮版本账本 ​

沿会话迁移与多键读取路线,交两份独立初始化的记录。第一份证明客户端换副本时没有遗忘所需历史;第二份证明一次多键结果自身满足依赖。向量分量、单键版本和逻辑顺序标签分别编号,不能看它们恰好都是小整数就混用。

下载标准库核验器,运行以下任一命令,JSON只写到标准输出:

text
python foundation-session-read-check.py
python -O foundation-session-read-check.py

第一份:三个副本、两个会话令牌 ​

固定A/B/C三个来源及同名完整副本,向量分量依次为A、B、C。所有初始前缀为000,客户端R=W=000,启用RYW、MR、MW、WFR。业务键x、y、z初始不存在。

每个写身份为(来源,来源序号)。每来源从1起连续产生写;一条消息到达时,只有来源下一号且dep≤F才公开,否则WAIT。每次本地成功写复制当前F为dep,并生成大于本节点所知标量的逻辑标签;同键按(标量,来源)最大者解释。

从自己的写到另一台机器 ​

操作 目标副本操作前F 下界L 结果 操作后R 操作后W
A写a1:x=draft 000 000 成功,A100 000 100
B读x 000 100 INCOMPLETE 000 100
B已接收a1,再读x 100 100 返回draft 100 100
B写b1:y=reply 100 100 成功,B110 100 110
C已有独立c1,主会话请求写z=done 001 110 INCOMPLETE 100 110
C补齐a1/b1后,再写c2:z=done 111 110 成功,C112 100 112
A读z 100 112 INCOMPLETE 100 112
A补齐b1/c1/c2后,再读z 112 112 返回done 112 112

表中c1是另一个客户端在C的独立写z=side,发生于b1之前或之后都不改变它与a1的独立性。C已应用c1不表示主会话读过它,主会话R在该行仍100。

四条业务写的记录为:a1的dep000、逻辑标量1;b1的dep100、标量2;c1的dep000、标量1;c2的dep111、标量3。c2把z从side改成done,因果覆盖和最大顺序选择一致。c1与a1标量相等并不等于同一写,来源区分身份。

先收到回复,仍不能先公开回复 ​

在C001时先投递b1,来源B确实是下一号1,但dep100尚未满足,所以返回WAIT。C不能把F直接改011。先应用a1变101,再重试同一b1,才变111。重复应用已存在的相同身份返回DUPLICATE;修改该身份的内容则拒绝。

这里有两个不同不足:客户端向C写时缺少会话令牌下界,复制消息b1向C公开时缺少写依赖。只修第一种入口、却让后台复制直接覆盖值,仍不能给会话外观察者保证MW/WFR。

交付时逐项列出每次INCOMPLETE之前与之后的R/W、F及写历史大小,确认拒绝没有产生本地副作用。这是已到服务器准入门的明确结果;网络RPC超时后的未知结果不在这份本地模拟里。

四种缺门的最小反例 ​

分别重新初始化,每次仅关闭一个保证,其他三个保持开启:

  • 关闭RYW:主会话在A写x=1,然后在B读到不存在。R还没增长,MR挡不住
  • 关闭MR:别人先在A写x=1,主会话读到它,再到B读不存在。主会话W始终0,RYW挡不住
  • 关闭MW:主会话在A写新库,再在未同步的B写依赖新库的程序;C只接收B写便可看到程序却没有库。此前没有读,所以WFR没有下界
  • 关闭WFR:主会话在A读原帖,再在B写回复;C只接收回复便可先看到回复。此前没有本会话写,所以MW没有下界

这四份执行在公开JSON中分别给出true的失败标识。应能解释哪项令牌为何为空,以及第三观察者为什么需要传播门;不必把同一例子的变量名换四遍。

第二份:精确补到2,而不是顺便取3 ​

重新初始化单集群的两个键x/y;每键单写者,初始0版为空。依次公开x1=public、y1=old,二者没有非零跨键依赖。版本号只在自己的键内计数,与第一份来源序号是另一套命名空间。

首轮冻结要补的目标 ​

请求集K={x,y}。首轮先读x1并原子登记pin(x)=1。随后公开x2=private,再公开依赖x2的y2=personal。首轮读y2并登记pin(y)=2,得到第一批结果(x1,y2)。

x2的完整依赖为{x:1};y2为{y:1,x:2}。将首轮实际版本和所有完整依赖在K内取最大值,得到目标t={x:2,y:2}。只需要第二轮get-exact(x,2),不用再读y。

新写不能改掉这张目标表 ​

在精确补读前,公开y3=sanitized;它继承y2的前驱,完整依赖为{y:2,x:2}。再公开x3=public并让它依赖y3,完整依赖为{x:2,y:3}。

正确算法仍返回x2=private与y2=personal。若把第二轮替换为latest(x),会得到x3和旧y2,违反x3所要求的y≥3。这是一个真实改变依赖的迁移,不只是把2换成3重新算一次。

要求列出第二轮版本x2为何没有额外要求:它的全部前驱已经包含在首轮y2的完整dep中。一般情形也是如此,每个次轮目标都来自某个首轮结果的实际依赖,不是临时猜测或尚未产生的版本。

精确版本的保留账本 ​

当前已经到x3/y3时运行GC。两个活跃pin分别为1和2:

阶段 x的保留前沿 x可以删 y的保留前沿 y可以删
事务仍在第二轮 1 0 2 0、1
结果返回并释放pin 3 1、2 3 2

第一行不能删除x2,尽管x3已经存在。第二行是接着第一行执行的删除列表,因而不会重复列已经删掉的0。关闭后各键只剩当前3版。

如果故意违反存储合同,在需要x2时把它删掉,参考器返回RETRY,保持原客户端上下文不变并释放已取得的pin。不要用x3补洞。显式取消也不更新上下文;即使目标历史值仍在,用旧句柄发起迟到exact仍会被拒绝。

第三份迁移:最近依赖与完整闭包 ​

重新初始化x/z/y各1版为old。首轮先读x1、z1。随后公开x2=new、依赖x2的z2=middle,以及依赖z2的y2=result;首轮最后读y2。

只看最近依赖时,y2只告诉你补z2,第二轮拿到z2才发现还缺x2,得到x1/z2/y2并不一致。完整dep(y2)为{y:1,z:2,x:2},首轮一次就算出x2/z2/y2;第二轮的两个精确请求并行完成,返回new/middle/result。

若请求集合改成仅{y},返回y2不必附带x/z的业务值;它们的存在由集群依赖先公开的合同负责。不能把“结果没有返回x”误判成丢失依赖,也不能在没有该集群合同的任意数据库上套用同一结论。

验收与成本 ​

会话部分交出全部本地前缀和R/W变更、明确拒绝与WAIT、四个缺门执行。可再把成功读返回的完整F改成一个已证明充分的相关写子集,说明可用性为何可能提高;没有相关写证据时不允许凭直觉删分量。

多键部分交出首轮值与完整依赖、固定目标、精确次轮结果、pin/GC/取消账本。对每个返回键y和也被请求的前驱键x,检查版本不小于dep(y)[x]。空请求集合返回空对象,不申请pin;输入重复键拒绝。

两轮最多2k个读取请求,客户端目标计算期望O(1+k+D)。最终结果的D′条依赖、已有上下文U项另付O(1+k+D′+U);示例释放和GC还扫描当前P份pin,GC另扫该键V份版本。两个m维会话令牌的O(m)空间、每键历史字节、依赖元数据和审计JSON分别计入,不把某一项小界套到全部系统。

这些轨迹模拟原子本地接口与合法消息,未实现可靠存储、网络认证或超时回收。无故障处理完成条件与真实网络延迟上界不同;有限测试通过也不构成对一个生产协议的认证。