关键问题：部件会坏，系统不能坏

你打开的每个网页背后，往往是成千上万台机器在协作。分布式系统带来的新挑战里，本章关注最主要的一个：故障（failure）。有意思的是，故障既是挑战也是机会：单台机器坏了，并不意味着整个系统必须停摆——把许多机器组合起来，就能做出一个"看起来几乎不坏"的系统，尽管它的部件经常在坏。

这让人想起第 38 章的 RAID：用多块会坏的盘拼出一个可靠的盘。但分布式系统的问题更复杂：除了故障，还要考虑性能（尽量少发消息、低延迟高带宽）和安全（确认对方身份、防止第三方窃听或篡改）。本章先打地基：机器之间怎么通信，以及通信层如何对付故障。接下来的第 49 章（NFS）和第 50 章（AFS）就是建立在这些通信原语之上的分布式文件系统。

核心概念速览

通信基础：丢包是常态

现代网络的核心信条是：通信从根本上就是不可靠的。无论是广域的互联网，还是局域网里的 InfiniBand 这类高速网络，包都会经常丢失、损坏，或者因为别的原因到不了目的地。原因有好几类：

第三点最关键：一个包到达路由器后，必须先放进路由器的内存里才能处理。如果同一时刻涌进来太多包，内存装不下，路由器唯一能做的就是丢掉一部分。端主机也一样：你向同一台机器猛发大量消息，它的资源很快就会被压垮，于是又开始丢包。所以丢包在网络中是根本性的，问题只能是：我们怎么应对它？

不可靠通信层：UDP

最简单的应对办法是：不处理。有些应用自己知道怎么处理丢包，给它们一个基本的不可靠消息层就够了——这也是后面会讲的"端到端论证"的一个例子。今天几乎所有系统都自带的 UDP/IP 协议栈就是这样的不可靠层：进程用套接字（sockets）API 创建一个通信端点，其他机器（或同一台机器）上的进程向它发送 UDP 数据报（datagram）——一个有最大长度限制的消息。

下面是原书 Figure 48.1 的客户端/服务端，只保留了核心部分：

// client code
int main(int argc, char *argv[]) {
    int sd = UDP_Open(20000);                     // 在本机 20000 端口建一个端点
    struct sockaddr_in addrSnd, addrRcv;
    int rc = UDP_FillSockAddr(&addrSnd, "cs.wisc.edu", 10000);  // 目的地：主机名 + 端口
    char message[BUFFER_SIZE];
    sprintf(message, "hello world");
    rc = UDP_Write(sd, &addrSnd, message, BUFFER_SIZE);          // 发出去（可能丢！）
    if (rc > 0)
        rc = UDP_Read(sd, &addrRcv, message, BUFFER_SIZE);       // 等回复（可能永远等不到）
    return 0;
}

// server code
int main(int argc, char *argv[]) {
    int sd = UDP_Open(10000);
    assert(sd > -1);
    while (1) {
        struct sockaddr_in addr;
        char message[BUFFER_SIZE];
        int rc = UDP_Read(sd, &addr, message, BUFFER_SIZE);     // addr 里记下是谁发来的
        if (rc > 0) {
            char reply[BUFFER_SIZE];
            sprintf(reply, "goodbye world");
            rc = UDP_Write(sd, &addr, reply, BUFFER_SIZE);       // 按原地址回复
        }
    }
    return 0;
}

它们依赖的小库（Figure 48.2）只是对套接字系统调用的薄封装：

int UDP_Open(int port) {
    int sd;
    if ((sd = socket(AF_INET, SOCK_DGRAM, 0)) == -1)   // SOCK_DGRAM：数据报 = UDP
        return -1;
    struct sockaddr_in myaddr;
    bzero(&myaddr, sizeof(myaddr));
    myaddr.sin_family      = AF_INET;
    myaddr.sin_port        = htons(port);              // 端口转成网络字节序
    myaddr.sin_addr.s_addr = INADDR_ANY;
    if (bind(sd, (struct sockaddr *) &myaddr, sizeof(myaddr)) == -1) {
        close(sd);
        return -1;
    }
    return sd;
}
int UDP_FillSockAddr(struct sockaddr_in *addr, char *hostname, int port) {
    bzero(addr, sizeof(struct sockaddr_in));
    addr->sin_family = AF_INET;          // host byte order
    addr->sin_port   = htons(port);      // network byte order
    struct hostent *host_entry;
    if ((host_entry = gethostbyname(hostname)) == NULL)   // 命名：主机名 → IP
        return -1;
    addr->sin_addr = *(struct in_addr *) host_entry->h_addr;
    return 0;
}
int UDP_Write(int sd, struct sockaddr_in *addr, char *buffer, int n) {
    return sendto(sd, buffer, n, 0, (struct sockaddr *) addr, sizeof(struct sockaddr_in));
}
int UDP_Read(int sd, struct sockaddr_in *addr, char *buffer, int n) {
    int len = sizeof(struct sockaddr_in);
    return recvfrom(sd, buffer, n, 0, (struct sockaddr *) addr, (socklen_t *) &len);
}

• socket(AF_INET, SOCK_DGRAM, 0)：创建 IPv4 的数据报套接字；bind 把它绑到一个端口上，别人才能按"IP + 端口"找到它。
• htons：把端口号从主机字节序转换为网络字节序（大端）。字节序问题在后面的 RPC 一节还会遇到。
• sendto 返回成功只代表"交给了本机网络栈"，不代表对方收到了。
• 客户端的 UDP_Read 会一直阻塞：如果请求或回复在路上丢了，客户端就永远等下去。

UDP 是不可靠通信层的典型：包会丢，发送方也不会被告知。但它也不是什么都不管——UDP 包含一个校验和，用来检测某些形式的包损坏。然而很多应用只想"把数据发过去"而不操心丢包，所以我们需要更多：在不可靠的网络之上构建可靠的通信。

可靠通信层：确认、超时/重传、序列号

设想客户端通过不可靠的连接给服务器发消息。第一个问题：发送方怎么知道接收方真的收到了？办法叫确认（acknowledgment，简称 ack）：接收方收到后回一条短消息。发送方收到 ack，就能放心对方收到了原始消息。

那没收到 ack 怎么办？再加一个机制：超时（timeout）。发送方发消息时设一个定时器；如果到期时还没收到 ack，就断定消息丢了，于是重试（retry）——再发一次同样的消息。为此发送方必须保留消息的副本。这套组合被称为超时/重传（timeout/retry）。

可惜仅有超时/重传还不够。看右边的情况：丢的不是消息而是 ack。在发送方看来情形完全一样——没收到 ack，于是超时重传；可在接收方看来，同一条消息收到了两次！有时这无所谓，但一般不行：想象你在下载文件，结果文件中间有些包被重复写了进去。所以可靠消息层通常还要保证每条消息恰好被接收一次（exactly once）。

为了识别重复，发送方要给每条消息一个唯一标识，接收方要能判断是否见过它。看到重复消息时，接收方照样回 ack（否则发送方会一直重传），但关键是不把它交给应用。

一种办法是每条消息带全局唯一 ID，接收方记住见过的所有 ID——但这需要无限的内存。更省的办法是序列计数器（sequence counter）：

最常用的可靠通信层是 TCP/IP（简称 TCP）。它比上面描述的复杂得多：有应对网络拥塞的机制、允许多个未完成的请求同时在途，以及上百个其他改进。下面的模拟器实现的是最简单的"停止-等待"版本：一次只有一条消息在途。

通信抽象（一）：分布式共享内存为什么不行

有了基本的消息层，下一个问题是：构建分布式系统时，应该给程序员什么样的通信抽象？

一派研究把操作系统的抽象扩展到分布式环境。例如分布式共享内存（distributed shared memory，DSM）让不同机器上的进程共享一个巨大的虚拟地址空间，分布式计算就变得像一个多线程程序，只不过线程跑在不同的机器上。它通常借助操作系统的虚拟内存实现：

访问一页时有两种情况：最好的情况，页面就在本机，很快；否则就触发缺页，缺页处理程序向另一台机器发消息取回该页，装进请求进程的页表，然后继续执行。

这种方法今天没什么人用，原因有二。最大的问题是故障处理：某台机器坏了，它上面的页怎么办？如果分布式计算的数据结构散布在整个地址空间里，部分数据结构会突然不可用——想象一个链表，某个 next 指针指向了已经消失的那部分地址空间。其次是性能：写代码时我们通常假设访存很便宜，而在 DSM 中有些访问很便宜、有些却要缺页并从远程取回。程序员不得不非常小心地组织计算，让几乎不发生通信——这就违背了这种抽象的初衷。尽管相关研究很多，实际影响很小：今天没人用 DSM 构建可靠的分布式系统。

通信抽象（二）：远程过程调用（RPC）

操作系统的抽象不适合构建分布式系统，而编程语言（PL）的抽象更合理。最主流的是远程过程调用（remote procedure call，RPC）。它的目标很简单：让在远程机器上执行代码像调用本地函数一样简单直接。客户端发起一次过程调用，一段时间后得到结果；服务器只需定义好要导出的例程，其余"魔法"都由 RPC 系统处理。RPC 系统一般有两部分：存根生成器（stub generator，也叫协议编译器 protocol compiler）和运行时库（run-time library）。

存根生成器

存根生成器的工作是把"把函数参数和结果打包成消息"这件痛苦的事自动化。好处有很多：从设计上避免手写这类代码时的低级错误；编译器还可能优化这些代码、提升性能。它的输入就是服务器想导出的一组调用，概念上可以简单到这样：

interface {
    int func1(int arg1);
    int func2(int arg1, int arg2);
};

生成器据此为客户端生成客户端存根（client stub），其中包含接口中的每个函数；客户端程序链接这个存根并调用它来发起 RPC。在客户端看来就是调用了 func1(x)，而存根里的 func1() 内部会：

1. 创建消息缓冲区——通常就是一段连续的字节数组。
2. 把所需信息打包进缓冲区：要调用的函数的标识符，以及函数需要的全部参数（例如 func1 的一个整数）。把这些信息放进一个连续缓冲区的过程叫参数封送（marshaling）或消息序列化（serialization）。
3. 把消息发给目标 RPC 服务器：通信细节由运行时库处理。
4. 等待回复：函数调用通常是同步的，所以要等它完成。
5. 解包返回码和其他结果：即解封（unmarshaling）或反序列化；复杂的函数可能返回列表等复杂结果。
6. 返回给调用者。

服务器端也会生成代码：解封消息（取出函数标识符和参数）→ 调用真正的函数（终于！）→ 打包结果到回复缓冲区 → 发送回复。

存根编译器还要考虑几个重要问题：

• 复杂参数：比如 write(fd, buf, size) 传的是一个指针。RPC 包拿到指针必须知道该如何解释、该发送哪些字节——通常靠众所周知的类型（例如 RPC 编译器认识的 buffer_t，按给定大小传递一块数据），或给数据结构加注解，让编译器知道要序列化哪些字节。指针本身的值（地址）传到另一台机器上毫无意义。
• 服务器的并发组织：最简单的服务器在一个循环里逐个处理请求，但一个 RPC 阻塞（比如等 I/O）时服务器资源就被浪费了。常见的组织方式是线程池（thread pool）：启动时创建有限个工作线程，主线程收到消息就分派给某个工作线程，自己继续接收其他请求。这提高了利用率，代价是编程复杂度——RPC 处理函数可能要用锁等同步原语（回想第 26–31 章）。

运行时库

运行时库承担了 RPC 系统的大部分重活，大多数性能和可靠性问题都在这里处理。

命名（naming）：客户端怎么找到远程服务？最简单的做法建立在现有命名系统之上，例如互联网协议提供的主机名和端口号：客户端必须知道运行 RPC 服务的机器的主机名或 IP 地址，以及服务使用的端口号（端口号用来区分一台机器上同时进行的多个通信活动）。协议栈负责把包从任意机器路由到这个地址。

传输协议选哪个：直觉上应该用可靠的 TCP——请求要可靠送达，回复也要可靠收到。然而在可靠层之上构建 RPC 会导致严重的性能浪费：

可靠层靠 ack + 超时/重传工作：客户端发出 RPC 请求，服务器回一个 ack 让调用方知道请求已收到；服务器发回复时，客户端也要 ack。于是一个请求/响应协议就多发了两条"额外"消息。因此许多 RPC 包建在不可靠的 UDP 之上，这让 RPC 层更高效，但可靠性的责任就落到了 RPC 系统自己身上：它像前面描述的那样使用超时/重传和确认；再借助某种形式的序列号，通信层可以保证每个 RPC 恰好执行一次（exactly once，没有故障时），或者至多执行一次（at most once，出现故障时）。

其他问题：

• 长时间运行的调用：按超时机制，一个执行很久的远程调用在客户端看来像是失败了，会触发重试。解决办法之一是：回复不能立即产生时，服务器先发一个显式的 ack，让客户端知道请求已收到；之后客户端可以定期询问服务器是否还在处理，只要服务器一直说"是"，客户端就继续等。
• 大参数：参数大到一个包放不下时，需要发送方分片（fragmentation）、接收方重组（reassembly）。有些底层协议提供这个功能；没有的话，RPC 运行时就要自己实现。
• 字节序（byte ordering）：有的机器是大端（big endian，从最高有效字节到最低有效字节存储，像我们写阿拉伯数字的顺序），有的是小端（little endian）。RPC 包通常在消息格式中规定一种明确的字节序，例如 Sun RPC 的 XDR（eXternal Data Representation）层。收发双方的字节序与 XDR 相同时直接收发；否则每项数据都要转换，带来少量性能开销。
• 是否暴露异步：典型 RPC 是同步的——调用后必须等它返回。有些 RPC 包支持异步 RPC：发出请求后立即返回，客户端可以去做别的事（包括发其他 RPC），之后再调用 RPC 层等待未完成的调用结束，取回返回值。

模拟器中服务器的实现（示例）：int func1(int arg1) { return arg1 * arg1; }、int func2(int arg1, int arg2) { return arg1 + arg2; }。消息格式（示意，类似 Sun RPC）：请求 = [xid][过程编号][参数…]，回复 = [xid][状态][返回值]，每项 4 字节、大端。

端到端论证

本章多次提到一个设计原则：端到端论证（end-to-end argument）。它认为，系统中最高的一层——通常是位于"端点"的应用——才是分层系统中某些功能唯一能真正实现的地方。Saltzer 等人在其经典论文中用"两台机器之间可靠地传输文件"作为例子：

如果只在底层加可靠性——比如用可靠的通信协议来实现可靠的文件传输——并不能构成真正可靠的文件传输：字节可能在通信开始之前就在发送方内存中损坏，或者接收方写盘时出了问题。字节虽然在网络上可靠送达，文件传输最终仍不可靠。要实现可靠的文件传输，必须加入端到端的检查，例如传输完成后读回接收方磁盘上的文件、计算校验和，与发送方文件的校验和比较。

推论是：在底层提供额外功能有时确实能提升性能、优化系统，所以不必一概排斥底层机制，而应结合它在整个系统中的最终用途，仔细权衡它的价值。TCP 的存在就是这种权衡的结果：它不能替代端到端检查，但让大部分应用少操心。

先预测再验证

动手实验

cd labs/48-distributed && make && make run

./server 1 & sleep 0.3; ./client localhost; wait
server: listening on UDP port 10000
client: sending "hello world" to localhost:10000
server: got "hello world" (1000 bytes) from 127.0.0.1:20000
server: replied (1000 bytes)
client: got reply "goodbye world" (1000 bytes) from 127.0.0.1:10000

./reliable -p 0.3 -m 5 -s 1        # 带序列号
./reliable -p 0.3 -m 5 -s 1 -n     # 不带序列号

loss=0.30 timeout=100ms msgs=5 seed=1 seq=on
    0.48 ms  sender:   send msg #1 (seq=1, try 1)
    0.84 ms  receiver: got seq=1 -> deliver, balance=100
    0.94 ms  receiver: send ACK seq=1
    0.95 ms  sender:   got ACK seq=1 -> msg #1 done, delete copy, timer off
    0.97 ms  sender:   send msg #2 (seq=2, try 1)
    0.98 ms  receiver: got seq=2 -> deliver, balance=200
    0.98 ms  receiver: send ACK seq=2  ... LOST in network
  101.10 ms  sender:   TIMEOUT for msg #2 -> retry
  101.16 ms  sender:   send msg #2 (seq=2, try 2)
  101.19 ms  receiver: got seq=2 but expected=3 -> DUPLICATE, discard (still ack)
  101.19 ms  receiver: send ACK seq=2  ... LOST in network
  200.28 ms  sender:   TIMEOUT for msg #2 -> retry
  200.34 ms  sender:   send msg #2 (seq=2, try 3)
  200.36 ms  receiver: got seq=2 but expected=3 -> DUPLICATE, discard (still ack)
  200.39 ms  receiver: send ACK seq=2
  200.39 ms  sender:   got ACK seq=2 -> msg #2 done, delete copy, timer off
  200.40 ms  sender:   send msg #3 (seq=3, try 1)  ... LOST in network
  300.52 ms  sender:   TIMEOUT for msg #3 -> retry
  ...（省略 msg #3~#5）
---- sender summary: 5 messages, 9 transmissions (4 retries), seq numbers ON
---- receiver summary: delivered=5, duplicates discarded=2, acks sent=7
---- final balance = 500 (expected 500) OK

---- sender summary: 5 messages, 9 transmissions (4 retries), seq numbers OFF
---- receiver summary: delivered=7, duplicates discarded=0, acks sent=7
---- final balance = 700 (expected 500) <-- WRONG! duplicate executed

自测题

常见误区与小结