前面几章所考虑的情况：机器宕机、网络延迟都相对较理想。但在实际的大型分布式系统中，情况会更加悲观，出错方式更加复杂。

构建分布式系统和单机软件完全不同。尽管我们总期望能构建处理任何可能故障的系统，但在实践中，一切都是权衡。因此，我们首先需要知道可能遇到哪些问题，才能进而选择：是否要在目标场景下解决这些问题、还是为了降低系统复杂度忽略这些问题。

本章将会探讨计算机网络的痼疾、时钟和时间、以什么程度避免上述问题等等。所有上述问题的原因都隐藏的很深，本章会探索如何理解分布式系统当前所处状态、如何定位分布式系统问题原因所在。

1. 故障和部分失败

单机系统通常具有一种很好地特性：要么正常运行、要么出错崩溃，而不会处于一种中间状态。但在构建分布式系统时，系统行为边界变得模糊起来。在分布式系统中，有很多我们习以为常的假设都不复存在，各种各样的异常问题都会出现。其中最令人难受的是：部分失败（partial failure），即系统的一部分正常工作，另一部分却以某种诡异的方式出错。这些问题，多数都是由于连接不同主机的异步网络所引入的。

1.1 云计算与超算

关于如何构建大规模计算系统，在选择上有如下一个光谱：

• 在光谱的一侧，是高性能计算（HPC，high-performance computing）。使用上千个 CPU 构建的超级计算机，用于计算密集型工作，如天气预报、分子动力学模拟。
• 在光谱的另一侧，是云计算。云计算不是一个严谨的术语，而是一个偏口语化的形象指代。通常指将通用的廉价的计算资源，通过计算机网络收集起来进行池化，然后按需分配给多租户，并按实际用量进行计费。
• 传统的企业自建的数据中心位于光谱中间。

不同构建计算系统的哲学，有着不同的处理错误的方式。对于高性能计算（也称超算）来说，只要其中部分出错后只要停止集群运行，等故障修复后在恢复最近的快照继续运行即可。超算更像是一个单节点系统而非分布式系统，它将局部失效升级为了整体失效。

但本章的重点在于基于互联网的服务系统，它与单机应用有着很多不同之处：

• 在线离线。互联网多为在线服务，这种场景下重启往往是不可接受的；但在高性能计算的离线任务中，影响相对较小。
• 专用通用。超算多用专用硬件构建而成，组件本身很可靠；而云服务多由通用机器组网而成，具有规模化堆数量的特点，经济但故障率高。
• 组网方式。大型数据中心通常基于 IP 和以太网，采用 Clos 拓扑组网以对分带宽；而超算常用特定拓扑结构来提高计算性能。
• 故障常态化。系统越大，其中局部组件失效的概率越大。在上千个节点组成的系统中，可以认为任何时刻，总有组件存在故障。
• 容错。当部分节点故障时，如果系统仍能作为一个整体而正常工作，将会对运维十分友好。
• 本地异地。多地部署的大型系统多通过互联网通信，更易出错；超算的多个节点都靠的很近。

为了让分布式系统能够工作，就必须假设故障一定会存在，并在设计层面考虑各种出错处理。即，我们要基于不可靠的组件构建一个可靠系统。因此，面向容错进行设计是对分布式系统软件的基本要求，为此，我们首先要了解分布式系统中的常见问题，并依此设计、编写、测试你的系统。

在实践中

但在实践中，任何设计都是取舍（trade-off），容错是有代价（昂贵、损失性能、系统复杂度提升等）的。因此，充分了解你的系统应用场景，才能做出合理的容错实现，过犹不及。

1.2 基于不可靠的组件构建可靠的系统

但在工程领域，这种思想并不少见。如：

• 纠错码能够容忍信道中偶尔一两个比特的误传。
• IP 层不可靠，但 TCP 层却基于 IP 层提供了相对可靠的传输保证。

不过，所有容错都是有限度的。如纠错码也没办法处理信号干扰造成的大量信息丢失，TCP 可以解决 IP 层的丢包、重复和乱序问题，但没办法对上层隐藏解决这些问题带来的通信时延。但，通过处理一些常见的基本错误，可以简化上层的设计。

2. 不可靠的网络

要明确的是，本书讨论的系统范畴是 share-nothing 系统：所有及其不共享资源（如内存、磁盘），通信的唯一途径就是网络。这种构建方式是最经济，也是复杂度最高的。

现在的网络多是异步封包网络（asynchronous packet networks），也就是说，一个机器向其他机器发送数据包时，不提供任何保证：你不知道数据包什么时候到、甚至不知道它是否能够到。下图展示了一次网络交互可能遇到的异常情况：

在异步网络中，当你发送出一个请求，并在一段时间内没有收到应答，任何事情都有可能发生：由于没有收到任何信息，你无从得知具体原因是什么。甚至，你都不知道你的请求是否已被送达处理。应对这种情况的惯常做法是——超时（timeout）。即，设定一个时限，到点后，我们便认为这个请求废了。但在实际上，该请求可能只是还在排队、可能稍后到到达远端节点、甚至可能最终还会收到应答。

2.1 实践中的网络故障

很多经验表明：即使在专门管理的数据中心，网络问题也相当普遍。

一项研究关于中型数据中心的研究表明，平均每月有 12 次网络故障，其中一半是单机失联，另一半是机架整个失联。另一项关于组件故障率的研究，包括 TOR 交换机、聚合交换机和负载均衡器。发现，增加网络冗余并不能如预期般减少故障，因为这不能避免造成网络中断的最主要原因——人为故障（如配置错误）。

尽管云服务相比自建数据中心会更加稳定，但没人能够真正逃脱网络故障：

• 如交换机软件升级引发的拓扑重置，会导致期间网络延迟超过一分钟
• 🦈 鲨鱼可能会咬断海底光缆
• 有些奇葩的网口会只传送单向流量（即使一个方向通信正常，你也不能假设对向通信没问题

虽然上述情况可能都比较极端，但你的软件如果处理不好，当网络问题一旦发生，你将面临各种难以定位莫名其妙的问题，并且可能会导致服务停止和数据丢失。

处理网络错误并不一定要容错，如果网络问题很少发生，直接让系统出现问题时停止运行并打印提示信息就可以。但要保证，在网络恢复之后，服务也能够恢复，并且不会造成意外损失。为此，你需要使用混沌测试工具来主动模拟各种网络异常，在交付前确保你的软件有足够的鲁棒性。

2.2 故障检测

在很多系统里，我们需要自动检测故障节点，并据此做出一些决策，比如流量的负载均衡、主节点的更换等。

但不幸的是，你很难准确的判断一个远端节点是否发生了故障。在下面的一些特定场景，你可以通过一些旁路信号来获取一些信息，来判断确实发生了故障：

• 操作系统通知。如果你能触达服务所在机器，但发现没有进程在监听预期端口（比如对应服务进程挂了），操作系统会通过发送 RST 或 FIN 包来关闭 TCP 连接。但是如果对端节点在处理你的请求时整个宕机了，就很难得知你请求的具体处理进度。
• daemon 脚本通知。可以通过一些 daemon 脚本，在本机服务进程死掉之后，主动通知其他节点。来避免其他节点通过发送请求超时来判断此节点宕机。当然这前提是，服务进程挂了，但所在节点没挂。
• 数据链路层面。如果你是管理员，并且能访问到你数据中心的网络交换机，可以在数据链路层判断远端机器是否宕机。当然如果你访问不到交换机，那这种方法就不太行。
• 路由层 IP 不可达。如果路由器发现你要发送请求的 IP 地址不可达，它会直接回你一个 ICMP 不可达包。但路由器也并不能真正判断是否该机器不可用了。

尽管有上述手段可以快速检测远端节点是否宕机，但你并不能依赖它们。因为，即使 TCP 层已经收到某个请求的 ACK，但对端服务仍有可能在应用层面没有处理完该请求就宕机了。因此，如果你想确定某个请求确实成功了，只能在应用层进行显式确认。

当然，如果对端出错，你可能会很快收到一个错误，但你并不能指望在任何情况下都能很快得到错误回复——可能过了一段时间我们仍然没有得到任何回复。因此，在应用代码里，必须设置一个合理的超时时限和重试次数。直到，你确认没有再重试的必要——即不管远端节点是否存活，我在重试几次后，都认为它不可用了（或者暂时不可用）。

2.3 超时和无界延迟

如上所述，超时是应用层唯一能动用的检测网络故障的手段。但另一个问题是：超时间隔要设置多久呢？总的来说：

• 不能太长：过长会浪费很多时间在等待上。
• 不能太短：太短会造成误判，误将网络抖动也视为远端节点失败。

过早将一个正常节点视为故障会有诸多问题：

1. 多次执行。如果节点已经成功执行了某动作，但却被认为故障，在另一个节点进行重试，可能会导致次动作被执行两次（如发了两次邮件）。
2. 恶性循环。如果系统本就处于高负载状态，此时还频繁错误的在其他节点上重试，可能会造成恶性循环，重试过多导致系统负载加重，系统负载加重反过来造成通信延迟增加，从而造成更多误判。

实际中网络都不会提供网络通信延迟的保证，尤其是当前网络环境下的异步网络。并且，大多数服务也很难保证在所有请求的处理时间都不超过某个上界。

2.3.1 数据包的排队

在计算机网络中，数据报有很多环节可能造成排队：

1. 去程网络排队。如果多个节点试图将数据包同时发给一个目的端，则交换机得将他们排队以逐个送达目的端。
2. 目的机器排队。当数据包到达目的端时，如果目标机器 CPU 负载很高，操作系统会将进来的数据包进行排队，直到有时间片分给他们。
3. 虚拟机排队。在虚拟化环境中，由于多个虚拟机共用物理机，因此经常会整体让出 CPU 一段时间的情况。在让出 CPU 等待期间，是不能处理任何外部请求的，又会进一步给网络请求的排队时延增加变数。
4. TCP 流量控制。会剪枝发送方的发送频率，因此可能在本机排队。

一个基本现象是：网络流量越满，单个请求延迟抖动越大。

2.3.2 超时间隔的设置

1. 静态设置。使用实验统计的方式，在检测过久和故障误报之间做一个权衡。

2. 动态调整。通过类似时间窗口的方式，不断监测过去一段时间内的请求时延和抖动情况，来获取请求时延的分布情况，进而动态调整超时间隔。Phi 累积故障检测算法（ The Φ Accrual Failure Detector）便是这样一种算法，Akka and Cassandra 中都用到了此种算法，它的工作原理和 TCP 重传间隔的动态调整类似。

2.4 同步网络和异步网络

这里计算机网络课程中都学了，不再展开

• 同步网络：固定电话网、电路网络
• 异步网络：分组交换网络

我们在设计分布式系统时，不能对网络传输的时延和稳定性有任何假设。我们必须要假定我们面对的网络会发生网络拥塞、会产生排队、会有无界延迟，在这种情况下，没有放之四海而皆准的超时间隔 。针对不同的具体情况，需要通过经验或者实验来确定它。

在异步网络中，可以认为是资源的动态分配导致了时延的不稳定性。这种不稳定的延迟并非什么不可变的自然法则，而仅是一种代价和收益权衡的结果罢了。

3. 不可靠的时钟

应用程序会以很多形式依赖时钟。有时用到的是时间间隔（durations），有时用到的是时间点（points in time）。在分布式系统中，时间是一个很棘手的问题，由于传输所带来的延迟，发生在分布式系统内的多个机器的事件，很难准确定序。

网络上每台机器有自己的系统时钟，通常是用石英振荡器做成的特殊硬件计时的，并独立供电持续运转。但这种时钟总是会有误差，有快有慢。因此实践中，常用 NTP（网络时间协议）对机器进行自动校准。其原理是：首先使用更精确时钟（如 GPS 接收器）构建一组可信服务器作为时钟源（比如阿里云的源），然后再利用这组服务器通过网络校准其他机器。

3.1 单调时钟和日历时钟

现代计算机内部至少有两种不同的时钟：日历时钟（time-of-day clock）和单调时钟（monotonic clock），两者服务于不同的目的。

3.1.1 日历时钟

日历时钟（time-of-day clock）：根据某个日历返回当前的日期和时间。

• 比如 Linux 上的 clock_gettime(CLOCK_REALTIME) 和 Java 的 System.currentTimeMillis() 会返回基于格里历（Gregorian calendar）1970 年 1 月 1 日 000000 时刻以来的秒数（或者毫秒数），不包括闰秒。

日历时钟可以与 NTP 同步。但特别的是，如果某个机器时间大大领先于 NTP 服务器，则其日历时钟会被重置，从而让该机器上的时间看起来倒流了一样。时钟回拨、跳过闰秒等等问题，使得日历时钟不能用于精确计算一个时间间隔。

3.1.2 单调时钟

单调时钟（monotonic clock）：它保证总是向前，不会时钟回拨，但它的绝对值没有任何意义。

• 比如 Linux 上的 clock_gettime(CLOCK_MONOTONIC) 和 Java 中的 System.nanoTime() 都是单调时钟。

单调时钟适合测量时间间隔。可以在一个时间点读取单调时钟的值，完成某项工作，然后再次检查时钟，时钟值之间的差值就是时间间隔。

在分布式系统中，使用单调时钟计算时间间隔很合适，因为时间间隔既不关心多机间进行时钟同步，也对时间精度不是很敏感。

3.2 时钟同步和精度问题

单调时钟不太需要关心多机同步问题，但日历时钟需要定时与 NTP 服务器或可信时钟源进行同步。

在计算机系统中，其本身的硬件时钟以及用于校准的 NTP 服务都不是完全可靠的：

• 单机的硬件时钟都不是很精确，会发生漂移（drift，走的快或者慢）。谷歌认为其服务器时钟为 200ppm（parts per million），也即每 30s 漂移 6ms、每天漂移 17s，这种漂移限制了时钟的精确度上限。
• 如果时钟与 NTP 的时钟差别太大，可能会出现拒绝同步，或者时钟跳变的现象。
• 错误的配置可能突然与 NTP 连接失败。
• NTP 同步受限于网络的延迟。实验表明，当通过互联网进行同步时，可能会产生至少 35 毫秒的偏差，最坏时则可能超过 1s。
• 闰秒的存在会导致一分钟可能有 59s 或者 61s。闰秒曾经使很多大型系统崩溃过。处理闰秒最好的办法是，让 NTP 服务器在一天中逐渐调整，摊平闰秒（也称为：拖尾，smearing），不过在实际中， NTP 服务器处理闰秒的行为不尽相同。
• 在虚拟机中，其物理时钟是虚拟化出来的，从而给运行其上并依赖精确计时的应用带来额外挑战。当 CPU 被共用时，VM 进程可能被切换，从应用代码的视角，其时钟就是毫无征兆的突然往前跳变了一段。
• 如果你的软件将会运行在不受控的设备上，如智能手机或者嵌入式设备，则你不能完全相信设备系统时钟。因为用户可能会由于一些原因（比如绕开游戏时间限制），故意将其硬件时钟设置成一个错误的日期和时间，从而引起系统时钟的跳变。

当然，如果不计代价，我们是能够获得足够精确的时钟的。但一般场景下，我们还是不要太依赖时钟精度。

3.3 依赖同步的时钟的情况

在设计系统，我们仍可能需要考虑时钟出现最坏的可能。

时钟问题造成的影响往往不容易被发现。如果 CPU 、内存或者网络故障，可能系统会立即出现很严重的问题；但如果不正确的依赖了时钟，可能系统仍然能在表面上看起来正常运转，比如时钟漂移是慢慢累加的，可能到第一程度才会出现问题。

因此，如果你的系统依赖（或者假设）所有参与的机器时钟同步（synchronized clocks），就必须通过一定的机制来检测系统内节点间的时钟偏移，如果某个节点系统时钟与其他相差过大，就及时将其从系统内移除，以此来规避时钟相差太大所造成的不可挽回的问题。

下面讨论一些需要依赖时钟同步的情况。

3.3.1 时间戳以定序

考虑一种危险的依赖时钟的情况：使用节点的本地时钟来给跨节点的事件定序。举个具体例子，如果两个客户端同时写入同一个分布式数据库，谁居前？谁靠后？

如上图，Client A 向节点 1 写入 x = 1，然后该写入被复制到节点 3 上；Client B 在节点上将 x 增加 1，得到 x = 2；最终上述两个写入都被复制到节点 2 。在图中所有待同步的数据都会被打上一个时间戳，并按照时间先后顺序应用到数据库中。但是由于发送请求的节点之间的日历时钟存在误差，可能会出现实际最新的操作会被认为是旧操作。

后者胜（Last write win，LLW）作为一种冲突解决策略，在多副本架构中被广泛使用，但这种策略很依赖时钟。因此在使用 LLW 解决冲突时，需特别注意如何判定哪个事件更近（most recent），因为其定序可能依赖于不同机器的本地时钟。

NTP 时钟同步无法做到足够精确来处理事件定序。因此，处理事件定序需要更精确的手段。

这里需要区分一下逻辑时钟和物理时钟：

• 逻辑时钟：使用自增计数器来实现，不会追踪自然时间或者耗时间隔，而仅用来确定的系统中事件发生的先后顺序。
• 物理时钟：用于追踪时间流逝，包括日历时钟和单调时钟。

3.3.2 时钟的置信区间

时钟误差主要来自于：

1. 石英晶振漂移
2. NTP 同步误差

总之，使用普通硬件，你无论如何都难以得到真正“准确”的时间戳。

因此，我们不应该将时钟读数视为一个精确的时间点，而更应该视为带有置信区间的时间范围。

但不幸，大多数服务器的时钟系统 API 在给出时间点时，并不会一并给出对应的不确定区间。例如，你使用 clock_gettime() 系统调用获取时间戳时，返回值并不包括其置信区间，因此你无法知道这个时间点的误差是 5 毫秒还是 5 年。

一个有趣的反例是谷歌在 Spanner 系统中使用的 TrueTime API，会显式的给出置信区间。当你向 TrueTime 系统询问当前时钟时，会得到一个区间而不是精确的时间点：[earliest, latest]，前者是最早可能的时间戳。后者是最迟可能的时间错。通过该不确定预估，我们可以确定准确时间点就在该时钟范围内。此时，区间的大小取决于，上一次同步过后本地石英钟的漂移多少。

使用这个 TrueTime API 得到的区间就可以用于事件的全局排序。

3.3.3 用于快照的同步时钟

之前讲过快照隔离，它能够让只读事务在不阻塞正常读写事务的情况下，看到数据库某个时间点之前的一致性视图。

快照隔离的实现需要一个全局自增的事务 ID，数据库根据这个全局自增的事务 ID 来判断一个事务的可见性。

在单机数据库中，使用一个全局自增计数器就可以了。但在多机数据库中，事务 ID 要求必须反映因果关系：当事务 B 读到事务 A 写的内容时，事务 B 的事务 ID 就需要比事务 A 大。否则快照将不能维持一致。

解决全局自增事务 ID 的生成有如下几个主流解决方案：

1. TSO 方案（Timestamp Oracle，统一中心授时）：专门由同一个服务器来产生时间戳，但面对大量频繁的数据包时可能会面临瓶颈。
2. ATLC：混合时钟，也就是本地时钟 + NTP + ...，这里没有详细说。
3. Google Spanner 的 TrueTime API。也就是自己用高精尖的硬件来做时间戳的确定。

Spanner 就使用了物理时钟实现了快照隔离，它是如何做到可用的呢？Spanner 在设计 TrueTime 的 API 时，让其返回一个置信区间，而非一个时间点，来代表一个时间戳。假如现在你有两个时间戳 A 和 B（A = [Aearliest, Alatest] and B = [Bearliest, Blatest]），且这两个时间戳对应的区间没有交集（例如，Aearliest < Alatest < Bearliest < Blatest），则我们可以确信时间戳 B 发生于 A 之后。但如果两个区间有交集，我们则不能确定 A 和 B 的相对顺序。

为了保证这种时间戳能够用作事务 ID，相邻生成的两个时间戳最好要间隔一个置信区间，以保证其没有交集。为此， Spanner 在索要时间戳时（比如提交事务），会等待一个置信区间。因此置信区间越小，这种方案的性能也就越好。为此，谷歌在每个数据中心使用了专门的硬件做为时钟源，比如原子钟和 GPS 接收器，以保证时钟的置信区间不超过 7 ms。

目前好像就只有使用物理时间戳的方式可以达到全局的全序，其他那种的方式（像 ATLC）只能实现一些偏序关系。

在分布式事务中使用时钟同步，是一个比较活跃的研究领域（本书出版时间 2017 年）。HLC 也算类似的实现，但本书并没有提这个。

3.4 进程停顿

3.4.1 进程暂停的原因和可能导致的错误

现在来看另一个在分布式系统中使用时钟的危险情况。假设数据库只有一个主节点，只有主节点可以接受写入，那么其他节点该如何确定这个主节点没有被宣告失效，可以安全地写入呢？

一种解决方案是使用租约（lease）。该机制类似于具有超时的锁：任意时刻只有一个副本可以持有改租约。因此，一旦某副本获取到租约，它就获取到了一段时间的领导权，直到租约过期；为了持续掌握领导权，该副本需要定期续租，且续租间隔要小于租期时间。如果该副本宕机，自然就会停止续约，其他副本就可以上位。

用伪代码表示，续租大概长这样：

while (true) {
    request = getIncomingRequest();
    
    // Ensure that the lease always has at least 10 seconds remaining
    if (lease.expiryTimeMillis - System.currentTimeMillis() < 10000) {
        lease = lease.renew();
    }
    if (lease.isValid()) {
        process(request);
    } 
}

这段代码有什么问题呢：

1. 依赖时钟同步。line 5 中的 lease.expiryTimeMillis 和 System.currentTimeMillis() 这两个时间戳的产生来源不一样，进行比较可能会产生问题。
2. 语句执行间隔的假设。line 7 中，可能在你刚续完约（renew）之后，进程就发生了暂停，并在暂停了很久之后导致租约过期了，进程恢复后没有及时意识到并继续处理这个 request，从而产生了并发问题。

补充一点，其实这些网络问题、时间戳问题、进程停顿问题，大部分情况下的编程并不会去考虑，99% 都不会发生，只有在构建鲁棒的分布式系统时才会去考虑。

进程暂停的可能原因：

• GC 导致的暂停。GC 有时产生的全暂停甚至可以长达数分钟，最新的 GC 算法已经减少了暂停时间，但仍需要时不时地停止一下。
• 在虚拟化环境中，虚拟机可能会在任意时间点被挂起，过段时间才恢复。这种功能常用于虚拟机的在线迁移，即把虚拟机从一个主机迁移到另一台主机而不需要重启。
• 用户可能合上笔记本。
• OS 的进程上下文切换。
• OS 的换页。为了避免此问题，服务器上的允许换页的配置项一般不打开。你也可以点杀一部分进程来释放内存，避免换页，这就是 trade off 了。
• Unix 系统中，用户可能向进程主动发送 SIGSTOP 信号来让其暂停。

所有上述情景都会在任意时刻中断正在运行的线程，并在之后某个时刻将其重新唤醒，而线程本身对这个过程是不感知的。

在单机上写多线程代码时，我们有很多手段来实现线程安全，比如互斥量、信号量等，但这些却无法直接用到分布式系统中，因为分布式系统不采用共享内存，而是在不可靠的网络上发送消息。

分布式系统中的一个节点必须假定：执行过程中的任意时刻、任意代码位置都有可能被暂停相当长一段时间。（有点像红王的时削）最终，被暂停的节点在回来继续执行时，除非再次检查时钟，否则它将对刚刚过去的暂停毫无意识。

3.4.2 响应时间的保证

如前所述，在很多语言和操作系统中，进程和线程都可能停顿任意时间，我们将其称之为无界时延。但如果我们付出足够代价，上述造成停顿的原因都可以被消除。

某些软件如果在指定时间内无法响应则会导致严重后果。比如飞机、火箭、机器人等需要对输入传感器做出快速的响应，超出了这个时限，整个系统可能会出现重大故障，这就所谓的强实时系统。

实时系统真的实时吗？ 在嵌入式系统里，实时意味着需要通过设计、测试等多层面来让系统在延迟上提供某种保证。其在 Web 中也有实时系统（real-time）的叫法，但更多的侧重于服务器会流式的处理客户端请求，并将数据发回客户端，但对响应时间并没有严苛的要求。

提供实时保证需要在全软件栈进行优化才能提供实时保证：

1. 在操作系统上，需要能提供指定所需 CPU 时间片的实时操作系统（real-time operating system ，RTOS）。
2. 在依赖库中，所有的函数都需要注释其运行时间的上界。
3. 在内存分配上，要限制甚至禁止动态内存分配（会有实时 GC 器，但不会占用太多时间）。
4. 在观测和测试上，需要进行详尽的衡量和测试，以保证满足实时要求。

上述要求极大的限制了编程语言、依赖库和工具的可选范围，从而使得开发实时系统代价极为高昂。也因此，这种系统通常被用在对安全性有严苛要求的嵌入式设备里。

这里需要说明的是，实时不意味着高性能。并且通常相反，实时系统都具有很低的吞吐，因为实时系统会把对时延的优化放在第一位，比如需要尽量消除并行所带来的运行的不可预测性，自然就降低了效率。

对于一般的服务端的数据处理系统来说，这种严苛的实时保证通常既不经济也不必要。也就是说，我们在设计服务端的数据系统时，还是要老老实实考虑由于任意停顿和不准确时钟所带来的问题。

3.4.3 限制 GC 的影响

我们有一些手段可以用来减轻进程停顿现象，且不必借助代价高昂的强实时系统。

• 比如垃圾回收器（GC 进程）可以实时追踪对象分配速率和剩余可利用内存，利用这些信息，GC 进程可以给应用程序提供一些信号。然后我们在构造系统时捕获这些信号，然后拒绝服务一段时间，等待 GC 结束。就跟临时故障或者下线的节点一样，别的节点会来接管请求。一些对延迟比较敏感的系统，如交易系统，就是用了类似的方法。
• 另一个相似的想法是，阉割一下 GC ，只用其对短时对象进行快速回收。对于生命周期较长的对象，通过通过定期重启来回收。在重启期间，该节点上的流量可以暂时切走，就像滚动升级一样。

这些手段虽然不能治本，但能一定程度上缓解 GC 对应用进程造成的影响。

4. 分布式中的知识、真相和谎言

本章已经梳理了分布式系统和单机系统的诸多差异。分布式系统中编程复杂度高的本质在于：身处网络中的节点，不能直接确信任何事情，而只能根据从网络中得到的信息（没有得到回复也是一种信息）来推测（guess），只能通过与其他节点交换信息来确定其状态。如果一个对端节点没有响应，我们难以分辨是是网络问题还是节点本身问题。

分布式系统中的节点唯一获取信息的渠道都是不可靠的，所以深究这些本质原因会引到哲学上了。

在分布式系统中，我们可以做一些基本假设，并基于这些假设设计真实系统。基于特定假设，我们能够设计出能够被证明正确性的算法。那么，纵然底层系统不怎么可靠，我们仍能通过罩一层协议，使其对上提供相对可靠的保证（比如 TCP）。

我们将继续探讨分布式系统中的知识和事实，来辅助我们思考对下做什么样的假设、对上提供什么样的保证。

4.1 真相由多数派定义

设想一个具有非对称故障（asymmetric fault）的网络：某个节点可以收到任何其他节点发送给他的信息，但其发出的消息却被丢弃或者延迟很高。此时，尽管该节点运行良好，并且能处理请求，但却无人能收到其响应。在经过某个超时阈值后，其他节点由于收不到其消息，会将其标记为死亡。

打个比方，这种情况就像一个噩梦：处于半连接的节点就像躺在棺材里被运向墓地，尽管他持续大喊：“我没有死”，但没有人能听到他的喊声，葬礼继续。

所以说，任何节点都不能独自断言其自身的当前状态。一个分布式系统不能有单点依赖，因为单个节点可能在任意时刻故障，进而导致整个系统卡住，甚而不能恢复。因此，大部分分布式算法会基于一个法定人数（quorum），即让所有节点进行投票：任何决策都需要达到法定人数才能生效，以避免对单节点的依赖。

最普遍的情况是，法定人数是集群中超过半数的节点，即多数派（其他比例的法定人数也有可能）。

4.1.1 主节点和锁

在很多场景下，系统会要求某些东西全局唯一，比如：

1. 每个数据库分片都有唯一的领导者，避免脑裂
2. 只有一个事务或者客户端允许持有某资源或者对象的锁，以避免并发写入或者删除
3. 每个名字最多允许一个用户注册，因为需要用用户名来唯一标识一个用户

在分布式系统中实现这种唯一性需要格外小心：尽管某个节点自认为它是那个“唯一被选中的（The chosen one）”（分区的主副本、锁的持有者、成功处理用户名注册请求的节点），这并不意味着法定数目的（Quorum）节点也都如此认为！可能一个节点以前是领导者，但在其领导期间，如果其他节点都认为它死了（可能由于网络故障或者 GC 停顿），它就有可能被降级，且其他节点被选举上位。当大多数节点认为前领导者死亡时，该节点仍然自顾自的行使领导权，在设计的不太好的系统中，就会带来一些问题。这样的前领导节点可能会给其他节点发送一些错误决策的消息，如果其他节点相信且接受了这些消息，系统在整体层面可能就会做出一些错误的事情。

所以，在分布式系统中，每一个节点都不能单独确认自己具有某种唯一性去进行某种决策。哪个节点具有这种唯一性是系统层面的一个决策。

下面是一个错误使用分布式锁的例子：客户端 1 的锁租约已经到期了，但它还自认为有效，最终导致文件被破坏：

上图的问题属于前面“进程暂停”的一种情况：如果持有租约的客户端停顿了过长时间，以至于租约过期。此时，另外一个客户端向锁服务请求并获取到同一个文件的租约，然后开始写文件。当前一个停顿的客户端恢复时，它想当然的认为自己仍然持有租约，也开始写文件。此时，这两个客户端的写入可能会产生冲突并导致文件的数据损坏。

4.1.2 防护令牌（fencing token）

当我们使用锁或租期来保护对某些资源的（如上图中的文件）互斥访问时，我们需要确保那些错误的认为自己是“被选中的人”（比如主副本、持有锁等）不能影响系统其他部分。此问题一个简单的解决方法是，使用 fencing token，如下图所示：

即，在锁服务每次授予锁或者租约时，会附带给一个防护令牌（fencing token）。该防护令牌其实就是一个单调递增数字，锁服务在每次锁被授予时，对其进行加一。当存储服务每次收到客户端的请求时，都会要求出示该令牌。

如上图，客户端 1 获得了一个关联了令牌号 33 的租期，但随即经历了长时间的停顿，然后租约过期。客户端 2 获得了一个关联令牌号 34 的租期，并且向存储服务发送了一个附带了该令牌号的写请求。稍后，当客户端 1 结束停顿时，附带令牌号 33 ，给存储服务发送写请求。然而，由于存储服务记下了它处理过更高令牌号（34）的请求，于是它就会拒绝该使用令牌号 33 的请求。这种做法就解决了客户端 1 在长时间停顿并恢复之后，会自认为自己继续持有锁的一个问题。

如果我们使用 ZooKeeper 作为锁服务，那么事务 ID zxid 或者节点版本 cversion 可以用于防护令牌。因为他们单调递增，符合需求。

注意到，该机制要求资源服务自己可以主动拒绝使用过期版本令牌的写请求，也就是说，仅依赖客户端对锁状态进行自检是不够的。对于那些不能显式支持防护令牌检查的资源服务来说，我们仍然可以有一些变通手段（work around，如在写入时将令牌号写到文件路径中），总之，引入一些检查手段是必要的，以避免在锁的保护外执行请求。

这是也某种程度上的真相由多数决定：客户端不能独自确定其对资源的独占性。需要在服务端对所有客户端的情况做一个二次核验。

在服务端检查令牌粗看下是个缺点，但其无疑是个可以言明的优点：默认所有客户端都是遵纪守法并不明智，因为运行客户端的人和运行服务的人具有完全不同的优先考虑点。因此，我们最好在服务端做好防护，使其免受不良客户端的滥用甚至攻击。

4.2 拜占庭错误

防护令牌只能检测并阻止无意（inadvertently，如不知道自己租约过期了）中犯错的客户端。但如果某个客户端节点存心想打破系统约定，可以通过伪造防护令牌来轻易做到。

在本书中我们假设所有参与系统的节点有可能不可靠（unreliable），但一定是诚实的（honest）。

如果系统中的节点有“说谎”（发送任意错误的的或者损坏的信息）的可能性，分布式系统将会变得十分复杂。如，一个节点没有收到某条消息却声称收到了。这种行为称为拜占庭故障（Byzantine fault），在具有拜占庭故障的环境中达成共识也被称为拜占庭将军问题（Byzatine Generals Problem）。

拜占庭将军问题的起源

拜占庭将军问题是两将军问题（Two Generals Problem）的泛化。两将军问题设想了一个需要达成作战计划的战争场景。有两只军队，驻扎在两个不同的地方，只能通过信使来交换信息，但信使有时候会迟到甚至迷路（如网络中的数据包）。第九章会详细讨论这个问题。

在该问题的拜占庭版本，有 n 个将军，但由于中间出了一些叛徒并试图阻扰他们达成共识，他们想达成共识更具难度。但大部分将军仍然是忠诚的，并且会送出真实的消息；与此同时，叛徒会试图通过送出假的或者失实的消息来欺骗和混淆其他人（同时保持隐蔽）。大家事先都不知道谁是叛徒。

如果有一些节点发生故障且不遵守协议，或者恶意攻击者正在扰乱网络，一个系统仍能正确运行，则该系统是拜占庭容错的（Byzantine fault-tolerant）。

举几个需要拜占庭容错的场景例子：

• 在航天环境中，由于高辐射环境的存在，计算机内存或者寄存器中的数据可能会损坏，因此飞控系统必须容忍拜占庭故障；
• 在一个有多方组织参与的系统中，有些参与方可能会尝试作弊或者欺骗别人。在这种环境中，由于恶意消息发送方的存在，无脑的相信其他节点的消息是不安全的。如，类似比特币或者其他区块链的 p2p 网络，就是一种让没有互信基础的多方，在不依赖中央权威的情况下，就某个交易达成共识的一种方法。

对于本书中讨论的大部分系统，我们都可以假设不存在拜占庭故障。让系统进行拜占庭容错的代价和复杂度也都很高。

而且我们无法使用拜占庭容错算法去避免我们的集群去免收安全攻击，因为由于系统不同节点所运行软件的同构性，如果攻击者能够拿下一个节点，那他大概率能拿下所有节点。因此，一些传统的中心防护机制（认证鉴权、访问控制、加密、防火墙等等）仍是让我们免于攻击的主要手段。

4.3 弱的谎言形式

这里就是将拜占庭错误中的主动欺骗弱化成了无意欺骗。

即使我们通常假设节点是诚实的，但为软件加上一些对弱谎言（week forms of lying）的简单防护机制仍然很有用，例如由于硬件故障、软件 bug、错误配置等问题，一些节点可能会发送非法消息。

比如：

• 由于底层的软硬件错误，我们需要在应用层校验字段；
• 可公开访问的应用需要仔细地过滤任何来自用户的输入；
• 可以为 NTP 客户端配置多个 NTP 服务源。更加鲁棒。

4.4 系统模型和现实

4.4.1 系统模型

前人已经设计了很多算法以解决分布式系统的的问题，如我们将要在第九章讨论的共识问题的一些解决方案。这些算法需要能够处理本章提到的各种问题，才能够在实际环境用有用。

在设计算法的时候，不能过重的依赖硬件的细节和软件的配置，这迫使我们对系统中可能遇到的问题进行抽象化处理。我们的解决办法是定义一个系统模型（system model），以对算法的期望会遇到的问题进行抽象。

对于时间的假设，有三种系统模型很常用：

1. 同步模型（synchronous model）。这种模型假设网络延迟、进程停顿和时钟错误都是有界的。但这不是说，时钟时完全同步的、网络完全没有延迟，只是说我们知道上述问题永远不会超过一个上界。但当然，这不是一个现实中的模型，因为在实践中，无界延迟和停顿都会实实在在的发生。
2. 半同步模型（partial synchronous）。意思是在大多数情况下，网络延迟、进程停顿和时钟漂移都是有界的，只有偶尔，他们会超过界限。这是一种比较真实的模型，即在大部分时间里，系统中的网络和进程都表现良好，否则我们不可能完成任何事情。但与此同时，我们必须要记着，任何关于时限的假设都有可能被打破。且一旦出现出现异常现象，我们需要做好最坏的打算：网络延迟、进程停顿和时钟错误都有可能错的非常离谱。
3. 异步模型（Asynchronous model）。在这种模型里，算法不能对时间有任何假设，甚至时钟本身都有可能不存在（在这种情况下，超时间隔根本没有意义）。有些算法可能会针对这种场景进行设计，但很少很少。

除时间问题，我们还需要对节点故障进行抽象。针对节点，有三种最常用的系统模型：

1. 宕机停止故障（Crash-stop faults）。节点只会通过崩溃的方式宕机，即某个时刻可能会突然宕机无响应，并且之后永远不会再上线。
2. 宕机恢复故障（Crash-recovery faults）。节点可能会在任意时刻宕机，但在宕机之后某个时刻会重新上线，但恢复所需时间我们是不知道的。在此模型中，我们假设节点的稳定存储中的数据在宕机前后不会丢失，但内存中的数据会丢失。
3. 拜占庭（任意）故障（Byzantine (arbitrary) faults）。我们不能对节点有任何假设，包括宕机和恢复时间，包括善意和恶意，前面小节已经详细讨论过了这种情形。

对于真实世界，半同步模型和宕机恢复故障是较为普遍的建模，那我们又要如何设计算法来应对这两种模型呢？

4.4.2 算法的正确性

我们可以通过描述算法需要满足的性质，来定义其正确性。举个例子，排序算法的输出满足特性：任取结果列表中的两个元素，左边的都比右边的小。

类似的，我们可以给出描述分布式算法的正确性的一些性质。如，我们想通过产生防护令牌的方式来上锁，则我们期望该算法具有以下性质：

1. 唯一性（uniqueness）：两个不同请求不可能获得具有相同值的防护令牌。
2. 单调有序性（monotonic sequence）：设请求 x 获取到令牌 tx，请求 y 获取到令牌 ty，且 x 在 y 之前完成，则由 tx < ty。
3. 可用性（availability）。锁服务必须是高可用的，我只要向你发送一个请求，你最终应该会回我一个 fencing token。

在某种系统模型下，如果一个算法能够应对该模型下的所有可能出现的情况，并且时刻满足其约束性质，则我们称该算法是正确的。但当然，如果所有节点都宕机了、或网络延迟变得无限长，那么没有任何算法可以正常运作。

4.4.3 安全性和存活性

为了进一步弄清状况，我们需要进一步区分两类不同的属性：安全性（safety）和存活性（liveness）。

• 安全性：上例中的唯一性和单调有序性属于安全属性，可以通俗理解为“没有坏事发生”。
• 存活性：上例中的可用性属于存活性，可以通俗理解为“好的事情最终发生了”。

存活性的定义中通常会暗示“最终”一词，比如最终一致性就是一种存活性。

不要对这些非正式定义太过咬文嚼字，因为所谓的“好”和“坏”都是相对的。安全性和存活性的严格定义都是精确且数学化的，可以参考相关文献。

• 如果违反了安全性，我们一定可以找到一个其被破坏的具体时间点。（如，对于防护令牌算法，如果违反了唯一性，则一定有个某个请求，返回了重复的令牌）一旦违反了安全性，造成的破坏不能被恢复，即破坏是永久的。
• 存活性正好相反，可能在某个时刻不满足（如某节点发出请求，但还没有被收到），但是在将来时刻总会被满足（即最终会收到消息）。

区分安全性和存活性的意义在于，我们可以处理一些复杂的系统模型。对于分布式系统算法，我们通常会比较关注安全性，在系统模型可能触到的各种情况下，安全性都必须满足。即，即使最不利的情况，所有节点都宕机、整个网络都瘫痪，算法也必须要保证安全，不能返回错误结果。

相反，对于存活性来说，我们放宽一些：如我们会说一个请求只有在大多数节点存活、网络最终通畅的情况下才会最终收到请求。半同步模型的定义其实蕴含着，它最终会回到同步状态，即，网络中断只会持续有限时间，终将被修复。

4.4.4 将系统模型映射到真实世界

在衡量分布式系统算法时，安全性、存活性和系统模型都是很有用的工具。但我们在真实世界里去实现一个实际的系统时，无数烦人的细节又都会浮现出来，时刻提醒你，系统模型终究只是对现实一种理想的简化。

比如：

• 宕机恢复模型一般会假设数据存在稳定存储上，在多次宕机重启后不会丢失。但在实践中，如果磁盘数据损坏怎么办？如果固件有 bug 导致重启时无法识别磁盘驱动怎么办？
• Quorum 算法多要求每个节点记住其所声明的内容。如果由于某个节点有“健忘症”，忘记了之前存的数据，就会打破 Quorum 算法的假设，从而破坏该算法的正确性。在这种情况下，我们可能需要一种新的系统模型，能允许节点在宕机重启时偶尔忘点东西，但我们难以推演基于这种模型算法的正确性。

我们在对算法进行理论描述的时候，可以假设一些事情不会发生。比如，在非拜占庭系统中，我们假设对哪些故障会发生、哪些不会做了假设。但在系统实现的代码中，我们通常也会保留处理这些假设之外的极端情况的代码，哪怕处理的很简单，比如打印一些文字：printf("Sucks to be you") 或者使用某个错误号来退出 exit(666)，然后让运维人员来做进一步排查（这种区别也是计算机科学和软件工程的不同之处）。

但这并不是说，理论的、抽象的系统模型毫无价值。事实上，恰恰相反，他能帮助我们将复杂真实的系统，提炼为可处理、可推演的有限故障集。据此，我们可以剖析问题，并进行系统性的解决问题。在特定的系统模型下，只要算法满足特定性质，我们就可以证明算法的正确性。

即使算法被证明是正确的，但在实际环境中，其实现并不一定总能够正确运行。不过，这已经是一个很好地开端了，系统的分析能够很快的暴露算法的问题。而在真实系统中，这些问题只有经过很长时间、当你的假设被某些极端情况打破后才可能发现。理论分析（Theoretical analysis）和实践测试（empirical testing）需要并重。