Skip to content

算法Algorithm

字节流上的长度前缀分帧

Application message framing · Length-prefixed framing · Short read

定义两字节大端长度的增量解析器,跨三次短读恢复CAT与OK,并检查超长、半帧EOF和输出队列边界。

形式陈述 ​

TCP字节流没有应用消息边界。本页固定一个小格式:每帧先放两字节无符号大端长度 L=256b0+b1,然后恰好 L 个载荷字节;允许 L=0,最大合法长度 Lmax=16。长度不含自己的两字节。连续帧直接拼接,读者必须保留跨接收调用的解析状态。

状态分为Header(h)、Body(L,p)、Error。h是已收但不足两字节的头,p是已收但不足L字节的载荷。初态Header(空)。每批输入按游标消费:先补满头,检查L≤16再进入Body;补满载荷便输出一帧并回到空Header,继续处理本批剩余字节。L=0立即输出空帧,不等待下一个字节。Error为本次解析的终态,不能跳过未知字节随意找下一个“看起来合法的头”。

接口区分“这次暂时没有字节”与真实EOF。对有序EOF,若处于空Header,字节格式在帧边界结束;若头只有1字节或载荷未满,则报告截断。格式合法结束仍不保证业务协议已完成,例如本来必须有一个响应但对方直接关闭。

解析不变量是:已消费的输入恰由已经输出的完整帧编码,加上当前未完成头或当前头及部分载荷组成;未消费输入保持原序。只有长度检查通过且载荷完整,才能产生一份输出。这确保任意合法短读切分都得到相同帧序列。

直觉

接收调用像把一条纸带随手剪成几段递来。长度头告诉解析器下一条消息需要多少格,而不是要求每段纸带恰好从消息头开始。一批输入中可以只有半个头,也可以装下好几条完整消息。

保留解析状态不是把所有历史无限攒起来。完整帧交给消费者后,解析器只需记住尚未完成的那一帧;下游来不及消费时,还要暂停接收或限制输出队列。

例子与边界

同一九字节跨三次短读 ​

两条载荷为ASCII的CAT与OK,完整字节是 00 03 43 41 54 00 02 4F 4B。接收调用故意返回三段:

输入批次 新输入 处理后的状态 本次输出
1 00 Header(00) 无
2 03 43 41 Body(3,CA) 无
3 54 00 02 4F 4B Header(空) CAT、OK

第二次才补满长度头,且仍差一个载荷字节。第三次的首字节T补完CAT,剩余四字节又构成完整OK帧。若每次read返回就当一条消息,三次输出都会错误。

同一九字节一次全到,或分成九次每次1字节,答案仍应是CAT、OK。零长度帧00 00后接00 01 58应输出空载荷和X;若解析器只在Body里收到新字节才检查完成,就会漏掉空帧。

失败应在哪一步发生 ​

FF FF给出65535,读完头就拒绝,不能先分配65535字节再检查。真实协议的最大值可能更大,但必须在分配、长度加法及类型转换前检查上限和溢出。只限制单帧长度也不能阻止无限多个合法小帧塞满消费者队列。

00后EOF是截断头;00 03 43 41后EOF是截断载荷;完整CAT帧后EOF是格式边界。非阻塞接收的EAGAIN表示当前没有数据,不是EOF,也不能清空半帧状态。错误中止时已经输出的早先完整帧仍然存在,解析器没有撤回它们的权力。

推论与应用

用输入游标避免反复搬移整个余串,每个输入字节处理常数次,解析成本为 O(n)。除输入批次和输出队列外,解析状态最多保存2字节头及16字节载荷,空间为 O(Lmax);若读取批次或输出队列无界,就不能把整个程序声称为有界内存。

完整帧可以继续做字段校验、请求关联与业务处理。分帧只保证边界可解析,不验证身份、不保证请求成功,也不处理响应丢失后的业务结果。可复算实现与任意切分测试见网络终点任务。

参考资料
  • RFC 9293,§2.2、§3.9:字节流接口不提供本页应用边界。
  • POSIX.1-2024,recv:stream忽略消息边界,等待全部数据也存在提前返回条件。
  • 本页两字节长度、16字节上限和状态机为自定教学协议;它不是HTTP、DNS或其他现存协议的通用解析器。
关系图谱6 个相邻概念 · 2 类关系

拖动节点调整位置。

显示关系

显示:依赖

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