“为让存储合同可执行,预先给定有限流集合 S 和每流数组界 B i;只接受 0≤o≤t≤B i。B i 是课堂实现容量,不是流最终长度,也不是对端收到的流控许可。本页暂令全部样例数据已获许可;…”
形式陈述
两层许可,两个不同的前沿
沿用独立重组的固定已认证连接,只计同一发送方向的流半部。每个流 i 维护最高已计费末端 H_i、尚未知或已知的最终长度 F_i,以及接收方授予的绝对上限 L_i;连接维护绝对总上限 C 和总账 T=ΣH_i。初态 H_i=0,F_i 未知。L_i 和 C 均以字节数计,范围不超过2⁶²−1,实际检查器还设64字节每流教学容量界。
r_i 是连续交付前沿;H_i 是最高计费末端,可以隔着缺口增长;缓存的实际字节数可以小于两者之差;应用消费位置又是另外一个量。本页信用以偏移承诺计,不按收到的包数或载荷副本数计。
接收一个 STREAM(i,o,b,fin) 时先令 t=o+len(b)。若 F_i 已知,t 不得大于 F_i;若本帧带 FIN,候选最终长度 f=t 必须不小于现有 H_i,且必须等于已经记录的 F_i(若有)。所有算术先检查非负、上限和溢出,再分配存储。令
只有 H'_i≤L_i 且 T'≤C 才能接受。通过后提交 H'_i、T',FIN 还记录 F_i=f,再交给重组接口。对一包多帧按暂存账本逐帧累计,不能每帧都拿同一个旧 T 检查。重复区间或较短区间的 Δ_i=0;同位置内容一致性仍由重组接口检查。
RESET_STREAM(i,f) 没有流数据载荷,却声明最终长度。先要求 f≥H_i、已有 F_i 时 f=F_i,再把 H'_i=f、Δ_i=f−H_i、T'=T+Δ_i 代入同一组两层额度检查。成功后 F_i=f,接收半部进入重置终态:停止新增交付、丢弃未交付缓存,保留输出历史与最终长度/总账。其余流不变。检查器选择保留终结元数据以严格检查后续矛盾;真实规范允许终态检查与状态保留作权衡,本教学模型的严格策略不等于所有实现必须无限保存每条已关闭流。
额度更新与终结合同
MAX通告沿数据的反方向传送:数据接收方授予许可,数据发送方收到 MAX_STREAM_DATA(i,l) 时将自己记录的L_i更新为max(L_i,l),收到 MAX_DATA(c) 时将C更新为max(C,c)。真实接收检查使用本端已通告上限,真实发送检查使用已收到上限;通告在途时两者可能不同。本文账本和检查器把“接收方已授予、发送方已获知”合并为一次同步许可事件,之后记录共同已知的上限,不模拟控制传播延迟。不能把本端收到的MAX直接用作本端在同一数据方向的接收预算。有效许可从不倒退。重报、重复或乱序带来的较小值无效,既不撤销旧许可,也不自动形成错误。流与连接额度分别更新:只提高一层,另一层仍可能阻止新增末端。
FIN 只给出最终长度,不保证 [0,F_i) 已完整到达。正常完成需要 F_i 已知且 r_i=F_i;空流可由 offset=0、空载荷且 FIN=true 正常完成。缺口未补时即使 FIN 已到,也不能向有序读者提前报告正常 EOF。重置则报告中断,不把缺字节补成零,也不回滚此前已经交付的前缀。
RESET 后,迟到且末端≤F_i、FIN长度也一致的旧帧只接受账本检查,不再输出或重组;超出最终末端、再次给出不同 final size 的 FIN/RESET 都由本模型报 FinalSizeError。已经正常完成后,也继续保留 F_i 检查矛盾;一致的迟到 RESET 不撤回已经交付的正常完成。这是本模型明确选择的终态规则。
本地停止读取是另一事件 stop_reading(i):可丢弃未交付缓存并请求向对端发送 STOP_SENDING,但此时未必知道 F_i。后续 STREAM 仍计入 H_i 和 T;本教学接口选择不再交付它们,直到 FIN 或 RESET 给出结算长度。不能把“我不想读”当成“对端从未发送”。
直觉
额度是两本账的上界:每条流有自己的账,连接还有一张合计账。每流账写的是最远承诺到哪个位置,不是当前桌上放着多少张纸。收到第六个位置,即使中间几张没来,也不能只按这一张纸付预算。
取消类似关闭一个已经用了部分额度的任务。可以把工作区腾出来,但仍须告诉总账这个任务最终算到哪儿。以后给其他任务更多许可,应提高总上限,而不是篡改历史支出。
例子与边界
独立的4+3信用账本
这条轨迹独立于上一页 abcd/XY 的6字节重组轨迹,不能偷偷把 XY 的长度2改成3。此处流0、4的最高末端分别为4、3,每流上限均为6,连接上限 C=8。因此 T=4+3=7,连接剩余1。虽然各流余量为2与3,全部新末端增量之和仍不得超过1。
| 事件 | H_0 | H_4 | C | T | 连接剩余 | 结果 |
|---|---|---|---|---|---|---|
| 独立初态 | 4 | 3 | 8 | 7 | 1 | 两层检查成立 |
| s0重复[2,4) | 4 | 3 | 8 | 7 | 1 | Δ=0 |
| MAX_DATA(10) | 4 | 3 | 10 | 7 | 3 | 只提高连接许可 |
| RESET s0,f=6 | 6 | 3 | 10 | 9 | 1 | Δ=2,接收半部重置 |
| 迟到s0:[4,6) | 6 | 3 | 10 | 9 | 1 | 不再交付,不再收费 |
| 旧MAX_DATA(8) | 6 | 3 | 10 | 9 | 1 | 较小值忽略 |
RESET 前可以只实际缓存 s0 的 [2,4) 两字节,仍有 H_0=4;RESET 后即使缓存归零,连接贡献也是6。若把流0从求和中直接删除,会错误地把 T 降到3,凭空创造6字节许可。可把已结束流的贡献汇总到历史累计量,而不是保留整份数据;无论采用哪种存储表示,累计贡献不能消失。
改掉一个数,在哪一道门失败
在原始 C=8 快照直接 RESET s0,f=6,候选总和9>8,必须报 FlowControlError;不能以控制帧没有载荷放行。另一份原始快照收到 f=3,则因3<H_0=4先报 FinalSizeError。若原先 FIN 已记录 F_0=4,再收到 f=6,即使 C 与 L_0 很大,也不能改变已经确定的最终长度。
每流许可也不能漏查:在 H_0=4、H_4=3、C=20、L_0=6 时,s0 新片段末端7仍违法。反过来,在 C=8、L_0=L_4=6 时,一包同时把 H_0提高到5、H_4提高到4,各流都没超6,但总和9超8,整包不能成功提交。
把许可6改报成3也不能让已获许可的发送字节变成违法;发送端保留6。若实现错误地用新收到的值覆盖旧值,乱序的一份旧 MAX_STREAM_DATA 就能使已经合法的末端4突然超过3。绝对信用取 max 恰好避免这一问题。
停读、缺口与终止的三种时刻
令 s0 已收到 [2,4)=cd,H_0=4、r_0=0,F_0 未知。应用停读并发出 STOP_SENDING,账仍为4。迟到 [4,5)=e 使 H_0升到5;即使字节当场丢弃,仍须有流及连接许可。随后 RESET(f=6) 再补记1,总贡献6,r_0仍为0,结果为中断。若把停读误当最终长度4,合法的在途e会被错误拒绝。
在另一条没有停读的运行中,先收到 s0:[2,4)=cd 且 FIN=true,F_0=4、r_0=0。补回 ab 后才交付 abcd 并正常完成;FIN 本身在 QUIC 流偏移中不额外占一个字节。这不同于TCP的FIN占一个序号,不能套用TCP的+1。
STOP_SENDING 是接收一方要求对端停止那个发送半部;RESET_STREAM 是发送一方终结自己正在发送的半部。对 Ready/Send 状态的发送半部,收到 STOP_SENDING 后应以 RESET 响应;已经发完数据等状态有规范规定的处理分支,不能一概要求再取消一次。双向流要停止两个方向,需要分别处理;终结 c2s 不清除 s2c 的流控、输出或结果。这里的两个接收对象只实现一方向账本,没有模拟控制帧可靠传送。
推论与应用
为什么总账保持正确
采用不变量 H_i≥0、T=ΣH_i、H_i≤L_i、T≤C;已知 F_i 时 H_i=F_i 且 F_i 不变。初态成立。普通数据只让一个 H_i 增加 Δ_i,同时让 T 增加相同量;先检查两个上限,再提交,故求和与许可都保持。FIN 同时保证 f不小于旧H_i且f=t,提交后 H_i=F_i。RESET 以 f−H_i补足缺失贡献,同样保持求和。迟到旧数据末端不越过 F_i,增量为0。单调额度更新只扩大允许集合,不破坏已接受状态。停读只改变缓存/交付策略,不改变求和。
多帧事件逐帧使用更新后的暂存总账,所以两条分别看似合法的增量不能共用同一份余额。FlowControlError、FinalSizeError 或 ContentConflict 不提交本次暂存结果,并使教学连接持久进入 FAILED,后续接收均拒绝;此前成功事件与已经交付的前缀仍然存在。比较其他错误分支时必须另建新快照,不能在已经失败的连接上继续当作成功路径。正文规则可用双层信用检查器逐步复算。
释放内存与授予新许可是两回事
接收流控通常随着应用消费或安全丢弃而提高累计许可。设实现已安全释放的累计计费量为 Q,总接收承诺预算为 W,一个简化策略是 C=Q+W;Q增长时提高C,而T保留历史。RESET给出F之后,未到达而已结算的部分也不再要求缓存,可按明确策略计入可释放量。不能在F未知时猜一笔释放,也不能同时减T又加C而重复返还。
接收端不应等到 DATA_BLOCKED 才决定是否发信用更新;通知可能丢失,发送端也未必发送该通知。新许可同样需要规范的控制信息恢复。许可充足仍不等于可以立即发:共享拥塞预算和调度继续限制发送。流控保护接收承诺,拥塞控制保护网络,这里不推导实际发送速率。
如果接收应用永久不消费,不再提高该流许可可以限制其新增数据。只提高连接许可也不能越过已满的单流上限;只提高单流许可又可能仍卡在连接上限。连接信用被某个慢流占用时,其他流即使没有字节缺口也可能等待。这是跨流共享资源效应,不违背独立重组的前缀证明。
账本每帧只需常数个整数运算,前提是按流查找为期望常数、维护增量T且整数在固定字长范围;逐帧重算全体ΣH_i则为O(K)。这只计算账本算术。检查器的RESET和stop_reading还逐格清理未交付数组,每次另需O(B_i);重复RESET同样可能再次扫描。整包复制、断言扫描和排序快照的演示成本见重组页。活跃流与已结束但保留检查状态的流各需元数据,空间为O(K_active+K_closed),另计载荷与gap区间。MAX_DATA不约束空流数、控制帧队列、对象头、加密副本或无限应用队列,因此不等于整个进程内存上限;应用背压与流数量限制仍有独立义务。