# The Trouble with Distributed Systems

## 简介

本节，我们将用最悲观的角度来看待分布式系统：“任何你觉得可能出问题的地方肯定会出问题”。这些问题具体包括但不限于：

* 通过网络发送的请求数据，可能丢失或者延迟任意长度的时间；类似地，响应数据也可能丢失或延迟。因此当你没有获得响应时，你完全不知道那条消息经历了什么
* 一个节点的时钟可能与其它节点不同步，它的绝对值可能在基准时间的上下波动，因此在依赖于节点的绝对时间前，需要先准确的衡量本地时钟的波动区间
* 一个进程 A 可能在执行过程中的任意时间点暂停一段时间，这段时间可长可短，可能造成别的进程误解 A 已死，等 A 恢复后，才发现 A 其实只是暂停

从故障的角度上看，分布式系统的特征之一就是 partial failures：当系统中的节点尝试与其它节点交互时，可能出现变慢、无响应甚至宕机。由于 partial failures 的存在，分布式系统的设计往往需要能够在某些组件故障时仍然能够正常运作，即 fault tolerance。

要想容错，第一步就是检测，但检测同样很困难。大部分分布式系统没有精确的故障检测机制，因此它们大多依赖于超时时长来判断节点是否故障。然而，超时可能只是网络问题，节点并未发生故障，显然这时候的判断是错误的。

一旦检测到故障，让系统能在故障下正常运作也很困难，原因在于不同节点之间没有任何共享的内容，没有全局变量、共享内存、没有任何可分享的状态。节点之间连 “现在是什么时间” 这样的问题都无法达成共识。节点之间唯一的交流途径就是通过不可靠的网络来传输数据，因此节点不能独自做决定，它们必须通过某种协议来保证共识的达成。

本节我们将深入地介绍分布式系统所面对的问题；下一节则介解决这些问题的方案。

## Faults and Partial Failures

当你写的代码只在一台计算机上运行时，它的行为通常是可预测的。要么有问题 (faults)，要么没问题，每次运行的结果是确定的，不会出现模棱两可的情况；当你写的代码需要在多台通过网络相连的计算机上运行时，场景和面临的问题就大相庭径。在分布式系统中，我们以往对软件故障的假设不再成立，系统运行的某一个小部分可能出现意料之外的故障，而其它部分则工作正常，这就是所谓的 partial failures，你不仅无法知道一个请求是否发送成功，你甚至无法知道一个请求已经处理成功。

#### Cloud Computing and Supercomputing

当系统处理的信息量增大时，我们需要扩展系统。通常扩展系统有两种思路：

* 纵向扩展/HPC/Supercomputing：即在单台机器上扩展硬件，更多、更高性能的内存、CPU 等
* 横向扩展/Cloud Computing：即通过 Internet 将许多普通性能的机器连接，提供弹性计算能力。

这两种思路在面对故障时，需要考虑的问题截然不同。在 Supercomputer 中，通常在执行的过程中会定时地将系统当前时间快照 (snapshots/checkpoints) 持久化，如果遇到故障，就修复故障，重启任务，从最后一次快照继执行，因此 Supercomputer 更像是单个计算节点，而不是分布式系统。不论遇到什么故障，它的思路都是先停下手头的工作，修复问题后再继续执行。Supercomputing 不在本课的讨论范围内，本课更关注的是 Cloud Computing 的思路，它与前者很不相同：

* 许多部署在 Cloud Computing 中的应用都是在线应用，它们需要在任何时刻都能在低延迟的前提下响应用户请求。在遇到故障时将机器停止修复对于这类应用来说不能接受。
* Cloud Computing 中使用的硬件都是消费级别硬件，相比 Supercomputer 使用的昂贵的商用级别硬件来说，能以更低的成本提供接近相似的性能，但同时带来的是更高的节点故障率。
* Cloud Computing 通过 IP 和以太网将节点相连；Supercomputer 则通常使用为 HPC 工作负载专门设计的网络拓扑结构和协议。
* Cloud Computing 中，系统越大，遇到故障的几率越大，在一个拥有上千节点的系统中，可以认为 “something is always broken”。如果在这种情况下使用 Supercomputer 的思路来解决问题，那么 Cloud Computing 将无法正常工作。
* Cloud Computing 的设计通常充分地考虑容错技术，它可以让系统在部分节点故障的情况下保持正常运行。比如在升级系统时，你可以一台一台机器做 (rolling upgrade)；如果有一台机器工作异常，你可以直接杀掉它再起一台新的。
* Cloud Computing 中，系统可以多地多中心部署，不同数据中心之间需要通过比局域网更不可靠、更慢的网络连接；Supercomputer 则通常认为自己的节点都是紧密连接的，网络的速度和安全都有保障。

如果我们想要让分布式系统正常运行，我们必须接受 partial failure 并以此为假设建立有效的容错 (fault-tolerance) 机制。尽管在分布式环境下没有完美的可靠性，我们仍然需要尽量做到最好。

*Building a Reliable System from Unreliable Components*

实际上在网络原理中，我们已经见识了如何 “在不可靠的组件上建立可靠的系统”：

* 在物理层、链接层以及其它层，都有自纠正的逻辑，能够容忍传输过程中出现少量 bits 错误的问题
* 网络层 (IP) 是不可靠的，它可能出现各种各样的问题，如丢包、延迟、重复、乱序等。TCP 在 IP 之上，提供了可靠的传输层，它通过重发、去重、重排序等方式，使得网络层的问对上层不可见

然而，尽管我们可以 “在不可靠的组件上建立可靠的系统”，但这种可靠系统的可靠程度是有限的。比如：自纠正逻辑只能解决少量的单 bit 错误，如果信号直接被切断，则自纠正无能为力；又比如 TCP 尽管可以帮你解决丢包、重复、乱序，单网络延迟永远无法解决。即便这些可靠的系统并不完美，但它仍然在解决一些恶心的低级错误方面很有效，同时使得剩下的错误更容易被发现和辨认。

## Unreliable Networks

公网和局域网都是 asynchronous package network，在这样的网络中，一个节点可以任意发送消息给另外一个节点，但网络本身不提供任何保证，数据是否能到达？何时能到达？都不确定。在你发送请求然后等待响应的过程中，许多问题可能出现：

* 请求可能丢失
* 请求可能在排队，等待调度
* 请求的目标节点可能故障
* 请求的目标节点可能暂时停止响应 (GC)
* 请求的目标节点可能已经处理请求，但响应丢失
* 请求的目标节点可能已经处理请求，但响应延误

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-LiB8YDekduLCrcqOVfG%2F-LiBIfhee2m8xwBUFZ_N%2FScreen%20Shot%202019-06-25%20at%209.44.46%20AM.jpg?alt=media\&token=e7071313-185a-4b4f-8a08-a6ced425a367)

如上图所示，当你发送一个请求未得到响应，你甚至无法确认是哪个环节出了问题，请求、处理请求、响应阶段都有可能。

通常的做法是使用超时 (timeout) 机制，经过一段预设的时间你仍然未收到响应，就认为请求失败。即便如此，这种判断很有可能出错，响应可能仍然在来的路上。

### Network Faults in Practice

许多系统性的调研表明，网络问题非常常见，即使在可控性极强的环境中，如公司内部的独占的数据中心，也是如此。一项调研发现，在中等规模的数据中心里，每个月可能出现 12 次网络故障，其中 6 次是一个节点失联，剩下 6 次是整个机架上的节点都失联。公有云服务如 EC2，则常常出现短暂的网络故障。诸如以上列举的情况极其常见。

如果网络故障的应对措施没有被认真设计和测试，那么任何坏事都有可能发生。如集群死锁、数据丢失等。因此在分布式系统上线前，你甚至需要通过故意触发一些网络问题来测试系统的故障容忍机制。尽管本课要介绍的是故障容忍方面的技术，但面对网络故障，容忍不是唯一的解决方案。如果你的环境非常可靠，那么你也可以直接通过保障维修来解决网络故障问题。

### Detecting Faults

生产环境中，许多系统需要自动检测故障节点，如：

* 负载均衡器需要通过检测节点故障来决定是否转发请求
* 在单领导复制模式下的分布式数据库中，如果 leader 故障，需要有一个 follower 被选举为 leader

不幸的是，网络的不确定性使得检测故障变得困难。

### Timeouts and Unbounded Delays

如果 timeout 是唯一检测故障的工具，那么我们应当设置多长时间的 timeout？不幸的是，这也没有简单的答案，因为实际请求可能出现无限期的延迟，可设置的范围很大。过长的 timeout 意味着需要等待很长时间才能够确认节点已经发生故障；过短的 timeout 尽管可以很快发现故障，但误报的概率也提高了，而且可能造成其他问题，比如节点正在执行操作，但由于各种原因超过了 timeout，就会导致其它节点重复执行该操作，从而使得相同的操作被执行两次。当一个节点被认为故障时，它的负载会被分摊到其它节点上，若此时整个系统已经处于高负载运转状态，那么分摊可能带来使得情况变得更糟糕。

### Network Congestion and Queueing

开车从 A 市到 B 市，所用时长的不确定性通常源自于交通拥堵。类似地，数据包在网络中传输延迟的不确定性也来自于拥堵导致的排队：

* 如果多个节点同时尝试向同一个目标节点发送数据，网络交换机处理不过来就会将这些请求在内存中排队，然后一个一个投递给目标节点。如果在交换机中排队的数据过多，可能导致数据包被丢弃

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-LiGIGhj3KQitLZpI279%2F-LiGK9G7PRGnMqod2V7C%2FScreen%20Shot%202019-06-26%20at%209.09.19%20AM.jpg?alt=media\&token=6ab8dde3-33c8-4122-b49d-798929c20579)

* 当数据包到达目标机器时，如果目标机器的所有 CPU 都在忙别的事情，请求数据就会被操作系统放入处理队列，等待 CPU 忙完后来处理。排队的时间由目标机器当时的负载决定，时间可能任意长
* 在虚拟环境中，正在运行中的操作系统可能会被暂停 10ms，让出物理环境的 CPU 时间给其它正在运行的操作系统，在这个过程中，虚拟环境的操作系统无法从网络中消费任何数据，因此发往它的请求会被虚拟机的监控模块放入队列，等待其重新获得 CPU 时间后再来处理
* TCP 使用 flow/congestion control 在限制数据发送方的速率，防止网络连接以及接收节点过载。因此在数据进入网络之前，也可能被放入队列等待。除此了排队之外，TCP 还有超时重发机制，丢失的数据包会被自动重发，虽然这对于应用层无感知，但也可能导致延迟的增加

以上提到的所有因素都会影响每个请求响应的网络延迟。排队导致的延迟在系统处于高负载状态时影响会被放大，而在低负载状态下，这些队列很容易能被消费干净。

在公网或者多租户数据中心中，资源会在众多消费者中共享，如网线、交换机、网卡、CPU 等等。批处理负载如 MapReduce 可以轻易地占有较多网络资源。因为你无法了解、控制其它消费者使用资源的方式，在这种情况下，你只能实验性地选择 timeout 的大小在不同的机器上测量网络延迟，从而来估计一个合理的预期延迟波动范围，选择合理的 timeout；比这种静态配置更理想的方案是持续地根据网络环境的变化来自动调整 timeout，这可以通过 Phi Accrual failure detector 来实现，具体可以了解它在 Akka 和 Cassandra 中的应用。

### Synchronous Versus Asynchronous Networks

在计算机网络环境下，请求的延迟可以任意长，我们称这样的网络为异步网络 (Asynchronous Networks)；在电话网络环境下，声音数据的发送延迟长度有固定上限，我们称这样的网络为同步网络 (Synchronous Networks)。为什么计算机网络不能是一个同步网络，使得分布式系统的设计将变得简单？原因在于计算机网络的负载模式与电话网络的负载模式不同：

* 电话网络传输的是两端的声音数据，这些数据传输所需的带宽固定；计算机网络传输的数据则不确定，可以是邮件、网页、图片，也可以是超大文件，甚至在大部分情况下，TCP 连接是空闲的，没有数据传输发生，占用的带宽为 0。如果使用固定的带宽，会降低带宽资源的利用率。
* 计算机网络传输数据常常呈现为爆发式；而电话网络传输则十分平稳。

## Unreliable Clocks

时钟和时间十分重要，应用在解决许多问题时需要依赖它们，如：

* 检查请求是否超时？
* 服务响应时间的 99% 分位点在哪？
* 在过去的五分钟，服务的平均 qps 是多少？
* 用户在访问网站时在每个地方停留多长时间？
* 这篇博客是什么时候发布的？
* 提醒邮件应该在什么时间发送？
* 什么时候清理 cache？
* 这条日志的时间戳是何时？

前 4 个问题问的是 duration，后 4 个问题问的是 points in time。在分布式系统中，时间是个问题，不同节点都拥有自己的时钟（硬件），但这些时钟并不是完美的时钟，每个节点的时钟都可能比别的节点走得快或者慢一些。在一定程度上，不同的节点可以通过 Network Time Protocol (NTP) 来访问 time servers，使用这些服务器返回的时间信息来调整本节点的时钟，但因为这个过程本身需要通过网络来完成，因此这样的调节精度有限。

### Monotonic Versus Time-of-Day Clocks

现代计算机通常拥有至少两种时钟：**time-of-day clock** 和 **monotonic clock**。尽管都用来测量时间，但二者有区别：

#### Time-of-day Clocks

Time-of-day clock 就是我们通常认识的时间，它根据日历返回 date 和 time。比如：

* Linux: clock\_gettime(CLOCK\_REALTIME)
* Java: System.currentTimeMillis()

time-of-day clock 通常使用 NTP 与 time servers 同步时间，即在语义上机器 A 与机器 B 的 time-of-day clock 的相同时间戳是等价的。然而 time-of-day clocks 可能会出现一些反常的现象：当本地时钟比 NTP servers 的时钟快太多，它可能会被强制重置，这样的结果就可能导致应用先后调用接口获取时间戳，后一次调用比前一次调用发生的时间还早。因此 time-of-day clocks 并不适合测量 duration。

#### Monotonic Clocks

monotonic clock ，顾名思义，它的绝对值单调递增，通常用于测量 duration，如计算 timeout。

* Linux: clock\_gettime(CLOCK\_MONOTONIC)
* Java: System.nanoTime()

monotonic clock 的时间绝对值毫无意义，它可能是计算机上一次启动后经过的 nanoseconds 数量。因此比较不同机器的 monotonic clock 毫无意义。如果一台机器上有多个 CPU，那么每个 CPU 可能都有各自的时钟。NTP 可能被用于调节 monotonic clock 移动的频率，但它不会造成 monotonic clock 向前或向后跳跃。在分布式系统中，使用 monotonic clock 来衡量 duration 是有效的。

### Clock Synchronization and Accuracy

上文提到，time-of-day clocks 需要与 NTP 服务器同步，然而即使有同步，时钟所展示的时间并没有想象中那么精确与可靠：

* 计算机中石英钟并不精确，存在飘移现象，飘移程度随着机器的温度变化而变化。Google 假设它们的机器的漂移程度在 200 ppm (parts per million) 左右，即每 30s 出现 6ms、每天出现 17s 飘移。飘移的程度限制了你可能达到的精度
* 如果计算机中的时钟与 NTP 服务器时差过大，它可能拒绝同步，也可能被强制同步，在强制同步的过程中，应用可能观察到时间向前、向后移动
* 如果一个节点长期被防火墙隔离，无法访问 NTP 服务器，将导致 time-of-day clock 精度出现问题
* 由于与 NTP 服务器同步的过程依赖网络通信，因此它的精度因为网络延迟的存在而受到限制。实验表明，同步的最大精度一般能达到 35ms，而在网络峰值情况下，这个精度可能降低到 1s，甚至导致 NTP 客户端放弃同步
* 一些 NTP 服务器如果没有正确配置，本身的时间信息就是不准确的。为了防止这种现象影响时钟同步，NTP 客户端通常选择访问多态 NTP 服务器，忽略数据中的奇点
* Leap seconds
* 在虚拟机中，物理时钟被虚拟化，运行在物理机之上的虚拟机相互切换的过程，会导致单台虚拟机看见的时间出现跳跃性变化（10ms 级别）
* 如果你的软件将在你无法控制的设备中运行，那么你甚至不能相信设备上的硬件时钟。一些用户故意将它们设备上的硬件时钟调整到不正确的日期和时间

### Relying on Synchronized Clocks

在上文中介绍到网络是不可靠的，因此建立于网络之上的软件都需要应对网络故障的问题；同理，时钟也是不可靠的，尽管在大多时候工作正常，因此，任何依赖于精确同步时间的软件，都要认真考虑时钟可能出问题的情况，如实时监控不同节点的时钟，将飘移过多的节点清理出集群等等。时钟问题一般不会造成软件崩溃，因此它可能默默地造成损失，严密的监控使得这种问题能够被扼杀在摇篮状态。

#### Timestamps for ordering events

许多软件会将时间戳作为不同节点上发生事件总体排序的依据，如：如果两个 clients 同时往分布式数据库中的不同节点写入相同的 key，谁的写操作先发生？谁的后发生？

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-LipR2Yss0HeM6xQW7jX%2F-LipRjdGH_FTX8J7S99s%2FScreen%20Shot%202019-07-03%20at%209.28.48%20AM.jpg?alt=media\&token=d13f433d-065b-4405-a69a-f282675b87a0)

如上图所示：clientA 往 node 1 中写入 x = 1，数据被复制到 node 3，clientB 将 node 3 中的 x 增加 1，此时 x = 2，最后这些数据被复制到 node 2。由于 node 1 的 time-of-day clock 比 node 3 走得稍快一点，因此实际上发生在 clientB 写操作之前的 clientA 写操作会被 node 2 认为后发生，因此 node 2 认为最终 x = 1。

这种依赖 time-of-day clock 的冲突解决策略被称为 last write wins (LWW)，而且它被广泛地应用于多领导复制和无领导复制的分布式数据库中，如 Cassandra 和 Riak。其中一些实现在 client 端生成时间戳，但这并没有改变 LWW 策略面临的根本问题：

* 数据库的写入操作可能神秘失踪：一个时钟滞后的节点在校准之前可能无法有效地写入数据，而这些数据将被默默丢弃，而没有错误警报
* LWW 策略无法辨别多个写操作是顺序快速生成还是并发生成
* 当时间戳精度不高时，有可能两个节点独立地产生时间戳相同的数据

总而言之，即使 LWW 希望通过保留最新数据作为最终数据，但记录这些数据产生时间依赖于不那么可靠的本地的 time-of-day clock。是否有一种拥有绝对顺序的时钟，能够用来判定不同操作发生的先后顺序？这就是 logical locks，一个不断自增的计数器而不是石英钟。logical locks 不用来衡量绝对时间，只用来作为不同操作发生先后的判定依据，因此它的绝对数值没有意义。

#### Clock readings have a confidence interval

你也许可以从机器的 time-of-day clock 中读取精确到微妙甚至纳秒的数据，但得到它并不代表它真的能达到相应的精度，因为 NTP 的误差在不同的网络环境中就已经达到几十毫秒到百毫秒左右。

#### Synchronized clocks for global snapshots

在 "Snapshot Isolation and Repeatable Read" 一节中，我们讨论了 snapshot isolation 的实现 --- 利用单调递增的 transaction ID，如果一个写操作的 transaction ID 大于当前 snapshot，那么该写操作就对该 snapshot 不可见。在单节点数据库上，一个本地的计数器就足够了。然而对于节点存在于不同机器甚至不同数据中心的分布式数据库，就需要一个全局的自增计数器。如果在系统运行过程中，在短时间内出现大量小的 transactions，那么生成 trasaction ID 可能成为系统的瓶颈。

我们能否使用来自于 time-of-day clocks 的时间戳作为 transaction ID 呢？Google  Spanner 就是利用 time-of-day clocks i实现 snapshot isolation。与一般时钟不同，它的 TrueTime API 支持返回时间的置信区间 (confidence intervals)，每次请求时间，返回的是当前可能的最早和最晚时间戳，如 $$A = \[A\_{earlist}, A\_{latest}]$$ ， $$B = \[B\_{earlist}, B\_{latest}]$$ ，只要两个时间区间不重叠，即 $$A\_{earlist} < A\_{latest} < B\_{earlist} < B\_{latest}$$ ，那么就可以确定地认为 B 在 A 之前发生。同时为了保证 transaction 的时间戳能够反映因果关系，Spanner 故意在 transaction commit 之前等待一小段与置信区间长度相同的时间，保证任意读取都在写入之后发生。为了保证系统性能，Spanner 必须保证时钟的执行区间尽可能小，最终 Google 通过一些特殊手段将区间缩短到 7 ms。

使用同步时钟作为分布式系统的事件先后判定依据是研究者活跃的研究领域，但这种方式在 Google 外部还从未被实现过。

#### Process Pauses

假设有一个单领导复制数据库，只有 leader 可以接收写请求，那么这个 leader 如何能确保自己仍然是合法的 leader？从而能够安全地接收写请求？

有一种做法是让 leader 先从其它节点获得 lease，类似一个超时自动释放的锁，这样它能够确切地认为自己在某段时间内是 leader。为了维持自己 leader 的身份，该节点需要周期性地在 lease 过期之前获取新的 lease，因此其它节点可以在它过期之后成为 leader。我们可以想象 leader 的运行逻辑中有这样一段：

```java
while (true) {
    request = getInconmingRequest();
    
    if (lease.expiryTimeMillis - System.currentTimeMillis() < 10000) {
        lease = lease.renew();
    }
    
    if (lease.isValid()) {
        process(request)
    }
}
```

这段代码的问题在于：

* 它依赖本地 time-of-day clock，来自于其它节点创建的 lease 被用于与本地时间 (System.currentTimeMillis()) 对比，二者的时钟可能不一致，就会导致很多奇怪的事件发生
* 假设使用的是 monotonic clock 来计算过期时间，程序仍然有可能在上面代码运行的每一行 (如 if (lease.isValid())) 中间暂停一段时间，这段时间甚至可能达到 10s，导致程序在 10s 后重新获得 CPU 时，还可能认为自己的 lease 尚未过期

听起来假设程序会在任何一行代码执行前后暂停 10s 是一件骇人听闻的事，但实际上这确实有可能发生：

* 许多程序语言的运行时（如 JVM) 有 GC 暂停
* 在虚拟环境中，一台虚拟机有可能随时被暂停和恢复运行
* 在移动端设备中，程序可能在任意时刻被暂停和恢复运行
* 在 OS 中，threads 切换
* 在应用程序执行 io 操作时，thread 可能会被挂起
* 一个 Unix Process 可能被 SIGSTOP 信号暂停，如用户按下 Ctrl-Z 组合键
* ...

以上所有情况都可能导致程序在运行任意一行代码的过程中被暂停，而程序本身并不知道这件事情。在分布式系统中的节点同样如此，它可能在运行过程中被随时暂停，而在此期间其它节点继续正常运行，等被暂停的节点恢复运行时，它还不知道自己已经“睡了一觉”。

#### Response time guarantees

一些系统设计要求请求的响应时间必须有限制，比如飞行器、火箭、机器人、汽车的驾驶系统，遇到紧急情况时必须立即反应，如果这时候遇到一段 GC，整个系统都将完蛋，因此这些系统也被称为 hard real-time systems。要提供 hard real-time 保证，必须在整个软件技术栈上提供保证。

#### Limiting the impact of garbage collection

通过最大程度上减少 GC 带来的影响，也可以缓和其对响应时间造成的影响。最近兴起的一种想法是把 GC 暂停看作是计划中的节点断电，在 GC 之前，节点需要通知其它节点自己即将 GC，于是应用层停止将请求打向该节点，待节点 GC 完毕后，再恢复流量。这种想法还有一种变体是阻止 GC 的发生，在节点即将 GC 前重启节点，同时关闭流量，等待进程重启后再恢复流量。

## Knowledge, Truth, and Lies

### The Truth Is Defined by the Majority

想象下列 3 个场景：

* A 可以接收到所有其它节点发送给它的消息，但 A 发送给其它节点的消息都未被接收，可能被丢弃或者延迟，即使 A 运转正常，同时也在接收其它节点发送给它的请求，但其它节点无法接收到它的响应，经过一段时间后，其它节点宣布 A 已经死亡。
* A 可以接收到所有其它节点发送给它的消息，而且 A 发现它发送给其它节点的消息都未得到响应，因此 A 认识到自己可能遇到了网络问题，A 明白自己即将被其它节点宣布死亡，但它无能为力。
* A 即可以接收来自其它节点的消息也可以正常向其它节点发送消息，但 A 忽然经历了一次 GC 暂停，这次 GC 的时间过长，导致其它节点长时间没有 A 的消息已经宣告了 A 的死亡。最终 GC 暂停恢复，A 如梦初醒，且对自己失联一段时间毫不知情。

这些场景告诉我们，一个节点不能相信自己的判断，一个分布式系统不能依赖于但个节点的判断，因为任何一个节点都可能在任意时间发生故障。因此分布式系统需要相信大多数 (quorum)，需要综合大多数节点的意见来作决定：**如果多数节点都认为 A 死亡，那么 A 就必须得死，即使 A 还活着**。通常 quorum 指的是超过半数，系统内部只可能出现一个 quorum，因此系统的决定也只可能有一个。

#### The leader and the lock

一个系统常常要求某些东西在系统内部必须唯一，如：

* 只有一个节点能够成为一个数据库分片的 leader
* 只有一个事务或者客户端可以拥有某个资源的锁
* 只有一个用户能够注册某个用户名
* ...

要在分布式系统中实现这点需要格外谨慎，因为即使一个节点相信它自己就是被选中的 leader，这并不意味着大多数节点都同意它的观点。之前被多数节点认可的 leader，也有可能因为一次 GC 被其它节点宣告死亡，如果这个节点在 GC 完成后还以 leader 的身份自居，这将给系统带来各种各样的问题。

看一个 HBase 曾经出现的问题：

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-LjE8RBifr4EiW2SG3XY%2F-LjEALyzAzHbWl4MtJQ0%2FScreen%20Shot%202019-07-08%20at%209.22.59%20AM.jpg?alt=media\&token=f17ddff1-f151-4adb-9320-b2ada62da960)

假设你希望保证在同一个存储设备上的文件每次只能被一个客户端访问，可以要求客户端在访问文件之前先从一个分布式锁上获取 lease。如上图所示：当 client 1 获取租约后，经历了一次 GC，在此期间 client 2 成功获取了下一段时间的 lease，而当 client 1 恢复后仍然认为自己拥有 lease，就会出现写冲突。

#### Fencing tokens

可以使用一种简单的技术 --- fencing tokens，来避免上文中的问题。fencing tokens 是单调递增的数字，客户端的每次写请求需要同时将 fencing token 放入请求中，如果存储设备接收到比上次成功写入更小的 fencing token，则拒绝请求，如下图所示：

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-LjE8RBifr4EiW2SG3XY%2F-LjECfaPw-enAtbe_GqJ%2FScreen%20Shot%202019-07-08%20at%209.33.11%20AM.jpg?alt=media\&token=3dd88411-8e14-4a63-8960-75a2746a2717)

### Byzantine Faults

Fencing tokens 可以检测并阻止一个无意犯错的节点，但面对一个有意破坏系统的节点，它可以很轻易地修改消息中的 fencing token，从而达到篡改数据的目的。在本书中，我们通常假设节点虽然不可靠但是是诚实的。但在分布式系统中，如果一个节点可以撒谎，那么解决问题将变得更加困难。这种问题被称为 Byzantine fault，而如何在不可信的环境中达成共识的问题被称为 Byzantine Generals Problem。解决了这个问题的系统被称为 Byzantine fault-tolerant，在一些场景中，这种方案很有必要，如：

* 在航空航天系统中，计算机中的内存、CPU 寄存器数据可能被辐射破坏，导致它们与其它节点的沟通行为可能出现任意无法预测的情况。这种系统中任意微小的差错都可能导致严重的后果，因此它们必须做到 Byzantine fault-tolerant
* 当一个系统中有多个参与者，其中一些参与者可能尝试欺骗其它参与者，这时候参与者就不能够轻易地相信来自其它节点的消息。如，Bitcoin 和其它区块链技术，可以被认为是一种使得互相不信任的参与方达成共识的方式。

而在本书讨论的系统中，如 DC 中用内网相连的各个节点，我们可以认为 Byzantine faults 不存在，因为环境基本受控。

#### Weak forms of lying

尽管我们假设节点是诚实的，但增加一些机制来保护节点可能出现的 ”轻度撒谎“ 现象是有价值的，这种 "轻度撒谎" 通常没有达到 Byzantine fault 的程度：

* 网络数据包可能因为硬件问题或 OS、driver、routers 的问题而被破坏。通常这种数据破坏可以被 TCP/UDP 的 checksums 机制来检测和解决，但有时候不能。简单地在应用层做一次 checksum 可以在很大程度上解决这个问题
* 一个向公众开放的应用应当小心谨慎地检查用户输入
* NTP clients 应该配置多个 time servers 来减小获得的时间数据的误差

## System Model and Reality

研究者设计了许许多多的算法来解决分布式系统面临的问题，在讨论这些算法之前，我们需要正式地定义这些算法在使用时所遇见的可能的分布式系统问题，这就是 System Model。

从时间上划分，有三种 System Models：

* Synchronous Model (SM)：假设网络延迟有上限，程序暂停有上限，时钟偏差有上限，即所有本节介绍的问题都在可控范围内。SM 不符合现实，但通常它是其它模型的起点
* Partially Synchronous Model (PSM)：PSM 假设系统在大部分时间符合 SM 假设，但偶尔会超出上限。PSM 符合大多数系统的现实场景，在 PSM 下，网络延迟、程序暂停、时钟偏差都没有上限。
* Asynchronous Model (AM)：AM 没有任何假设，它甚至没有时钟，无法使用延迟逻辑。

从节点故障上划分，有三种 System Models：

* Crash-stop Faults：一个节点故障的方式只有一个，就是忽然直接崩溃，且永远无法恢复
* Crash-recovery Faults：一个节点可能在任意时刻故障，但将会在未知长的一段时间后恢复
* Byzantine (arbitrary) Faults：节点可能做任何事情，甚至包括在系统内部搞破坏

在为现实场景建模时，Partially Synchronous Model + Crash-recovery 的模型组合通常最有效。

## 参考

DDIA chapter 8