Lecture 18: Remote Procedure Calls and Marshalling — 远程过程调用与编组
第七部分：并发、复制与事务
这一部分从单个远程调用出发，逐层构建到跨多个站点的分布式事务： RPC 的语义与失败模式、并发控制与可串行化、复制协议与两阶段提交。
Lecture 18: Remote Procedure Calls and Marshalling — 远程过程调用与编组
讲义对应：CS 425 FA2026 Lecture 18。本章对应课程的 Lecture 20「RPCs and Concurrency Control」中 RPC 与编组的部分（原始讲义
L19-20.FA25.pdf，共 57 页，Final 版：RPC 动机、LPC 对比、RPC 组件与桩代码生成、编组与 CDR、调用语义表、幂等性）。同一份讲义里的事务、可串行化、悲观/乐观并发控制、死锁、最终一致性属于 Lecture 19 章，本章不重复。 教材对应：Coulouris 5th Ed. Ch. 5（Remote Invocation） 为主线；补充 Sec. 4.3（External Data Representation and Marshalling）、Sec. 4.4（Request-Reply Protocols）、Ch. 8（Distributed Objects and Components：Java RMI、CORBA）。 阅读材料：Andrew D. Birrell & Bruce Jay Nelson, Implementing Remote Procedure Calls, ACM TOCS 2(1), 1984（RPC 奠基论文，讲义中”Proposed by Birrell and Nelson in 1984”即指此文）；课程 Resources 页推荐的网络编程资料：Beej’s Guide to Network Programming、W. R. Stevens, UNIX Network Programming（socket API 权威参考）、IETF RFC 文档；补充：Jim Waldo et al., A Note on Distributed Computing, 1994；gRPC 与 Protocol Buffers 官方文档。
18.1 概述
本讲回答一个看起来只是”语法糖”、实际上是整个分布式系统工程基石的问题：既然一台机器上”调用一个函数”这件事如此简单，我们能不能让一个进程像调用本地函数一样调用另一个进程（甚至另一台机器）上的函数？ Birrell 和 Nelson 在 1984 年给出的答案是 RPC（Remote Procedure Call，远程过程调用）：让调用代码在语法上完全不变，把编组、网络传输、重试、请求匹配这些分布式细节全部藏进桩（stub）。这个抽象极为成功——今天几乎所有分布式系统（云服务、微服务、文件系统、键值存储、MapReduce 的 worker 通信）都建立在 RPC 之上。对象世界里的对应物叫 RMI（Remote Method Invocation，远程方法调用）。
但是本讲真正要讲的不是”如何成功”，而是”为什么它不能完全成功“。本地调用之所以简单，是因为它默认了三件在分布式系统里永远不成立的前提：同一个地址空间（所以可以传指针）、没有故障（所以调用不会丢）、延迟可忽略（所以可以随意细粒度调用）。跨进程、跨网络之后，这三条全部失效，于是 RPC 带来了一系列本地调用根本没有的问题：参数必须按值复制（引出编组 marshalling），消息可能丢失、重复、乱序、延迟（引出 RPC 调用语义），而最致命的是部分失败（partial failure）——超时之后，调用者永远无法区分”对方没执行”和”对方执行了但响应丢了”。本讲的核心内容就是围绕这三件事展开的：RPC 的组件架构与执行流程（18.2.5-18.2.6）、编组与数据表示（18.2.7-18.2.9）、调用语义与去重（18.2.10）、异步 RPC（18.2.11）、真实系统谱系与现代框架（18.2.12-18.2.13）、以及截止时间与重试风暴等高级主题（18.2.14）。
本讲在整门课中的位置非常特殊：它是“并发与复制”这一部分的入口。讲义自己就点明了这一点——”Now that we know RPCs, we can use them as a building block to understand transactions”：Lecture 19 的事务就是”一串 RPC”，Lecture 19 的并发控制解决的是”多个客户端的 RPC 交错执行”，Lecture 21 的两阶段提交解决的是”跨多个服务器的 RPC 如何原子提交”，Lecture 17 的复制状态机 + 客户端去重解决的正是本讲留下的 exactly-once 难题的另一半。所以本章的一句话黄金法则必须写在最前面：
RPC 的困难不在于”调用”，而在于”部分失败”——超时之后你永远不知道对方是否执行了。因此 RPC 的语义设计（at-most-once / at-least-once / exactly-once）比 RPC 的语法设计重要得多。
18.2 核心概念与分布式机制图解
18.2.1 本地过程调用（Local Procedure Call, LPC）
定义与目的：LPC 指同一个进程内一个函数调用另一个函数。讲义给出的三个机制要点是：用栈（stack）传递参数与返回值；通过指针（C）或引用（Java）访问对象；并且 LPC 具有 exactly-once 语义——只要进程还活着，被调用的函数就恰好被执行一次。LPC 是 RPC 的”参照系”：不理解 LPC 默认了什么，就看不出 RPC 多了哪些困难。
直观解释（”它是什么？”）：LPC 像在自己家里喊室友递杯水。你们共用同一个房间（地址空间）、同一批杯子（对象），你只要说”把那个杯子给我”（传指针），对方立刻就知道是哪个杯子；喊一声的延迟短到你根本不会去想”他到底听见了没有”；而且他要么递给你，要么不递，绝不会”递了但你没接住，而且你还不知道他递没递”。RPC 则是打电话请另一栋楼里的同事办事——你得把杯子长什么样描述清楚（编组），电话可能断线（消息丢失），最要命的是：电话断了之后，你不知道他到底办了没办。
机制图解：LPC 的时间线与内存布局。
┌────────────────────────── 同一个进程 / 同一个地址空间 ──────────────────────────┐
│ main() 的栈帧 f1() 的栈帧 │
│ ┌──────────────────┐ ① 参数压栈 ┌──────────────────┐ │
│ │ 局部变量 a, b │ ─────────────► │ 参数 x, y │ 高地址 │
│ │ ... │ │ 保存的返回地址 │ ↑ │
│ │ (高地址) │ │ 被调用者保存寄存器│ │ 栈向低地址增长 │
│ └──────────────────┘ │ 局部变量 │ │
│ ▲ └────────┬─────────┘ │
│ │ ③ ret: 返回值在 eax/rax 中 │ ② call f1: PC 跳转到 f1 │
│ └──────────────────────────────────────┘ │
│ ④ 指针 &: &a 在 main 和 f1 里指向同一块内存 ⇒ 可以自由传递引用 │
└───────────────────────────────────────────────────────────────────────────────┘
时间: 纳秒级 (约 1-10 ns 量级) 故障: 无 (函数体要么执行要么不执行)
- 关键假设与系统模型：LPC 隐含四条假设，而 RPC 会把它们逐条打破：(1) 同一地址空间——所以指针有效、对象可共享；(2) 无部分失败——调用与返回发生在同一个控制流里，没有”消息丢失”这个状态；(3) 延迟可忽略——纳秒级，可以放进循环里调用上百万次；(4) 无并发干扰（在单线程语义下）——没有人会在你调用期间改你的对象。讲义用一句话总结 LPC 的语义：exactly-once。
18.2.2 远程过程调用（Remote Procedure Call, RPC）
定义与目的：RPC 指调用者函数与被调者函数位于不同进程中的函数调用。讲义的三条定义性说明是：(1) 函数调用跨越进程边界（a function call crosses a process boundary）；(2) 通过全局引用（global reference）访问过程——不能用指针跨进程，因为进程 $P_1$ 中的一个引用地址在另一个进程 $P_2$ 中可能指向完全不同的对象；(3) 因此过程地址必须是一个全局可解释的名字，例如 IP + port + procedure number。在面向对象的场景里，同一思想叫 RMI（Remote Method Invocation）；RPC 让代码可以复用（allows code reuse），且被绝大多数分布式系统（包括云系统）实现和使用。
直观解释（”它是什么？”）：RPC 就是”打电话办事”。你（Client）想请另一栋楼的同事（Server）帮你订一张机票：你先要把请求说清楚（把参数编组成双方都听得懂的普通话，这就是编组）；电话线路可能占线、可能断（网络不可靠）；对方听懂了、办了事、再口头把结果告诉你（响应）；你把结果记下来（解组）。整个过程中最关键的一点是：如果你说了之后电话断了、你等了很久没等到回话，你根本无法判断对方是”没听清”、”没去办”、还是”办完了但回话时电话断了”。你唯一能做的是”再打一次电话问一遍”——但这一遍可能让对方又订了一张票。这就是 RPC 的全部困难所在。
机制图解：从 LPC 到 RPC 的演进（讲义用同一组函数图逐步加上了第二个进程、第二台主机、请求/响应消息）。
── 只有 LPC ── ── 跨进程 ── ── 跨主机 ──
┌─────────────────┐ ┌──────────┐ ┌──────────┐ ┌──────────┐ ┌──────────┐
│ P1 │ │ P1 │ │ P2 │ │ Host A │ │ Host B │
│ main() │ │ main() │ │ f2() │ │ P1 │ │ P2 │
│ │ LPC │ │ │ │ │ ▲ │ │ main() │ │ f2() │
│ ▼ │ │ ▼ │ │ │ │ │ │ │ │ ▲ │
│ f1() ──LPC──► │ │ f1() │ │ │ │ │ f1() │ │ │ │
│ f2() │ │ │ │ │ │ │ │ │ │ │
└─────────────────┘ │ RPC ───┼──┼───┘ │ │ RPC ────┼──┼───┘ │
一个地址空间, 无故障 └──────────┘ └──────────┘ └──────────┘ └──────────┘
两个地址空间 RPC request 消息 ──────►
指针失效 RPC reply 消息 ◄──────
网络: 会丢/会重/会乱序
- 关键假设与系统模型：讲义的措辞是”Under failures, hard to guarantee exactly-once semantics“（在有故障时，难以保证恰好一次语义）。它列出了函数可能没有被执行的四种情形，以及函数可能被执行多次的一种情形：
| 情形 | 现象 | 客户端能观察到什么 |
|---|---|---|
| 请求（call）消息丢失 | 服务端根本没收到 | 客户端超时，调用未执行 |
| 响应（reply）消息丢失 | 服务端执行了，结果回不来 | 客户端超时，调用已执行（客户端不知道） |
| 被调进程在执行前崩溃 | 没执行 | 客户端超时，调用未执行 |
| 被调进程在执行后崩溃 | 执行了，结果没保存 | 客户端超时，调用已执行（且副作用可能丢失） |
| 请求消息被重复投递 | 执行了多次 | 客户端可能毫无察觉（除非返回值暴露了重复） |
讲义接着指出：“Hard for caller to distinguish these cases”（调用者很难区分这些情况）——这五种情形在客户端看来几乎完全一样（都是一次超时）。这不是工程细节，而是分布式系统的本质限制：在异步系统中，你无法用一个本地可观测的事件把”消息丢了”和”对方慢了/崩了”区分开。本章剩下所有内容，本质上都是围绕这一个事实，在”语义、性能、复杂度”三者之间做的取舍。
18.2.3 RPC 与本地调用的七个本质区别
讲义用 LPC 的机制要点和 RPC 的定义作为对照，把差异压缩成了几句话；下面把这七条差异逐一展开。这七条是本讲的骨架：后面每一节都在解决其中的某一条。
区别 1：地址空间不同 ⇒ 参数必须复制，指针不能传。
LPC 传指针是因为两边共享同一块内存；RPC 两边是不同的地址空间（甚至不同的机器、不同的体系结构），一个地址值在远端毫无意义。因此 RPC 的默认参数传递方式是按值传递（call-by-value）：调用者把参数复制进消息。这直接引出两个新问题：(a) 复制的字节是什么格式？——即编组（marshalling）（18.2.7）；(b) 如果我真的想”传一个对象/引用”怎么办？——只能传一个远程引用（remote reference）：一个全局可解释的名字（如 IP + port + procedure number，或 RMI 里的对象句柄），让对方用这个名字回调我（18.2.9）。
区别 2：网络不可靠 ⇒ 需要定义”调用语义”。
本地调用不会”丢”，RPC 的消息可能丢失、重复、乱序、延迟。讲师给出的可能语义直接对应了这个事实（18.2.10 详述）：
| RPC 语义 | 是否重传请求 | 是否过滤重复请求 | 重复到达时怎么办 |
|---|---|---|---|
| At least once（至少一次） | 是 | 否 | 重新执行函数 |
| At most once（至多一次） | 是 | 是 | 重传上次的响应，不重新执行 |
| Maybe（尽力而为 / best-effort） | 否 | 不适用 | 不适用 |
注意这张讲义原表的两个细节，它们常被误解：(1) 讲义口径下的 at most once 是要重传请求的，它靠”过滤重复请求 + 重传上次响应“来保证服务端不重复执行；(2) 真正”不重传”的那一档，讲义叫 Maybe / best-effort（CORBA 的做法）。很多教材把”不重传”直接叫 at-most-once——两种口径都保证服务端最多执行一次，差别只在客户端是否主动重传（见 18.2.10 的对照表）。
区别 3：延迟高且可变 ⇒ 不能细粒度、高频调用。
本地调用是纳秒级；RPC 至少一个网络往返（RTT）：同机房几十微秒，同城约 0.5-1 ms，跨大陆 60-150 ms，跨洲际可以到 200-300 ms。这意味着把本地循环里的 $10^6$ 次函数调用改成 RPC，代价从数毫秒变成数小时。这就是”RPC 的性能陷阱“：接口看起来一样，代价差 $10^3 \sim 10^6$ 倍（18.5 有实测量级）。设计后果：接口要粗粒度（coarse-grained）、要批量化、要避免”chatty”（唠嗑式）的调用模式。
区别 4：可能部分失败（partial failure）——RPC 最核心的困难。
本地调用只有两种结果：正常返回或抛出异常（进程崩溃则整个进程一起没了）。RPC 多出第三种结果：不知道（indeterminate）。客户端发出请求后超时，此时请求可能丢在去程、可能丢在回程、服务端可能在执行前崩溃、可能执行后崩溃——客户端无法区分（这正是 18.2.2 那张表）。本地调用没有这个问题，因为本地调用不存在”半个”结果。 需要强调的是：这不是”实现得不好”，而是在异步网络里从原理上无法区分——除非要么服务端维护持久化的去重状态（18.2.10 的 drop box + 18.3.3 的正确性边界），要么把操作改造成幂等的（18.2.14）。
区别 5：并发性（concurrency）。
本地调用在单线程里是”一次一个”，语义清晰。RPC 服务端通常同时服务多个客户端：讲义在下一节（Lecture 19 的事务部分）正是从这里切入——”Multiple Clients, One Server: What could go wrong?”。服务端需要考虑线程模型（每请求一线程 / 事件循环 / 线程池）、共享状态的并发访问（锁、原子性），以及请求交错（interleaving） 带来的可串行化问题。详见 Lecture 19 章。
区别 6：接口与实现的分离 ⇒ 需要 IDL 与桩生成器。
本地调用时，编译器从函数原型就能知道参数类型与调用约定。RPC 中，客户端与可能在不同的机器上、用不同的语言、由不同的团队实现，双方必须共享一份接口契约：这就是 IDL（Interface Definition Language，接口定义语言）。IDL 是语言中立的，由 IDL 编译器 / 桩生成器（stub compiler，讲义举例：Sun XDR 接口描述喂给 rpcgen） 生成客户端桩、服务端桩、编组代码，以及（在现代框架里）服务定义与客户端库。
区别 7：安全性。
跨网络的调用意味着不可信的对端：需要认证（authentication）“你是谁”、授权（authorization）“你能做什么”、加密与完整性（confidentiality / integrity）“内容不能被看、不能被改”。本地调用天然信任同进程内的代码（或至少交给 OS 的进程边界处理），RPC 则必须显式处理——包括本讲最后要强调的反序列化漏洞（18.2.14）。详见 Lecture 25。
┌───────────────────────────── LPC ─────────────────────────────┐
│ 同地址空间 │ 无故障 │ ns 级 │ 无部分失败 │ 单线程 │ 编译器知道类型 │ 信任 │
└─────────────────────────────┬─────────────────────────────────┘
│ 跨进程 / 跨网络 ⇒ 七条假设逐条失效
┌─────────────────────────────▼─────────────────────────────────┐
│ 不同地址空间 ⇒ 编组 │ 网络不可靠 ⇒ 调用语义 │
│ ms 级延迟 ⇒ 粗粒度接口 │ 部分失败 ⇒ 不确定性(本讲核心) │
│ 并发 ⇒ 线程模型 │ 接口分离 ⇒ IDL 与桩生成 │
│ 不可信对端 ⇒ 认证/授权/加密 │
└───────────────────────────────────────────────────────────────┘
- 关键假设与系统模型：本章的 RPC 模型默认 crash-stop / crash-recovery 的进程 + 可能丢失、重复、乱序、延迟的异步网络（与课程工作定义一致：实体自治、异步、易故障，通信介质不可靠）。注意”重复”必须被显式处理：即使客户端从不重传，网络本身（重传的 TCP 段、中间代理、应用层重试）也可能造成重复投递——这是讲义原表里”Filter duplicate requests”这一列存在的原因。
18.2.4 “透明性”的危险：RPC 应当假装是本地调用吗？
定义与目的：Birrell 与 Nelson 的原始目标包含很强的透明性（transparency）抱负：让远程调用在语法上与本地调用无法区分（讲义原文：client stub “has same function signature as callee()”，从而 “allows same caller() code to be used for LPC and RPC”）。这一节的目的是指出这种“看起来完全一样”的透明性是危险的，并说明现代 RPC 框架为什么主动放弃它。
直观解释（”它是什么？”）：透明的 RPC 像”伪装成本地快递的同城闪送”：界面完全一样，价格标签却差三个数量级，而且偶尔包裹会莫名其妙消失。如果程序员相信它就是本地调用，他会自然而然地写出”在循环里调用 1000 次”的代码——在本地是 1 微秒，在 RPC 就是 100 毫秒起步，甚至因为尾延迟放大（18.5）变成 1 秒。透明性没有消灭复杂性，只是把它藏起来了，而藏起来的复杂性最后会以故障和性能事故的形式还给你。
机制图解：透明性帮了什么、骗了什么。
┌──────────────────── 透明性带来的好处 (RPC 的成功之处) ────────────────────┐
│ z = f(x, y) ← 同一行代码, 编译期不变; 客户端逻辑无需改动 │
│ 自动化: IDL -> 桩 -> 编组代码全部生成, 程序员不写一行网络代码 │
└───────────────────────────────────────────────────────────────────────────┘
┌──────────────────── 透明性隐藏掉的代价 (RPC 的危险之处) ───────────────────┐
│ 1. 延迟: ns -> ms (10^3 ~ 10^6 倍) 2. 部分失败: 超时后不确定是否执行 │
│ 3. 参数语义: 传"引用"其实传的是值(或句柄), 语义已变 │
│ 4. 资源: 每个调用消耗连接/线程/带宽 5. 安全: 不可信输入进入反序列化 │
│ 6. 故障传播: 一次调用失败可能级联放大(重试风暴) │
└───────────────────────────────────────────────────────────────────────────┘
- 关键假设与系统模型：透明性假设“远程调用的语义与本地等价”，而这个假设在故障下不成立（区别 4）。一个关键的补充说明（不属于本讲讲义原文，但与本讲的结论完全一致）：Waldo 等人在 1994 年的 A Note on Distributed Computing 中系统地论证了”本地与远程的统一对象模型”失败的原因，核心论点正是延迟、内存访问、并发、部分失败这四项差异是不可消除的，因此”接口应当让远程性可见“。这正是现代框架的做法：gRPC 的调用返回一个可能失败的
status、ReST 用状态码表达结果、几乎所有框架都强制程序员指定 deadline（18.2.14）——它们都在提醒程序员：”这不是本地调用。”
18.2.5 RPC 的组件架构（Client Stub / Server Stub / Runtime / Dispatcher）
- 定义与目的：讲义给出的 RPC 实现结构由五个部件组成，程序员只写两个函数（
caller()与callee()），其余全部由中间件自动生成：
| 部件 | 位置 | 职责（讲义原文口径） |
|---|---|---|
Client（调用者 caller()） | 客户端进程 | 写业务逻辑，只管调用 callee() 的名字 |
| Client stub（客户端桩 / 代理） | 客户端进程 | 与 callee() 有相同的函数签名（same function signature），负责编组参数、发送请求、等待响应、解组返回值 |
| Communication Module（通信模块 / RPC runtime） | 两端各有 | “Forwards requests and replies to appropriate hosts”——把请求与响应转发到正确的主机；负责重传与请求匹配 |
| Dispatcher（分发器） | 服务端进程 | “Selects which server stub to forward request to”——按过程标识符选择正确的服务端桩 |
| Server stub（服务端桩 / 骨架 skeleton） | 服务端进程 | “Calls callee(), allows it to return a value”——解组参数、调用真函数、编组返回值 |
直观解释（”它是什么？”）：把 RPC 想成寄一封挂号信请人办事：Client stub 是帮你写信并翻译成对方语言的秘书（编组）；Communication module 是邮局（传输、重发、按挂号单号核对回信）；服务端的分发器是公司前台，看一眼信封上的部门编号就把信转给对应科室（过程标识符 → 正确的 server stub）；server stub 是把外文信翻译成本科室能读的便签、并在办完后把结果翻译回去的秘书。你和对方业务人员都不需要懂邮政和翻译——但业务人员必须知道”信可能寄丢”。
机制图解：讲义的组件图加上”谁生成谁”的关系。
┌──────────────── 客户端进程 P1 (client) ────────────────┐ ┌──────── 服务端进程 P2 (server) ────────┐
│ int caller() ← 程序员写 │ │ int callee() ← 程序员写 │
│ │ (1) 调用 stub.f2(x, y) │ │ ▲ │
│ ▼ │ │ │ (8) │
│ ┌──────────────┐ (2) 编组 (3) 发请求 │ │ ┌────────────────┐ (7) 调用 │ │
│ │ Client stub │ ────────────► ┌───────────────────┐ │ │ │ Server stub │ ─────────┘ │
│ │ 签名同 callee │ │ Communication │ │ │ │ 解组/编组 │ │
│ └──────────────┘ ◄──────────── │ Module (runtime) │ │ │ └────────────────┘ │
│ ▲ (10) 解组返回值 │ 重传/请求匹配 │ │ │ ▲ (6) 分派 │
│ │ └─────────┬─────────┘ │ │ ┌───────┴────────┐ │
│ │ │ │ │ │ Dispatcher │ │
└────────┼──────────────────────────────────┼─────────────┘ │ └───────▲────────┘ │
│ │ └──────────┼─────────────────────────────┘
│ ▼ │
│ ╔══════════════════════╗ │
└───────────────────────║ 网络 (不可靠) ║────────────────┘
║ 丢/重/乱序/延迟/分区 ║
╚══════════════════════╝
生成方式: IDL (如 Sun XDR 接口描述) ──► rpcgen / IDL 编译器 ──► { client stub, server stub, dispatcher 表, 编组代码 }
中间件系统 (Middleware): Sun RPC、CORBA、Java RMI 等把这些部件打包提供给程序员
- 关键假设与系统模型：这套架构的隐含假设是：接口可以静态描述（因此可以生成桩）、过程标识符可以被全局解释（因此 dispatcher 能路由）、通信模块可以重传（因此需要请求 ID 与去重）。讲义特别强调”these components together part of a Middleware system”，并给了三个例子：CORBA、Sun RPC、Java RMI。补充说明：现代框架在这套架构上做了两处重要扩展：(a) 桩生成从”生成源码”改为”生成客户端库 + 运行时反射/代码生成”（gRPC 两种都支持）；(b) 在 runtime 之上增加了截断器（interceptor / middleware 链），用于截止时间传播、重试、熔断、鉴权、追踪——见 18.2.14。
18.2.6 RPC 的完整执行流程与每一跳的失败模式
定义与目的：这一节把 18.2.5 的组件串成一条完整的时间线（12 跳），并逐跳回答两个问题：这一步在做什么？这一步失败时客户端知道什么？ 前者是”RPC 的语法”，后者才是”RPC 的语义”。
直观解释（”它是什么？”）：这条时间线就是打电话办事的完整流程，只是每个环节都有一个专职人员：你说（1）、秘书翻译（2-3）、总机转接（4-5）、前台分派到科室（6）、科室秘书翻译（7）、业务员办事（8）、秘书翻译回话（9）、总机回传（10）、你方秘书翻译（11-12）。只要中间任何一跳断了，你看到的都是同一件事：电话没声音。
机制图解：RPC 完整调用流程时序图（竖直方向是时间，横向是八个部件）。
Client ClientStub RpcRuntime Network ServerRt Dispatcher SrvStub Server
│ │ │ │ │ │ │ │
│────────────►│ │ │ │ │ │ │
1. f(x,y) 本地调用
│ │ │ │ │ │ │ │
│ │──────────────►│ │ │ │ │ │
2. 编组参数 marshal(x,y)
│ │ │ │ │ │ │ │
│ │ │──────────────►│ │ │ │ │
3. send(request: req_id, proc_id, args)
│ │ │ │ │ │ │ │
│ │ │ │───────────►│ │ │ │
4. 投递到服务端
│ │ │ │ │ │ │ │
│ │ │ │ │────────────────►│ │ │
5. dispatch(proc_id)
│ │ │ │ │ │ │ │
│ │ │ │ │ │────────────►│ │
6. 选中对应的 server stub
│ │ │ │ │ │ │ │
│ │ │ │ │ │ │──────────────►│
7. 解组 unmarshal(args)
│ │ │ │ │ │ │ │
│ │ │ │ │ │ │──────────────◄│
8. foo(x,y) 执行 + 返回值
│ │ │ │ │ │ │ │
│ │ │ │ │──────────────────────────────◄│ │
9. 编组返回值 + 发响应(同一 req_id)
│ │ │ │ │ │ │ │
│ │ │───────────────────────────◄│ │ │ │
10. 响应回到客户端 runtime
│ │ │ │ │ │ │ │
│ │──────────────◄│ │ │ │ │ │
11. 按 req_id 匹配到等待的调用
│ │ │ │ │ │ │ │
│────────────◄│ │ │ │ │ │ │
12. 解组返回值并返回给 Client
│ │ │ │ │ │ │ │
逐跳展开（与图中编号一一对应）：
| # | 动作 | 关键数据 | 这一跳失败时，客户端会经历什么？ |
|---|---|---|---|
| 1 | Client 调用 client_stub.f(x, y) | 参数值 x, y | 不可能失败（本地栈操作，除非客户端自己崩溃） |
| 2 | Client stub 编组参数 | 字节流 marshal(x,y) | 可能失败：不可序列化的类型（如文件句柄、函数指针、线程锁）→ 只能本地报错，绝不能发出半个消息 |
| 3 | Client stub 经 runtime 发送请求 | req_id, proc_id, args | 请求可能根本没发出（连接断开）：客户端立刻知道（send 报错），确定未执行 |
| 4 | 网络把消息送到服务端 | 完整消息帧 | 消息丢失：客户端只能等超时；也可能被重复投递或乱序 |
| 5 | 服务端 runtime 收到，交给 Dispatcher | proc_id | 服务端进程崩溃/重启中：消息无人接收，客户端超时 |
| 6 | Dispatcher 按 proc_id 选 server stub | 过程标识符 | 未知过程号（版本不匹配）：服务端应返回”未实现”错误，客户端能确定未执行 |
| 7 | Server stub 解组参数 | 参数对象 a, b | 解组失败（损坏消息、类型/长度越界、恶意输入）：必须在调用真函数之前检测并拒绝（安全性关键，见 18.2.14） |
| 8 | 真正执行 foo(x, y) | 业务逻辑与副作用 | 可能执行前崩溃（未执行）或执行后崩溃（已执行，但结果/副作用可能丢失）——对客户端完全不可区分 |
| 9 | Server stub 编组返回值并发送响应 | 同一 req_id + 结果 | 响应丢失：服务端已执行，客户端超时——最危险的一跳 |
| 10 | 响应经网络回到客户端 runtime | 同一 req_id | 客户端可能在等待期间崩溃：重启后无从得知结果（除非有持久化去重表，18.3.3） |
| 11 | 按 req_id 匹配到等待中的调用 | req_id ↔ 等待表项 | 匹配失败（如 req_id 被复用、客户端多线程共用连接）→ 会把响应交给错误的调用（严重 bug，18.7 有专门讨论） |
| 12 | Client stub 解组返回值并返回 | 结果值 | 解组失败：客户端已确定服务端执行了，但拿不到结果——只能报错并交由上层决定（重试 = 可能重复执行） |
- 关键假设与系统模型：这条时间线假设：服务端为每个请求生成一份响应（因此每个请求恰好一份响应）、请求 ID 在客户端内唯一且不复用、响应可以按
req_id匹配、网络端点可能消失（因此需要超时）。注意”超时”是一个客户端单方面的决定：它不是协议事件，而是本地计时器到期。这一点在后面论证 at-most-once / exactly-once 的正确性时会反复用到——超时只能说明”我还没收到响应”，不能说明”对方没做”。
18.2.7 编组（Marshalling）：把数据变成字节
定义与目的：编组（marshalling，也译”封送”）= 把参数与返回值从本机的数据结构表示转换成可以放进消息传输的字节序列；解组（unmarshalling）= 反向过程。讲义给出的完整链条是：不同的体系结构用不同方式表示数据 → 因此中间件定义一种与平台无关的公共数据表示（Common Data Representation, CDR）→ 调用者把参数转换成 CDR 格式（这就是 marshalling）→ 被调者从消息中把参数提取成自己平台的格式（这就是 unmarshalling）→ 返回值在被调进程编组、在调用进程解组。同义词包括 serialization（序列化）、encoding（编码）、pickling（腌制）；严格来说 marshalling 通常还包含”把参数按接口顺序拼装成消息”的语义，serialization 更偏”把对象图变成字节”，本讲不区分。
直观解释（”它是什么？”）：编组就像把一件家具拆成零件装箱寄走。问题在于：每家工厂的”零件编号规则”不一样。A 工厂（大端机器）认为”编号 12-AC-33”要从左往右写；B 工厂（小端机器）认为同样的编号要倒着写。如果 AB 直接对寄，B 会把 33 当成最高位——这不是小错，这是灾难性的静默错值。解决办法是双方约定一套”国际标准装箱规范（CDR）“：寄之前都改成规范格式，收到后再改回自己的格式。装箱拆箱的这套规范，就是外部数据表示（XDR）。
机制图解（一）：字节序（endianness）——讲义的原例。
数值 0x12AC33 (十六进制) 在内存中的字节顺序
┌────────────────────── Big endian（大端）──────────────────────┐
│ 最低地址 ────────────────────────────────────────► 最高地址 │
│ 12 AC 33 │
│ ▲ 最高有效字节 (most significant) 放在最低地址 │
│ 代表: IBM z 系列、System/360、SPARC、网络字节序（TCP/IP 规定的） │
└───────────────────────────────────────────────────────────────┘
┌────────────────────── Little endian（小端）────────────────────┐
│ 最低地址 ────────────────────────────────────────► 最高地址 │
│ 33 AC 12 │
│ ▲ 最低有效字节放在最低地址 │
│ 代表: Intel x86/x86-64（也就是绝大多数 PC 与服务器） │
└───────────────────────────────────────────────────────────────┘
若 Intel 机器把 0x12AC33 直接按内存 dump 发出、IBM 机器按自己的方式解释:
IBM 读到的是 0x33AC12 —— 不报错, 只是值错了。这是最危险的一类 bug。
- 机制图解（二）：编组的字节级布局。下面是一个具体结构体的编码结果——接口是
book(int flight_id, string origin, double price, list<int> seats)，实参是(300, "ORD", 289.5, [1, 12, 300])，编码规则为”1 字节类型标签 + varint（变长整数）+ 大端序 + 变长字段用长度前缀“（18.4 的代码18-C3/18-C1实现了这套规则）。
字段 字节区间 十六进制字节流 含义
─────────────────────────────────────────────────────────────────────────────────────
flight_id [ 0.. 2] 01 D8 04 TAG_INT + zigzag(300)=600 的 varint
origin [ 3.. 7] 03 03 4F 52 44 TAG_STR + 长度 varint(3) + UTF-8 内容 "ORD"
price [ 8..16] 02 40 72 18 00 00 00 00 00 TAG_FLOAT + IEEE-754 大端 double (289.5)
seats [17..25] 04 03 01 02 01 18 01 D8 04 TAG_LIST + 元素数 3 + 3 个 TAG_INT 元素
─────────────────────────────────────────────────────────────────────────────────────
总长度 26 字节
偏移 00 01 02 03 04 05 06 07 08 09 0A 0B 0C 0D 0E 0F
0000 01 D8 04 03 03 4F 52 44 02 40 72 18 00 00 00 00
0010 00 04 03 01 02 01 18 01 D8 04
逐字节读法 (按偏移):
0 = 01 类型标签 TAG_INT (flight_id)
1-2 = D8 04 zigzag(300) = 600 的 varint
3 = 03 类型标签 TAG_STR (origin)
4 = 03 字符串长度 3 (varint 单字节)
5-7 = 4F 52 44 UTF-8 内容 "ORD"
8 = 02 类型标签 TAG_FLOAT (price)
9-16 = 40 72 18 00 00 00 00 00 IEEE-754 大端 double = 289.5
17 = 04 类型标签 TAG_LIST (seats)
18 = 03 元素个数 3
19-20 = 01 02 TAG_INT + zigzag(1) = 2
21-22 = 01 18 TAG_INT + zigzag(12) = 24
23-25 = 01 D8 04 TAG_INT + zigzag(300) = 600
这张图里几乎每一个设计决策都值得注意：标签回答”这是什么类型”（类型安全）；varint 让 300 只占 2 字节、12 只占 1 字节（紧凑性）；zigzag 让负数也只用 1 字节（-1 → 01，1 → 02）；长度前缀回答”变长字段到哪里结束”（可解析性）；固定大端序回答”多字节整数怎么排”（跨平台一致性）；最后 seats 的 count=3 替代了终止符（用数量界定边界比用哨兵值安全——哨兵值可能与真实数据冲突）。
- 必须解决的四个问题（逐一展开）：
(1) 数据表示的异构性（heterogeneity）。 这是编组存在的根本理由：
| 异构维度 | 具体差异 | 若不处理会怎样 |
|---|---|---|
| 字节序（endianness） | 大端（IBM z、System/360、网络字节序）vs 小端（Intel） | 整数值静默错误（0x12AC33 读成 0x33AC12） |
| 字长（word size） | int 32 位 vs 64 位；long 在 Windows 是 32 位、在 Linux 64 位是 64 位 | 溢出截断、字段错位导致后续全部解析错误 |
| 浮点表示 | 绝大多数用 IEEE 754，但仍有 machine 的 long double（80 位扩展精度）、非规格化数/NaN 的位模式差异 | 精度丢失、NaN 比较行为不一致 |
| 字符编码 | ASCII、UTF-8、UTF-16、Latin-1、EBCDIC（IBM 大型机） | 中文/emoji 乱码；更糟的是长度计算错误（UTF-8 中一个汉字 3 字节）导致解析越界 |
| 对齐（alignment）与填充（padding） | 编译器为对齐插入 padding（如 4 字节 int 后跟 8 字节 double 会插入 4 字节空洞）；#pragma pack 会改变布局 | 内存里的结构体布局不可移植，直接 dump 结构体内存是最经典的错误 |
| 数据结构表示 | 数组、结构体、链表、树、对象、指针的表示完全不同 | 指针绝对不能传（见下）；链表必须扁平化（flattening）成数组或有向图 |
| 类型信息 | 接收方如何知道字节流里是什么？ | 没有标签就只能靠”约定”，一旦版本错配就会把 int 解释成 float——静默数据损坏 |
(2) 指针无法传输。 一个指针是”本地址空间内的偏移”，远端没有任何意义。因此编组必须做两件事之一：扁平化（flattening）——把指针结构展开成自包含的线性/图结构（如把链表转成数组，或按引用编号整理成一个表）；或者保持引用关系但换成远程引用——把指针换成全局可解释的名字（IP + port + 对象/过程号），接收方拿到的是一个”句柄”，用它可以回调（callback）发送方。循环引用（如对象 A 引用 B、B 又引用 A）是扁平化的经典陷阱：天真递归会无限展开，必须维护”已编码对象表”（按 ID 去重）。
(3) 类型安全（type safety）。 接收方必须能验证字节流与期望的接口一致——否则一个被篡改的 4 字节长度字段可以声称”后面有 40 亿字节”，直接导致缓冲区溢出或 OOM。防御手段包括：计算校验和/长度校验、解组时逐字段边界检查（永远不要相信消息里声明的长度，必须先与剩余可用字节数比较）、生成代码中的类型标签校验、以及限制最大消息尺寸（现代框架的默认 4 MB 上限）。
(4) 效率。 编组是每字节都要经过 CPU 的操作：编码/解码次数 $\times$ 每次的开销，会直接进入调用延迟。讲义没有展开这一点，但 18.5 的实测会显示：在小消息上，编组的 CPU 开销可以与网络 RTT 同量级甚至更大。
- 关键假设与系统模型：编组假设 消息可能被截断、篡改或来自恶意对端（因此必须做边界与类型检查）；假设 两端可能运行不同体系结构/不同语言/不同版本的 IDL（因此必须有规范格式或 schema 演进机制）。反过来说，如果两端保证同构（同机器、同编译器、同版本），则可以跳过编组——这正是共享内存、同一进程内调用、以及某些 RDMA/共享内存传输能”零拷贝”的原因。
18.2.8 外部数据表示（XDR）与两种编码风格
- 定义与目的：解决异构性的标准方案是规范数据表示（canonical / external data representation）：定义一种与机器无关的、唯一的表示，发送方先转换到它，接收方再从它转换回本地格式。讲义把它称为 CDR（Common Data Representation），并明确”middleware has a common data representation, platform-independent“。工程上对应多种具体标准：
| 标准 / 格式 | 出身与用途 | 关键特征 |
|---|---|---|
| XDR（eXternal Data Representation） | Sun RPC / ONC RPC（1980s，RFC 4506） | 4 字节对齐、大端序、类型显式（int/string/opaque/array/struct/union）、用”4 字节长度 + 4 字节倍数补齐”表示变长数据 |
| CDR（GIOP CDR） | CORBA 的 IIOP | 类似思路，但有小端/大端协商机制与”对齐到自然边界”的规则 |
| ASN.1 + BER/DER | 电信（SS7、SNMP）、安全（X.509 证书、LDAP） | 极其严谨的自描述格式（TLV：Tag-Length-Value）；DER 是 BER 的规范子集，要求唯一编码（安全场景必需） |
| Protocol Buffers | Google、gRPC | 字段号 + wire type（半自描述）、varint、向后/向前兼容 |
| Thrift | Facebook / Apache | 二进制协议、紧凑协议（TCompact）、可选字段号 |
| Avro | Hadoop / Kafka 生态 | schema 与数据分离（写入时通常不携带 schema），依赖 reader/writer schema 解析 |
| MessagePack / CBOR | 通用二进制自描述 | “JSON 的二进制版”，保留标签，体积与速度都优于文本 JSON；CBOR 用于 IoT/CoAP |
| JSON / XML | Web、配置文件 | 文本、自描述、人类可读、无类型/弱类型、体积大、解析慢 |
直观解释（”它是什么？”）：规范表示就像国际邮件统一用英文写地址：不管寄件人用中文还是阿拉伯文，到了国际中转站都翻成英文（规范格式），收件国的邮局再翻成本地文字。代价是两次翻译（发送方 → 规范，规范 → 接收方）；收益是 $N$ 种机器的两两互操作从 $O(N^2)$ 条转换规则降到 $O(N)$ 条（都只面向规范格式转换）。
必须对比的两种编码风格：
(a) 基于类型/标签（tagged / self-describing）。 每个值都带一个类型标签（JSON 的 "、true、数字字面量；XML 的标签名；MessagePack 的 type byte；ASN.1 的 Tag）。优点：不需要外部 schema 就能解析；字段可增删、顺序可打乱；调试友好。缺点：体积大（每个值至少多一个标签；JSON 还要重复写字段名）、解析慢（要逐字符/逐标签判断类型）。
(b) 基于位置/无标签（untagged / positional）。 发送方与接收方约定字段的顺序与类型（如 XDR 的 struct 就是按声明顺序依次编码；某些紧凑格式甚至不带类型）。优点：体积最小、解析最快（可以按固定偏移直接取字段）。缺点：对 schema 演进极不友好——只要一端改了字段顺序、加了一个字段、或把 int32 改成 int64，另一端的偏移全部错位，解析出来的是一片垃圾且不会报错。
(c) Protocol Buffers 的巧妙折中：字段号 + wire type。 这是现代 RPC 的基石，值得详细拆解。Protobuf 的消息是一串 (field_number, wire_type) 键 + 值 的序列：
Protobuf 的编码单位: 一个 key = varint( (field_number << 3) | wire_type )
┌──────────────────────────────────────────────────────────────────────────┐
│ wire type 0 = Varint (int32/int64/uint/bool/enum/sint 的 zigzag) │
│ wire type 1 = 64-bit (fixed64/sfixed64/double) │
│ wire type 2 = Length-delimited (string/bytes/嵌套消息/打包的 repeated) │
│ wire type 5 = 32-bit (fixed32/sfixed32/float) │
└──────────────────────────────────────────────────────────────────────────┘
例: field_number=2, wire_type=2 -> key = (2<<3)|2 = 18 = 0x12
field_number=1, wire_type=0 -> key = (1<<3)|0 = 8 = 0x08
message Booking { int32 flight_id = 1; string origin = 2; repeated int32 seats = 3; }
实例: flight_id=300, origin="ORD", seats=[1,12,300]
字节流: 08 D8 04 | 12 03 4F 52 44 | 1A 03 02 18 D8 04
└── 字段1 ─┘└── 字段2 ──┘└────── 字段3 (packed) ──────┘
08=int32字段1 D8 04=300 12=string字段2 03=长度 1A=repeated字段3
为什么它能兼容演进？ 关键在于三条不变量（这是”向后兼容/向前兼容”的全部秘密）：
| 变更 | 兼容性 | 为什么 |
|---|---|---|
| 增加一个新字段（用新的字段号） | 双向兼容 | 旧代码收到未知字段号时直接跳过（因为 wire type 告诉它这个值占多少字节），新代码读到旧消息时该字段取默认值 |
| 删除一个字段 | 兼容（但必须保留字段号，即 reserved） | 旧数据里该字段被跳过；但若把同一编号复用给新类型，旧数据会被误解析 |
| 字段顺序改变 | 完全兼容 | 解析靠字段号，不靠位置 |
int32 → int64 | 兼容（同为 varint） | wire type 相同，只是值域扩大 |
int32 → sint32（变成 zigzag） | 不兼容 | wire type 相同但语义不同，负数会被解析成错误的巨大正数 |
optional → required | 不兼容 | 旧数据可能没有该字段 |
| 改变字段的数据类型（如 int32 → string） | 不兼容 | wire type 变化，解析直接失败 |
所以 Protobuf 的折中不是”完全没有标签”也不是”完全自描述”，而是只带”怎么解析”的最小元数据（字段号 + wire type），把”这个字段的完整类型和含义”留给共享的 .proto 文件。这带来三个工程上极有价值的结果：(1) 体积紧凑（一个字段平均 1 字节 key + varint 值，没有字段名字符串）；(2) 可演进（只要不违反上表，就能灰度发布新旧版本）；(3) 可部分解析（旧程序不需要理解新字段也能正确处理消息——这一点在滚动升级的微服务里是刚需）。
- 机制图解：tagged 与 untagged 的字节代价对比（同一个
Booking消息）。
tagged 自描述 (JSON, 文本) untagged 位置约定 (XDR 风格)
{"flight_id":300,"origin":"ORD","seats":[1,12,300]} <4B int>300 <4B len>3 "ORD"+pad <4B cnt>3 <int>1 <int>12 <int>300
└─ 每个字段名重复出现在字节流里 (约 10 字节/字段) ─┘ └─ 无字段名, 无类型标签, 纯按声明顺序 ─┘
优点: 无需 schema, 可读, 可增删 优点: 最小体积, 解析最快(可直接映射到内存布局)
缺点: 体积大, 解析慢 缺点: 改 schema 就崩; 错值时不会报错, 只会静默错
Protobuf 折中 (字段号 + wire type)
08 D8 04 | 12 03 4F 52 44 | 1A 03 02 18 D8 04
└ 1B 键+varint 值 ┘└ 键+长度+内容 ┘└ 键+长度+打包元素 ┘
优点: 体积接近 untagged, 却能按字段号跳过/缺省 ⇒ 新旧版本互操作
- 关键假设与系统模型：规范表示假设 “两端都遵守同一个规范”——一旦某一端的实现有 bug（例如 XDR 里字符串补零的对齐规则处理错），错误会以”偶发的解析异常“形式出现，且往往只在特定长度/特定字段时才复现。Protobuf 的兼容性则严格依赖”字段号永不复用、类型不放宽也不收窄、required 不引入”这三条纪律——这不是技术限制，而是协议治理（schema governance）问题，工程上通常靠 CI 检查（
buf breaking之类的兼容性检查器）来强制。
18.2.9 参数传递的语义：值、引用、对象
定义与目的：RPC 的参数传递语义决定了”参数在远端到底是什么“。本地调用有三种经典语义（值、引用、值-结果），RPC 中默认只能实现第一种，另外两种必须改写。
直观解释（”它是什么？”）：传值像”把文件的复印件寄过去”：对方怎么改都不影响你手里的原件。传引用像”把保险柜钥匙给别人”：对方能直接改你的东西——但跨地址空间的钥匙是没用的（对方根本没有你的保险柜）。所以 RPC 里想要”引用语义”，只能改成“把保险柜的地址和编号告诉对方，让他打电话回来取”（远程引用/回调），或者“先寄复印件，让他改完寄回来，你再覆盖原件”（copy-restore）。
| 语义 | 本地调用的含义 | RPC 中如何实现 | 代价与陷阱 |
|---|---|---|---|
| call-by-value（值传递） | 复制实参 | RPC 的默认：编组复制 | 大对象（几 MB 的数组/图）复制代价高；对象的身份（identity）丢失（对端拿到的是副本，== 不再是同一对象） |
| call-by-reference（引用传递） | 传地址，被调者可改写调用者变量 | 无法直接实现；改写为远程引用（remote reference）：传一个 IP + port + 对象/过程号 的全局名字，对端用它回调（callback RPC） | 需要双方都能被连接（NAT/防火墙会挡住回调）；生命周期问题：引用指向的对象可能已经被回收（悬空引用）；需要租约（lease）或引用计数 |
| copy-restore（copy-in/copy-out，值-结果） | 参数初值传入，返回时把结果写回 | 传值 + 在返回消息里把该参数的最终值带回来，调用者写回本地变量 | 只有在调用成功返回时才写回；若调用失败/超时，是否写回就成为一个语义约定（一般不写回）；并发修改会被静默覆盖 |
| 传递对象（Java RMI 风格） | 对象引用 | 序列化整个对象图（把对象及其可达对象全部编码） | ① 体积爆炸（深对象图可能几 MB）；② 循环引用需特殊处理；③ 跨语言差（Java 序列化只有 Java 能解）；④ 安全灾难（反序列化漏洞，见 18.2.14）；⑤ 版本脆弱（类的字段改了就可能反序列化失败，需 serialVersionUID 治理） |
- 机制图解：三种语义在 RPC 里的落地方式。
调用者 P1 被调者 P2
┌──────────────────────────────────────────┐ ┌─────────────────────────┐
│ int y = 5; │ │ int foo(int a, int b) │
│ obj = {name: "alice", age: 30}; │ │ │
│ │ │ │
│ ① 值传递: foo(x, y) │ ── 复制 x,y ──► │ a, b 是副本; 改 a,b │
│ 对端改 a,b 完全不影响 x,y │ │ 不影响 P1 的 x,y │
│ │ │ │
│ ② 引用传递: 本地 foo(&y) 无法跨进程实现 │ │ 需要"引用"就只能: │
│ ⇒ 改写为远程引用: 传 handle= │ │ 用 handle 反向发起 RPC │
│ (IP=10.0.0.7, port=9001, objid=42) │ ◄── 回调 RPC ── │ setAge(handle, 31) │
│ 于是 P1 必须同时是 server(可被连接) │ │ ⇒ 双向连接要求 │
│ │ │ │
│ ③ 传递对象(Java RMI): 序列化整个对象图 │ ── 序列化图 ──► │ 反序列化出一个"结构等价 │
│ {name,age} 的所有可达对象一起编码 │ │ 但身份不同"的新对象 │
└──────────────────────────────────────────┘ └─────────────────────────┘
另: 返回值的编组方向与参数相反 —— 被调者编组返回值, 调用者解组 (讲义原文明确这一点)
- 关键假设与系统模型：值传递假设 “复制是廉价且无副作用”的——公有云里跨可用区复制 1 MB 参数的代价可能超过计算本身。远程引用假设 “被引用对象在整个调用期间存活且可达”——这在有 GC 的 RMI 与有故障的分布式环境里都不自动成立（RMI 用租约（lease）+ 分布式垃圾回收处理，详见 Lecture 8 的 DHT 中”引用”与本课术语的一致性）。Java RMI 的序列化假设 “两端是同一版本的同一个类”——因此它天然是同构（Java 到 Java）的，这也是它没能跨语言普及的根本原因之一。
18.2.10 RPC 的调用语义（Call Semantics）：at-most-once / at-least-once / exactly-once
定义与目的：调用语义回答的问题是：一次”逻辑上的调用”，在服务端到底被执行了几次？客户端又能观察到什么？ 本地调用（LPC）的答案是干净的 exactly-once：”若进程存活，被调函数恰好执行一次”。RPC 在有故障时无法免费获得这个性质，只能显式选择一种语义，并为它付出复杂度或正确性的代价。这是本讲最重要的语义部分。
直观解释（”它是什么？”）：打电话请人订票。你说了之后没等到回话（超时），你有三个选择：(a) 就当作失败，报告”没订上”——可能对方其实订了（at-most-once 的风险：假失败）；(b) 再打一次——对方可能又订一张（at-least-once 的风险：重复执行）；(c) 再打一次，并且让对方先查一下”你是不是刚办过这件事”——对方查台账，办过就把上次的结果告诉你，不再重办（exactly-once 的做法：去重表 / drop box）。第三种听起来完美，但它有一个致命前提：台账不能丢——如果对方失忆了（服务端崩溃重启且台账丢失），重复执行又会回来。
机制图解：讲义原表——三种语义的实现方式（这是本讲的官方口径，务必按列读）：
| RPC 语义（讲义口径） | 重传请求（Retransmit request） | 过滤重复请求（Filter duplicate requests） | 重复到达时（Re-execute function or retransmit reply） |
|---|---|---|---|
| At least once（至少一次） | 是 | 否 | 重新执行函数（Re-execute） |
| At most once（至多一次） | 是 | 是 | 重传上次的响应（Retransmit reply） |
| Maybe（尽力而为） | 否 | 不适用（NA） | 不适用（NA） |
这张表最容易读错的地方是：讲义口径下的 at-most-once 也要重传请求，它靠”服务端过滤重复请求 + 重传上次响应“来防止重复执行；而”完全不重传“的那一档，讲义叫 Maybe / best-effort（讲义举例 CORBA）。而大多数教材与工程文档采用另一种(更粗糙的)口径：at-most-once = 不重传、at-least-once = 超时重传、exactly-once = 重传 + 服务端去重。两种口径的核心区别总结如下（这也是本章实验 18-C2 中同时实现”不重传”与”重传 + 去重”两档的原因）：
| 口径 | 不重传 | 重传，不去重 | 重传 + 去重 |
|---|---|---|---|
| 讲义口径 | Maybe（best-effort） | At least once | At most once |
| 教材/工程常用口径 | At most once | At least once | Exactly once |
| 服务端执行次数上界 | 没有上界（网络重复投递仍可致重复执行） | 没有上界（重传次数 + 网络重复） | 恰好 1 次（在服务端不崩溃的前提下） |
| 客户端是否一定拿到结果 | 否 | 尽力而为（重试有限则可能仍失败） | 尽力而为（重试有限则可能仍失败） |
关键洞见（把两种口径统一起来）：“服务端至多执行一次”这个性质，只能靠服务端的去重来保证，而不是靠”客户端不重传”来保证。 因为重复请求可能有三个来源：(1) 客户端超时重传；(2) 网络本身重复投递（重传的 TCP 段、中间代理、负载均衡器的重试）；(3) 客户端应用层的重试逻辑。即使客户端从不重传，第 (2) 类重复依然存在——这就是讲义表里”Filter duplicate requests“这一列存在的理由，也是本章实验里”不重传的 at-most-once 在请求重复投递时执行了 2 次“的原因。
- 机制图解：两种丢失情形下三种语义的执行序列对比（
C= 客户端时间轴，S= 服务端时间轴）。
── 情形 A: 请求消息在去程丢失 ──
at-most-once (不重传) at-least-once (重传) exactly-once (重传+去重)
C │──req(X)──►╳ 丢 C │──req(X)──►╳ 丢 C │──req(X)──►╳ 丢
│ 超时 │ 超时 => 重传 │ 超时 => 重传
│ => 调用失败/未知 │────req(X)────► │────req(X)────►
S │ (未收到请求) │◄────resp───── │◄────resp─────
│ 执行次数 = 0 S │ 执行次数 = 1 S │ 执行次数 = 1
│ │ 客户端拿到结果 │ 去重表命中 0 次
── 情形 B: 响应消息在回程丢失 (最危险: 客户端不知道对方已执行) ──
at-most-once (不重传) at-least-once (重传) exactly-once (重传+去重)
C │──req(X)─────► C │──req(X)─────► C │──req(X)─────►
│◄──resp──►╳ 丢 │◄──resp──►╳ 丢 │◄──resp──►╳ 丢
│ 超时 => 返回失败 │ 超时 => 重传 │ 超时 => 重传
│ (以为“没执行”) │────req(X)────► │────req(X)────►
S │ 执行次数 = 1 !! S │ 执行次数 = 2 !! S │ 执行次数 = 1
│ 副作用已发生 │ 副作用发生两次 │ 重发缓存响应(未重执行)
图像说明：情形 A 里三种语义都能得到”正确”的服务端状态（执行 0 次或 1 次），差别只在客户端成功率；情形 B 才是分水岭——at-most-once 制造”假失败”（服务端执行了但客户端以为失败），at-least-once 制造”重复执行”（执行 2 次），只有 exactly-once 同时避免了这两者。这也解释了为什么”响应丢失”是 RPC 语义实验里最关键的场景。
语义一：at-most-once（至多一次）
- 客户端视角：要么得到结果，要么得到一个”失败/未知”的答复，绝不会因为这次调用而使服务端执行两次。注意”失败”在这里是不可靠的：客户端报”失败”时，服务端可能已经执行了（响应丢失、服务端执行后崩溃）。因此 API 语义上正确的表述是”客户端最多观察到一次成功，但观察到失败不代表没有副作用“。
- 服务端视角：被调函数最多执行一次。实现要点是过滤重复请求：维护一个以
(client_id, seq)为键的表，命中则重发上次的响应而不重新执行（这就是讲义表里的 at-most-once，也等价于教材口径的 exactly-once 机制）；若不重传且不去重（讲义口径的 Maybe），则”至多一次”并不成立。 - 具体场景：非幂等操作的标准选择——”从账户扣款 100 元”、”下单”、”发送一条不可撤销的通知”。Java RMI 是讲义给出的 at-most-once 代表系统。
- 代价：需要服务端有状态（去重表/响应缓存）、需要缓存容量管理（见下文的窗口设计），并且在”查不到记录”时无法给出确定答案。
语义二：at-least-once（至少一次）
- 客户端视角：只要还有重传机会，客户端最终会拿到一个结果（除非连续失败到放弃）。但客户端无法知道服务端执行了几次——返回值可能来自第一次执行，也可能来自第二次。
- 服务端视角：至少执行一次，可能执行多次。实现最简单：超时就重传，服务端照常执行，不做任何去重。
- 具体场景与硬性要求：必须只用于幂等（idempotent）操作。讲义的幂等性判据非常明确——“可以被重复执行多次而不产生额外副作用（without any side effects）”，并以服务端变量
x为例：
| 操作 | 幂等？ | 为什么 |
|---|---|---|
x = 1; | ✅ 幂等 | 重复执行的结果与执行一次相同（赋值，不依赖于旧值） |
x = y;（y 是参数） | ✅ 幂等 | 同上：写入一个与 x 旧值无关的值 |
x = x + 1; | ❌ 不幂等 | 重复执行会多加一次（读-改-写） |
x = x * 2; | ❌ 不幂等 | 重复执行会多乘一次 |
append(log, entry) | ❌ 不幂等 | 日志里会出现两条记录（本章实验中”状态记录数 > 1”就是这个现象） |
put(key, value)（覆盖写） | ✅ 幂等 | 覆盖式写，重复执行结果相同（但若带版本号/自增计数就不再幂等） |
讲义给出的结论就是设计规则：“Idempotent operations can be used with at-least-once semantics”——幂等操作可以安全地配合至少一次语义。
- 代表系统：讲义点名 Sun RPC 采用 at-least-once；NFS（建立在 Sun RPC 之上）正是靠”文件系统操作大多幂等”（
read、write到指定偏移、lookup等）来消化这一语义的（详见 Lecture 22）。
语义三：exactly-once（恰好一次）—— 需要服务端去重
- 目标：服务端恰好执行一次，客户端拿到这次执行的结果。
- 实现机制（服务端去重：RPC drop box / duplicate request cache）：
- 客户端为每个请求分配全局唯一的请求 ID：$(\text{client\_id}, \text{seq})$。
client_id保证多客户端不冲突（服务端重启后客户端 ID 也可能需要重新协商），seq在该客户端内单调递增且永不复用。 - 服务端维护去重表：
cache[(client_id, seq)] = reply，同时用highest_seq[client_id]记录”见过的最大序号”。 - 收到请求时先查表：命中 ⇒ 直接重发缓存里的响应，不重新执行；未命中 ⇒ 执行、缓存响应、更新
highest_seq。 - 缓存回收：只保留”最近 $W$ 个序号”（滑动窗口），更早的条目丢弃以免内存无限增长。
- 客户端为每个请求分配全局唯一的请求 ID：$(\text{client\_id}, \text{seq})$。
- RPC drop box 的两个细节必须讲清楚：
- 如何判定重复？ 判据是
(client_id, seq)的完全匹配，而不是“请求内容相同”——因为内容相同的两次调用可能是合法且必须都执行的（例如”再买一张同样的票”）。 - 缓存多久？丢弃的风险是什么？ 这正是设计难点。如果缓存太短，一个被延迟很久的重复请求（网络重传、客户端长时间重试、客户端崩溃后重启再重发）到来时已经查不到记录，服务端只能重新执行——重复就发生了，而且服务端此时连”这是重复”都不知道。因此窗口宽度 $W$ 必须大于客户端可能的最大重传时间跨度（工程上取”最大重试次数 $\times$ 最大超时”的若干倍）。严格来说，任何有限窗口都无法给出”恰好一次”的绝对保证——这是理论上的边界，不是实现缺陷。
- 如何判定重复？ 判据是
- 机制图解：RPC drop box 的去重机制（请求 ID 窗口 + 响应缓存）。
Drop box: 每个客户端一个"请求序号窗口" + 一条"响应缓存" (缓存最近 W 个请求的响应)
客户端 C1 的请求序号 seq (单调递增, 永不复用) ───────────────────────────────────►
... │ ...
60 61 62 63 │ 64 65 66 67 68 69
│ │ │ │ │ │ │ │ │ │ │
▼ ▼ ▼ ▼ │ ▼ ▼ ▼ ▼ ▼ ▼
┌───────────────────────────────────┬────────────────────────────────────────┐
│已滑出窗口: 查不到记录 │窗口 W=6 内: 保留响应 │
│重复请求到达也不可判定 │(C1,64) ... (C1,69) 共 6 条 │
│⇒ 只能重新执行(可能重复) │⇒ 命中后可重发缓存响应 │
└───────────────────────────────────┴────────────────────────────────────────┘
(C1,60..63) 已被回收 │ (C1,64..69) 可以去重
│
若此时到达重复的 (C1,61): │ 若此时到达重复的 (C1,66):
窗口内查不到记录 ⇒ 无法判定 │ 命中 cache ⇒ 重发缓存响应
⇒ 只能重新执行(可能重复) ❌ │ 不重新执行(恰好一次) ✅
结论: 窗口越窄越省内存, 但"查不到记录"的重复请求越多 ⇒ exactly-once 越不可靠。
服务端处理一个请求 (cid, seq) 的完整判定流程:
收到 (cid, seq)
│
▼
┌──────────────────────────────────────┐
│ 1. seq <= highest_seq[cid] ? │
└──────────────────────────────────────┘
│ 否 (这是新请求)
│ 执行 foo(); 把响应写入 cache;
│ highest_seq[cid] = max(旧值, seq); 回收窗口外条目 ✅
▼ 是 (可能是重复)
┌──────────────────────────────────────┐
│ 2. cache 中有 (cid, seq) ? │
└──────────────────────────────────────┘
│ 是 (命中缓存)
│ 重发缓存的响应, 不重新执行; dedup_hits += 1 ✅
▼ 否 (重复, 但已滑出窗口)
┌──────────────────────────────────────────┐
│ 无法判定 ⇒ 只能重新执行(可能重复), │
│ 或返回 INDETERMINATE 错误。 │
│ ⇒ exactly-once 的边界条件: 窗口 │
│ 有限 + 服务端不崩溃 时才成立。 │
└──────────────────────────────────────────┘
- exactly-once 的边界条件（必须明确写出来）：drop box 只在“服务端进程从崩溃中恢复后，去重表仍然存在”的前提下才有效。如果服务端崩溃重启后内存里的去重表丢失，那么一个重复请求会被当成新请求重新执行 ⇒ 重复发生。因此：
- 内存版 drop box 提供的其实是”at-most-once（在服务端不崩溃的前提下）”——这也是讲义口径把这一档称为 at-most-once 的原因之一；
- 要获得真正的 exactly-once，必须让去重状态持久化或复制：把”是否执行过 + 执行结果”写入持久化日志/数据库，或用 复制状态机把”请求 ID + 结果”复制到多数派。这正是 Lecture 17 的 Paxos/Raft 在真实系统里的第二大用途（第一大是配置管理）：客户端去重表（client session / dedup table）必须以共识或复制日志的方式保存，这样即使 leader 切换、副本重启，去重记录也不会丢。etcd/ZooKeeper 的”顺序 zxid + 会话 ID”、Kafka 的幂等生产者 ID + 序列号、gRPC 里那层”应用自定义幂等键”都是同一思想的工程化。
- 一个常见的务实结论：工程上”exactly-once”几乎总是被实现为 “at-least-once 的传输 + 幂等（或去重）的处理”——传输层做不到恰好一次，应用层的幂等性把它”变成”恰好一次。
- 三种语义全面对比表（表格中的”客户端结果”指客户端能观察到的东西）：
| 维度 | Maybe（best-effort） | At most once | At least once | Exactly once |
|---|---|---|---|---|
| 客户端是否重传 | 否 | 是（讲义口径）/ 否（教材口径） | 是 | 是 |
| 服务端是否去重 | 否 | 是（必须） | 否 | 是 |
| 服务端执行次数 | 0 或 ≥1（网络重复可致多次） | ≤ 1 | ≥ 1（可能多次） | = 1（服务端不崩溃前提下） |
| 客户端超时的含义 | 未知 | 未知（可能是假失败） | 会得到结果，但可能来自重复执行 | 会得到结果，且只执行了一次 |
| 客户端能观察到 | 失败 / 结果（无保证） | 成功 或 失败（失败≠未执行） | 成功（可能重复副作用） | 成功（无重复副作用） |
| 对操作幂等性的要求 | 无（但结果无保证） | 无（服务端不重执行） | 必须幂等 | 无（服务端不重执行） |
| 服务端状态 | 无状态 | 需要去重表 + 响应缓存 | 无状态 | 需要持久化/复制的去重表 |
| 额外开销 | 最低（1 条消息） | 中（重传 + 缓存 + 内存） | 中（重传） | 高（重传 + 缓存 + 持久化/共识） |
| 代表系统 | CORBA（讲义举例） | Java RMI（讲义举例） | Sun RPC / NFS（讲义举例） | 需要应用层幂等键：gRPC + 幂等键、Kafka 幂等生产者、etcd/ZooKeeper |
| 典型场景 | 可容忍丢失的通知、指标上报 | 非幂等的扣款/下单 | 幂等的覆盖写、读、删除 | 支付/转账/订单入库（配合业务去重表） |
18.2.11 异步 RPC（Asynchronous RPC）与尾延迟放大
定义与目的：同步 RPC（synchronous RPC） 是”发出请求后阻塞当前线程直到响应到达或超时”。异步 RPC 把”发起调用”与”获取结果”解耦，使客户端在等待期间可以做别的事或并发发起更多调用。它的价值随着两件事上升：RPC 延迟上升（跨机房/跨洲）与 fan-out 变大（一个请求要调用多个后端）。
直观解释（”它是什么？”）：同步 RPC 像”打一个电话、一直举着听筒等对方查完资料”——对方查 30 秒，你就举着 30 秒，什么都干不了，而且你的线程（听筒）被占着。异步 RPC 像”发一条短信，然后去处理别的邮件，收到回复再回来处理”：同一时间你能发出 100 条短信并同时等待 100 个回复。但要小心：短信式的并发只压缩了”等待”，没有压缩”服务端处理”——如果 100 个服务里有一个要 100 ms，你依然要等 100 ms（这就是尾延迟放大）。
- 两种经典形式（讲义之外的补充说明，与本讲的 request/reply 模型完全兼容）：
- 无返回值的异步 RPC（fire-and-forget，单向调用）：客户端发出请求后立即返回，服务端不回响应。最省消息（1 条），但可靠性最弱：客户端完全不知道对方是否收到、是否执行（这实际上就是”Maybe”语义的极端形式）。适用于日志上报、指标采集、可容忍丢失的通知。gRPC 里用一个只带请求、返回空响应的
unary方法或client streaming实现；UDP 上的单向消息也属于这一类。 - 带延迟响应的异步 RPC（deferred synchronous / polling / callback）：客户端发出请求后立即返回一个”凭据”，稍后通过轮询（polling）或回调（callback）取结果。轮询简单但有额外 RTT 与延迟；回调省 RTT 但要求客户端也能被连接（NAT/防火墙问题），且引入”回调本身也可能失败”的递归难题。
- 无返回值的异步 RPC（fire-and-forget，单向调用）：客户端发出请求后立即返回，服务端不回响应。最省消息（1 条），但可靠性最弱：客户端完全不知道对方是否收到、是否执行（这实际上就是”Maybe”语义的极端形式）。适用于日志上报、指标采集、可容忍丢失的通知。gRPC 里用一个只带请求、返回空响应的
现代实现：Future / Promise / async-await 把这一模式变成语言级抽象：Java 的
CompletableFuture、Python 的asyncio.Future+async/await（配asyncio.gather并发等待多个调用）、JavaScript 的Promise.all、gRPC 的异步 API（C++CompletionQueue、Pythongrpc.aio、JavaStreamObserver）。它们都等价于”给每个请求发一张取货凭证，最后统一取货”。- 机制图解：fan-out 与尾延迟放大（tail latency amplification）。
一个客户端请求扇出到 100 个后端服务 (fan-out = 100)
客户端
│
├────► 服务 1 p(快, 1 ms) = 0.99 p(慢, 100 ms) = 0.01
├────► 服务 2 p(快) = 0.99 p(慢) = 0.01
├────► 服务 3 p(快) = 0.99 p(慢) = 0.01
├────► ... 各服务的慢事件相互独立
└────► 服务 100 p(快) = 0.99 p(慢) = 0.01
│
│ 并发发出 (asyncio.gather / Promise.all), 然后等全部完成
▼
总延迟 = max(所有服务的响应时间) ← 决定整体体验的是"最慢的那一个"
P(至少一个服务慢) = 1 - 0.99^100 = 1 - 0.366 = 0.634 (63.4%)
E[总延迟] = 0.366 x 1 ms + 0.634 x 100 ms = 63.8 ms
中位延迟 = 100 ms (因为 P(至少一个慢) = 0.634 > 0.5, 过半请求都会踩到慢的)
对比参照:
- 单次调用 (无 fan-out): E = 1.99 ms, 中位数 = 1 ms
- 串行调用 100 个服务: E = 100 x 1.99 ms = 199 ms, 且 63.4% 的请求会被慢节点"卡住"
⇒ 结论: 并发(异步)把 199 ms 降到 63.8 ms, 但"尾部"依然支配总延迟:
必须配合 超时裁剪(timeout budget) / 对冲请求(hedged request) / 副本备份请求
- 关键假设与系统模型：异步 RPC 假设“等待期间线程/连接可以被复用”（因此需要事件循环或非阻塞 I/O；这也是 gRPC 建立在 HTTP/2 多路复用上的原因——一条 TCP 连接上可以同时有成千上万个活跃请求，而 HTTP/1.1 的”每请求一连接”会让连接数成为瓶颈）。它同时假设“并发发出的调用不会互相阻塞”：在同一个事件循环里，任何一次同步阻塞调用（例如在 async 函数里做了一次阻塞的磁盘 I/O）都会卡住整个循环，把异步的收益抹平——这是异步编程最常见的性能陷阱。
18.2.12 RPC 的实现谱系：Sun RPC、DCE、Java RMI、CORBA/DCOM、SOAP、REST
定义与目的：这一节沿着时间线看真实系统如何实现 18.2.5 那套架构，以及它们各自为什么兴衰。理解”失败者”和”成功者”的共同原因，比记住名词更重要。
- Sun RPC / ONC RPC（1980s，至今仍在运行）：Sun 的 ONC RPC（Open Network Computing RPC） 是 RPC 的第一个广泛部署的实现，也是讲义中 “Sun XDR 接口描述 →
rpcgen编译器” 这条代码生成链的原型。它的设计要点：- 用 XDR 编组（规范表示、大端序、4 字节对齐）；
- UDP 与 TCP 两种传输都支持；在 UDP 上的实现必须自己做超时重传 + 请求 ID 去重——这正是at-most-once vs at-least-once 的经典案例：
rpcgen生成的客户端可以配置重传次数，服务端的重复请求缓存（duplicate request cache）在窗口内重发上次响应； - 端口映射器（portmapper / rpcbind）解决”如何动态找到服务端口”的问题：程序号（program number）+ 版本号 + 过程号构成全局名字，服务器启动时向
rpcbind（约定端口 111）注册“程序号 → 动态端口”，客户端先查rpcbind再连真正的端口。这就是”服务发现”的雏形； - NFS 建立在 Sun RPC 之上（详见 Lecture 22）；NFSv3 是无状态的（stateless），每个
READ/WRITE都独立携带文件句柄与偏移，正因为这样它才能在 at-least-once 语义下安全工作（操作幂等）。
- DCE RPC（OSF，1990s）：在 Sun RPC 基础上补齐了企业级需求：真正的 IDL（DCE IDL）与跨语言桩生成、UUID 接口标识（全局唯一接口名，替代程序号）、认证（Kerberos）、以及一套完整的命名服务（CDS）与时间服务（DTS）。DCE 的技术遗产非常深：Windows 的 RPC（MSRPC） 直接源自 DCE RPC，Windows 域环境里的认证、
\\pipe\\命名管道以及 UUID 接口标识，都是 DCE 的直系后代。 - Java RMI（1997）：把 RPC 升级为面向对象的形式——远程方法调用、序列化整个对象图作为参数/返回值、远程引用（
Remote+UnicastRemoteObject）、动态代理与注册表（rmiregistry）。它的局限正是”RPC 七条区别”的集中体现：只限 JVM（跨语言差）、序列化体积大且慢、反序列化漏洞（RCE）、依赖 TCP 双向可达（回调难穿防火墙）、缺少版本演进机制。讲义把 Java RMI 作为 at-most-once 的代表，并把它列为 RPC 在对象世界的对应物。 - CORBA / DCOM（1990s 的”统一对象总线”梦想）：CORBA 试图用 OMG IDL + 对象请求代理（ORB） + IIOP 实现”任何语言的对象调用任何语言的对象”，DCOM 是微软的对应物。讲义把 CORBA 作为 “Maybe / best-effort” 语义的代表，并把它列为中间件系统的典型例子。它们失败的原因：① 复杂度爆炸（IDL 映射、生命周期、事务、安全、事件、命名等服务层层叠加）；② 重量级运行时（部署 ORB、注册对象、管理引用，与轻量快速迭代的互联网开发方式冲突）；③ 厂商立场分裂（各 ORB 互操作性差，”CORBA 的沼泽”，而 HTTP/XML 的”最小共识”反而成功）；④ 抽象层选错——对象级远程调用（细粒度、有状态、带引用生命周期）恰是分布式系统里最难做对的粒度，而今天胜出的 gRPC 走的是”粗粒度、无状态、可重试”的路线。
- XML-RPC / SOAP / WSDL（Web Services，2000s）：用 HTTP 作传输（穿透防火墙）、XML 作编组、WSDL 作 IDL、UDDI 作服务注册，一度是企业集成的标准答案。失败原因：XML 极其冗长（一个简单调用的 SOAP 信封动辄数百字节）、解析开销大（DOM/SAX + 命名空间）、WSDL 与 WS-* 工具链复杂，以及只把 HTTP 当传输层（只用 POST，浪费了 HTTP 的缓存、状态码与语义）。
- REST：它不是 RPC。这一点必须在概念上分清：
| 维度 | RPC 风格（gRPC / SOAP / Sun RPC） | REST 风格 |
|---|---|---|
| 中心抽象 | 动作/过程（bookFlight(...)） | 资源（/flights/ABC123/seats） |
| 用什么表达操作 | 方法名 + 参数 | HTTP 动词（GET/PUT/POST/DELETE）+ 资源路径 |
| 接口描述 | IDL（.proto / WSDL / XDR） | 通常无正式 IDL；用 OpenAPI/Swagger 描述 |
| 状态 | 服务端可有会话状态（RMI/CORBA 尤其） | 无状态（讲义原话：”RESTful protocols are stateless”），每个请求自包含 |
| 可缓存性 | 一般不缓存 | GET 可被 HTTP 缓存/代理/CDN 缓存（巨大的性能与扩展优势） |
| 错误表达 | 自定义状态码 / 异常对象 | HTTP 状态码（200/201/404/409/503…） |
| 典型负载 | 二进制（protobuf/Thrift） | JSON（文本） |
| 优势 | 强类型、快、支持流、易做代码生成 | 简单、通用、易调试、对浏览器与中间设施友好 |
| 劣势 | 需要 IDL 与代码生成；对 HTTP 生态不友好 | 无 schema（类型弱）、体积大、无流式语义、资源建模有争议 |
讲义在讲 HTTP 时给出了 REST 无状态的理由，值得原样记住：“Protocols that maintain session state are complex!”——状态必须被维护和更新，而且”if server/client crashes, their views of state may be inconsistent, and hence must be reconciled“（若服务器或客户端崩溃，双方对状态的理解可能不一致，必须对账）。无状态把”对账”这个难题从服务器上移除，代价是每个请求都要携带完整上下文（最典型的就是 token 认证）。
18.2.13 现代 RPC 框架
定义与目的：现代框架 = HTTP/2（或自定义传输）+ 紧凑二进制编码 + IDL 代码生成 + 运行时中间件（截断器链）。
- gRPC（Google，2015，今天的事实标准）：
- 传输用 HTTP/2：带来四个直接收益——多路复用（multiplexing）（一条 TCP 连接上并发跑成千上万个请求，摆脱 HTTP/1.1 的连接数瓶颈）、头部压缩（HPACK）、双向流（streaming）、基于流控的连接复用；
- 编码用 Protocol Buffers：字段号 + wire type 的兼容性机制（18.2.8 详述）；
- 四种调用模式（必须记住）：(1) Unary RPC——一请求一响应，等价于经典 RPC；(2) Server streaming——客户端一个请求、服务端返回一串响应（行情推送、分块下载大结果集）；(3) Client streaming——客户端发一串请求、服务端返回一个汇总响应（分批上传 + 最终统计）；(4) Bidirectional streaming——双方各自独立收发（聊天、交互式会话）；
- 代码生成：
protoc从.proto生成消息类 + 客户端桩 + 服务端骨架，天然跨语言； - 截断器（interceptor / middleware）：统一的横切层，承载截止时间传播、重试、熔断、鉴权、指标、分布式追踪——这是现代 RPC 相比 Sun RPC 最重要的架构进步：把分布式策略从业务代码里抽出来，放到每个调用都会经过的链上；
- 截止时间（deadline）：客户端传入
deadline，框架通过grpc-timeout头把剩余时间传播给下游（见 18.2.14）。
- Apache Thrift（Facebook，2007）：与 gRPC 同期但更早，特点是可插拔协议栈：Transport（socket/TLS/文件…）$\times$ Protocol（TBinary/TCompact/TJSON）$\times$ Processor 三层自由组合，语言支持极广。TCompactProtocol 用 varint + zigzag + 字段号实现紧凑编码，思路与 protobuf 一致。代价是生态与工程体验不如 gRPC（HTTP/2、流式、跨语言一致的超时/重试语义较弱），因此今天多用于已部署的内部系统。
- Cap’n Proto / FlatBuffers：零拷贝（zero-copy）序列化。这是重要的性能突破：传统编组必须”编码 → 传输 → 解码”（两次全量 CPU 搬运），零拷贝格式让数据在字节流中的布局与在内存中的布局一致——接收方只需把收到的缓冲区当作对象直接访问（
buf.getRoot<Booking>().flightId()），没有任何解码步骤。实现要点：定长字段用固定偏移、变长字段用”相对偏移指针”、多字节值按格式规定的字节序存放。代价：字节流体积通常比 protobuf 大（为对齐与随机访问牺牲紧凑性）、schema 演进支持较弱（Cap’n Proto 靠预留字段与 union，FlatBuffers 靠 vtable 间接层）、很多实现是只读设计（变长字段难就地修改）。适用：读多写少、延迟敏感、只需访问消息中少数字段（RPC 转发代理、游戏、时序数据）。 - Avro：与前三者相反，Avro 把 schema 与数据分离——数据里不带字段号也不带标签，只有紧凑的二进制值；解析依赖 writer schema（写数据时的 schema，随文件/主题存储）与 reader schema（读数据时的 schema）之间的模式解析（schema resolution）。优势：体积最小、schema 演进表达力最强（可加默认值、可改名、可用 union）。典型用途是大数据批处理与 Kafka（配合 Schema Registry，用 schema ID 代替内联 schema）。代价：脱离 schema 无法解析字节流（不适合自描述调试场景），且 schema 变更需要注册中心治理。
JSON over HTTP（最朴素的 RPC）：
POST /api+ JSON 请求体。优点：零学习成本、人类可读、浏览器原生支持、调试工具齐全、无 IDL 治理负担。缺点：体积大（本章实测为紧凑二进制的 1.24 倍）、无 schema（字段名拼错要到运行时才炸）、解析慢、无流式/无截止时间/无标准化错误。适合低频、非性能敏感、面向外部开发者的 API，不适合服务间高频内部调用。- 现代 RPC 框架对比表：
| 框架 / 风格 | 传输 | 编码 | 流式支持 | Schema 演进 | 跨语言 | 相对性能 | 代表用户 |
|---|---|---|---|---|---|---|---|
| gRPC | HTTP/2（多路复用） | Protocol Buffers（默认） | ✅ 四种模式（unary/server/client/bidi 流） | ✅ 字段号机制，强 | ✅ 极广（protoc） | 高（紧凑 + 连接复用 + 成熟实现） | Google 内部、Kubernetes（CRI/CSI）、etcd、Envoy、各大云厂商 SDK |
| Apache Thrift | 原生 socket / 可选 HTTP | TBinary / TCompact / TJSON | ⚠️ 有限（一次一响应，无内建双向流） | ✅ 可选字段号 | ✅ 很广 | 高（TCompact 接近 protobuf） | Facebook 早期内部、HBase Thrift 接口、Evernote 等 |
| Cap’n Proto | 任意（常配自定义 socket / RPC 层） | Cap’n Proto（零拷贝） | ✅（promise pipelining） | ✅（预留字段 / union） | 中等（C++/Rust/Go/Java） | 延迟最低（解码为零），字节流偏大 | Cloudflare（Workers 内部）、Sandstorm |
| FlatBuffers | 任意 | FlatBuffers（零拷贝 + vtable） | 无内建 RPC 语义（可搭 gRPC） | ✅（vtable + 字段 ID） | ✅（C++/Java/Go/Rust/Python） | 读最快、写较慢、体积中等 | Android、游戏行业、TensorFlow Lite 模型元数据 |
| Avro | 任意（常配 Kafka / 文件） | Avro 二进制 + Schema Registry | 不适用（面向数据流/批处理） | ✅ 最强（schema resolution + 默认值） | ✅ 广 | 体积最小、编解码快 | Hadoop 生态、Kafka、Confluent Schema Registry、数据湖 |
| JSON-RPC / JSON over HTTP | HTTP/1.1 或 HTTP/2 | JSON（文本） | ❌ | ❌（弱类型，无正式机制） | ✅ 语言无关 | 低（体积大、解析慢） | 区块链节点 API（如 Ethereum JSON-RPC）、内部简单服务、公开 API |
| REST（架构风格，不是 RPC） | HTTP/1.1 或 HTTP/2 | JSON 为主 | ⚠️（可用 SSE/分块，非 RPC 语义） | ⚠️ 靠约定 + OpenAPI | ✅ 语言无关 | 中（可缓存，但文本编码慢） | 绝大多数公开 Web API、AWS S3、Stripe、GitHub |
18.2.14 RPC 的高级主题：截止时间、重试风暴、幂等键、连接与安全
定义与目的：这一节讲把实验室里的 RPC 变成生产级 RPC 的七个工程机制——它们不出现在”RPC 是什么”的教科书定义里，但决定了系统在真实故障下是否崩溃。
机制图解：截止时间传播（deadline propagation）——链路上的时间预算。
没有截止时间传播 (危险) 有截止时间传播 (gRPC 的 grpc-timeout 头)
────────────────────────────────────── ──────────────────────────────────────
客户端 deadline: 100 ms 客户端 deadline: 100 ms
│ t=0 A ──► │ t=0 A ──► (header: grpc-timeout: 100m)
│ t=10 A 调 B (不知道还剩多少时间) │ t=10 A 调 B (header: grpc-timeout: 90m)
│ t=30 B 调 C (仍以为有 100 ms) │ t=30 B 调 C (header: grpc-timeout: 70m)
│ t=100 客户端超时, 放弃 │ t=60 C 发现只剩 40ms ⇒ 降级/少查一些数据
│ t=180 C 才返回 ⇒ 150ms 的"僵尸请求"仍在跑 │ t=100 客户端超时, 且取消信号已沿链路传播
│ ⇒ 浪费 CPU/内存/连接, 甚至触发重试 │ ⇒ 无僵尸请求, 资源立即释放
────────────────────────────────────── ──────────────────────────────────────
没有传播: 每层各自拍一个超时 ⇒ 总延迟 = 各层超时之和(可能 3x), 失败后下游还在跑
有传播: 每层只判断"剩余时间是否够"⇒ 快速失败(cancel) 沿链路上传
要点：截止时间（deadline）与超时（timeout）不同——timeout 是”我最多等多久”（相对时间，每层独立），deadline 是”这个请求最晚必须完成”（绝对时间，可跨进程传递）。必须传绝对时间或剩余时间，否则下游只能重新计时，链路上每一层都会把总时长加长一次。gRPC 用 grpc-timeout 头承载剩余时间，并在取消（cancellation）时沿链路传播取消信号，让下游立刻停止无用功。
- 重试（Retry）与重试风暴（Retry Storm）：重试放大是乘性的：设每个服务有 $n$ 个上游、失败时重试 $r$ 次，一次故障会让下游负载瞬时放大到 $1+r$ 倍；跨多层则按 $(1+r)^{\text{层数}}$ 增长。级联雪崩的典型剧本：某后端变慢 → 上游超时 → 上游重试 → 下游负载翻倍 → 更多请求超时 → 更多重试 → 整个集群被自己的重试流量压垮（故障从”慢”升级为”全挂”）。工程解法（必须成套使用）：
- 指数退避 + 抖动（exponential backoff with jitter）：第 $k$ 次重试等待 $\min(\text{base}\cdot 2^k, \text{cap})\cdot U(0,1)$；“抖动”是必须的——否则所有客户端会同时醒来重试（惊群 / thundering herd），把随机故障变成规律性打击；
- 重试预算（retry budget）：限制”重试请求 / 原始请求”的比值（如 10%），预算按服务、按集群全局统计，超预算就拒绝重试——把重试从”每个客户端各自为政”变成”集群级控制”；
- 断路器（circuit breaker）：连续失败超阈值就直接快速失败（不发请求），避免把流量打给已确定不可用的下游，并定期”半开”探测恢复；
- 负载丢弃（load shedding）：过载时主动拒绝部分请求（
503/RESOURCE_EXHAUSTED），保住已接受请求的延迟——“拒绝一部分”通常优于”全部变慢”； - 只在幂等操作上重试，且重试必须尊重 deadline 的剩余时间（剩余时间不够就不该重试）。
- 幂等性与去重（idempotency key）：既然 exactly-once 的传输层不可得，工程标准做法是 “at-least-once 传输 + 幂等处理 + 业务去重表”：客户端为每个业务操作生成幂等键（idempotency key，通常 UUID），服务端把
idempotency_key → 处理结果写进带唯一约束/事务的存储；重复请求到来时唯一约束冲突即意味着”已处理过”，直接返回上次结果。关键点是去重状态与业务状态在同一事务里提交（”记账”与”去重”原子化），这样即使服务端崩溃重启也不会重复执行。这就是 Stripe 的Idempotency-Key头、Kafka 幂等生产者（producer ID + 序列号）、etcd/ZooKeeper 客户端去重表所用的同一机制。注意幂等键的作用域：必须限定在”同一客户端 + 同一业务意图”，不能跨用户复用（否则用户 A 的操作会返回用户 B 的结果——这是真实发生过的严重漏洞）。 - 连接管理与负载均衡：长连接 + 连接池避免每次调用的 TCP 三次握手与 TLS 握手（后者代价巨大：一次完整握手要 1-2 个 RTT 加非对称加密运算）；多路复用（HTTP/2）让一条连接承载大量并发请求；客户端负载均衡（client-side LB） 由客户端直接选择后端（省一跳，但需要服务发现且客户端要感知后端列表变化），服务端/代理式负载均衡（service mesh） 由独立代理（Envoy/Linkerd）承担（对应用透明，但多一跳延迟）。服务发现负责”后端列表从哪来”：DNS、注册中心（Consul/etcd/ZooKeeper）或平台内建（Kubernetes Service/Endpoint）。与 Lecture 17 的联系：注册中心本身必须强一致（否则会返回已死的后端或脑裂视图），因此它内部就用了 Raft/Paxos。
- 序列化的安全问题：这是必须强调的一条红线。编组的逆过程——反序列化——在很多语言里可以执行代码：
- Java 反序列化（
ObjectInputStream.readObject）：反序列化会调用对象的readObject/readResolve，攻击者构造恶意 gadget 链即可实现 RCE（远程代码执行）；Apache Commons Collections、WebLogic、Jenkins 等都因此出过严重漏洞； - Python
pickle：pickle.loads会按字节流里的指令构造任意对象并调用任意可调用对象（__reduce__直接给出”调用谁、用什么参数”）。因此pickle从来不是一个”安全的数据格式”，它只是一个”Python 对象的转储格式”； - PHP / .NET 的同类机制同样存在反序列化 RCE。 结论（必须记住）：永远不要对不可信来源的字节流做反序列化。工程对策：(a) 用只有数据、没有行为的格式（protobuf/JSON/FlatBuffers 的解析器不会执行代码，只构造数据）；(b) 若必须用原生序列化，加上密码学完整性保护（签名/MAC + 类白名单过滤器，如 Java 的
ObjectInputFilter）；(c) 把解析放在强隔离进程中（沙箱、低权限容器）；(d) 限制消息尺寸与嵌套深度（防御解组炸弹）。本章18-C3用无害 payload演示了pickle.loads能执行任意代码。（安全详见 Lecture 25。）
- Java 反序列化（
18.3 算法伪代码与正确性分析
算法 18.3.1：RPC 客户端与服务端桩的完整流程（含请求 ID 与 dispatcher 分派）
假设与系统模型
- 进程模型：客户端 $P_c$ 与服务端 $P_s$ 是两个独立进程，各有独立地址空间；服务端可能同时服务 $m$ 个客户端（并发）。
- 故障模型：crash-stop / crash-recovery（进程可能崩溃，也可能重启后继续服务）；非 Byzantine（不会伪造/篡改消息）。
- 通道假设：异步、可能丢失、可能重复、可能乱序的可靠字节流之上（TCP 提供有序不丢的字节流，但连接断开等价于消息丢失；UDP 直接提供”可能丢失/重复/乱序”的数据报）。“有序”不等于”不会重复”——应用层重传与中间设备仍会制造重复。
- 接口模型：$k$ 个方法的接口，每个方法有唯一的过程标识符 $pid \in \{1,\dots,k\}$；客户端请求 ID 由 $(\text{client\_id}, \text{seq})$ 唯一确定，
seq单调递增且永不复用。 - 目标（本算法只保证”流程正确”）：消息与调用的正确配对（不会把响应交给错误的调用），以及编组/解组的互逆。调用语义（0 次/1 次/多次执行）由 18.3.3、18.3.4 分别处理。
伪代码
── 客户端 runtime 状态 ──
seq := 0 # 单调递增的请求序号
pending := {} # req_id -> 等待该响应的同步量/回调
conn # 到 server 的通信通道
── 客户端桩 (每个方法一个, 由 IDL 生成, 与本地调用同签名) ──
procedure stub_f(x1, ..., xn) # f 的过程标识符为 pid_f
msg := <pid := pid_f, args := marshal(x1,...,xn)> # 编组
reply := RPC_CALL(msg)
return unmarshal(reply.ret) # 解组
procedure RPC_CALL(msg) # 由客户端 runtime 提供
seq := seq + 1 ; rid := (my_id, seq)
pending[rid] := <waiter>
send(conn, <type := REQUEST, req_id := rid, body := msg>)
upon reply := receive_response(rid) or timeout(rid):
if reply is a RESPONSE and reply.req_id = rid:
pending.remove(rid)
return reply.body # 正常路径
else: # 超时
pending.remove(rid)
return <status := INDETERMINATE> # ★ 不知道对方是否执行
end
── 服务端 runtime / dispatcher / 服务端桩 ──
upon receive(conn, m) and m.type = REQUEST:
if sem == AT_MOST_ONCE or sem == EXACTLY_ONCE:
if DEDUP_CHECK(m.req_id) = HIT: # 见算法 18.3.3
send(conn, DEDUP_GET_REPLY(m.req_id)) ; return
stub := DISPATCH(m.body.pid) # ★ dispatcher: pid -> server stub
if stub = nil:
send(conn, <type := ERROR, req_id := m.req_id, status := UNIMPLEMENTED>) ; return
try:
args := unmarshal(m.body.args) # 解组(含边界与类型校验)
catch BadEncoding:
send(conn, <type := ERROR, req_id := m.req_id, status := BAD_REQUEST>) ; return
result := stub.f(args) # ★ 调用真正的服务过程
out := marshal(result) # 编组返回值
if sem == AT_MOST_ONCE or sem == EXACTLY_ONCE:
DEDUP_STORE(m.req_id, out) # 先缓存, 再发送
send(conn, <type := RESPONSE, req_id := m.req_id, body := out>) # ★ 携带同一 req_id
算法逻辑解说
- 调用者视角只有一行：
z := f(x, y)。桩负责后续一切；这正是讲义所说的”client stub 与 callee 同签名，因此同一份caller()代码既可用于 LPC 也可用于 RPC“。 - 编组在发消息之前完成：如果参数里有不可编组的类型（文件句柄、线程锁、函数指针），必须在本地就失败，绝不能发出半个消息——否则服务端会收到一个无法解组的骨架。
req_id是配对的唯一依据：客户端把(my_id, seq)放进请求，服务端原样回填到响应；客户端用pending[rid]找到等待者。没有请求 ID 就无法支持”一条连接上多个并发请求”（HTTP/1.1 的管线化就因为没有 ID 而必须严格保序，最终失败）。- dispatcher 是一张表：
pid → server stub。讲义原文是”selects which server stub to forward request to”。它是版本兼容的关口：未知pid直接返回UNIMPLEMENTED，客户端能确定未执行。 - 服务端的异常也要变成响应：
try/catch把服务端异常编组成ERROR消息回传，否则客户端只能等到超时——“快速失败”与”超时失败”在语义上完全不同（前者确定未执行，后者不确定）。 - 一个具体小例子：客户端调用
add(2,3)：seq=7，编组得1B 01 04 01 06（TAG_INT,2与TAG_INT,3）；服务端pid=1命中add的桩，解组得(2,3)，执行得5，编组响应[rid=7, ok=True, 5]回传；客户端按rid=7匹配、解组得5。
正确性论证
- 安全性 Safety 1（响应不会错配）：设客户端为请求 $r_1$（
req_id$= (c,s_1)$）与 $r_2$（(c,s_2)$，$s_2 \ne s_1$）各等待一次响应。服务端为每个收到的请求**生成携带其自身req_id的响应**（伪代码中m.req_id原样回填），因此任何响应都只可能满足**唯一一个**pending表项。又因为seq单调递增且不复用，故不存在两个不同请求具有相同req_id，**响应绝不会被交给错误的调用**（除非客户端把req_id` 复用——所以”永不复用”是这条论证的关键假设）。 - 安全性 Safety 2（编组/解组的互逆）：该性质由算法 18.3.2 单独论证（$\text{decode}(\text{encode}(x))=x$）。本算法只依赖它，并额外要求解组失败时绝不放行到业务函数：伪代码中
unmarshal抛异常即直接返回BAD_REQUEST，因此畸形消息不会导致服务端执行任何业务逻辑。 - 活性 Liveness（客户端最终得到答复）：若请求与响应各在有限时间内到达、且服务端不崩溃，则客户端在超时前收到响应并返回（有限步）。若发生丢失，活性只能由重传提供——这正是 18.3.4 的内容；本算法在不重传时只能保证”最终返回一个结果或 INDETERMINATE”，即”有限时间内有答复“，而不是”有限时间内有正确结果”。
- 不可保证的性质（必须明确指出）：“服务端是否执行了”无法由本算法确定。因为超时是纯本地事件（本地计时器到期），它与”请求丢失”“响应丢失”“服务端崩溃”这些远端事实没有必然联系。这是 RPC 部分失败的形式化表述：$\text{timeout} \not\Rightarrow \neg\text{executed}$，也 $\text{timeout} \not\Rightarrow \text{executed}$。
复杂度
- 消息复杂度：每次调用 2 条消息（1 请求 + 1 响应）；无重传时为最小下界（至少需要 1 个往返）。
- 时间：编组 $O(\text{size}(args))$ + 1 RTT + 服务时间 + 解组 $O(\text{size}(ret))$。
- 客户端空间：
pending表大小 = 并发在途调用数 $w$，$O(w)$。 - 服务端空间：无状态时为 $O(1)$（每个连接一个线程/会话）；开启去重后为 $O(W \cdot m)$（$W$ 为窗口宽度，$m$ 为客户端数）。
算法 18.3.2：编组/解组的编解码算法（字节序、定长/变长字段、嵌套结构）
假设与系统模型
- 值域：$x \in \{\text{bool},\text{int64},\text{double},\text{string(UTF-8)},\text{list},\text{map(string}\to\text{value)}\}$（足够覆盖 RPC 参数的绝大多数情况）。
- 规范表示（canonical representation）：所有多字节整数与浮点统一大端序（network byte order）；整数用 zigzag + varint；字符串/容器用 varint 长度前缀；浮点用 IEEE 754 binary64 的 8 字节大端；每个值前有 1 字节类型标签；map 的键约定为字符串因而省略标签。
- 接收方不信任输入：长度字段必须与剩余字节数比较，标签必须在已知集合内，递归深度要有上限。
伪代码
# ---- 编码 ----
function ENCODE(x) -> bytes
if x is bool: return TAG_INT || PUT_VARINT(zigzag(int(x)))
if x is int: return TAG_INT || PUT_VARINT(zigzag(x))
if x is double: return TAG_FLOAT|| PUT_BE64(x) # struct.pack('!d', x)
if x is string: b := utf8(x) ; return TAG_STR || PUT_VARINT(len(b)) || b
if x is list:
out := TAG_LIST || PUT_VARINT(len(x))
for each e in x: out := out || ENCODE(e) # 元素自带标签
return out
if x is map:
out := TAG_DICT || PUT_VARINT(len(x))
for each (k, v) in x:
kb := utf8(k)
out := out || PUT_VARINT(len(kb)) || kb || ENCODE(v) # 键无标签
return out
raise UnsupportedType(type(x)) # ★ 本地失败, 不发半个消息
function zigzag(n) = (n << 1) XOR (n >> 63) # 有符号 -> 无符号
function PUT_VARINT(u): # 每字节 7 位 + 继续位
out := empty
repeat: byte := u AND 0x7F ; u := u >> 7
out := out || (byte OR (0x80 if u > 0 else 0x00))
until u = 0 ; return out
# ---- 解码 ----
function DECODE(buf, off) -> (value, new_off)
require off < len(buf) else raise BadEncoding # ★ 边界检查
tag := buf[off] ; off := off + 1
if tag = TAG_INT: (u, off) := GET_VARINT(buf, off)
return UNZIGZAG(u), off
if tag = TAG_FLOAT:
require off + 8 <= len(buf) else raise BadEncoding
return BE64_TO_DOUBLE(buf[off..off+8]), off + 8
if tag = TAG_STR:
(n, off) := GET_VARINT(buf, off)
require off + n <= len(buf) else raise BadEncoding # ★ 不信声明的长度
return utf8_decode(buf[off..off+n]), off + n
if tag = TAG_LIST:
(n, off) := GET_VARINT(buf, off)
require n <= MAX_ELEMS else raise TooLarge # ★ 防解组炸弹
out := [] ; repeat n times: (v, off) := DECODE(buf, off) ; out.append(v)
return out, off
if tag = TAG_DICT:
(n, off) := GET_VARINT(buf, off)
require n <= MAX_ELEMS else raise TooLarge
out := {} ; repeat n times:
(ln, off) := GET_VARINT(buf, off)
require off + ln <= len(buf) else raise BadEncoding
k := utf8_decode(buf[off..off+ln]) ; off := off + ln
(v, off) := DECODE(buf, off) ; out[k] := v
return out, off
raise BadEncoding("unknown tag")
function UNZIGZAG(u) = (u >> 1) XOR (-(u AND 1))
算法逻辑解说
以 18.2.7 的具体例子走一遍：book(300, "ORD", 289.5, [1,12,300])。
300：zigzag(300) = 600 = 0b1001011000→ 低 7 位1011000 = 0x58带继续位得0xD8；600 >> 7 = 4→0x04。故300编码为01 D8 04（标签 + 2 字节 varint）。若用固定 8 字节整数，这里要多花 6 字节。"ORD"：TAG_STR=0x03，长度 3 →03，内容4F 52 44。03 03 4F 52 44。解码方必须检查off + 3 <= len(buf)，否则一个声称长度为 $2^{31}-1$ 的恶意字符串就能触发崩溃。289.5：02 40 72 18 00 00 00 00 00（0x4072180000000000是 289.5 的 IEEE 754 binary64 大端表示）。注意这是无法压缩的固定 8 字节——这也是”二进制格式并不总是更小”的原因之一。[1,12,300]：04+ 元素数03+ 三个元素各自带标签：01 02（1 的 zigzag=2）、01 18（12 的 zigzag=24）、01 D8 04（300）。合起来04 03 01 02 01 18 01 D8 04。- 嵌套结构靠”元素自带标签 + 长度前缀”递归解析：解析器不需要外部 schema就能知道边界在哪——这是 tagged 编码相对 positional 编码的核心优势（代价是每个值多 1 字节标签；对
[1,12,300]这样的数组，标签占了 3/9 的字节，这正是 protobuf 用 packed repeated 把标签压成一个的原因）。
正确性论证
- 定理（互逆性）：对所有合法输入 $x$，$\text{DECODE}(\text{ENCODE}(x), 0) = (x, \text{len}(\text{ENCODE}(x)))$。按 $x$ 的结构归纳（structural induction）：
- 基础情形：bool/int 用双射的 zigzag（$\text{UNZIGZAG}(\text{zigzag}(n)) = n$ 对所有 64 位整数成立，因为右移与异或在符号位上互为逆运算）；double 用 IEEE 754 的固定 8 字节大端（
BE64_TO_DOUBLE与PUT_BE64互为逆）；string 用 UTF-8 编解码（互为逆）+ 长度前缀。 - 归纳情形（list）：设长度 $n$ 的前缀编码为 $\text{PV}(n)$ 且 $\text{GET\_VARINT}(\text{PV}(n)) = (n, \vert \text{PV}(n)\vert )$（varint 的可解性：每字节 7 位、最高位为继续标志，故按位拼接可唯一还原，且终止位置唯一确定）。归纳假设每个元素 $e_i$ 满足互逆性，解码器按 $n$ 次递归依次消费字节，由于每一步都返回精确的新偏移，故总偏移等于总编码长度，还原出的列表等于 $[e_1,\dots,e_n]$。
- 归纳情形（map）：与 list 同理，键用”长度前缀 + 字符串”编码（无标签但仍自界定），值用归纳假设；键的唯一性由 Python dict 保证，故 $n$ 对键值足以唯一还原。
- 边界条件对论证的影响：varint 的非规范编码（如
0x80 0x00表示 0）虽然能解码出相同的值，但在规范表示下不允许出现——这正对应 ASN.1 中 BER 与 DER 的区别（DER 要求唯一编码），在需要”字节流可作为指纹/签名对象”的安全场景中，唯一性是必需的。
- 基础情形：bool/int 用双射的 zigzag（$\text{UNZIGZAG}(\text{zigzag}(n)) = n$ 对所有 64 位整数成立，因为右移与异或在符号位上互为逆运算）；double 用 IEEE 754 的固定 8 字节大端（
- 安全性（抗畸形输入）：每次读取都先做边界检查，故解码器永不越界读取；
MAX_ELEMS与递归深度上限保证解码所需时间为 $O(\text{输入长度})$ 而非指数级（否则一个嵌套很深的 list 会耗尽栈）。注意：这些检查只保证”不崩溃”，不保证”内容是善意的”——语义层的校验（如”金额必须为正”）必须在业务函数里做。 - 活性：解码每一步都严格推进偏移（
off至少 +1，且每次读取前已确认有足够字节），故必然在 $\le \text{len}(buf)$ 步内终止：要么成功返回，要么抛出BadEncoding，不会死循环。
复杂度
- 时间：编码/解码均为 $O(s)$，$s$ = 序列化后的字节数（每个字节常数次操作）。递归深度 $O(d)$，$d$ = 嵌套深度。
- 空间：编码 $O(s)$（单趟追加即可，无回溯）；解码 $O(s)$（构造出的对象）$+\ O(d)$（栈）。
- 字节效率：小整数 1 字节（vs 固定 8 字节）、短字符串 $1+\ell$ 字节、每个值 1 字节标签开销。实测（18-C3）：一个含 2 个嵌套对象 + 2 个 double + 8 个整数的典型 RPC 参数，本格式 152 字节，JSON 189 字节，pickle 192 字节。
算法 18.3.3：RPC drop box（去重缓存）实现 exactly-once
假设与系统模型
- 通道：可能丢失、可能重复、可能乱序投递（因此去重不能依赖”重复紧跟在原请求之后”）。
- 故障模型：(i) 强假设（正确性前提）：服务端从不崩溃（crash-free），或去重表被持久化/复制从而可在崩溃恢复后重建。(ii) 弱假设（真实情形）：服务端可能 crash-recovery 且内存去重表丢失——此时exactly-once 不成立，退化为 at-least-once。本节会明确区分这两个情形。
- 客户端模型：客户端为每个逻辑调用生成唯一 $(cid, seq)$，永不提前复用；客户端可能重传同一 $(cid, seq)$ 任意多次。
- 参数：窗口宽度 $W$（缓存最近 $W$ 个序号）；客户端数 $m$。
伪代码
── 服务端去重表状态 ──
highest[cid] : the largest seq seen from client cid, 初值 0 # 每客户端一个水位
cache[cid] : ordered map seq -> reply, 只保留 (highest[cid]-W, highest[cid]] 区间
hits : 去重命中计数 (用于监控)
── 处理一个到达的请求 (cid, seq, op, args) ──
procedure HANDLE(cid, seq, op, args):
# 情形 1: 序号落在已处理区间内 => 必然是重复
if seq <= highest[cid]:
if seq in cache[cid]:
hits := hits + 1
SEND_REPLY(cache[cid][seq]) # ★ 重发缓存响应, 绝不重新执行
return
else: # 已滑出窗口: 无法判定
SEND_REPLY(<status := INDETERMINATE, # 或选择重新执行(违反 exactly-once)
reason := "seq expired from window">)
return
# 情形 2: 新请求 (seq > highest[cid]) —— 注意乱序到达时跳号也要接受
reply := EXECUTE(op, args) # ★ 唯一真正执行的位置
cache[cid][seq] := reply
highest[cid] := max(highest[cid], seq)
EVICT(cid) # 回收窗口外条目
SEND_REPLY(reply)
procedure EVICT(cid):
while smallest seq in cache[cid] <= highest[cid] - W:
delete that entry
—— 崩溃恢复（弱假设下的关键动作） ——
upon restart:
if dedup table is persistent: RELOAD(cid, highest[cid], cache[cid])
else: highest[*] := 0 ; cache[*] := {} # ★ 去重能力完全丢失!
算法逻辑解说
- 判重依据是
(cid, seq)的精确匹配，而不是”内容相同”。理由：内容相同的两次合法调用（”再买一张同样的票”）必须都被执行；只有同一客户端、同一序号才表示”同一个逻辑调用”。 highest[cid]水位 + 窗口的两级判定：seq > highest[cid]一定是新请求（无需查表，$O(1)$）；seq <= highest[cid]才需要查缓存，命中则重发响应，未命中说明”太老、已滑出窗口”。- 乱序处理：由”重传 + 乱序”造成的到达顺序可能是 $7, 9, 8$——
9到达时highest升到 9，之后8到达时8 <= 9且8在窗口内 ⇒ 正确判为重复。但若8是真正的第一次到达（不是重复）（例如客户端不同线程乱序发出），它会被误判为重复并重发一个并不存在的缓存响应——因此真实实现要么强制每个客户端只有一个在途请求（串行调用），要么只用seq判重而不阻止跳号（即：seq > highest[cid]就执行，即使它不是highest+1）。本伪代码采用后者（highest := max(...)而非highest := seq），这是重要细节。 - 一个具体的数值例子（$W=3$）：客户端依次发出
seq = 1,2,3,4；服务端highest=4，cache={2:r2, 3:r3, 4:r4}（1已滑出）。此时到达重复的seq=3⇒ 命中，重发r3，不重新执行；到达重复的seq=1⇒ 未命中，返回INDETERMINATE（或重新执行，从而违反 exactly-once）。 - 崩溃恢复是最脆弱的一环：若去重表在内存里，重启后
highest=0、cache={}，则一个”延迟很久的重复请求”会被当成全新请求重新执行 ⇒ 重复副作用。
正确性论证
- 定理（在服务端不崩溃的前提下，exactly-once）：设一次逻辑调用对应唯一标识 $(cid, seq^\)$，且客户端对该标识只发送这一种请求（重传只改变消息份数，不改变标识）。若服务端从不崩溃（或被复制的去重表可恢复），则
EXECUTE对每个 $(cid, seq^\)$ 恰好被调用一次。- 至多一次（Safety）：
EXECUTE只出现在”情形 2”的代码路径上，而进入情形 2 的充要条件是seq > highest[cid]。该分支执行时立即把highest[cid]提升到 $\ge seq$ 并把响应写入cache。由于highest[cid]单调不减，同一seq的第二次到达必然满足seq <= highest[cid]，从而进入情形 1，不可能再次到达EXECUTE（除非它已滑出窗口——这正是下面要指出的失败条件）。故EXECUTE对同一标识至多一次。 - 至少一次（Liveness）：客户端在超时后重传，只要至少一份请求在有限时间内到达服务端且未被判为过期，服务端即执行一次并回响应；响应若丢失，重传会命中缓存并重发同一响应，因此客户端最终能拿到结果（前提是重传次数足够、且请求不早于窗口过期）。
- 合起来 = 恰好一次。
- 至多一次（Safety）：
- 失败条件（必须明确、这是本算法最重要的一条）：
- 窗口过期：若
seq <= highest[cid]但seq ∉ cache[cid]（已滑出窗口），算法无法判定是否执行过：返回INDETERMINATE则丧失活性（客户端永远拿不到结果），重新执行则丧失安全性（可能重复）。因此 $W$ 必须大于”客户端可能的最大在途时间跨度”（最大重试次数 $\times$ 最大超时 $+$ 网络最大抖动）。任何有限窗口都无法提供绝对的 exactly-once——这是工程参数，不是理论保证。 - 服务端崩溃且去重表丢失：恢复后
highest=0，所有”延迟重复”都被视为新请求 ⇒ 重复执行。因此真正的 exactly-once 需要持久化的去重状态或共识：把 $(cid, seq, reply)$ 写入持久日志，或用复制状态机（Lecture 17 的 Paxos/Raft）把去重记录复制到多数派——这正是”exactly-once 需要共识”的准确含义。 - 客户端标识复用：若客户端重启后
cid不变而seq又从 1 开始，则会与旧记录冲突（旧序号被误判为重复）⇒ 必须每次客户端会话生成新的cid（如 UUID），或把会话 ID 纳入标识。 - 去重表本身不可被用户数据污染：
cid必须由服务端认证后赋给，不能由客户端自由指定（否则恶意客户端可以伪造别人的cid来读取别人的响应——这是真实系统里的越权漏洞）。
- 窗口过期：若
- 与 Lecture 17 的联系：状态机的客户端去重（client session / dedup table） 也是复制状态机的标准组成部分——Paxos/Raft 保证”日志不丢”，应用层保证”重复日志不重复执行”，两者合起来才是端到端的”恰好一次”。
复杂度
- 时间：去重判定 $O(1)$（水位比较 + 哈希查表）；
EVICT均摊 $O(1)$ 每条。 - 空间：$O(m \cdot W)$ 条响应缓存（若响应很大，实际系统会只缓存响应摘要或指纹，或对超过阈值的响应改存到外部存储）。
- 消息复杂度：不变（去重不增加消息，只是把”重新执行”变成”重发缓存”）；但带宽可能增加（重发完整响应而非重新计算结果）。
- 缓存失效率：在总请求数 $N$、窗口 $W$、重传延迟分布下，失效率 ≈ $P(\text{重复请求的年龄} > W)$。工程经验：把 $W$ 取为”正常重试时间跨度的 10 倍”以上。
算法 18.3.4：at-most-once 与 at-least-once 的语义对比实现
假设与系统模型
- 与 18.3.1 相同的进程与通道模型（异步、可丢失、可重复）。
- 超时 $T$：客户端本地计时器；最大重试次数 $R$（$R=1$ 表示”只发一次”）。
- 服务端提供同一接口
op(args) -> reply；测量量：$E$ = 服务端EXECUTE的实际调用次数（这是判断语义的唯一客观依据），$\text{Reply}$ = 客户端观察到的结果。 - 两种客户端实现共享同一套桩与编组代码，唯一差别在重传策略（以及服务端是否开启去重）。
伪代码
# ============ 客户端 A: at-most-once 风格 (不重传) ============
procedure CALL_A(op, args):
seq := seq + 1 ; rid := (my_id, seq)
send(<REQUEST, rid, op, args>) # ★ 只发一次, 绝不重发
reply := wait_for_reply(rid, timeout = T)
if reply = nil:
return <status := FAILED, certainty := UNKNOWN> # ★ 失败≠未执行(响应可能只是丢了)
return <status := OK, value := unmarshal(reply.body)>
# ============ 客户端 B: at-least-once 风格 (超时重传) ============
procedure CALL_B(op, args):
seq := seq + 1 ; rid := (my_id, seq)
for attempt in 1 .. R:
send(<REQUEST, rid, op, args>) # ★ 同一 rid 重传多次
reply := wait_for_reply(rid, timeout = T)
if reply ≠ nil:
return <status := OK, value := unmarshal(reply.body), attempts := attempt>
return <status := FAILED, attempts := R>
# ============ 服务端: 两种模式 ============
procedure SERVER_HANDLE(req):
if mode = DEDUP_ON: # exactly-once 所需的额外一步
if (req.cid, req.seq) in cache:
send(cache[(req.cid, req.seq)]) ; return # 重发, 不重新执行
result := EXECUTE(req.op, req.args) # E := E + 1
if mode = DEDUP_ON:
cache[(req.cid, req.seq)] := marshal(result)
send(<RESPONSE, req.rid, marshal(result)>)
算法逻辑解说
- 两者的差别只有三行：A 用
send一次就等（R=1且不回环），B 把send放进for attempt in 1..R循环。桩、编组、请求 ID、dispatcher 全部相同——这正好印证了本讲的核心论点：RPC 的困难与设计重点在”语义策略”，而不在”调用语法”。 - 在无故障时两者完全无法区分：$E=1$、客户端都得到结果、延迟相同。语义差别只在故障下显现——这是本章实验
18-C2反复强调的一点，也是为什么”RPC 语义”必须用注入故障的方式才能观察到。 - 在”响应丢失”下三者分道扬镳（实测数据，见 18.4 的
18-C2输出）：
| 场景（1 次逻辑调用） | at-most-once（不重传） | at-most-once + 去重 | at-least-once（重传） | exactly-once（重传 + 去重） |
|---|---|---|---|---|
| 响应丢失 | $E=1$，客户端超时/无结果（假失败，副作用已发生） | $E=1$，客户端超时/无结果 | $E=\mathbf{2}$（重复执行！），客户端得到结果 | $E=1$，去重命中 1 次，客户端得到结果 |
| 请求丢失 | $E=0$，客户端超时 | $E=0$，客户端超时 | $E=1$，客户端得到结果 | $E=1$，客户端得到结果 |
| 请求被重复投递 | $E=\mathbf{2}$（网络重复，客户端不知情） | $E=1$（去重命中） | $E=\mathbf{2}$ | $E=1$（去重命中） |
- 随机丢包下的统计对比（$p_{\text{req}}=0.25$，$p_{\text{resp}}=0.25$，$p_{\text{dup}}=0.10$，15 次调用）：at-most-once 成功 2 次 / 服务端执行 14 次；at-least-once 成功 13 次 / 服务端执行 28 次（出现 13 次重复副作用）；exactly-once 成功 13 次 / 服务端执行 15 次（去重命中 13 次，零重复副作用）。at-least-once 用”13 次重复副作用”换来了”成功次数从 2 提升到 13”——这就是语义选择的真实权衡。
正确性论证
- at-most-once（不重传）的安全性：客户端对每个逻辑调用只发送一次请求消息（伪代码 A 中
send在循环之外），因此服务端最多收到一份该标识的请求 ⇒ $E \le 1$（在无网络重复投递的假设下）。但必须强调：这不是”服务端最多执行一次”的完整保证——若网络或中间设备重复投递同一请求（伪代码 B 之外的因素），服务端仍会执行两次（实测表中第三行即为此情形）。真正的 at-most-once 需要服务端去重（讲义原表的 “Filter duplicate requests” 列）。 - at-most-once 的活性缺陷（这是它的本质代价）：由于不重传，任何单次消息丢失都会导致调用失败。形式上：$P(\text{成功}) = P(\text{请求不丢}) \cdot P(\text{响应不丢})$。在 $p=0.25$ 的实测中只有 $2/15 \approx 13\%$ 成功。因此它只适合”失败可以安全上报给上层/用户”的场景（例如用户可见的”下单失败，请重试”），不适合”必须有结果”的后台任务。
- at-least-once 的安全性 = 无：算法没有任何机制阻止重复执行（服务端不去重、客户端重传），因此$E$ 无上界（$E \le R$ 在”每份请求最多到达一次”时成立，但网络重复会打破它；实测 $E=28 > 15$ 即为证据）。它唯一保证的是”$\ge 1$”——这要求”至少一份请求到达且至少一份响应回到客户端”。
- at-least-once 的正确性前提（幂等性）：设操作 $f$ 满足 $f(f(x)) = f(x)$（幂等），则重复执行不改变最终状态，于是”$E \ge 1$”就是可接受的语义。形式化地：若操作的副作用映射 $S$ 满足 $S \circ S = S$（幂等），则对任意 $E \ge 1$，最终状态 $S^{E}(s_0) = S(s_0)$ 与 $E=1$ 相同，因此 at-least-once 在幂等操作上等价于 exactly-once 的效果。这解释了讲义为什么说”Idempotent operations can be used with at-least-once semantics”——幂等性把”至少一次”的语义缺陷抵消掉了。反之，若 $S$ 不幂等（如
x = x + 1），则 $S^E(s_0) \ne S(s_0)$，正确性被破坏。 - 活性（两者都成立）：只要 $R$ 有限且每次尝试的超时为 $T$，客户端必然在 $\le R \cdot T$ 内返回（要么成功、要么报告失败）——这就是”有限时间有答复”，但答复的内容（成功/失败）不保证与远端事实一致。
复杂度
| 指标 | at-most-once（不重传） | at-least-once（重传，$R$ 次） | exactly-once（重传 + 去重） |
|---|---|---|---|
| 最坏消息数 | 1 | $2R$ | $2R$ |
| 服务端执行次数 | $\le 1$（需服务端去重） | $\ge 1$，无上界 | $=1$（服务端不崩溃时） |
| 客户端额外空间 | $O(1)$ | $O(1)$（只有当前 rid） | $O(1)$ |
| 服务端额外空间 | 无 | 无 | $O(m \cdot W)$ |
| 成功概率（单边丢失率 $p$） | $(1-p)^2$ | $1-p^{2R}$ 量级（近似） | $1-p^{2R}$ 量级 |
| 失败模式 | 假失败（执行了但报错） | 重复副作用 | 窗口过期/服务端崩溃时退化为上述两者 |
算法 18.3.5：异步 RPC 与截止时间传播
假设与系统模型
- 调用链长度 $k$（客户端 → $S_1$ → $S_2 \to \dots \to S_k$），每跳处理时间 $c_i$，网络单程延迟 $d_i$。
- 绝对截止时间（deadline） $D$：由最初的客户端设定（如 $D = t_0 + 500\,\text{ms}$），以绝对时刻的形式沿链路传递（或等价地传递”剩余时间”）。
- 时钟假设：各节点的物理时钟只是近似同步（详见 Lecture 26），因此工程上使用剩余时间（budget） 而非绝对时刻更稳健：每跳收到”我还剩多少时间”，再减去本跳开销后往下传。gRPC 的
grpc-timeout头正是”剩余时间”。 - 故障模型同 18.3.1；取消（cancellation）是尽力而为的：取消信号本身可能丢失，因此每个节点仍必须自己检查本地剩余时间。
伪代码
── 客户端: 并发发起 n 个异步调用并等待全部完成 ──
procedure FANOUT(requests, budget):
D := now() + budget
futures := []
for r in requests:
futures.append(ASYNC_CALL(r, deadline = D)) # ★ 不阻塞, 立即返回 Future
results := AWAIT_ALL(futures, deadline = D) # asyncio.gather / Promise.all
return results # 任一个超过 D 则整体失败
procedure ASYNC_CALL(r, deadline):
rid := (my_id, next_seq())
sends: <REQUEST, rid, r, timeout := REMAINING(deadline)> # ★ 携带剩余时间
return Future(rid) # 结果到达时 resolve
function REMAINING(deadline) = max(0, deadline - now())
── 服务端 Si 收到请求 (含 timeout 字段 = 上游剩余时间) ──
upon receive(<REQUEST, rid, body, timeout>):
my_deadline := now() + timeout # 换算成本地截止时刻
if REMAINING(my_deadline) <= 0:
send(<ERROR, rid, status := DEADLINE_EXCEEDED>) ; return # ★ 过期直接拒绝, 不做无用功
budget_for_child := REMAINING(my_deadline) - ESTIMATED_LOCAL_COST
if HAS_DOWNSTREAM(body):
child_deadline := my_deadline
results := FANOUT(child_requests, budget_for_child) # ★ 递归传播
else:
results := LOCAL_PROCESS(body, deadline = my_deadline) # 只做"剩余时间够用"的工作
send(<RESPONSE, rid, results>)
── 取消传播 (尽力而为) ──
upon local timer expires or upstream sends <CANCEL, rid>:
mark rid as cancelled
send <CANCEL, rid> to all downstream nodes still working on rid # 递归向下
abort local computation for rid ; free buffers/connections
算法逻辑解说
deadline必须传播，否则产生”僵尸请求”：若无传播，每层各自拍一个超时 $T$，则总时长可能达到 $\sum_i T_i \approx kT$（各层串行累加），并且在客户端已经放弃之后，下游仍在继续计算（CPU、内存、连接全被占用），甚至它的响应会触发上游的重试，把故障放大。- 每一跳只做”剩余时间够用”的工作：这是传播的真正价值——$S_k$ 看到只剩 40 ms 时，可以选择降级（少查几个分片、返回部分结果、用缓存）而不是”先干 200 ms 的活再发现来不及”。这把超时从”事后丢弃”变成”事前裁剪”。
- 并发 fan-out 的延迟是 max 而非 sum：$n$ 个并发子调用的总延迟是 $\max_i L_i$（而串行是 $\sum_i L_i$）。但 $\max$ 会放大尾延迟：$P(\max > \theta) = 1 - \prod_i P(L_i \le \theta)$，在 $n=100$、单个慢概率 1% 时高达 63.4%（18.2.11 的算例）。因此异步 fan-out 必须配超时裁剪（到了 budget 就返回已有的部分结果）或对冲请求（hedged request：向第二个副本再发一份，取先到者）。
- 取消要向下传播：否则”客户端已经走了，下游还在算”。取消是尽力而为的（取消消息可能丢失），所以每个节点仍要自己有计时器——这是”分布式取消”与”本地取消”的本质区别。
正确性论证
- 安全性（不会超出截止时间返回）：设每跳在开始时检查
REMAINING(my_deadline) > 0，且在等待下游时使用同一个 deadline（而不是重新计时）。由于now()单调递增，任意节点在任意时刻的剩余时间 $\text{REMAINING}(D) = D - \text{now()} \le 0$ 时立即返回错误，因此在 $D$ 之后不会有成功响应产生。⇒ 客户端在 $D$ 之后不会收到”迟到的成功”（它可能收到迟到的响应消息，但会被丢弃）。该论证的关键假设是：等待下游时不能重置计时器——这正是”传 deadline 而不是传 timeout”的形式化收益。 - 活性（客户端必然在有限时间内得到答复）：异步调用返回 Future，
AWAIT_ALL带本地超时 $D$；即使所有下游都不响应，本地计时器也会到期 ⇒ 客户端在 $\le D$ 内返回（可能是”部分成功 + 超时”）。 - “僵尸请求不产生”的论证：取消传播是尽力而为的，因此不能证明”一定没有僵尸请求”；能证明的是“僵尸请求的有害影响被限制在单跳的本地成本内”：每个节点在进入昂贵计算前检查剩余时间，故僵尸工作的时长 $\le$ 单跳的估计成本 $c_i$，而不是整条链路的剩余时间。要更强的保证就需要租约（lease）：下游只在租约有效期内为上游保留资源。
- 尾延迟放大是”事实”而非”缺陷”：$\max$ 算子的尾部分布必然比单个元素更差（$P(\max > \theta) = 1 - \prod(1 - p_i(\theta)) \ge \max_i p_i(\theta)$）。这是数学不等式，无法通过优化实现消除，只能通过减少 fan-out 的规模（聚合/缓存/批处理）、提高单个服务的尾延迟（消除 GC 停顿、避免队头阻塞、隔离慢查询）或对冲请求来缓解。
复杂度
- 时间：并发 fan-out 为 $O(\max_i L_i)$（对比串行 $O(\sum_i L_i)$）；加上截止时间检查后上界为 $O(D)$。
- 消息复杂度：每跳 2 条消息（请求 + 响应）$+\ O(\text{fan-out})$ 条子请求；取消在最坏情况下额外增加 $O(\text{fan-out})$ 条消息（每层都向下传）。
- 空间：每个在途调用 $O(1)$ 状态（Future + deadline）；服务端需为每个在途请求保留上下文，因此过长的 deadline 会直接放大服务端的内存占用——这是”deadline 越长越危险”的原因。
- 对标量：若无 deadline 传播，最坏总延迟可达 $\sum_{i=1}^{k} T_i$；有传播则为 $\min(D, \sum c_i + \sum d_i)$。
18.4 代码示例与分布式实现
三个程序都只用 Python 标准库、都可直接 python3 file.py 运行。它们分别验证本章的三条主线：18-C1 验证 RPC 的架构与流程（IDL → 桩 → 编组 → 传输 → dispatcher），18-C2 验证调用语义（这是本讲最重要的实验：把 at-most-once / at-least-once / exactly-once 的差别”跑出来”），18-C3 验证编组的代价与安全边界。
18.4.1 代码 18-C1：从零实现一个完整 RPC 系统
这段代码把 18.2.5 的五个部件（client、client stub、runtime、dispatcher、server stub）全部手工实现一遍，并且用 IDL 在运行时动态生成桩（等价于 rpcgen 的运行时版本）。为了控制在可读长度内，这里分两块给出；把代码块 A 与代码块 B 依次拼接，即为完整可运行的 rpc_from_scratch.py（共 213 行）。
#!/usr/bin/env python3
"""从零实现一个完整 RPC 系统: IDL -> 动态桩生成 -> 编组 -> TCP -> 请求 ID -> dispatcher。"""
import itertools, socket, struct, threading, time
# ===== 1. 编组/解组: 带类型标签的紧凑二进制编码, 统一大端序 =====
def encode(obj):
if isinstance(obj, bool): # bool 必须在 int 之前判
return b'i' + struct.pack('!q', int(obj))
if isinstance(obj, int):
return b'i' + struct.pack('!q', obj)
if isinstance(obj, float):
return b'f' + struct.pack('!d', obj)
if isinstance(obj, str):
raw = obj.encode('utf-8') # 变长字段: 长度前缀 + 内容
return b's' + struct.pack('!I', len(raw)) + raw
if isinstance(obj, (list, tuple)):
parts = [b'l', struct.pack('!I', len(obj))]
return b''.join(parts + [encode(x) for x in obj])
if isinstance(obj, dict):
parts = [b'd', struct.pack('!I', len(obj))]
for k, v in obj.items(): # 键值交替, 靠数量界定边界
parts += [encode(k), encode(v)]
return b''.join(parts)
raise TypeError('unsupported type: %r' % type(obj))
def decode(buf, off=0):
tag = buf[off:off + 1]; off += 1
if tag == b'i':
(val,) = struct.unpack_from('!q', buf, off); return val, off + 8
if tag == b'f':
(val,) = struct.unpack_from('!d', buf, off); return val, off + 8
if tag == b's':
(n,) = struct.unpack_from('!I', buf, off)
return buf[off + 4:off + 4 + n].decode('utf-8'), off + 4 + n
if tag == b'l':
(n,) = struct.unpack_from('!I', buf, off); off += 4
out = []
for _ in range(n):
val, off = decode(buf, off); out.append(val)
return out, off
if tag == b'd':
(n,) = struct.unpack_from('!I', buf, off); off += 4
out = {}
for _ in range(n):
key, off = decode(buf, off); val, off = decode(buf, off); out[key] = val
return out, off
raise ValueError('bad tag %r at offset %d' % (tag, off - 1))
def pack_message(obj): # 分帧: 长度前缀 + 消息体
body = encode(obj)
return struct.pack('!I', len(body)) + body
def recv_exactly(sock, n):
chunks, got = [], 0
while got < n:
chunk = sock.recv(n - got)
if not chunk:
raise ConnectionError('peer closed')
chunks.append(chunk); got += len(chunk)
return b''.join(chunks)
def recv_message(sock):
(n,) = struct.unpack('!I', recv_exactly(sock, 4))
return decode(recv_exactly(sock, n))[0]
# ===== 2. IDL: 接口定义 (方法名 + 参数类型 + 返回类型) =====
IDL = {'add': {'args': ['int', 'int'], 'ret': 'int'},
'concat': {'args': ['str', 'str'], 'ret': 'str'},
'scale': {'args': ['list', 'float'], 'ret': 'list'},
'summarize': {'args': ['dict'], 'ret': 'dict'},
'metrics': {'args': [], 'ret': 'dict'}}
TYPE_CHECK = {'int': lambda v: isinstance(v, int) and not isinstance(v, bool),
'float': lambda v: isinstance(v, float),
'str': lambda v: isinstance(v, str),
'list': lambda v: isinstance(v, (list, tuple)),
'dict': lambda v: isinstance(v, dict)}
def make_client_stub(idl, runtime):
"""由 IDL 在运行时生成客户端桩: 每个方法名一个与本地调用同形的函数。"""
cls = type('ClientStub', (), {})
def stub_init(self, rt):
self._runtime = rt
cls.__init__ = stub_init
for name, spec in idl.items():
def method(self, *args, _name=name, _spec=spec):
if len(args) != len(_spec['args']):
raise TypeError('%s expects %d args' % (_name, len(_spec['args'])))
for val, typ in zip(args, _spec['args']):
if not TYPE_CHECK[typ](val):
raise TypeError('%s arg expects %s, got %r' % (_name, typ, val))
return self._runtime.call(_name, list(args)) # 编组->发送->等待->解组
setattr(cls, name, method)
return cls(runtime)
def make_server_dispatch(idl, impl):
"""由 IDL + 服务实现生成服务端桩表: 解组->校验->调用真函数->返回结果。"""
table = {}
for name, spec in idl.items():
def handler(args, _name=name, _spec=spec):
if len(args) != len(_spec['args']):
raise ValueError('arity mismatch for %s' % _name)
for val, typ in zip(args, _spec['args']):
if not TYPE_CHECK[typ](val):
raise ValueError('type mismatch for %s: %r' % (_name, val))
return getattr(impl, _name)(*args) # 调用真正的服务过程
table[name] = handler
return table
# ===== 3. RPC runtime: 真实 TCP 传输 + 请求 ID + dispatcher =====
class RpcServer(threading.Thread):
def __init__(self, dispatch, host='127.0.0.1', exec_latency=0.0):
super().__init__(daemon=True)
self.dispatch, self.exec_latency, self.served = dispatch, exec_latency, 0
self.ready = threading.Event()
self.sock = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
self.sock.setsockopt(socket.SOL_SOCKET, socket.SO_REUSEADDR, 1)
self.sock.bind((host, 0)) # 端口 0 = 让内核分配
self.port = self.sock.getsockname()[1]
def run(self):
self.sock.listen(4); self.ready.set()
conn, _ = self.sock.accept() # 长连接: 一个连接跑多次调用
conn.setsockopt(socket.IPPROTO_TCP, socket.TCP_NODELAY, 1)
with conn:
while True:
try:
req_id, method, args = recv_message(conn)
except ConnectionError:
return
if self.exec_latency:
time.sleep(self.exec_latency)
try:
reply = [req_id, True, self.dispatch[method](args)] # 分派到 server stub
except Exception as exc: # 服务端异常也要回给客户端
reply = [req_id, False, '%s: %s' % (type(exc).__name__, exc)]
conn.sendall(pack_message(reply)); self.served += 1
class RpcRuntime:
"""客户端 runtime: 请求 ID 分配 + 请求-响应匹配 + 超时。"""
def __init__(self, host, port, timeout=5.0):
self.sock = socket.create_connection((host, port), timeout=timeout)
self.sock.settimeout(timeout)
self.sock.setsockopt(socket.IPPROTO_TCP, socket.TCP_NODELAY, 1)
self.seq = itertools.count(1)
self.log = []
def call(self, method, args):
req_id = next(self.seq) # 每个请求一个唯一 ID
payload = pack_message([req_id, method, args])
t0 = time.perf_counter()
self.sock.sendall(payload)
got_id, ok, value = recv_message(self.sock)
rtt = time.perf_counter() - t0
if got_id != req_id: # 按请求 ID 匹配响应
raise RuntimeError('reply id %r != request id %r' % (got_id, req_id))
self.log.append((method, len(payload), rtt))
if not ok:
raise RuntimeError(value)
return value
# ===== 4. 服务实现: 程序员只写这一段 + 上面的 IDL =====
class FlightService:
def __init__(self):
self.calls = 0
def add(self, a, b):
self.calls += 1; return a + b
def concat(self, a, b):
self.calls += 1; return a + b
def scale(self, xs, k):
self.calls += 1; return [x * k for x in xs]
def summarize(self, rec):
self.calls += 1
return {'n': len(rec), 'keys': sorted(rec.keys()), 'total': sum(rec.values())}
def metrics(self):
self.calls += 1; return {'calls': self.calls, 'server': 'FlightService'}
# ===== 5. 测试 =====
if __name__ == '__main__':
samples = [42, -7, 3.5, 'hello 分布式', [1, 2, [3, 'x'], {'k': 1.5}],
{'flights': [{'id': 'ABC123', 'seats': 10}, {'id': 'XYZ789', 'seats': 0}], 'ok': True}]
print('--- encode/decode round-trip (互逆性) ---')
for s in samples:
blob = encode(s)
assert decode(blob)[0] == s
print(' %-45.45r -> %3d bytes, round-trip ok' % (s, len(blob)))
impl = FlightService()
server = RpcServer(make_server_dispatch(IDL, impl))
server.start(); server.ready.wait()
runtime = RpcRuntime('127.0.0.1', server.port)
stub = make_client_stub(IDL, runtime) # IDL 生成的客户端桩
print('\n--- RPC calls over real TCP (127.0.0.1:%d) ---' % server.port)
assert stub.add(2, 3) == 5
assert stub.concat('CS', '425') == 'CS425'
assert stub.scale([1.0, 2.0, 3.0], 2.5) == [2.5, 5.0, 7.5]
assert stub.summarize({'a': 3, 'b': 4, 'c': 5}) == {'n': 3, 'keys': ['a', 'b', 'c'], 'total': 12}
assert stub.metrics()['server'] == 'FlightService'
print(' all assertions passed; server-side execution count =', impl.calls)
print(' summarize(50 keys) total ->', stub.summarize({'n%d' % i: i for i in range(50)})['total'])
N, t0 = 200, time.perf_counter()
for i in range(N):
assert stub.add(i, i) == 2 * i
total = time.perf_counter() - t0
print('\n--- performance on localhost ---')
print(' %d unary RPCs in %.1f ms -> %.1f us/call, %.0f calls/s'
% (N, total * 1000, total / N * 1e6, N / total))
print(' %-10s %-7s %-8s' % ('method', 'bytes', 'RTT(us)'))
by_method = {}
for name, size, rtt in runtime.log:
by_method.setdefault(name, []).append((size, rtt))
for name, rows in by_method.items():
print(' %-10s %-7d %-8.1f' % (name, rows[0][0], sum(r for _, r in rows) / len(rows) * 1e6))
print(' server-side executions =', impl.calls, '| served replies =', server.served)
runtime.sock.close()
运行输出（本机 200 次一元 RPC 的实测，RTT 随机器负载在 60-95 $\mu$s 波动）
--- encode/decode round-trip (互逆性) ---
42 -> 9 bytes, round-trip ok
-7 -> 9 bytes, round-trip ok
3.5 -> 9 bytes, round-trip ok
'hello 分布式' -> 20 bytes, round-trip ok
[1, 2, [3, 'x'], {'k': 1.5}] -> 63 bytes, round-trip ok
{'flights': [{'id': 'ABC123', 'seats': 10}, { -> 122 bytes, round-trip ok
--- RPC calls over real TCP (127.0.0.1:43815) ---
all assertions passed; server-side execution count = 5
summarize(50 keys) total -> 1225
--- performance on localhost ---
200 unary RPCs in 18.8 ms -> 93.8 us/call, 10665 calls/s
method bytes RTT(us)
add 49 85.5
concat 49 111.3
scale 74 97.3
summarize 87 173.5
metrics 35 80.9
server-side executions = 206 | served replies = 206
【代码做什么？】
- 编组层（
encode/decode）：实现 18.3.2 的算法——1 字节类型标签（i/f/s/l/d）+struct.pack('!q')/('!d')的大端定长编码 + 4 字节长度前缀的变长字段；decode用偏移量逐段推进，与encode严格互逆。 - 分帧（
pack_message/recv_message）：在消息外面套 4 字节大端长度前缀。这一步是 TCP 上实现 RPC 的必要条件：TCP 是字节流，不保留消息边界（”粘包/半包”），没有长度前缀就无法区分两条消息。 - IDL（
IDL字典）：声明 5 个方法的参数类型与返回类型，等价于.proto/XDR 接口描述。 - 桩生成（
make_client_stub）：用type()动态造类、用闭包给每个方法生成函数、用setattr挂到类上。生成出来的stub.add(2,3)与本地调用写法完全一致——这就是讲义所说的”client stub 与 callee 同签名”。 - 服务端桩表（
make_server_dispatch）：为每个方法生成”校验参数 → 调用真实现”的 handler，构成pid/方法名 → stub的分派表。 - RPC runtime（
RpcServer/RpcRuntime）：服务端用bind(('127.0.0.1', 0))让内核分配端口（这模拟了 Sun RPC 的 portmapper：先拿到端口，再告诉客户端），接受一条长连接并在其上循环处理多个请求；客户端维护itertools.count(1)生成的请求 ID，并把req_id放进请求、与响应比对。 - 测试：先做 6 组
encode/decode往返断言（含中文、嵌套 list/dict），再通过真实 TCP 调用add/concat/scale/summarize/metrics并断言结果，最后打印每个方法的编组字节数与平均 RTT。
【分布式机制透视】
- 地址空间与复制：
FlightService在服务端进程里维护self.calls计数；客户端拿到的只是复制过去的返回值。客户端无法通过参数把服务端对象的指针传过来——这正是 18.2.3 区别 1。 - 请求 ID 与匹配：
RpcRuntime.call每调用一次就取一个新 ID，并在收到响应后核对got_id == req_id；若交换了顺序（例如服务端并发处理），这个检查会立刻报错。这就是”请求-响应匹配”的最小实现。 - dispatcher 的对应物：
self.dispatch[method](args)这一行就是服务端的 dispatcher——用方法名（可理解为 procedure number）选到一个 server stub。 - 失败模式的可见性：
RpcServer.run里except ConnectionError: return模拟”对端消失”；RpcRuntime设了timeout=5.0，超时会抛socket.timeout——在这段代码里，超时与”服务端没执行”无法区分，这正是 18.2.3 区别 4 的实证。18-C2会把这一点做成可控实验。 - TCP_NODELAY：代码关闭了 Nagle 算法。这不是细节：Nagle（攒小包）与 TCP 的延迟确认（delayed ACK）相互作用，会让小消息的 RTT 出现几十毫秒级的诡异抖动（经典的 “Nagle + delayed ACK” 问题）。RPC 框架默认关闭 Nagle。
- 真实对应物：IDL 字典 ↔
.proto/XDR；make_client_stub↔protoc/rpcgen生成的客户端库；RpcRuntime↔ gRPC 的Channel（含连接池、负载均衡、重试）；pending/req_id↔ gRPC 的 HTTP/2 stream ID；FlightService↔ 你真正写的业务服务。
【与理论的对应】
encode/decode↔ 算法 18.3.2 的伪代码逐行对应（含标签、varint 思路、长度前缀、大端）；往返断言就是互逆性定理的可执行版本。make_client_stub+RpcRuntime.call+RpcServer.run+make_server_dispatch↔ 算法 18.3.1 的四段（客户端桩、客户端 runtime、服务端 runtime/dispatcher、服务端桩）一一对应，且图中的 12 跳在这段代码里都能指出具体语句。- 代码只实现了算法 18.3.1 的流程正确性（响应不错配、编解码互逆），没有实现调用语义：服务端不重传、客户端不重试、没有去重表——因此它的语义是”没有故障时 exactly-once，有故障时未知“。把这一点想清楚，就理解了本章的全部动机。
18.4.2 代码 18-C2：RPC 调用语义实验（请求丢失 / 响应丢失 / 请求重复）
这是本章最重要的实验：在同一套桩与编组之上，通过注入故障与切换语义策略，把三种语义的差别量化出来。为了与讲义原表对齐，代码实现了四档：at-most-once（不重传，不去重）、at-most-once+dedup（不重传 + 服务端去重，即讲义口径的 “At most once”）、at-least-once（重传，不去重）、exactly-once（重传 + 去重）。
#!/usr/bin/env python3
"""RPC 调用语义实验: 注入请求丢失/响应丢失/请求重复, 对比 at-most-once / at-least-once / exactly-once。"""
import queue, random, threading, time
CLIENT_ID = 'C1'
TIMEOUT = 0.02 # 模拟客户端的重传超时 (秒)
MAX_ATTEMPTS = 3 # at-least-once / exactly-once 的最大重传次数
class ScriptedPlan:
"""按剧本决定每条消息的命运: ok / drop / dup。"""
def __init__(self, req=(), resp=()):
self.req, self.resp, self.ri, self.si = list(req), list(resp), 0, 0
def on_request(self):
act = self.req[self.ri] if self.ri < len(self.req) else 'ok'
self.ri += 1
return act
def on_response(self):
act = self.resp[self.si] if self.si < len(self.resp) else 'ok'
self.si += 1
return act
class RandomPlan:
def __init__(self, rng, p_req_drop, p_resp_drop, p_dup=0.0):
self.rng, self.pr, self.ps, self.pd = rng, p_req_drop, p_resp_drop, p_dup
def on_request(self):
if self.rng.random() < self.pr:
return 'drop'
return 'dup' if self.rng.random() < self.pd else 'ok'
def on_response(self):
return 'drop' if self.rng.random() < self.ps else 'ok'
class Server(threading.Thread):
"""服务端: 可选开启 drop box (去重缓存)。"""
def __init__(self, inq, outq, dedup):
super().__init__(daemon=True)
self.inq, self.outq, self.dedup = inq, outq, dedup
self.exec_count = 0 # 服务过程被真正执行的次数
self.applied = [] # 服务端状态里留下的记录 (重复执行会多出记录)
self.dedup_hits = 0
self.cache = {} # (client_id, seq) -> 上次的响应
self.stop = object()
def run(self):
while True:
item = self.inq.get()
if item is self.stop:
return
cid, seq, op, arg = item
key = (cid, seq)
if self.dedup and key in self.cache: # 重复请求: 重发上次响应, 不重新执行
self.dedup_hits += 1
self.outq.put(self.cache[key])
continue
self.exec_count += 1
self.applied.append('%s#%d' % (op, arg)) # 副作用: 在状态里留下一条记录
reply = (seq, '%s(%d) -> ok, exec#%d' % (op, arg, self.exec_count))
if self.dedup:
self.cache[key] = reply
self.outq.put(reply)
def rpc_call(plan, semantics, seq, op, arg, inq, outq):
"""一次 RPC 调用 (含语义决定的客户端行为)。返回 (结果 or None, 尝试次数)。"""
max_attempts = MAX_ATTEMPTS if semantics in ('at-least-once', 'exactly-once') else 1
attempts = 0
while attempts < max_attempts:
attempts += 1
action = plan.on_request()
if action != 'drop': # drop = 请求消息在网络中丢失
inq.put((CLIENT_ID, seq, op, arg))
if action == 'dup': # dup = 网络重复投递同一请求
inq.put((CLIENT_ID, seq, op, arg))
try:
reply = outq.get(timeout=TIMEOUT)
except queue.Empty:
continue # 超时 -> 按语义决定是否重传
if plan.on_response() == 'drop': # 响应在回程丢失
continue
if reply[0] == seq: # 按请求 ID 匹配
return reply[1], attempts
return None, attempts
def run_scenario(name, semantics, plan, seq=1):
inq, outq = queue.Queue(), queue.Queue()
dedup = semantics in ('at-most-once+dedup', 'exactly-once') # 讲义口径: 过滤重复请求
srv = Server(inq, outq, dedup)
srv.start()
result, attempts = rpc_call(plan, semantics, seq, 'book', 7, inq, outq)
time.sleep(0.05)
srv.inq.put(srv.stop); srv.join()
return {'scenario': name, 'semantics': semantics, 'exec': srv.exec_count,
'state_rows': len(srv.applied), 'dedup_hits': srv.dedup_hits,
'attempts': attempts, 'observed': ('得到结果' if result else '超时/无结果')}
if __name__ == '__main__':
random.seed(425)
scenarios = [
('请求丢失', lambda: ScriptedPlan(req=['drop'])),
('响应丢失', lambda: ScriptedPlan(resp=['drop'])),
('请求重复投递', lambda: ScriptedPlan(req=['dup'])),
]
print('=== 实验 A: 故障剧本下的四种语义变体 (客户端 1 次逻辑调用) ===')
print('%-12s %-20s %-8s %-8s %-8s %-6s %-10s' %
('场景', '语义', '执行次数', '状态记录', '去重命中', '重传数', '客户端观察'))
rows = []
SEMANTICS = ('at-most-once', 'at-most-once+dedup', 'at-least-once', 'exactly-once')
for name, make_plan in scenarios:
for sem in SEMANTICS:
r = run_scenario(name, sem, make_plan()) # 每个语义用全新的故障剧本
rows.append(r)
print('%-12s %-20s %-10d %-10d %-10d %-8d %-10s' %
(r['scenario'], r['semantics'], r['exec'], r['state_rows'],
r['dedup_hits'], r['attempts'], r['observed']))
print()
# 断言: 响应丢失场景下三种语义的差别必须被跑出来
resp_loss = {r['semantics']: r for r in rows if r['scenario'] == '响应丢失'}
assert resp_loss['at-most-once']['exec'] == 1 and resp_loss['at-most-once']['observed'] == '超时/无结果'
assert resp_loss['at-least-once']['exec'] == 2, '至少一次必须重复执行'
assert resp_loss['exactly-once']['exec'] == 1 and resp_loss['exactly-once']['observed'] == '得到结果'
assert resp_loss['exactly-once']['dedup_hits'] >= 1
print(' [断言通过] 响应丢失: at-most-once 执行1次但客户端超时; '
'at-least-once 执行2次(重复!); exactly-once 执行1次且客户端拿到结果')
print('\n=== 实验 B: 随机丢包+重复 (p_req=0.25, p_resp=0.25, p_dup=0.10, 15 次调用, seed=425) ===')
print('%-20s %-10s %-12s %-12s %-10s' %
('语义', '成功次数', '服务端执行', '状态记录数', '去重命中'))
for sem in SEMANTICS:
rng = random.Random(425)
plan = RandomPlan(rng, 0.25, 0.25, 0.10)
inq, outq = queue.Queue(), queue.Queue()
srv = Server(inq, outq, sem in ('at-most-once+dedup', 'exactly-once'))
srv.start()
ok = 0
for seq in range(1, 16):
res, _ = rpc_call(plan, sem, seq, 'book', seq, inq, outq)
ok += 1 if res else 0
time.sleep(0.05)
srv.inq.put(srv.stop); srv.join()
distinct = len(set(srv.applied))
print('%-20s %-10d %-12d %-12d %-10d' %
(sem, ok, srv.exec_count, len(srv.applied), srv.dedup_hits))
if sem == 'exactly-once':
assert len(srv.applied) == distinct, 'exactly-once 不允许重复执行'
print(' -> exactly-once: 执行次数 == 去重后的请求数 (%d == %d), 无重复副作用' %
(len(srv.applied), distinct))
if sem == 'at-least-once':
print(' -> at-least-once: 执行次数(%d) > 去重后的请求数(%d) => 出现重复副作用' %
(len(srv.applied), distinct))
print('\n结论: 语义差别只在"故障"下才显现; 没有故障时所有语义的表现完全一样。')
运行输出（固定 random.seed(425) + random.Random(425)，可复现）
=== 实验 A: 故障剧本下的四种语义变体 (客户端 1 次逻辑调用) ===
场景 语义 执行次数 状态记录 去重命中 重传数 客户端观察
请求丢失 at-most-once 0 0 0 1 超时/无结果
请求丢失 at-most-once+dedup 0 0 0 1 超时/无结果
请求丢失 at-least-once 1 1 0 2 得到结果
请求丢失 exactly-once 1 1 0 2 得到结果
响应丢失 at-most-once 1 1 0 1 超时/无结果
响应丢失 at-most-once+dedup 1 1 0 1 超时/无结果
响应丢失 at-least-once 2 2 0 2 得到结果
响应丢失 exactly-once 1 1 1 2 得到结果
请求重复投递 at-most-once 2 2 0 1 得到结果
请求重复投递 at-most-once+dedup 1 1 1 1 得到结果
请求重复投递 at-least-once 2 2 0 1 得到结果
请求重复投递 exactly-once 1 1 1 1 得到结果
[断言通过] 响应丢失: at-most-once 执行1次但客户端超时; at-least-once 执行2次(重复!); exactly-once 执行1次且客户端拿到结果
=== 实验 B: 随机丢包+重复 (p_req=0.25, p_resp=0.25, p_dup=0.10, 15 次调用, seed=425) ===
语义 成功次数 服务端执行 状态记录数 去重命中
at-most-once 2 14 14 0
at-most-once+dedup 2 12 12 2
at-least-once 13 28 28 0
-> at-least-once: 执行次数(28) > 去重后的请求数(15) => 出现重复副作用
exactly-once 13 15 15 13
-> exactly-once: 执行次数 == 去重后的请求数 (15 == 15), 无重复副作用
结论: 语义差别只在"故障"下才显现; 没有故障时所有语义的表现完全一样。
【代码做什么？】
- 模拟不可靠网络：用两个
queue.Queue（inq客户端→服务端、outq服务端→客户端）表示双向通道；ScriptedPlan按剧本决定每条消息的命运（ok/drop/dup），RandomPlan用固定种子的随机数按概率决定。 - 服务端（
Server）：维护exec_count（被调函数真正执行的次数——这是判断语义的唯一客观依据）、applied（副作用记录，重复执行会留下多余记录）、dedup_hits、cache。dedup=True时执行前先查(cid, seq)，命中就重发缓存响应并continue，不重新执行。 - 客户端（
rpc_call）：max_attempts由语义决定（不重传档 = 1，重传档 = 3）；每次尝试先经过plan.on_request()（可能丢弃或重复投递），再outq.get(timeout=0.02)模拟等响应；响应到达时还要经过plan.on_response()（可能丢弃）；只有reply[0] == seq才认为匹配成功。 - 实验 A（故障剧本）：三种剧本 $ imes$ 四种语义 = 12 组，每组用全新的服务端、队列与故障剧本（否则剧本计数器会串味——这是实现中必须注意的坑），打印执行次数/状态记录数/去重命中/重传次数/客户端观察。
- 实验 B（随机丢包）：$p_{\text{req}}=0.25$、$p_{\text{resp}}=0.25$、$p_{\text{dup}}=0.10$，每种语义跑 15 次调用，统计成功次数、服务端执行次数、状态记录数、去重命中。
- 断言（把结论固化成测试）：
响应丢失场景下必须满足at-most-once 执行 1 次且客户端超时、at-least-once 执行 2 次、exactly-once 执行 1 次且客户端拿到结果；随机实验中exactly-once必须满足”执行次数 == 去重后的请求数“（即零重复副作用）。
【分布式机制透视】
- 故障注入点非常具体：”请求丢失” = 消息在去程消失；”响应丢失” = 服务端已经执行、副作用已经发生，但客户端不知道；”请求重复投递” = 网络把一个请求送了两份。这三种故障在真实系统里都极其常见（丢包、超时重发、负载均衡器重试、TCP 重传）。
exec_count与applied是两个不同层次的状态：exec_count是”执行了多少次”，applied是”服务端状态被改了几次”。在 at-least-once 下两者一起变大，说明重复执行已经污染了服务端状态——如果applied是”扣款记录”，这就是真实事故。- 去重命中（
dedup_hits）是 exactly-once 的”代价指标”：随机实验里 exactly-once 有 13 次去重命中，意味着 13 次重传请求全都被缓存挡住了——这就是用服务端内存换正确性。 - 超时的语义：代码里的
TIMEOUT = 0.02秒是”客户端本地计时器”，与远端事实无关。at-most-once在响应丢失时返回None，客户端只知道”我没拿到结果”，绝不会知道服务端已经执行了 1 次——这是本实验最想传达的一件事。 - 真实对应物：
ScriptedPlan/RandomPlan↔ 网络丢包与中间设备的重复投递；cache↔ Sun RPC 的 duplicate request cache / gRPC 的幂等键去重表；exec_count↔ 业务数据库里的副作用；MAX_ATTEMPTS↔ gRPC 的retryPolicy（含maxAttempts、退避与重试预算）。
【与理论的对应】
- 算法 18.3.4 的两种客户端实现：
max_attempts = 1与for attempt in 1..R的两条路径，在代码中体现为同一个while循环的两个上限；服务端的if self.dedup and key in self.cache就是算法 18.3.3 的HANDLE情形 1。 - 正确性论证的实证：讲义表的每一列都能在实验 A 的 12 行里找到对应；特别是”请求重复投递时 at-most-once 也执行了 2 次“这一行，证明了”不重传 ≠ 服务端至多执行一次“，即讲义原表中 “Filter duplicate requests” 这一列为什么必需。
- at-least-once 要求幂等：实验里
applied出现两条相同记录（非幂等副作用），这就是讲义 “Idempotent Operations” 一节的实证——如果book(7)是x := 7（幂等），两条记录也不会改变最终状态；但如果它是x := x + 7（非幂等），状态就错了。 - exactly-once 的边界：本实验的服务端从不崩溃（
Server线程不会被杀死），因此去重表始终有效；只要把服务端改成”每处理一个请求就重启并清空cache“，实验 A 中响应丢失那一行就会立刻退化为at-least-once的行为（执行 2 次）。这就是算法 18.3.3 中”崩溃且去重表丢失 ⇒ 不再 exactly-once”的可执行证明。
18.4.3 代码 18-C3：序列化格式对比与反序列化的安全边界
#!/usr/bin/env python3
"""序列化格式对比: 自写紧凑二进制(变长整数 varint) vs JSON vs pickle, 并演示 pickle 反序列化的危险性。"""
import json, os, pickle, struct, tempfile, time
# ===== 1. 自写紧凑二进制编组: 类型标签 + varint(变长整数) + 大端序 =====
T_INT, T_FLOAT, T_STR, T_LIST, T_DICT = 1, 2, 3, 4, 5
def put_varint(u):
"""无符号变长整数: 每字节 7 位数据 + 1 位继续标志。"""
out = bytearray()
while True:
byte = u & 0x7F
u >>= 7
out.append(byte | (0x80 if u else 0))
if not u:
return bytes(out)
def get_varint(buf, off):
shift = result = 0
while True:
byte = buf[off]; off += 1
result |= (byte & 0x7F) << shift
if not byte & 0x80:
return result, off
shift += 7
def encode(obj):
if isinstance(obj, bool):
obj = int(obj) # bool 先退化为 int (标签粒度不够细)
if isinstance(obj, int):
zz = (obj << 1) ^ (obj >> 63) # zigzag: 小数也只用 1 字节
return bytes([T_INT]) + put_varint(zz)
if isinstance(obj, float):
return bytes([T_FLOAT]) + struct.pack('!d', obj) # 8 字节 IEEE 754 大端
if isinstance(obj, str):
raw = obj.encode('utf-8')
return bytes([T_STR]) + put_varint(len(raw)) + raw
if isinstance(obj, (list, tuple)):
return bytes([T_LIST]) + put_varint(len(obj)) + b''.join(encode(x) for x in obj)
if isinstance(obj, dict):
out = bytearray([T_DICT]); out += put_varint(len(obj))
for k, v in obj.items():
key = k.encode('utf-8') if isinstance(k, str) else encode(k)
out += put_varint(len(key)) + key # map 的键省略类型标签(约定为字符串)
out += encode(v)
return bytes(out)
raise TypeError('unsupported: %r' % type(obj))
def decode(buf, off=0):
tag = buf[off]; off += 1
if tag == T_INT:
u, off = get_varint(buf, off)
return (u >> 1) ^ -(u & 1), off # zigzag 逆变换
if tag == T_FLOAT:
(v,) = struct.unpack_from('!d', buf, off); return v, off + 8
if tag == T_STR:
n, off = get_varint(buf, off)
return buf[off:off + n].decode('utf-8'), off + n
if tag == T_LIST:
n, off = get_varint(buf, off)
out = []
for _ in range(n):
v, off = decode(buf, off); out.append(v)
return out, off
if tag == T_DICT:
n, off = get_varint(buf, off)
out = {}
for _ in range(n):
ln, off = get_varint(buf, off)
key = buf[off:off + ln].decode('utf-8'); off += ln
out[key], off = decode(buf, off)
return out, off
raise ValueError('bad tag %r' % tag)
# ===== 2. 待编码的典型 RPC 参数 =====
PAYLOAD = {'op': 'bookFlight', 'flight': 'ABC123', 'date': '2026-11-02', 'seats': 2,
'passengers': [{'name': 'alice', 'age': 31, 'vip': True},
{'name': 'bob', 'age': 25, 'vip': False}],
'meta': {'retries': 0, 'ratio': 0.75}}
FORMATS = [
('custom-binary(varint+标签)', lambda o: encode(o), lambda b: decode(b)[0]),
('json(文本/自描述)', lambda o: json.dumps(o, separators=(',', ':')).encode(),
lambda b: json.loads(b.decode())),
('pickle(平台相关/不安全)', lambda o: pickle.dumps(o), lambda b: pickle.loads(b)),
]
if __name__ == '__main__':
print('=== 实验 A: 同一数据结构的编码体积与耗时 (每项重复 5000 次) ===')
print('%-28s %-8s %-11s %-11s %-7s' % ('格式', '字节数', '编码us/次', '解码us/次', '体积比'))
base = None
for name, enc, dec in FORMATS:
blob = enc(PAYLOAD)
assert dec(blob) == PAYLOAD, name # 往返互逆性断言
N = 5000
t0 = time.perf_counter()
for _ in range(N):
blob = enc(PAYLOAD)
t_enc = (time.perf_counter() - t0) / N * 1e6
t0 = time.perf_counter()
for _ in range(N):
dec(blob)
t_dec = (time.perf_counter() - t0) / N * 1e6
base = base or len(blob)
print('%-28s %-8d %-11.2f %-11.2f %-7s' % (name, len(blob), t_enc, t_dec,
'%.2fx' % (len(blob) / base)))
raw = json.dumps(PAYLOAD)
print(' JSON 文本片段: %s' % raw[:66])
print(' -> 二进制靠 varint 让小数只占 1 字节, 且无重复字段名; 但每个 8 字节 double 无法压缩。')
print('\n=== 实验 B: 反序列化的安全边界 ===')
parsed = json.loads('{"__reduce__": "print(1)", "args": ["x"]}')
print(' json.loads(恶意字符串) -> %r: 纯数据, 不执行任何代码' % parsed)
class HarmlessExploit:
"""教学用无害 payload: 反序列化时执行 print (真实攻击可执行任意命令)。"""
def __reduce__(self):
return (print, (' [!] pickle.loads() 真的执行了任意代码 —— 反序列化 RCE',))
evil = pickle.dumps(HarmlessExploit())
print(' 恶意 pickle (%d 字节) 前缀: %r' % (len(evil), evil[:30]))
print(' 执行 pickle.loads(evil), 观察它的副作用:')
pickle.loads(evil) # 这一行就会执行代码
marker = os.path.join(tempfile.gettempdir(), 'cs425_pickle_marker.txt')
class FileMarker:
def __reduce__(self):
return (open, (marker, 'w')) # 甚至能打开任意文件
handle = pickle.loads(pickle.dumps(FileMarker()))
handle.write('pwned by pickle'); handle.close()
print(' pickle 还能打开任意文件:', os.path.exists(marker),
'内容 =', open(marker).read())
os.remove(marker)
print(' => 结论: 绝不要对不可信来源的字节流调用 pickle.loads / ObjectInputStream。')
运行输出
=== 实验 A: 同一数据结构的编码体积与耗时 (每项重复 5000 次) ===
格式 字节数 编码us/次 解码us/次 体积比
custom-binary(varint+标签) 152 27.40 16.66 1.00x
json(文本/自描述) 189 5.54 3.53 1.24x
pickle(平台相关/不安全) 192 1.29 1.56 1.26x
JSON 文本片段: {"op": "bookFlight", "flight": "ABC123", "date": "2026-11-02", "se
-> 二进制靠 varint 让小数只占 1 字节, 且无重复字段名; 但每个 8 字节 double 无法压缩。
=== 实验 B: 反序列化的安全边界 ===
json.loads(恶意字符串) -> {'__reduce__': 'print(1)', 'args': ['x']}: 纯数据, 不执行任何代码
恶意 pickle (112 字节) 前缀: b'\x80\x04\x95e\x00\x00\x00\x00\x00\x00\x00\x8c\x08builtins\x94\x8c\x05print\x94'
执行 pickle.loads(evil), 观察它的副作用:
[!] pickle.loads() 真的执行了任意代码 —— 反序列化 RCE
pickle 还能打开任意文件: True 内容 = pwned by pickle
=> 结论: 绝不要对不可信来源的字节流调用 pickle.loads / ObjectInputStream。
【代码做什么？】
- 紧凑二进制编组器：在
18-C1的基础上把整数改成 zigzag + varint（小数只占 1 字节），长度字段也用 varint，map 的键省略类型标签，浮点仍用 8 字节大端 IEEE 754。 - 三格式对比：对同一个典型 RPC 参数（含两个嵌套对象、2 个 double、8 个整数、6 个字符串），分别测量 自定义二进制 / JSON / pickle 的字节数与 5000 次编码/解码的平均耗时，并各自做往返正确性断言（
dec(enc(x)) == x）。 - 安全演示（无害 payload）：构造一个
__reduce__返回(print, (...))的类，pickle.dumps后执行pickle.loads，观察它真的执行了代码；再用(open, (tmpfile, 'w'))证明它还能打开任意文件（写入标记文件后删除，不做任何危险操作）。 - 对照组：
json.loads('{"__reduce__": ...}')只得到一个普通 dict，不会执行任何代码。
【分布式机制透视】
- 体积对比的结论是”取决于负载形态”：自定义二进制 152 字节（基线）、JSON 189 字节（1.24 倍）、pickle 192 字节（1.26 倍）。二进制的优势来自两处：varint 让小数只占 1 字节、map 不需要重复写字段名。但注意 JSON 片段里
"2026-11-02"这类短字符串与 8 字节 double 是无法压缩的——如果负载以浮点数组为主，二进制与 JSON 的体积差距会大幅缩小（Protobuf 为此提供了float（4 字节）与fixed64的不同选择）。 - 时间对比的结论更值得注意：紧凑二进制编码 28.5 $\mu$s/次、解码 16.8 $\mu$s/次，而 JSON 只有 5.5 / 3.5 $\mu$s，pickle 只有 1.3 / 1.6 $\mu$s。手写的 Python 编组器比 C 实现的
json/pickle慢 5-20 倍——这告诉我们：序列化性能不只取决于”格式好不好”，更取决于”实现是不是在 C/Rust 层、有没有反复分配内存”。真实系统的编组器（protobuf、Thrift、Cap’n Proto）都是 C++/Rust 实现，并且大量使用零拷贝、预分配缓冲、批量写入来压制这部分开销。 - 反序列化的攻击面是真实存在的：
pickle.loads的字节流本质上是一段虚拟机指令，__reduce__/__reduce_ex__直接指定”调用哪个可调用对象、参数是什么”。因此它不是数据格式，而是 Python 对象的转储格式。这在分布式系统里的含义非常直接：RPC 的编组层是网络入口，一旦使用 pickle / Java 原生序列化，任何能发送字节流的人都可以在你的进程里执行代码。真实系统里的对应防护是：只接受”只有数据、没有行为”的格式（protobuf/JSON），或对原始字节流做签名 + 类白名单校验。 - 其他真实对应物：
put_varint/get_varint↔ protobuf 的 varint；TAG_*↔ protobuf 的 wire type；”map 键省略标签” ↔ protobuf 的 field number 代替字段名；float用 8 字节 ↔ protobufdouble（8B）/float（4B）的选择；JSON 的可读性 ↔ 调试与外部 API 场景。
【与理论的对应】
- 三个格式的往返断言共同验证了 算法 18.3.2 的互逆性定理；而”二进制更小但更慢“这一实测结果，正是 18.5 要分析的编组开销占比问题的直接证据：在本机 localhost 上，编码 + 解码约 45 $\mu$s，与一个 TCP 往返（约 60-90 $\mu$s）同量级——也就是说，在低延迟链路上，编组开销可能和网络开销一样大。
18-C3的安全演示对应 18.2.14 的”序列化的安全问题”：不要反序列化不受信任的字节流；也对应 18.2.7 的”(3) 类型安全”——解码器必须做边界与类型检查，而”能执行代码的格式”连这一层都无法补救。
18.5 性能与可扩展性分析
18.5.1 RPC 的延迟构成
一次 RPC 的端到端延迟可以分解为六项：
\[L_{ ext{RPC}} = L_{ ext{stub}} + L_{ ext{marshal}} + L_{ ext{net}} + L_{ ext{queue}} + L_{ ext{exec}} + L_{ ext{unmarshal}} + L_{ ext{stub}}^{\prime}\]| 组成项 | 典型量级 | 影响因素 | 本章实测 |
|---|---|---|---|
| 桩与框架开销 $L_{\text{stub}}$ | 1-20 $\mu$s | 语言（Java/C++ 反射 vs 生成代码）、截断器链长度、日志/追踪埋点 | 含在 RTT 内 |
| 编组 $L_{\text{marshal}}$ | 0.1-50 $\mu$s（依消息大小） | 编码格式、实现语言、是否零拷贝、分配次数 | 28.5 $\mu$s（手写 Python 编组 152 字节负载） |
| 网络 $L_{\text{net}}$ | 同机 20-100 $\mu$s；同机房 0.2-1 ms；跨大陆 60-150 ms；跨洲际可达 200-300 ms | 物理距离（光速下界）、交换机跳数、拥塞、协议（HTTP/2 多路复用 vs 每请求连接） | 60-95 $\mu$s（localhost TCP，TCP_NODELAY） |
| 排队 $L_{\text{queue}}$ | 0 到数百 ms（取决于负载，是最容易失控的一项） | 服务端并发度、线程池大小、慢请求占用的连接、GC 停顿 | 代码中 exec_latency 模拟 |
| 服务执行 $L_{\text{exec}}$ | 业务决定 | 数据库查询、下游调用 | 5 次业务调用 |
| 解组 $L_{\text{unmarshal}}$ | 与编组同量级 | 同上 | 16.8 $\mu$s |
关键结论 1：在低延迟链路（同机/同机房）上，编组 + 解组的 CPU 开销可能与网络 RTT 相当甚至更大。 本章实测：编组 28.5 + 解组 16.8 = 45.3 $\mu$s，而 localhost 的 TCP RTT 是 60-95 $\mu$s。这意味着：(a) 优化编组不是”微优化”（用零拷贝格式可以省掉一整块延迟）；(b) 用大消息比用多次小消息更划算（编组的固定开销被摊薄，而网络开销不会随消息变大而成比例增长）。这也解释了为什么现代框架偏好 批处理（batching） 与 流式（streaming）。
关键结论 2：在高延迟链路（跨大陆）上，CPU 开销完全被网络淹没（45 $\mu$s vs 100 ms，相差 2000 倍），此时唯一有效的优化是”减少往返次数”——这正是”接口要粗粒度”的量化依据。同一个设计决策在不同链路上有完全不同的收益，这是分布式系统里”所有答案都依赖于工作负载”的典型例子。
18.5.2 RPC 与本地调用的性能差距
| 操作 | 典型延迟 | 相对本地调用 |
|---|---|---|
| 本地函数调用（已缓存指令/数据） | 1-10 ns | $1 imes$ |
| 本地调用（缓存未命中、含内存分配） | 50-200 ns | $10$-$100 imes$ |
| 同进程内的 stub 编组 + 解组（无网络） | 1-45 $\mu$s | $10^3$-$10^4 imes$ |
| 同机 RPC（localhost TCP） | 60-100 $\mu$s | $\mathbf{10^4}$-$10^5 imes$ |
| 同机房 RPC（同数据中心） | 0.2-1 ms | $10^5$-$10^6 imes$ |
| 跨区域 RPC（如 us-east → us-west） | 60-100 ms | $10^7$-$10^8 imes$ |
| 跨洲际 RPC（含 TLS 握手的新连接） | 200-300 ms | $10^8 imes$ |
量级结论：RPC 相对本地调用慢 $10^3 \sim 10^6$ 倍（同机约 $10^4$，跨机房约 $10^5$，跨大陆约 $10^7$）。这个差距无法通过工程优化消除（光速是硬下界：纽约到伦敦约 5600 km，光纤中往返的理论下界约 56 ms）。它的设计含义非常清楚：任何”把本地循环改成 RPC 循环”的重构都必须先算清调用次数——把 $10^5$ 次本地调用改成同机 RPC，延迟从 1 ms 变成 10 s。
18.5.3 吞吐、可扩展性与尾延迟放大
| 维度 | 数值 / 分析 |
|---|---|
| 单连接吞吐 | 受限于”每请求一次往返”的串行化：同机 15,000 calls/s（本章实测，含编组）；若不等待（异步/流水线），吞吐可提升数十倍直至打满 CPU 或带宽 |
| 连接数瓶颈 | HTTP/1.1 每请求一连接：1000 个并发客户端 = 1000 条 TCP + 1000 个线程；HTTP/2 多路复用把这一项从瓶颈中移除（一条连接承载成千上万并发流） |
| 序列化 CPU 占比 | 小消息（< 200 字节）时，编组+解组的 CPU 可能与网络时间相当（本章实测 45 $\mu$s vs 60-95 $\mu$s）⇒ 吞吐上限可能由 CPU 而非带宽决定 |
| 带宽 | 消息越小，有效载荷/头部比越低（一个 35 字节的 metrics() 调用在 TCP/IP 下实际线路字节会翻倍以上）⇒ 小消息场景应批量合并 |
| 可扩展性瓶颈 | ① 无状态服务可线性扩展；② 有状态的服务端去重表（exactly-once）会随客户端数线性增长（$O(mW)$）；③ 服务发现/注册中心成为新瓶颈（需要自己的扩展方案，如多级缓存 + 一致性哈希） |
| 尾延迟放大（fan-out） | $n=100$ 个服务、单个慢（100 ms）概率 $p=0.01$：$P(\ge 1\text{ 慢}) = 1-0.99^{100} \approx \mathbf{63.4\%}$；$E[\text{总延迟}] = 0.366\times 1 + 0.634\times 100 = \mathbf{63.8\,ms}$；中位延迟 = 100 ms（因为 $0.634 > 0.5$）。对照：串行调用 100 个服务的期望总延迟是 $100 \times 1.99 = 199$ ms |
计算细节（课堂必会的一种题）：设每个子调用独立地以概率 $p$ 变慢到 $T_{\text{slow}}$、以 $1-p$ 保持 $T_{\text{fast}}$，则 $P(\text{至少一个慢}) = 1-(1-p)^n$，$E[\max] = (1-p)^n T_{\text{fast}} + \bigl(1-(1-p)^n\bigr) T_{\text{slow}}$（18.2.11 与 18.8 题 1 有完整算例）。注意中位数：当 $1-(1-p)^n > 0.5$ 时，过半请求都会踩到慢节点，此时中位延迟就等于 $T_{\text{slow}}$——这就是”尾延迟放大“：你不需要自己变慢，只需要依赖很多个”偶尔慢”的服务，你就会经常慢。
现代优化手段（及其作用点）：
| 优化 | 作用在哪一项开销 | 说明与代价 |
|---|---|---|
| 零拷贝序列化（Cap’n Proto / FlatBuffers） | 编组 + 解组（可归零） | 字节流布局即内存布局，无需解码；代价是字节流偏大、写入较慢、变长字段修改受限 |
| 紧凑编码 + varint（protobuf / TCompact） | 编组时间 + 带宽 | 减小消息体积、降低拷贝量；代价是编码逻辑变复杂（CPU 换带宽） |
| 异步 / 流水线（pipelining） | 等待时间（$L_{\text{net}}$ 的重叠） | 多个在途请求相互重叠，吞吐提升；代价是并发控制、乱序处理、内存占用上升 |
| 连接复用与多路复用（HTTP/2） | 握手开销 + 连接数 | 消除每请求的 TCP/TLS 握手；代价是队头阻塞（HTTP/2 的 TCP 层 HOL）需要用更细的流控或 HTTP/3(QUIC) 缓解 |
| 批处理（batching） | 编组固定开销 + 网络次数 | 把 $k$ 个小请求合成 1 个大请求：延迟可能略增（攒批），吞吐显著提升；代价是延迟敏感场景不适用 |
| 截止时间传播 + 取消 | 排队与僵尸请求 | 防止资源被”已放弃的请求”占用；代价是需要全链路配合 |
| 对冲请求（hedged request） | 尾延迟 | 到 $p95$ 还没返回就向副本再发一份，取先到者；代价是流量放大（通常限制在 1-5%） |
| 客户端负载均衡 + 最少连接/最少延迟选择 | 排队时间 | 避开已经过载的后端；代价是需要实时健康与负载信息 |
18.6 关键要点
- RPC 的语法很简单，语义才是一切：
z = f(x,y)这一行的写法可以在本地与远程之间随意切换，但“这一次调用到底执行了几次”这个语义问题无法靠写法解决——at-most-once / at-least-once / exactly-once 必须被显式选择并付出对应的实现代价。 - 超时是本地事件，不是远端事实：$\text{timeout} \not\Rightarrow \neg\text{executed}$ 且 $\text{timeout} \not\Rightarrow \text{executed}$。“不知道”是 RPC 的第三种结果，也是所有 RPC 工程师必须先在脑子里建立起来的直觉——本地调用没有这个状态，这就是 RPC 与 LPC 最本质的差别。
- “服务端至多执行一次”只能靠服务端去重，不能靠客户端不重传：请求重复有三个来源（客户端重传、网络重复投递、中间设备重试），所以 at-most-once 的实现必须包含请求过滤（
(client_id, seq)去重表 + 响应缓存），而不是”只发一次”。 - 恰好一次 = at-least-once 的传输 + 幂等的（或去重的）处理：传输层无法做到恰好一次；工程上要么把操作做成幂等（
x := 1而不是x := x + 1），要么把去重状态与业务状态放进同一个事务/日志（幂等键），要么用复制状态机持久化去重表（Lecture 17）。内存里的 drop box 只提供”服务端不崩溃时的 at-most-once”。 - 编组不是免费的午餐：它把异构性（字节序、字长、浮点、字符编码、对齐）从”每个应用各自处理”变成”中间件统一处理”；代价是 CPU 与体积。在低延迟链路上，编组/解组的开销可能与网络 RTT 同量级（本章实测 45 $\mu$s vs 60-95 $\mu$s），所以零拷贝、varint、批处理都不是微优化。
- 透明性是危险的：RPC 把”延迟差三个数量级、可能部分失败、参数语义已经改变”这些事实藏起来，而藏起来的复杂性会在故障时以”慢”和”重复副作用”的形式爆炸。现代框架（gRPC 的 status/deadline、字段号兼容机制、幂等键）所做的，本质上都是把分布式事实重新暴露给程序员。
18.7 常见陷阱与注意事项
- 陷阱：把 at-most-once 理解成”客户端不重传”。 为什么错：重复请求可能来自网络重复投递或中间设备重试，客户端不重传并不能阻止服务端执行两次（
18-C2实测：请求重复投递时”不重传”档执行了 2 次）。正确做法：把”至多一次”实现为服务端的请求过滤（去重表 + 响应缓存）；客户端是否重传只影响”成功率”，不影响”至多一次”。 - 陷阱：把 at-least-once 用在非幂等操作上。 为什么错：一次响应丢失就会让
x = x + 1被执行两次（实测：15 次调用产生 28 次执行、13 次重复副作用）。正确做法：要么让操作幂等（x := 常量、带版本号的覆盖写、put覆盖），要么改用”幂等键 + 去重表”，绝不能靠”应该不会丢”来赌。 - 陷阱：认为重试能提高可用性，于是无脑加重试。 为什么错：重试是乘性放大的（每层 $(1+r)$ 倍），在故障时会形成重试风暴，把”某个后端慢”升级为”全集群挂”。正确做法：指数退避 + 抖动（抖动必须有，否则惊群）、重试预算（全局比例上限）、断路器（快速失败）、负载丢弃（过载时主动拒绝），并且只在幂等操作上重试、且尊重 deadline 的剩余时间。
- 陷阱：不传播截止时间，每一层各拍一个超时。 为什么错：各层超时串行累加，客户端放弃后下游仍在计算（僵尸请求），浪费 CPU/内存/连接，还可能触发上游重试形成级联。正确做法：把剩余时间（
grpc-timeout）沿调用链传下去，每跳开始前判断”剩余时间是否够”，不够就降级或快速失败，并向下传播取消。 - 陷阱：传”绝对时刻”作为 deadline，或依赖各机器物理时钟一致。 为什么错：各节点时钟只是近似同步（Lecture 26），跨机比较绝对时刻会出现”时间倒流”式 bug。正确做法：传相对剩余时间，或同时携带时钟偏差处理；每跳自己也要有本地计时器兜底。
- 陷阱：用指针/引用作为 RPC 参数，或期待”引用语义”。 为什么错：地址在远端无意义；序列化后对端拿到的是副本，对象身份（identity）丢失，对端改了也不会影响调用者。正确做法：明确采用值传递；需要共享可变对象时改用远程引用（IP + port + 对象号）+ 回调（并处理悬空引用与生命周期），或使用 copy-restore 并在文档中写清”只在成功返回时写回”。
- 陷阱：手写结构体内存序列化（
memcpy(struct)后直接发）。 为什么错：对齐与填充（padding）是编译器与平台相关的，字节序也可能不同，接收方按自己的布局解释会得到静默的错误值（不报错，只是错）。正确做法：使用规范表示（XDR/protobuf/JSON），或至少显式规定字节序、字段宽度与对齐方式并逐字段读写。 - 陷阱：反序列化任何来源的字节流。 为什么错：
pickle.loads、Java 原生反序列化等会执行代码（__reduce__/ gadget 链 ⇒ RCE）。正确做法：只用”只有数据、没有行为”的格式（protobuf/JSON/FlatBuffers）；若必须用原生序列化，加签名/MAC + 类白名单 + 尺寸与深度上限，并把解析放进强隔离进程。 - 陷阱：去重表的水位用
highest[cid] := seq推进。 为什么错：一个乱序到达的更大序号会把中间序号”跳过”，使它们之后到达时被判为”过期”而无法去重，于是 exactly-once 悄悄退化。正确做法：水位用max推进、用”窗口内序号集合”做精确判重，并让窗口宽度远大于最大重传时间跨度。
18.8 思考题（带答案）
题 1（计算题）：某前台请求需并发调用 $n=50$ 个后端服务，每个后端独立地以 $p=0.02$ 的概率慢到 $T_{\text{slow}}=200$ ms，其余情况为 $T_{\text{fast}}=2$ ms。计算：(a) 至少一个后端变慢的概率；(b) 前台请求的期望延迟与中位延迟；(c) 若改为串行调用，期望延迟是多少？(d) 若把后端的慢概率降到 $p=0.002$（降 10 倍），(a)(b) 变成多少？并说明对”尾延迟治理”的启示。
答： (a) $P(\text{至少一个慢}) = 1-(1-p)^n = 1-0.98^{50}$。由 $0.98^{50} = e^{50\ln 0.98} = e^{-1.0101} = 0.3642$，得概率 $= \mathbf{63.6\%}$。 (b) $E[\max] = 0.3642\times 2 + 0.6358\times 200 = 0.73 + 127.2 = \mathbf{127.9\ ms}$。中位延迟 = 200 ms，因为 $63.6\% > 50\%$，过半请求都会踩到慢后端。（对照：无 fan-out 时 $E = 0.98\times2 + 0.02\times200 = 5.96$ ms——fan-out 把期望放大 21 倍，把中位数放大 100 倍。） (c) 串行：$E = 50\times 5.96 = \mathbf{298\ ms}$。并发把 298 ms 降到 127.9 ms，但依然被尾部支配——并发解决”累加”，解决不了”取最大”。 (d) $0.998^{50} = e^{-0.1001} = 0.9047$ ⇒ $P = \mathbf{9.5\%}$；$E[\max] = 0.9047\times2 + 0.0953\times200 = 1.81 + 19.06 = \mathbf{20.9\ ms}$；中位数回到 2 ms（因为 $9.5\%<50\%$）。 启示：把单服务慢概率降低 10 倍，整体尾延迟从 127.9 ms 降到 20.9 ms（改善约 6 倍），中位数从 200 ms 回到 2 ms（改善 100 倍）。这就是尾延迟放大的杠杆：在 fan-out 场景下，优化单个服务的尾部分布（消除 GC 停顿、隔离慢查询、避免队头阻塞）比优化平均延迟的收益大得多；同时要用超时裁剪、对冲请求、减少 fan-out 规模（聚合/缓存）从结构上削弱 $\max$ 算子。
题 2（”直观但错误”）：”既然客户端超时重传可能导致服务端重复执行，那么只要客户端不重传，服务端就最多执行一次了。” 这个想法错在哪？
答：错在把”重复的唯一来源”当成了客户端重传。重复请求至少有三个来源：(1) 客户端超时重传；(2) 网络/中间设备重复投递（TCP 段重传、负载均衡器或服务网格的重试、代理转发）；(3) 客户端应用层的重试（上层重试逻辑、消息队列的至少一次投递）。即使客户端一次都不重传，(2) 依然会发生——18-C2 实测中”请求重复投递”场景下，不重传档的执行次数是 2。所以”至多一次”是服务端的责任（过滤重复请求 + 缓存并重发上次响应），客户端不重传只能提高”至多一次”的概率，不能提供保证。推论：这正是讲义原表把 at-most-once 定义为”重传请求 + 过滤重复请求 + 重传上次响应“、而把”完全不重传”单独称为 Maybe / best-effort 的原因——后者的服务端执行次数没有上界。
题 3（概念题）：为什么”exactly-once”在真实系统里几乎总是被实现成”at-least-once 传输 + 幂等/去重处理”？请从传输层、服务端状态、正确性边界三个角度说明。
答：(1) 传输层：在异步网络中发送方无法区分“消息丢失”与”对端崩溃/变慢”，因此任何”保证送达且只送达一次”的传输协议都必须依赖无限等待或无限重传——前者丧失活性，后者必然产生重复。所以传输层只能做到 at-least-once（重传到成功）或 at-most-once（有限重传/不去重），做不到恰好一次。(2) 服务端状态：要让”重复请求不重复执行”，服务端必须记住”这个请求 ID 已处理过”以及”上次响应是什么”，即有状态的去重表 + 响应缓存；而要让这份记忆在崩溃恢复后仍有效，它必须被持久化或复制（复制状态机 / 共识日志，Lecture 17）——这会把”恰好一次”的成本提到”一次共识写入”的量级，解释了为什么 exactly-once 的吞吐与延迟代价显著高于 at-least-once。(3) 正确性边界：即使有去重表，窗口宽度 $W$ 有限、崩溃可能丢失去重记录，因此”恰好一次”只在”服务端不崩溃（或去重状态可恢复）+ 重复请求年龄小于 $W$”下成立；而“幂等”是操作自身的性质，不依赖服务端记住任何东西，在任何崩溃情形下都成立。结论：把”恰好一次”的责任从”传输层的有状态去重”转移到”业务层的幂等性/幂等键”，既更便宜（无需每请求一次共识），也更鲁棒（不依赖窗口与内存）——这就是工程界的一致选择。
题 4（设计题）：设计一个转账 RPC：transfer(from, to, amount)。说明你会选择哪种调用语义，并给出完整的失败处理方案（超时后怎么办、如何防止重复扣款、如何让用户在超时后得到确定答案）。
答：不能只选 at-most-once（超时时会给用户”假失败”，而钱可能已经转了，用户重试会造成混乱），也不能把 at-least-once 直接用在 balance = balance - amount 这种非幂等操作上（会重复扣款）。正确方案是”at-least-once 传输 + 幂等键 + 服务端事务内去重”，五步：
- 客户端生成幂等键：为这次转账生成 UUID
idem_key，并在用户重试时复用同一个 key（最关键的一点）；请求携带(idem_key, from, to, amount)。 - 服务端在同一数据库事务里做两件事：向
transfer_log(idem_key UNIQUE, from, to, amount, status, created_at)插入一行，并执行余额扣减/入账。唯一约束冲突即表示”已处理过”⇒ 直接返回上次的结果（从transfer_log读出），不再扣款。因为”记账”与”扣款”在同一事务提交，崩溃重启后不会重复扣款（提交前崩溃整体回滚，重启不会重放）。 - 超时后的客户端行为：不要立刻向用户报”失败”，也不要换一个新幂等键重试；应当用同一个
idem_key重试（at-least-once），或调用getTransferStatus(idem_key)查询状态（即”延迟响应/轮询”模式），把”未知”变成”确定”。 - 服务端返回明确终态：
SUCCEEDED/FAILED/PENDING。只在拿到SUCCEEDED或FAILED时才向用户报告；PENDING时提示”处理中，请稍后查询”——绝不向用户报告”未知”（用户会自己重复发起）。 - 运维与治理：为
idem_key设保留期（如 24 小时，覆盖最大重试跨度）；对idem_key建唯一索引保证并发下也不会双扣；幂等键按用户作用域隔离（防越权）；配合截止时间传播 + 重试预算 + 断路器避免重试风暴（18.2.14）。最终保证：用户可见的语义是 exactly-once（无论重试多少次，钱只扣一次），代价是一次额外的唯一约束写入，而不是一次共识提交。