Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

CSC4303 Network Programming

基础

五层模型，TCP&UDP，三次握手，流控制，滑动窗口，MAX-MIN，IP，DHCP，ARP，ICMP，NAT，最长前缀匹配，HTTP，DNS，CDN

一、 宏观架构：五层模型 (Five-Layer Model)

网络通信的模块化基石。每一层只和对等层（Peer）交互，并向下层请求服务。

  • 应用层 (Application Layer)：报文 (Message)。负责应用程序间的通信（如 HTTP, DNS, SMTP）。
  • 传输层 (Transport Layer)：报文段 (Segment)。负责进程到进程 (Process-to-Process) 的端到端通信，建立在端口号之上（TCP, UDP）。
  • 网络层 (Network Layer)：数据报 (Datagram/Packet)。负责主机到主机 (Host-to-Host) 的路由和转发，跨越不同的网络（IP, ICMP）。
  • 链路层 (Link Layer)：数据帧 (Frame)。负责同一局域网内相邻节点 (Node-to-Node) 的数据传输（Ethernet, WiFi, MAC地址）。
  • 物理层 (Physical Layer)：比特 (Bit)。负责在线缆、光纤中传输物理信号。

二、 传输层核心：TCP、UDP 与控制机制

这部分是重灾区，搞懂控制逻辑是关键。

1. TCP vs UDP (考点：场景选型)

  • TCP：面向连接、可靠的字节流。有确认重传、流量控制、拥塞控制。适用于对数据完整性要求极高的场景（网页浏览、文件下载、RPC 强一致性调用）。
  • UDP：无连接、不可靠的数据报。尽最大努力交付，无拥塞控制（发多快全凭应用程序），报文大小受限。适用于对延迟极其敏感、容忍丢包的场景（视频流、语音通话、DNS查询）。

2. 三次握手 (Three-Way Handshake)

  • 目标：在双向数据传输前，同步双方的初始序列号 (ISN, Initial Sequence Number)。
  • 过程：
    1. 客户端发送 SYN (SEQ=x)，进入 SYN_SENT 状态。
    2. 服务端收到后，发送 SYN (SEQ=y, ACK=x+1)，进入 SYN_RCVD 状态。
    3. 客户端收到后，发送 ACK (SEQ=x+1, ACK=y+1)，连接建立。
  • ⚠️ 陷阱：为什么不是两次？因为如果只有两次，服务端发出 SYN-ACK 后就以为连接建立了，但如果这个包在路上丢了，客户端并不知道，服务端就会一直死等，浪费资源。

3. 流控制 (Flow Control) & 滑动窗口 (Sliding Window)

  • 目标：保护接收方。防止发送方发得太快，把接收方的缓存（Buffer）撑爆。
  • 滑动窗口机制：允许发送方在收到确认之前，连续发送多个数据包，从而提高网络利用率（摆脱了极度低效的停等协议 Stop-and-Wait）。
  • 两种经典实现 (必考对比)：
    • Go-Back-N (GBN, 回退 N 步)：发送方只维护一个定时器。如果包 $N$ 丢失，定时器超时后，发送方必须重传包 $N$ 以及它之后的所有包（即使后面的包接收方已经收到了，也要重新发）。
    • Selective Repeat (SR, 选择性重传)：为每个发出的包维护独立的定时器。接收方缓存乱序到达的包。发送方只重传真正丢失的那个包。效率更高，但实现复杂。

4. Max-Min Fairness (最大最小公平)

  • 目标：在多条数据流共享网络瓶颈时，如何分配带宽最公平？
  • 原则：最大化那些需求最小的流的分配额。
  • 算法/计算逻辑：
    1. 将所有流的需求从小到大排序。
    2. 将剩余总带宽平均分给当前所有未满足的流。
    3. 如果某个流的需求小于平均值，就只给它需要的量。
    4. 把它没用完的“找零”带宽，拿出来继续平分给剩下那些“需求大于平均值”的流。
  • (注：TCP 的 AIMD 加法增乘法减机制，最终会在宏观上收敛到这种公平状态。)

三、 网络层基石：IP、路由与辅助协议

这里主要考对寻址和网络包生存周期的理解。

1. IP (Internet Protocol)

  • 核心功能：全局寻址（IPv4 是 32 位，IPv6 是 128 位）与数据包的路由转发。
  • CIDR 表示法：如 192.168.1.0/24，/24 表示前 24 位是网络号（Subnet），后 8 位是主机号。

2. 最长前缀匹配 (Longest Prefix Matching)

  • 机制：路由器的转发表中，可能有多个子网掩码都能匹配目的 IP。路由器必须选择**掩码最长（即最具体、范围最小）**的那条规则进行转发。
  • 做题技巧：把 IP 转换为二进制，从左到右数，看谁匹配的位数最多。

3. 四大辅助神将：DHCP, ARP, ICMP, NAT

  • DHCP (Dynamic Host Configuration Protocol)：
    • 作用：给刚接入网络、还没有 IP 的设备动态分配 IP 地址。
    • 机制：新设备因为不知道找谁，只能在局域网内发广播（目的 IP 设为 255.255.255.255，MAC 设为全 F）。DHCP 服务器听到后会“租”给它一个 IP。
  • ARP (Address Resolution Protocol)：
    • 作用：将逻辑上的 IP 地址转换为物理上的 MAC 地址。
    • 机制：要在局域网内发包，你必须知道对方网卡的 MAC 地址。ARP 会在局域网内大喊：“谁的 IP 是 x.x.x.x？把你的 MAC 告诉我！”
  • ICMP (Internet Control Message Protocol)：
    • 作用：网络层的错误报告与诊断协议（实际上封装在 IP 包里传输）。
    • 应用：你用的 ping（发 Echo Request，收 Echo Reply）和 traceroute（利用 TTL 过期报错）底层跑的全是 ICMP。
  • NAT (Network Address Translation)：
    • 作用：拯救了 IPv4 地址枯竭的救星。允许整个局域网（如校园网）里的所有设备，共享一个公网 IP 上网。
    • 机制：路由器内部维护一张 NAT 转换表，通过修改 IP 包头的 源私有IP : 源端口 -> 路由器公网IP : 新分配端口 来实现映射。

四、 应用层加速：HTTP、DNS 与 CDN

这三者是现代互联网秒级加载网页的铁三角。

1. HTTP (HyperText Transfer Protocol)

  • 核心：建立在 TCP 之上的无状态、Request/Response 模型。
  • 性能指标：PLT (Page Load Time)。现代 Web 优化全是为了降低 PLT，比如减小文件大小、使用 HTTP 并行连接/复用、使用缓存。

2. DNS (Domain Name System)

  • 核心：互联网的电话本。把人类可读的域名（www.google.com）翻译成机器能懂的 IP 地址。通常跑在 UDP 53 端口上。
  • 解析层级 (常考顺序)： 本地缓存 -> DNS 递归解析器 (ISP提供) -> Root DNS (根服务器) -> TLD DNS (顶级域名服务器，如 .com) -> Authoritative DNS (权威服务器，如 google.com)。

3. CDN (Content Delivery Network)

  • 核心：对抗物理距离带来的延迟。把静态资源（图片、视频、CSS）缓存在全球各地距离用户最近的“边缘节点”上。
  • 联动机制：CDN 强依赖于 DNS。当你请求域名时，DNS 服务器会根据你的源 IP 地址，智能地把域名解析到离你最近的那个 CDN 节点的 IP，而不是源站的真实 IP。

P2P

一、 为什么我们需要 P2P？（传统 C/S 模型的痛点）

PPT 一开始回顾了你熟悉的 C/S（客户端/服务器）模型（第 2 页）。它的逻辑很简单：客户端发请求（“Do A for me”），服务器回响应。

但当客户端数量达到数百万时，可扩展性问题 (Scaling Problem) 就出现了（第 3 页）。所有的流量都涌向服务器，会导致网络拥塞和服务器崩溃（Meltdown）。

解决方案（第 4-6 页）：

  • P2P (Peer-to-Peer) 系统：与其让服务器一个人干活，不如发动群众。利用客户端机器（Peers）自身的计算、存储和带宽资源。
  • 传统的 P2P 共享计算、存储和带宽；现代的甚至可以共享移动性、加密货币和传感器数据。
  • 在 P2P 存储网络中，每个成员既是下载者也是提供者。难点在于：文件可能在任何地方，我们怎么找到它（Searching/Lookup problem）？ 此外，节点随时可能上线或下线（Node churn），这让搜索更困难。

二、 P2P 的搜索策略演进

为了解决“寻找文件”的问题，P2P 网络发展出了几种不同的策略（第 11-23 页）。所有的 P2P 框架都需要解决四个基本原语：Join（加入）、Publish（发布）、Search（搜索）、Fetch（获取）。

1. Napster（中心化目录）

  • 原理：虽然文件存在各个客户端电脑上，但有一个中央服务器记录着“谁拥有什么文件”的目录。
  • 流程：
    • Publish：节点告诉服务器“我有文件 X”。
    • Search：客户端问服务器“谁有文件 A？” 服务器返回对应的 IP 节点（例如 123.2.0.18）。
    • Fetch：客户端直接去找 123.2.0.18 下载文件。
  • 优缺点：
    • 优点：简单，搜索速度极快（时间复杂度 $O(1)$）。
    • 缺点：中央服务器压力巨大（维护 $O(N)$ 状态），且存在单点故障（服务器一挂，全网瘫痪；服务器被查封，游戏结束）。

2. Gnutella（去中心化泛洪）

  • 原理：彻底没有中央服务器。通过节点互相询问来找文件。
  • 流程：
    • Join：连上几个邻居节点。
    • Search (Query Flooding)：客户端问邻居“谁有文件 A？”，邻居再问邻居的邻居（广播泛洪）。为了防止消息无限传播，会设置 TTL（生存时间）。谁有文件，就原路返回消息。
  • 优缺点：
    • 优点：彻底去中心化，抗摧毁能力强。支持复杂的搜索语义。
    • 缺点：网络开销巨大（为了找一个文件要惊动全网），搜索范围受限，可能找不到文件。网络极不稳定。

3. BitTorrent (BT 下载)

  • 原理：结合了 Tracker 服务器和文件分块群集（Swarming）下载。专注于“少数大文件”的分发。
  • 流程：
    • Join：连接中央 Tracker 服务器获取同伴列表。
    • Fetch：向其他拥有该文件块的节点（Peers）下载，同时把你自己下载好的块上传给别人。
  • 核心策略：Tit-for-tat（以牙还牙）：为了防止“只下不传”的伸手党（Freeloaders），BT 规定：谁给我传得快，我就优先给谁传。同时会保留一小部分带宽进行“乐观解锁”（Optimistic unchoke），给新人一点机会，也借此发现更快的节点。
  • Rarest first（最稀缺优先）：优先下载网络中最稀缺的文件块，保证文件的整体存活率。

三、 终极解决方案：DHT 与 Chord 算法

前面几种方案要么有单点故障，要么搜索效率低。为了保证“只要文件存在，就一定能在有限步数内找到”，科学家引入了 DHT（分布式哈希表）（第 24-36 页）。

1. DHT 的概念

把整个 P2P 网络抽象成一个巨大的哈希表。

  • $Key = Hash(Data)$：文件的标识是哈希值。
  • $Lookup(Key) \rightarrow IP$：可以通过 Key 快速找到存储该文件的节点 IP。
  • DHT 要求：去中心化、可扩展（网络开销低）、高效（查询延迟低）、动态（能应对节点频繁上下线）。

2. Chord 算法与一致性哈希 (Consistent Hashing)

Chord 是 DHT 的一种经典实现。

  • 地址空间环：把所有的 IP 地址和文件 Key 用相同的 Hash 函数（如 SHA-1）映射到一个巨大的环形数字空间里。
  • 存储规则：一个 Key 会被存储在顺时针方向上第一个大于等于它的节点上（即它的后继节点 Successor）。
    • 举例（第 28 页）：节点有 N32, N60, N90, N105。Key 80 会顺时针找，存到 N90 上。

3. Chord 的核心：Finger Table (指针表/路由表)

如果每次查找都顺时针一步一步走，那时间复杂度是 $O(N)$，太慢了。Chord 给每个节点配备了一个路由表 (Finger Table) 来实现跳跃查找（第 30-35 页）。

  • 表结构：假设地址空间大小是 $2^m$。每个节点的 Finger Table 记录了距离自己 $2^0, 2^1, 2^2 \dots 2^{m-1}$ 距离后的第一个后继节点。
  • 查找逻辑：当节点收到查询请求时，如果自己不是目标节点，就去查自己的 Finger Table，把请求转发给表中距离目标 Key 最近且不超过目标 Key 的那个节点。
  • 效果：每次转发，距离目标的剩余距离期望能减半。

4. DHT 的总结（第 36-39 页）

  • 性能：路由表大小是 $O(\log N)$，查询时间跳数也是 $O(\log N)$。
  • 优点：保证能找到数据，良好的可扩展性和容错性。一致性哈希这个概念极其成功，不仅用在 P2P，后来还成了所有现代分布式数据库（比如 Amazon Dynamo, Cassandra）的基石。
  • 缺点：只能做精确匹配（Hash查找），很难做模糊搜索或关键字搜索。如果需要强一致性或极高性能（比如银行系统），就不适合用 P2P 架构。

Dynamo

没问题，咱们不整花里胡哨的，老老实实、硬核地拆解 Amazon Dynamo 这个分布式系统领域的“扛把子”。这部分是期末考试的绝对重点，特别是它的机制权衡（Trade-offs）和计算。

结合你前面复习的 P2P 知识，理解 Dynamo 会非常顺畅：它本质上就是把 P2P 网络里的一致性哈希理念，做成了一个工业级的、去中心化的 Key-Value 数据库。

以下是面向考试的知识点拆解：

1. 为什么要有 Dynamo？（设计哲学）

Dynamo 是亚马逊为“购物车”业务量身定制的。

  • 核心诉求：永远可写（High Availability for Writes）。对于电商而言，绝不能拒绝用户的“加入购物车”请求，否则就是直接损失收入。
  • 妥协代价：为了保证“写”的极高可用性，Dynamo 放弃了强一致性，只保证最终一致性（Eventual Consistency）。这意味着在短时间内，用户可能会读到旧的购物车数据，但这比写失败要好。

2. 数据存在哪？—— 一致性哈希与虚拟节点（必考概念）

Dynamo 使用完全对等的架构（没有像 GFS 那样的 Master 节点）。

  • 一致性哈希 (Consistent Hashing)：所有物理机器和数据 Key 都被哈希映射到一个首尾相接的逻辑环上。一个 Key 顺时针方向遇到的第一个节点，就是负责存储它的节点。
  • 虚拟节点 (Virtual Nodes / vnodes)：这是为了解决数据倾斜（负载不均）的绝招。
    • 问题：如果环上只有几个物理节点，数据分布会极不均匀。
    • 解决：让一台物理机器在环上映射出多个“虚拟节点”。这不仅完美解决了负载均衡，还可以根据物理机的性能高低，分配不同数量的 vnode。

3. 数据怎么保证不丢？—— N、R、W Quorum 机制（必考计算与分析）

为了防止节点宕机导致数据丢失，Dynamo 会把数据顺时针复制给 N 个节点。考试最爱考的就是这三个参数的配置组合：

  • N（Replication Factor）：总副本数。
  • W（Write Quorum）：一次写操作，必须收到 W 个节点的确认，才算“写成功”。
  • R（Read Quorum）：一次读操作，必须向 R 个节点发起查询，才能返回数据。

核心考试逻辑：

  • 如果 R + W > N，系统保证强一致性。因为读取的集合和写入的集合必然有交集（鸽巢原理），你一定能读到最新写入的那份数据。
  • 如果 R + W <= N，系统退化为最终一致性。

经典考点（基于 N=3）：

  • 配置 (3, 2, 2)：系统最常用的平衡配置。读写速度适中，容错性好。
  • 配置 (3, 1, 3)：写极快、读极慢。因为写 1 个节点就返回，但读要等 3 个节点。风险：只要有 1 个节点宕机，读操作就会因为凑不齐 3 个响应而直接失败。
  • 配置 (3, 3, 1)：读极快、写极慢。且写操作非常脆弱，任意一个节点挂了，写操作就会失败（这违背了 Dynamo 的初衷）。

4. 数据冲突了怎么办？—— 向量时钟 (Vector Clock)

既然 Dynamo 追求极速写入，甚至在网络断开（Network Partition）的情况下也允许不同节点接收写请求，那就必然会产生数据冲突（例如同一个 Key 在两个节点上被改成了不同的值）。

  • 机制：系统通过向量时钟（如 [Node A: 1, Node B: 2] 这样的计数器数组）来追踪数据的因果关系。
  • 解决策略：
    • 如果向量时钟能看出明显的先后顺序，系统自动用新版本覆盖旧版本。
    • 如果向量时钟显示这是两个并行的、冲突的版本（比如在断网时，用户分别在手机和电脑往购物车里加了不同的东西），Dynamo 不会自己瞎决定，而是把两个版本都保留，丢给**客户端（应用层）**去解决。例如，让购物车的业务代码把这两件商品合并。

5. GFS vs Dynamo 终极对比（常考辨析题）

考试很可能会让你判断某个场景该用 GFS 还是 Dynamo：

  • GFS / HDFS：适合大文件、追加写入、批处理（如服务器日志分析）。它重视的是整体的吞吐量，采用的是中心化（Master-Worker）架构。
  • Dynamo：适合小对象、随机读写、实时交互（如购物车、会话状态）。它重视的是极低延迟和超高可用性，采用的是去中心化（P2P）架构。

GFS

这份 PPT（13-gfs.pdf）详细介绍了 GFS (Google File System)，它是现代分布式存储系统的鼻祖，也是 Hadoop HDFS 的蓝本。

一、 GFS 深度解析：为大数据而生

GFS 的核心逻辑是：用廉价、不可靠的机器，组建一个可靠、高性能的超大规模文件系统。

  1. 目标环境与假设：

    • 故障是常态：数千台机器中，总有磁盘损坏或网络断开，系统必须能自动恢复。
    • 文件巨大：处理的是 TB 级的文件，不能按传统文件系统的方式管理。
    • 写多读少 (Append-only)：数据主要是追加（Append）进去的，很少随机修改。重点是高吞吐量（一次搬运大量数据），而不是低延迟（快速响应一个字节）。

  2. 核心设计决策：

    • 分块 (Chunks)：文件被切成 64MB 或 128MB 的大块（比普通文件系统的 4KB 大得多），减少了 Master 节点的元数据压力。
    • 多副本：默认 3 副本。为了容灾，通常在同一个机架存 1 份，其他不同机架存 2+ 份。
    • 单一 Master：为了简化逻辑，所有文件名的管理、块的分配都由一个 Master 负责。

  3. 读写流程 (Architecture)：

    • Master：只存元数据（文件名、块 ID、块在哪个机器上）。它不碰实际数据，所以不会成为带宽瓶颈。
    • Chunkserver：在本地 Linux 磁盘上存实际数据块。
    • 流程：Client 问 Master“文件 A 的第 1 块在哪？”，Master 回复“在机器 X、Y、Z 上”。Client 缓存这个位置，然后直接去找机器 X 读数据。

二、 GFS 与 Dynamo：相同与差别

这两个系统代表了分布式存储的两个极端。相同点在于它们都通过数据复制 (Replication) 来解决不可靠硬件带来的容错 (Fault Tolerance) 和高可用性 (High Availability) 问题。

但它们的架构设计和适用场景完全不同：

维度GFS (及 HDFS)Amazon Dynamo
接口类型文件系统 (提供文件夹、文件操作)键值对 (KV) 存储 (提供 get/put 操作)
架构模式中心化 (Master-Worker)：有一个指挥官 Master去中心化 (P2P)：所有节点地位平等，使用一致性哈希
负载假设巨型文件，顺序读取，一次写入多次读取小型对象 (如购物车)，随机读写频繁
优化目标高吞吐量 (Throughput)：适合离线批处理低延迟 (Latency)：适合实时交互式应用
一致性放松的一致性：主要保证追加数据的原子性最终一致性：允许冲突，通过向量时钟解决
典型用途搜索引擎索引构建、大规模日志分析购物车状态、用户会话管理

总结：

  • 如果你要跑一个 MapReduce 任务分析 10TB 的日志，选 GFS。
  • 如果你要让用户的网页请求在毫秒内更新购物车状态，选 Dynamo。

RPC

没问题，既然咱们要硬核，那就把底层细节全盘托出。RPC（Remote Procedure Call，远程过程调用）是整个现代分布式系统（包括微服务架构）的绝对基石。

理解 RPC，核心是理解它在“骗”你。它试图把不可靠、极其复杂的网络通信，伪装成一次普通的本地函数调用。

咱们顺着这套逻辑，把 RPC 这部分的 PPT 考点和底层机制彻底剥开：

第一层：为什么要搞 RPC？（Socket 的原生痛点）

在没有 RPC 的黑暗时代，程序员只能用 Socket（套接字）写网络程序。 假设你想调用远程服务器上的一个加法函数 add(int a, int b)。如果用纯 Socket，你会面临以下极其折磨人的问题：

  1. 协议打包与解析：你怎么把 a 和 b 发过去？是拼成字符串 "add,1,2" 发送，还是按字节流发？
  2. 异构性问题 (Heterogeneity)：如果客户端是 C++（小端序），服务端是 Java（大端序），整数 1 在内存里的字节排布是完全反的。直接把内存字节发过去，服务端读出来的就是一个天文数字。
  3. 粘包与半包：网络底层是流（TCP），你发了 "add,1,2"，服务端可能先收到了 "ad"，又收到了 "d,1,2"。你怎么保证读取的是完整的一个请求？
  4. 并发与匹配：如果客户端在一个连接上同时发了 10 个请求，服务端返回了 10 个结果，客户端怎么知道哪个结果对应哪个请求？

结论：Socket 太底层了，每次写业务都要处理这些恶心的网络细节。RPC 的诞生就是为了把这些脏活累活全部封装起来。

第二层：RPC 的核心架构 —— 瞒天过海的 Stub (存根)

RPC 的终极目标是：让调用远程机器上的代码，看起来就像调用本地内存里的函数一样简单。

为了实现这个错觉，RPC 引入了两个极其关键的中间人：Client Stub（客户端存根） 和 Server Stub（服务端存根）。

一次完整 RPC 调用的微观过程（必考流程）：

  1. 本地调用：客户端业务代码调用本地函数 add(1, 2)，但这其实不是真正的函数，而是 Client Stub。
  2. 序列化 (Marshaling)：Client Stub 拿到参数 1 和 2，把它们转换成一种与机器无关的二进制字节流（比如统一转成大端序，加上数据类型标记）。这个过程叫 Marshaling 或 Serialization。
  3. 网络传输：Client Stub 调用底层的 Socket，把这串字节流发给服务器。
  4. 反序列化 (Unmarshaling)：服务端的 OS 收到字节流，交给 Server Stub。Server Stub 解码字节流，还原出参数 1 和 2。
  5. 实际调用：Server Stub 用这俩参数去调用真正的服务端业务代码 add，拿到结果 3。
  6. 原路返回：Server Stub 把 3 序列化发回给客户端，Client Stub 反序列化后，把 3 返回给本地代码。

在这个过程中，业务程序员只觉得做了一次普通的 add(1, 2)，完全感觉不到网络的发生。

IDL (接口描述语言)

这么牛逼的 Stub 代码是谁写的？不用人写，是机器自动生成的。 程序员只需要用 IDL (Interface Description Language) 写一个简单的配置文件（声明函数名、参数类型、返回值类型）。然后用 IDL 编译器（比如 gRPC 的 protoc）一跑，就能自动生成 C++ 的 Client Stub 和 Python 的 Server Stub。这完美解决了跨语言和跨平台的异构性问题。

第三层：RPC 的三大核心挑战 (考试重灾区)

RPC 虽然好用，但“网络就像本地调用”终究是个错觉。网络是会骗人的，这也是考试最爱挖坑的地方。

1. 性能损耗 (Performance)

  • 考点/概念：一次本地调用的耗时在纳秒级（$\approx 3$ ns，大概 10 个 CPU 周期）。
  • 但是，如果是同一个数据中心内的 RPC，耗时在微秒级（$\approx 10$ µs），慢了 $10^3$ 倍。
  • 如果是广域网（比如跨国请求），耗时在毫秒级，慢了 $10^6$ 倍。
  • 启发：程序员不能肆无忌惮地在一个 for 循环里发几万次 RPC，必须用批量发送（Batching）或异步调用（Asynchronous）来缓解网络延迟。

2. 异构性与服务寻址 (Heterogeneity & Rendezvous)

  • 寻址：客户端怎么知道服务器的 IP 和端口？怎么知道目标机器上哪个函数对应这个请求？通常需要一个注册中心（Registry）或者在协议头中带上特定的函数 ID（Dispatching）。

3. 故障处理语义 (Failure Handling) —— ★★★ 绝对核心大题 ★★★

本地函数调用，要么成功，要么由于进程崩溃而彻底死掉。但 RPC 不一样，如果客户端发了请求但没收到回音，它根本不知道到底发生了什么：

  • 是请求在去程的路上丢了？
  • 是服务器正在处理，只是特别慢？
  • 是服务器处理完了，但在回程的路上结果丢了？
  • 是服务器崩溃了？

为了应对这种薛定谔的状态，RPC 提供了几种不同的故障处理语义 (Semantics)，你需要根据业务场景来选择：

A. At-least-once (至少一次语义)

  • 机制：客户端死缠烂打。设置一个超时时间，如果在时间内没收到回音，就重传 (Retransmission) 请求。直到收到回音为止。
  • 副作用：如果其实是回程的包丢了，服务器会重复执行这个操作。
  • 适用场景：必须用于幂等 (Idempotent) 的操作。比如“读取某个文件的内容”、“把计数器设置为 5”。这些操作你执行一万次，结果也和执行一次一样。

B. At-most-once (至多一次语义)

  • 机制：服务器必须长记性。服务器端会维护一个状态历史表，记录它已经处理过了哪些客户端的哪些 Request ID。
  • Duplicate Filtering (过滤重复)：如果服务器收到了一个曾经处理过的 Request ID，它绝对不会再执行一遍业务逻辑，而是直接把缓存在表里的上一次的计算结果再发回给客户端。
  • 清理状态：为了防止这张表无限变大，通常会配合 Cumulative ACKs (累积确认) 机制来定期丢弃已经确定的旧状态。
  • 适用场景：用于非幂等操作。比如“扣除账户 100 块钱”、“订一张机票”。绝不能因为重传而导致用户被扣两次钱。

C. Exactly-once (精确一次语义)

  • 机制：终极理想态。即要求底层具备 At-least-once（保证能达到），加上 At-most-once（保证不重复执行），再加上容错机制（Fault tolerance，比如服务器中途宕机重启后也能恢复状态），且整个过程没有任何外部副作用泄露。
  • 现实：在纯粹的网络 RPC 层面上极难完美实现，通常需要结合业务层面的分布式事务或两阶段提交 (2PC) 来做。

考场抢分指南

如果考卷上出现 RPC 的题目，通常是这样设问的：

  • 题型 1：RPC vs Socket。如果问 RPC 解决了什么问题，记住两个关键词：屏蔽底层网络细节（自动 Marshaling）和 解决异构性（跨语言、跨平台 IDL）。
  • 题型 2：语义选择题（必拿分）。类似 Sample 里的题目，给你一个场景（比如电商下单、查询天气），问你选 At-least-once 还是 At-most-once。
    • 解题心法：盯住这个操作重做一遍会不会出事。不出事（如只读查询、绝对赋值）选 At-least-once；出事（如加减钱、下单、发邮件）选 At-most-once。
  • 题型 3：At-most-once 的实现细节。如果要求简述 At-most-once 怎么做，一定要写出关键术语：客户端带上唯一的 ID，服务端做重复过滤 (Duplicate filtering)，服务端需要缓存结果以应对网络丢包。

Collective

这是所有高级网络编程和分布式系统课程的绝对核心：集合通信算法（Collective Communication Algorithms）的底层拓扑与通信代价的数学推导。

这部分不难，但极其考验你对公式的推导逻辑。只要搞懂了代价模型 (Cost Model)，所有公式你都能在考场上自己推出来。下面我为你硬核拆解这部分的数学计算，保你这道大题拿满分：

零、 万物之源：线性通信代价模型

在评估任何分布式通信算法前，必须先建立数学模型。假设两个节点之间发送一个长度为 $n$ 的消息，总耗时 $T$ 可以表示为：

$$T = \alpha + n\beta$$

  • $\alpha$ (Alpha, Latency/Startup time)：延迟/启动时间。这是建立连接、网卡准备等固定开销，与消息大小无关。
  • $\beta$ (Beta, Inverse Bandwidth)：传输每个字节（或 Word）所需的时间。即 $\frac{1}{\text{Bandwidth}}$。
  • $n$ (Message size)：消息的总长度。
  • $p$ (Number of nodes)：参与通信的节点总数。为了方便推导，通常假设 $p$ 是 2 的幂次方，即 $p = 2^k$，所以经过的层数 $k = \log_2(p)$。

一、 最小生成树 (MST / Binomial Tree) 家族

核心结论：为了优化“小消息”设计。它的 $\alpha$ 开销极小（只有 $\log p$ 级别），但 $\beta$ 带宽利用率不高。

1. Broadcast (广播) 的推导

  • 逻辑：节点 0 发给 1；然后 0 和 1 发给 2 和 3；接着 4 个节点发给另外 4 个。
  • 步数：每次翻倍，总共需要 $\log_2(p)$ 步。
  • 每步代价：每次都是发送完整的消息 $n$，所以单步代价是 $\alpha + n\beta$。
  • 总代价： $$T_{MST\_Bcast} = \log_2(p)(\alpha + n\beta) = \log_2(p)\alpha + \log_2(p)n\beta$$

2. Gather (收集) 的推导 (⚠️ 极易考的难点)

  • 逻辑：把分散在所有节点的数据（每份大小为 $\frac{n}{p}$，总大小为 $n$）汇总到一个节点。这是 Broadcast 的逆过程，数据像滚雪球一样越来越大。
  • 推导过程：
    • 第 1 步：节点两两配对，一半的节点向另一半发送自己仅有的一份数据 $\frac{n}{p}$。耗时：$\alpha + \frac{n}{p}\beta$。
    • 第 2 步：剩下的 $\frac{p}{2}$ 个节点继续两两配对，发送已经拼好的双份数据 $\frac{2n}{p}$。耗时：$\alpha + \frac{2n}{p}\beta$。
    • 第 $i$ 步：发送的数据量是 $2^{i-1}\frac{n}{p}$。耗时：$\alpha + 2^{i-1}\frac{n}{p}\beta$。
  • 求和计算（步数从 $1$ 到 $\log_2 p$）： $$T_{MST_Gather} = \sum_{i=1}^{\log_2 p} \left( \alpha + 2^{i-1}\frac{n}{p}\beta \right)$$ 其中 $\alpha$ 加了 $\log_2 p$ 次，后面是一个等比数列求和：$1 + 2 + 4 + \dots + 2^{\log_2 p - 1} = 2^{\log_2 p} - 1 = p - 1$。
  • 总代价： $$T_{MST\_Gather} = \log_2(p)\alpha + \frac{p-1}{p}n\beta$$ (你对照一下你的 Sample Question 5b，完全吻合！)

3. Scatter (分发) 的推导

  • 逻辑：Gather 的完全逆过程。根节点把大小为 $n$ 的数据切分，一开始发一半出去，然后两边再各自切分发一半。
  • 总代价：与 Gather 在数学上完全对称，公式一模一样： $$T_{MST\_Scatter} = \log_2(p)\alpha + \frac{p-1}{p}n\beta$$

4. AllGather (全收集) 的推导

  • 逻辑：每个节点都有一份 $\frac{n}{p}$ 的数据，最终要让每个节点都拥有完整的 $n$。在 MST 中，这通常被拆解为两步：先 Gather 到根节点，再由根节点 Broadcast 给所有人。
  • 总代价 = $T_{MST_Gather} + T_{MST_Bcast}$

$$T_{MST_AllGather} = \left(\log_2(p)\alpha + \frac{p-1}{p}n\beta\right) + \left(\log_2(p)\alpha + \log_2(p)n\beta\right)$$ $$T_{MST_AllGather} = 2\log_2(p)\alpha + \left(\log_2(p) + \frac{p-1}{p}\right)n\beta$$

二、 环形拓扑 (Ring Algorithm) 家族

核心结论：为了优化“大消息”设计。它的带宽利用率极高（$\beta$ 项最优），但会产生大量的启动延迟（$\alpha$ 项高达 $p-1$）。

1. Ring AllGather 的推导

  • 逻辑：把 $p$ 个节点连成一个环。每个节点初始有 $\frac{n}{p}$ 数据。在每一步中，每个节点都把上一轮刚收到的那块数据，发送给它的右手边邻居。
  • 步数：需要循环传递，直到每个人都拿到别人的拼图，总共需要 $p-1$ 步。
  • 每步代价：每次传递的数据块大小固定是 $\frac{n}{p}$。单步耗时：$\alpha + \frac{n}{p}\beta$。
  • 总代价： $$T_{Ring\_AllGather} = (p-1)\left(\alpha + \frac{n}{p}\beta\right) = (p-1)\alpha + \frac{p-1}{p}n\beta$$

2. Ring Reduce-Scatter 的推导

  • 逻辑：和 Ring AllGather 刚好相反，每个节点一开始都有完整的 $n$（分为 $p$ 块），目标是把不同节点对应位置的块相加（Reduce），最后每个节点只保留一块 $\frac{n}{p}$ 的结果。
  • 总代价：步骤和数据流向与 AllGather 相同。 $$T_{Ring\_ReduceScatter} = (p-1)\alpha + \frac{p-1}{p}n\beta$$

3. Ring AllReduce 的推导 (经典大考点)

  • 逻辑：让所有节点的数据相加，且每个人都得到完整的最终结果。在 Ring 算法中，它被完美拆解为：先做一次 Reduce-Scatter，再做一次 AllGather。
  • 总代价 = $T_{Ring_ReduceScatter} + T_{Ring_AllGather}$

$$T_{Ring_AllReduce} = 2(p-1)\alpha + 2\frac{p-1}{p}n\beta$$

三、 考场绝杀：什么时候选 MST，什么时候选 Ring？

考卷上一定会问你：为什么要设计这两种算法？我们来对比 AllGather 这一项：

  • MST 的代价：$2\log_2(p)\alpha + \left(\log_2(p) + 1\right)n\beta$ （这里把 $\frac{p-1}{p}$ 近似为 1）
  • Ring 的代价：$(p-1)\alpha + 1n\beta$

直击灵魂的数学分析：

  1. 当消息极小（$n$ 很小）时，公式里的 $n\beta$ 项可以忽略不计，整个耗时由 $\alpha$ 决定。此时 MST 的 $\log_2(p)$ 远小于 Ring 的 $p-1$。结论：小消息用 MST。
  2. 当消息极大（$n$ 很大）时，$\alpha$ 可以忽略不计，耗时由 $\beta$ 决定。此时 Ring 的带宽系数是 $1$，而 MST 的带宽系数是 $\log_2(p) + 1$。说明 MST 会产生巨大的冗余带宽开销。结论：大消息用 Ring。

Distributed ML and LLM

别慌！这份 PPT（17-mlsys.pdf）虽然长达 73 页，但其实它的逻辑主线非常清晰。它只讲了一件事：在现代 AI 领域，模型太大了，单台机器搞不定，我们该如何用分布式系统来训练和部署它们？

还记得你之前用 PyTorch 训练图像分类模型吗？当时模型估计能直接塞进单张显卡里跑。但到了工业界，像 GPT-3 这样的模型有 1750 亿参数，光是存下这些权重就需要 350GB 的显存，一张 80GB 的 A100 根本装不下。

为了应对这个挑战，这份 PPT 拆解了三个核心模块，这也是考试必考的重点：

模块一：分布式训练 (Distributed Training) —— 怎么把大模型拆开练？

如果一张卡装不下或跑得太慢，我们必须并行。这里有三大流派：

1. 数据并行 (Data Parallelism)

  • 做法：模型完整复制到每张卡上，把训练数据切成小块分给不同卡跑 。
  • 痛点与考点：跑完后大家需要把梯度汇总（Aggregation）。如果用中心化的 Parameter Server，参数服务器会成为网络瓶颈 ；如果用 Naïve AllReduce，通信量高达 $N^2 \times M$ 。
  • 终极解法：Ring AllReduce。把 GPU 连成一个环，每个 GPU 只给右边的邻居发数据，通信量降为 $2 \times M$，与节点数 $N$ 无关，具有极佳的可扩展性 。

2. 张量模型并行 (Tensor Model Parallelism)

  • 做法：把一层网络（比如矩阵乘法）切开，大家各算一部分最后拼起来 。
  • 特点：在前向和反向传播中需要极度频繁地传输中间结果，所以通常只能在一个机器内部（比如 NVLink 互联的 8 张卡）做，没法跨机器大规模扩展。

3. 流水线模型并行 (Pipeline Model Parallelism) —— ⚠️ 重点计算题

  • 做法：把网络按层切段（比如前 10 层给 GPU 1，中间 10 层给 GPU 2）。
  • 痛点 (气泡 Bubble)：如果按正常流程跑，GPU 1 算完传给 GPU 2 时，GPU 2 一直在干等，这叫计算气泡 。
  • 解法与公式：把一个 Mini-batch 进一步切分成多个 Micro-batch ($m$) 来流水线作业 。考试极有可能会让你计算气泡占比 (Bubble Fraction)，公式为 $\frac{p-1}{m}$（其中 $p$ 是流水线阶段数/GPU数）。为了降低显存占用，通常会采用 1F1B (One Forward One Backward) 调度策略 。

为了帮你在考前对这个极其重要的公式建立直觉，我为你做了一个流水线气泡计算器：

模块二：大模型推理服务 (LLM Serving) —— 怎么高效地给用户生成文本？

训练好模型后要上线提供服务。LLM 的生成是“自回归”的，一次只能蹦出一个词 。

  • 两个关键阶段：
    • Prefill (预填充阶段)：处理用户的 Prompt，计算密集型 (Compute-bound)。决定了 TTFT (Time To First Token，首字延迟) 。
    • Decoding (解码阶段)：利用之前存下的 KV Cache，一个个吐字，显存带宽密集型 (Memory-bound) 。决定了 TPOT (Time Per Output Token，单字延迟) 。
  • 核心痛点：Continuous batching (连续批处理) 机制
    • 静态批处理必须要等同一批所有请求都生成完才能接客，造成大量 GPU 闲置 。
    • 现代系统（如 Orca）采用连续批处理：只要有请求结束（遇到 <EOS>），下一秒的迭代立马把新请求加进来一起跑，极大提高了 GPU 的利用率 (Higher GPU utilization) 。

模块三：前沿系统设计 (State-of-the-Art Systems) —— 解决极致的性能冲突

这是这门课的拔高部分，主要讲了两篇顶会论文的思想：

1. 分离式架构 (Disaggregated Serving / DistServe 论文)

  • 问题：Prefill 和 Decoding 放在同一台机器上跑会互相打架 (Interference) 。因为 Prefill 吃算力，Decoding 吃显存，这导致同时保证 TTFT 和 TPOT 的 SLO 变得很难。
  • 解法：剥离！ 一组专门的 GPU 实例只负责算 Prefill (优化 TTFT)，算完后把 KV Cache 通过网络传给另一组专门做 Decoding 的 GPU 实例 (优化 TPOT) 。

2. 快速扩容 (Fast LLM Scaling / FaaScale 论文)

  • 问题：当流量像双十一一样突然暴增时，传统的 Serverless 需要从 S3 远端下载几百 GB 的模型，太慢了 。
  • 解法：利用 GPU 集群内部的 RDMA 高速网络，像 BT 下载一样把模型快速广播 (Multicast) 分发。同时，采用“边加载边推理 (Execute-while-load)”的策略，不等模型完全传完，前几层传到了就开始算 。

这 73 页的灵魂就在这里了。如果考试考大题，大概率会让你：

  1. 计算流水线并行的 Bubble Fraction。
  2. 解释 Ring AllReduce 相比 Parameter Server 为什么好。
  3. 阐述为什么 LLM 推理要把 Prefill 和 Decoding 拆开。