分布式系统

1 引言

分布式系统改变了世界的面貌。当您的网络浏览器连接到地球上其他地方的网络服务器时，它正在参与看似简单形式的客户端/服务器（CS）分布式系统。然而，当您联系 Google 或 Facebook 等现代网络服务时，您不仅仅是在与一台机器进行交互。在幕后，这些复杂的服务是由大量（即数千台）机器构建的，每台机器相互协作以提供站点的特定服务。

构建分布式系统时会出现许多新的挑战。我们主要关注的是失败；机器、磁盘、网络和软件都会时不时地出现故障，因为我们不（并且可能永远不会）知道如何构建“完美”的组件和系统。然而，当我们构建现代 Web 服务时，我们希望它对客户来说似乎永远不会失败；我们怎样才能完成这个任务呢？

关键：如何构建在组件出现故障时仍能正常工作的系统？

有趣的是，虽然失败是构建分布式系统的主要挑战，但它也代表着机遇。是的，机器会出故障；但一台机器发生故障并不意味着整个系统一定会发生故障。通过将一组机器集合在一起，我们可以构建一个似乎很少发生故障的系统，尽管它的组件经常发生故障。这一事实是分布式系统的核心魅力和价值，也是为什么它们成为您使用的几乎所有现代网络服务（包括 Google、Facebook 等）的基础。

TIP：通信本质上是不可靠的

在几乎所有情况下，最好将通信视为一种本质上不可靠的活动。bit损坏、链路和机器瘫痪或无法工作，以及传入数据包缺乏缓冲空间，都会导致同样的结果：数据包有时无法到达目的地。要在这种不可靠的网络之上建立可靠的服务，我们必须考虑能够应对数据包丢失的技术。

还存在其他重要问题。系统性能往往至关重要；由于网络将我们的分布式系统连接在一起，系统设计者往往必须仔细考虑如何完成既定任务，尽量减少发送信息的数量，并进一步提高通信效率（低延迟、高带宽）。

最后，安全也是一个必要的考虑因素。确保远程方的真实身份成为一个核心问题。此外，确保第三方无法监视或改变两个人之间正在进行的通信也是一个挑战。

在本介绍中，我们将讨论分布式系统中最基本的新问题：通信。也就是说，分布式系统中的机器应该如何相互通信？？我们将从最基本的可用原语（消息）开始，并在它们之上构建一些更高级别的原语。正如我们上面所说，故障将成为焦点：通信层应如何处理故障？

2 通信基础

现代网络的核心原则是通信从根本上来说是不可靠的。无论是在广域互联网中，还是在 Infiniband 等局域高速网络中，数据包经常会丢失、损坏或无法到达目的地。

造成数据包丢失或损坏的原因有很多。有时，在传输过程中，某些位会由于电气或其他类似问题而翻转。有时，系统中的某个元件（例如网络链路或数据包路由器甚至远程主机）会因某种原因损坏或无法正常工作；网络电缆确实会被意外切断，至少有时是这样。

然而，更根本的是由于网络交换机、路由器或端点内缺乏缓冲而导致的数据包丢失。具体来说，即使我们可以保证所有链路正常工作，并且系统中的所有组件（交换机、路由器、终端主机）都按预期启动并运行，但由于以下原因，仍然有可能发生丢失。

想象一下一个数据包到达路由器；要处理数据包，必须将其放置在路由器内存中的某个位置。如果许多此类数据包同时到达，则路由器内的内存可能无法容纳所有数据包。此时路由器唯一的选择是丢弃一个或多个数据包。同样的行为也发生在终端主机上；当你向一台机器发送大量消息时，机器的资源很容易被淹没，从而再次出现丢包。

因此，数据包丢失是网络中的基础。那么问题就变成了：我们该如何应对？

3 不可靠通信层

一种简单的方法是：我们不去处理它。因为某些应用程序知道如何处理数据包丢失，所以有时让它们与基本的不可靠消息传递层进行通信是有用的，这是人们经常听到的端到端论点的一个例子。UDP/IP 网络协议栈就是这种不可靠层的一个很好的例子，目前几乎所有的现代系统都有这种协议栈。使用 UDP 时，进程使用socket API 创建通信端点；其他机器（或同一机器）上的进程向原始进程发送 UDP 数据报（数据报是固定大小的报文，最大不超过某个最大值）。

端到端论点

端到端论点认为，系统的最高层，即通常位于 “端 “的应用程序，最终是分层系统中唯一能真正实现某些功能的地方。在具有里程碑意义的论文中，Saltzer 等人通过一个极好的例子论证了这一点：两台机器之间的可靠文件传输。

如果要将文件从机器 A 传输到机器 B，并确保最终到达机器 B 的字节与开始到达机器 A 的字节完全相同，就必须进行 “端到端 “检查；而网络或磁盘等较低级别的可靠机制则无法提供这种保证。

与此形成鲜明对比的是一种试图通过在系统较低层增加可靠性来解决可靠文件传输问题的方法。例如，我们建立了一个可靠的通信协议，并用它来建立可靠的文件传输。该通信协议保证发送方发送的每个字节都能被接收方按顺序接收，例如使用超时/重试、确认和序列号。不幸的是，使用这样的协议并不能实现可靠的文件传输；试想一下，在通信开始之前，发送方内存中的字节就已经损坏，或者接收方将数据写入磁盘时发生了什么不好的事情。在这种情况下，即使字节在网络上可靠地传输，我们的文件传输最终也是不可靠的。要建立可靠的文件传输，必须包括端到端的可靠性检查，例如，在整个传输完成后，读回接收方磁盘上的文件，计算校验和，并将校验和与发送方的文件进行比较。

这句格言的推论是，有时让下层提供额外功能确实可以提高系统性能或优化系统。因此，你不应该排除在系统中的较低层次使用这种机制；相反，你应该仔细考虑这种机制的效用，考虑到它在整个系统或应用程序中的最终用途。

下面这两段代码显示了构建在 UDP/IP 之上的简单客户端和服务器。客户端可以向服务器发送消息，然后服务器做出响应。通过这么少量的代码，您就拥有了开始构建分布式系统所需的一切！

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

// client.c
#include <stdio.h>
#include "udp.h"

#define BUFFER_SIZE 1024

int main() {
    struct sockaddr_in addrSend, addrRecv;

    int fd = UDP_Open(CLIENT_PORT);
    int rc = UDP_FillSockAddr(&addrSend, "localhost", SERVER_PORT);

    char message[BUFFER_SIZE];
    sprintf(message, "hello world");

    printf("client:: sending message [%s]\n", message);
    rc = UDP_Write(fd, &addrSend, message, BUFFER_SIZE);
    if (rc < 0) {
        fprintf(stderr, "Client:: Failed to send message\n");
        return -1;
    }

    printf("client:: waiting for reply...\n");
    rc = UDP_Read(fd, &addrRecv, message, BUFFER_SIZE);
    if (rc < 0) {
        fprintf(stderr, "Client:: Failed to read message\n");
        return -1;
    }
    printf("client:: read %d bytes (message: %s)\n", rc, message);
    
    return 0;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

//server.c
#include <stdio.h>

#include "udp.h"

#define BUFFER_SIZE 1024

int main(int argc, char **argv) {
    int fd = UDP_Open(SERVER_PORT);
    if (fd < 0) {
        fprintf(stderr, "Failed to create socket\n");
        return -1;
    }

    while (1) {
        struct sockaddr_in addr;
        char buffer[BUFFER_SIZE];
        printf("server:: waiting for data...\n");
        int rc = UDP_Read(fd, &addr, buffer, 1024);
        printf("server:: read %d bytes (message: %s)\n", rc, buffer);
        if (rc > 0) {
            char reply[BUFFER_SIZE];
            sprintf(reply, "goodbye world");
            rc = UDP_Write(fd, &addr, reply, BUFFER_SIZE);
	        printf("server:: reply\n");
        }
    }

    return 0;
}

UDP 是不可靠通信层的一个很好的例子。而发送方从不会因此被告知数据包丢失。但是，这并不意味着 UDP 完全不防范任何故障。例如，UDP 包含一个校验和来检测某些形式的数据包损坏。

然而，由于许多应用程序只是想将数据发送到目的地而不担心数据包丢失，因此我们需要更多。具体来说，我们需要在不可靠的网络上进行可靠的通信。

4 可靠的通信层

为了构建可靠的通信层，我们需要一些新的机制和技术来处理丢包。让我们考虑一个简单的示例，其中客户端通过不可靠的连接向服务器发送消息。我们必须回答的第一个问题：发送者如何知道接收者确实收到了消息？

我们将使用的技术称为确认，简称 ack。想法很简单：发送者向接收者发送消息；然后接收者发回一条短消息以确认其收到。下图描述了该过程。

当发送方收到消息的确认时，它就可以放心，接收方确实收到了原始消息。但是，如果发送方没有收到确认，该怎么办？

为了处理这种情况，我们需要一个额外的机制，称为超时。当发送者发送消息时，发送者现在设置一个计时器在一段时间后关闭。如果此时未收到确认，则发送方断定消息已丢失。然后，发送者只需重试发送，再次发送相同的消息，希望这次能够成功。为了使这种方法发挥作用，发送者必须保留消息的副本，以备需要再次发送时使用。超时和重试的结合导致一些人将这种方法称为超时/重试，下图显示了一个示例。

不幸的是，这种形式的超时/重试还不够。下图显示了可能导致问题的数据包丢失示例。

在此示例中，丢失的不是原始消息，而是确认消息。从发送方的角度来看，情况似乎是一样的：没有收到确认，因此需要超时和重试。但从接收者的角度来看，情况就大不一样了：现在同一条消息已经收到两次了！虽然在某些情况下这可能是可以的，但一般来说是不行的；想象一下当您下载文件并且在下载过程中重复额外的数据包时会发生什么。因此，当我们的目标是建立一个可靠的消息层时，我们通常还希望保证接收者只接收每条消息一次。

为了使接收方能够检测到重复的消息传输，发送方必须以某种独特的方式识别每条消息，并且接收方需要某种方式来跟踪它之前是否已经看过每条消息。当接收方看到重复传输时，它只是确认消息，但（关键）不会将消息传递给接收数据的应用程序。因此，发送方收到 ack，但消息不会被接收两次，从而保留了上述的恰好一次语义。有多种方法可以检测重复消息。例如，发送者可以为每条消息生成一个唯一的ID；接收者可以追踪它所见过的每一个ID。这种方法可行，但成本高昂，需要无限的内存来跟踪所有 ID。

有一种更简单的方法可以解决这个问题，只需要很少的内存，这种机制被称为序列计数器。使用序列计数器时，发送方和接收方商定一个计数器的起始值（如 $1$），由双方共同维护。每当发送一条信息时，计数器的当前值就会随信息一起发送；这个计数器值（$N$）就是信息的 ID。信息发送后，发送方会递增计数器值（到 $N + 1$）。

接收方使用其计数器值作为该发送方发来信息的 ID 的预期值。如果接收到的信息 ID（N）与接收者的计数器（也是 N）相匹配，接收者就会接收该信息并将其上传给应用程序；在这种情况下，接收者就会断定这是第一次收到该信息。然后，接收方递增计数器（到 $N + 1$），等待下一条信息。

如果丢失了应答，发送方将超时并重新发送信息 $N$。这一次，接收方的计数器更高（$N + 1$），因此接收方知道自己已经收到了这条信息。因此，它会接收信息，但不会将其上传给应用程序。通过这种简单的方式，序列计数器可用于避免重复。

最常用的可靠通信层被称为 TCP/IP，简称 TCP。TCP 比我们上面描述的要复杂得多，包括处理网络拥塞、多个未处理请求以及数百种其他小调整和优化的机制。

TIP：小心设置超时值

正如您可能从讨论中猜到的那样，正确设置超时值是使用超时重试消息发送的一个重要方面。

• 如果超时太小，发送方将不必要地重新发送消息，从而浪费发送方的CPU时间和网络资源。
• 如果超时太大，则发送方等待太长时间才能重新发送，从而降低发送方的感知性能。

因此，从单个客户端和服务器的角度来看，“正确”值是等待足够长的时间来检测数据包丢失，但不再等待。

然而，正如我们将在以后的章节中看到的那样，分布式系统中通常不仅仅只有一个客户端和服务器。在许多客户端向单个服务器发送数据的情况下，服务器上的数据包丢失可能表明服务器过载。如果为真，客户端可能会以不同的自适应方式重试；例如，在第一次超时后，客户端可能会将其超时值增加到更高的值，可能是原始值的两倍。这种指数退避方案在早期的 Aloha 网络中首创并在早期以太网中采用，避免了因过度重发而导致资源过载的情况。稳健的系统努力避免这种性质的过载。

5 通信抽象

给定了基本的消息传递层，我们现在讨论本章中的下一个问题：在构建分布式系统时我们应该使用什么通信抽象？

多年来，系统界开发了许多方法。其中一项工作是将操作系统的抽象概念扩展到分布式环境中运行。例如，分布式共享内存（DSM）系统能让不同机器上的进程共享一个大型虚拟地址空间。这种抽象将分布式计算变成了类似于多线程应用程序的东西；唯一的区别是，这些线程运行在不同的机器上，而不是同一机器上的不同处理器上。

大多数 DSM 系统的工作方式是通过操作系统的虚拟内存系统。在一台机器上访问一个页面时，可能会发生两种情况。

• 在第一种（最佳）情况下，页面已经在本地计算机上，因此可以快速获取数据。
• 第二种情况是，页面当前在其他机器上。页面故障发生后，页面故障处理程序会向其他机器发送信息，以获取页面，并将其安装到请求进程的页表中，然后继续执行。

由于多种原因，这种方法目前并未得到广泛应用。DSM 面临的最大问题是如何处理故障。例如，设想一下，如果一台机器发生故障，那么这台机器上的页面会发生什么情况？如果分布式计算的数据结构遍布整个地址空间怎么办？在这种情况下，这些数据结构的一部分将突然不可用。当部分地址空间丢失时，处理故障是非常困难的；想象一下，在一个链表中，“下一个 “指针指向的地址空间部分已经消失。

另一个问题是性能。在编写代码时，我们通常会假设访问内存的成本很低。在 DSM 系统中，有些访问是廉价的，但有些访问却会导致页面故障，并从远程机器上获取昂贵的数据。因此，这种 DSM 系统的程序员必须非常小心地组织计算，使其几乎不发生任何通信，这在很大程度上违背了这种方法的初衷。尽管在这一领域进行了大量研究，但几乎没有产生实际影响；如今，没有人使用 DSM 构建可靠的分布式系统。

6 远程过程调用 (RPC)

操作系统抽象对于构建分布式系统来说是一个糟糕的选择，而编程语言（PL）抽象则更有意义。最主要的抽象基于**远程过程调用（简称 RPC）**的思想。

远程过程调用包都有一个简单的目标：使在远程机器上执行代码的过程像调用本地函数一样简单明了。因此，对客户端来说，只需进行一次过程调用，一段时间后就会返回结果。服务器只需定义一些它希望导出的例程。RPC 系统一般由两部分组成：存根生成器（有时称为协议编译器）和运行时库。下面我们将详细介绍其中的每一部分。

6.1 存根生成器

存根生成器的工作很简单：通过自动化来消除将函数参数和结果打包到消息中的一些痛苦。这样做会带来许多好处：通过设计可以避免手工编写此类代码时出现的简单错误；此外，存根编译器也许可以优化此类代码，从而提高性能。

这种编译器的输入只是服务器希望导出到客户端的一组调用。从概念上讲，它可能像这样简单：

1
2
3
4

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

存根生成器采用这样的接口并生成一些不同的代码片段。

• 对于客户端，生成一个客户端存根，其中包含接口中指定的各个功能；希望使用此 RPC 服务的客户端程序将与此客户端存根链接并调用它以进行 RPC。在内部，客户端存根中的每个函数都执行执行远程过程调用所需的所有工作。对于客户端来说，代码只是显示为函数调用（例如，客户端调用 func1(x)）；在内部，func1() 的客户端存根中的代码执行以下操作：
  • **创建消息缓冲区。**消息缓冲区通常只是某个大小的连续字节数组。
  • 将所需信息打包到消息缓冲区中。该信息包括要调用的函数的某种标识符，以及函数需要的所有参数（例如，在上面的示例中，func1 是一个整数）。将所有这些信息放入单个连续缓冲区的过程有时称为参数的编组或消息的序列化。
  • **将消息发送到目标RPC 服务器。**与 RPC 服务器的通信以及使其正确运行所需的所有细节均由 RPC 运行时库处理，如下所述。
  • **等待回复。**由于函数调用通常是同步的，因此调用将等待其完成。
  • 解压返回代码和其他参数。如果函数仅返回单个返回码，则此过程很简单；然而，更复杂的函数可能会返回更复杂的结果（例如，列表），因此存根可能也需要解压这些结果。此步骤也称为解组或反序列化。
  • 返回调用者。最后，只需从客户端存根返回到客户端代码即可。
• 对于服务器，也会生成代码。在服务器上采取的步骤如下：
  • 解压消息。此步骤称为解组或反序列化，从传入消息中取出信息，提取函数标识符和参数。
  • 调用实际函数。最后！我们已经到达了实际执行远程函数的阶段。 RPC 运行时调用 ID 指定的函数并传入所需的参数。
  • **将结果打包。**返回参数被打包回单个回复缓冲区。
  • 发送回复。回复最终发送给调用者。

存根编译器还需要考虑其他一些重要问题。

• 首先是复杂参数，即如何打包和发送复杂的数据结构？例如，当调用 write() 系统调用时，需要传递三个参数：一个整数文件描述符、一个指向缓冲区的指针和一个表示要写入多少字节（从指针开始）的大小。如果一个 RPC 程序包传递了一个指针，它就需要知道如何解释该指针，并执行正确的操作。通常，这可以通过两种方式实现：一种是众所周知的类型（例如，用于传递给定大小的数据块的buffer_t，RPC 编译器可以理解），另一种是为数据结构注释更多信息，使编译器知道哪些字节需要序列化。

• 另一个重要问题是服务器的并发组织。简单的服务器只是在一个简单的循环中等待请求，并一次处理一个请求。但是，正如你可能已经猜到的那样，这样做的效率会非常低：如果一个 RPC 调用阻塞（例如，在 I/O 上），服务器资源就会被浪费。

  因此，大多数服务器都是以某种并发方式构建的。一种常见的组织方式是线程池。在这种组织结构中，服务器启动时会创建一组有限的线程；当消息到达时，它会被分派到这些工作线程中的一个，然后工作线程会执行 RPC 调用的工作，并最终回复；在此期间，主线程会不断接收其他请求，并可能将其分派给其他工作线程。这种组织方式可以在服务器内实现并发执行，从而提高服务器的利用率；同时也会产生标准成本，主要是编程复杂度，因为 RPC 调用现在可能需要使用锁和其他同步原语，以确保其正确运行。

6.2 运行时库

运行时库负责处理 RPC 系统中的大部分繁重工作；大部分性能和可靠性问题都由运行时库处理。下面我们将讨论构建这样一个运行时库所面临的一些主要挑战。

我们必须克服的首要挑战之一是如何定位远程服务。这个命名问题是分布式系统中的常见问题，在某种意义上超出了我们当前讨论的范围。最简单的方法是利用现有的命名系统，例如当前互联网协议提供的主机名和端口号。在这种系统中，客户端必须知道运行所需的 RPC 服务的机器的主机名或 IP 地址，以及它正在使用的端口号（端口号只是一种识别机器上正在进行的特定通信活动的方法，允许同时使用多个通信通道）。然后，协议套件必须提供一种机制，将数据包从系统中的任何其他机器路由到特定地址。

一旦客户端知道应该与哪台服务器通信以获取特定的远程服务，下一个问题就是 RPC 应该基于哪种传输级协议。具体来说，RPC 系统应该使用 TCP/IP 这样可靠的协议，还是建立在 UDP/IP 这样不可靠的通信层之上？

天真地认为，选择似乎很容易：显然，我们希望请求能可靠地传送到远程服务器，显然，我们希望能可靠地收到回复。因此，我们应该选择可靠的传输协议，如 TCP，对吗？

不幸的是，在可靠通信层之上构建 RPC 会导致性能严重低下。回想一下上文讨论的可靠通信层的工作原理：确认加超时/重试。因此，当客户端向服务器发送 RPC 请求时，服务器会以确认的方式作出响应，以便调用者知道请求已收到。同样，当服务器发送回复给客户端时，客户端也会发出确认响应，以便服务器知道它已收到。在可靠的通信层之上建立请求/响应协议（如 RPC），需要发送两条 “额外 “信息。

因此，许多 RPC 程序包都建立在不可靠的通信层（如 UDP）之上。这样做可以提高 RPC 层的效率，但却增加了为 RPC 系统提供可靠性的责任。RPC 层通过使用超时/重试和确认来达到所需的责任水平，这一点与我们上面所描述的非常相似。通过使用某种形式的序列号，通信层可以保证每个 RPC 恰好发生一次（在无故障的情况下），或最多发生一次（在出现故障的情况下）。

6.3 其他问题

RPC 运行时还必须处理一些其他问题。例如，当远程调用需要很长时间才能完成时会发生什么？考虑到我们的超时机制，长时间运行的远程调用可能会对客户端显示为失败，从而触发重试，因此这里需要注意。一种解决方案是在未立即生成回复时使用显式确认（从接收方到发送方）；这让客户端知道服务器收到了请求。然后，经过一段时间后，客户端可以定期询问服务器是否仍在处理该请求；如果服务器一直说“是”，客户端应该很高兴并继续等待（毕竟，有时过程调用可能需要很长时间才能完成执行）。

运行时还必须处理带有大参数的过程调用，这些参数大于单个数据包所能容纳的参数。一些较低级别的网络协议提供此类发送方分段（将较大的数据包分解为一组较小的数据包）和接收方重组（将较小的部分分解为一个较大的逻辑整体）；如果没有，RPC 运行时可能必须自己实现此类功能。

许多系统处理的一个问题是字节排序问题。您可能知道，某些机器以所谓的大端顺序存储值，而其他机器则使用小端顺序。大端存储从最高有效位到最低有效位的字节（例如，整数），很像阿拉伯数字；小端则相反。两者都是存储数字信息的同等有效的方式；这里的问题是如何在不同字节序的机器之间进行通信。

RPC 包通常通过在其消息格式中提供明确定义的字节顺序来处理此问题。在Sun的RPC包中，XDR（外部数据表示）层提供了此功能。如果发送或接收消息的机器与 XDR 的字节顺序匹配，则消息将按预期发送和接收。但是，如果通信的机器具有不同的字节顺序，则必须转换消息中的每条信息。因此，字节顺序的差异可能会带来很小的性能成本。

最后一个问题是是否向客户端公开通信的异步特性，从而实现一些性能优化。具体来说，典型的 RPC 是同步进行的，即当客户端发出过程调用时，它必须等待过程调用返回才能继续。由于等待时间可能很长，并且客户端可能还有其他工作要做，因此某些 RPC 包允许您异步调用 RPC。当发出异步RPC时，RPC包发送请求并立即返回；然后客户端可以自由地执行其他工作，例如调用其他 RPC 或其他有用的计算。客户端有时会希望看到异步 RPC 的结果；因此，它回调 RPC 层，告诉它等待未完成的 RPC 完成，此时可以访问返回参数。