第 9 章 分布式系统的麻烦

事故是个古怪东西：它不发生时永远不发生；一旦发生，你就摊上了。

—— A. A. 米尔恩，《小熊维尼之家》（1928）

正如第 43 页"可靠性与容错"所讨论的，让一个系统可靠就是要保证：即便出错（即发生故障），系统作为整体仍能继续工作。然而要预想所有可能的故障并妥善处理并不容易。作为开发者，我们很容易只盯着顺利路径（毕竟多数时候一切都正常），而忽视故障——它们引入了一大堆边角情形。

如果你希望系统在故障下仍然可靠，就必须从根本上转变思维：去关注可能出错的事，哪怕它看起来很不可能发生。即便概率只有百万分之一也没关系——在足够大的系统中，这种百万分之一的事件每天都会上演。运维老手都会告诉你：凡是可能出错的事就一定会出错（墨菲定律）。

与单机软件相比，分布式系统在本质上有所不同——主要差别在于：事情可以以诸多新颖且令人瞠目的方式出错 [1, 2]。本章你将领略这些在实践中出现的问题，并搞清楚你究竟能依赖什么、不能依赖什么。

为理解我们要面对的挑战，本章会把悲观情绪开到最大，逐一探讨分布式系统中可能出错的种种情形——网络问题、时钟与时序问题等等。所有这些问题的后果都令人迷茫，因此我们也会讨论该如何思考分布式系统的状态、如何对已发生的事进行推理。第 10 章则会展示在这些事件下实现容错的若干例子。

故障与部分失败

在一台计算机上写程序时，程序通常以相当可预测的方式工作：要么能用、要么不能用。有 bug 的软件可能给人"今天电脑心情不好"的错觉（这种问题往往重启就能修复），但那基本上只是糟糕代码的后果。

单机上的软件没有理由不稳定。硬件正常工作时，相同操作总是产生相同结果（确定性）。一旦硬件出问题（比如内存损坏或接触不良），后果通常是整个系统失效（内核 panic、蓝屏、无法启动等）。一台跑着良好软件的计算机通常要么完全可用、要么彻底坏掉，没有中间态。

这是计算机设计的有意选择：一旦发生内部故障，我们宁愿让计算机彻底崩溃，也不让它返回错误结果——错误结果难以处理且令人困惑。因此计算机刻意隐藏了它所依托的物理现实，呈现出一个理想化的、近乎完美的数学化系统模型：CPU 指令永远做同一件事；写入内存或磁盘的数据保持完整、不会随机损坏。如第 44 页"硬件与软件故障"所述，这其实并不完全成立——数据确实会被悄无声息地损坏、CPU 也偶尔会静默返回错误结果——但这种情况罕见到我们多数时候可以忽略。

可一旦你的程序运行在多台通过网络相连的计算机上，情形就根本不同了。分布式系统里故障要频繁得多，我们再不能视而不见——必须直面物理世界的种种混乱。物理世界什么古怪事都会发生，下面这则轶事便是例证 [3]：

在我有限的经验里，我处理过单数据中心里长时间的网络分区、PDU（配电单元）失效、交换机失效、整个机架意外断电再上电、整个数据中心骨干网失效、整个数据中心断电；甚至还遇到过一位低血糖司机把他的福特皮卡撞进了数据中心的暖通空调系统。而我甚至都还算不上是搞运维的。

—— Coda Hale

在分布式系统里，某些部分可能以不可预知的方式失效，即便其他部分一切正常。这叫部分失败（partial failure）。麻烦在于，部分失败是非确定的：你做任何涉及多节点与网络的事，时而成功时而失败、毫无规律。我们将看到，你甚至无从得知某件事究竟有没有成功！

正是这种非确定性与部分失败的可能性使分布式系统难以驾驭 [4]。但反过来，分布式系统若能容忍部分失败，便能做到许多强大的事——例如滚动升级：一次重启一个节点更新软件，整体仍持续工作。容错让分布式系统比单节点系统更可靠：可以用不可靠的零件构筑可靠的系统。

要实现容错，必须先弄清要容忍哪些故障。我们要把可能的故障——哪怕极其不太可能的——都纳入考虑，并在测试环境中人为制造它们，观察会发生什么。在分布式系统里，怀疑、悲观与偏执都是值得的。

不可靠的网络

过去，老式计算机（如大型机）靠让单个组件冗余来获得可靠性——例如用 RAID 在单盘故障下仍能撑住。如第 51 页"共享内存、共享磁盘与无共享架构"所述，本书关注的分布式系统属于无共享系统：一组通过网络相连的机器。无共享系统不靠单机内的组件冗余，而是通过跨独立机器的复制实现冗余。这些机器只能通过网络相互通信。我们假定每台机器都有自己的内存与磁盘，一台机器无法访问另一台的内存或磁盘（除非通过网络向某服务发请求）。即便存储是共享的（如对象存储），机器之间仍要通过网络与该共享存储服务通信。

互联网与数据中心内部多数网络（通常是以太网）都是异步分组网络。在这种网络里，节点可以向另一节点发送一条消息（数据包），但网络既不保证消息何时到达，也不保证一定能到。如果你发出请求等待回复，可能出错的事情很多（图 9-1 列举了几种）：

• 请求可能丢失（也许有人拔了网线）。
• 请求可能在队列里等待，稍后才送达（也许网络或接收端过载）。
• 远端节点可能已失效（崩溃或断电）。
• 远端节点可能暂时不响应（也许正在经历漫长的 GC 暂停；见第 366 页"进程暂停"），稍后又恢复。
• 远端节点其实已处理了请求，但响应在网络上丢失（也许某交换机配置错误）。
• 远端节点已处理请求，但响应被延迟、稍后才送达（也许网络或你自己的机器过载）。

图 9-1. 发出请求却得不到回应时，无法区分（a）请求丢失、（b）远端节点已挂、（c）响应丢失。 发送方甚至无从判断数据包是否被送达。唯一的方法是接收端发回响应消息——而响应消息同样可能丢失或延迟。在异步网络里这些情形彼此无法区分；你掌握的唯一信息就是"还没收到响应"。如果你向另一节点发请求却没收到响应，不可能得知原因。

处理这一问题的通常做法是超时：等待一段时间后放弃，并假定响应不会再来了。但超时发生时你仍不知道远端节点是否收到了请求（请求若还卡在某个队列里，即便你已放弃，它最终仍可能被送达）。

TCP 的局限

网络数据包有最大尺寸（一般几千字节），但许多应用需要发送超出单包容量的消息（请求、响应）。这些应用最常使用 TCP（传输控制协议）建立连接，把大数据流切成一个个数据包，并在接收端拼回完整数据。

这里对 TCP 的描述大多也适用于较新的替代品 QUIC，以及 WebRTC 中使用的 SCTP（流控制传输协议）、BitTorrent 的 uTP 等传输协议。与 UDP 的对比见第 354 页"TCP vs UDP"。

TCP 通常被描述为提供"可靠"投递：检测并重传丢失的数据包、检测乱序并将其放回正确顺序、用简单校验和发现包损坏。它还会自动决定发送速率，让数据尽快传输又不至于压垮网络或接收节点；这叫拥塞控制、流量控制或背压[5]。

写到 socket 的数据并不会立刻被发出，而是先放入操作系统管理的缓冲区。当拥塞控制算法判断有容量可发包时，便从缓冲区取一包数据交给网络接口。包经过若干交换机与路由器，最终到达接收节点；接收方的操作系统把它放入接收缓冲区，并向发送方回送一个确认包。直到此时，接收方操作系统才通知应用又有数据到达。

那么 TCP 的"可靠性"是不是意味着我们就不必担心网络不可靠了呢？遗憾的是不能。TCP 在某段超时后未收到确认便判定包已丢失，但无法分辨究竟是发出的包丢了，还是确认丢了。它会重发，但无法保证重发的包一定能到达（网线被拔了，它也替你插不回去）。最终若可配置超时仍未确认，它就向应用报错放弃。此外 TCP 的去重与重传只对单条连接有效；应用若重连后再发，数据仍可能重复。

如果一条 TCP 连接异常关闭——也许是远端节点崩溃或网络中断——你便无从得知远端实际处理了多少数据 [6]。即便收到了某包的送达确认，那也只代表远端节点的操作系统内核收到，应用可能还没处理这段数据就崩溃了。要确信请求真正成功，你需要应用本身的肯定回应 [7]。

不过 TCP 仍十分有用，因为它提供了一种方便的方式来收发超出单包容量的消息。建立 TCP 连接后，你也可以在其上发送多个请求与响应。常见做法是先发一段表明后续消息字节数的头部，再发实际消息。HTTP 与许多 RPC 协议（见第 180 页"通过服务的数据流：REST 与 RPC"）便是如此。

实践中的网络故障

人类建造计算机网络已有数十年——按理说到今天我们应该早已搞清楚怎样让它们可靠了。可惜并没成功。一些系统性研究及大量轶事证据表明，网络问题远比预想常见，即便在受控环境（如某公司自营的数据中心）下也是如此 [8]：

• 一项针对中型数据中心的研究发现，每月约出现 12 次网络故障，其中半数让一台机器掉线，半数让一整机架掉线 [9]。
• 另一项研究测量了机架顶交换机、汇聚交换机、负载均衡器等组件的故障率 [10]，结果是：增加冗余网络设备并不能像你想的那样大幅减少故障，因为它无法防御人为失误（如交换机配错），而人为失误才是宕机的主要原因。
• 长途光纤链路中断曾被归咎于奶牛 [11]、海狸 [12] 与鲨鱼 [13]（不过随着海底电缆屏蔽改进，鲨鱼咬伤已经少了 [14]）。人也常出问题——配置失误 [15]、盗窃废金属 [16]、乃至蓄意破坏 [17]。
• 跨云区域往返时间的高百分位曾出现过持续数分钟的记录 [18，表 3]。即便在单个数据中心内，软件升级触发交换机网络拓扑重配置时也可能出现一分钟以上的包延迟 [19]。因此我们必须假定消息可能被任意延迟。
• 通信有时会出现部分中断——结果取决于你在和谁通信：例如 A 与 B 能通、B 与 C 能通、唯独 A 与 C 不通。其他出人意料的故障还有：网络接口有时丢弃所有入站包但出站照常 [22]；某条链路在一个方向工作并不保证反方向也工作。
• 即便短暂的网络中断也可能引发远超原始问题的连锁反应 [8, 20, 23]。

哪怕你的环境中网络故障少见，光是它可能发生这一事实就意味着你的软件必须能处理它们。只要通信走过网络，它就可能失败——别无他法。

网络分区

网络分区（network partition，又称 netsplit）这一术语有时用来描述网络故障导致网络的某一部分与其余部分被切断的情形。本质上它与其他网络中断没有什么不同；它也与存储系统中的"分片"（也叫 partitioning，见第 7 章）是两码事。

如果对网络故障的处理没有明确定义并经过测试，就可能发生各种糟糕的后果——例如集群陷入死锁，即便网络已恢复也再无法服务请求 [24]；又或者把你的数据全删掉 [25]。软件一旦被置于未曾预料的处境，就可能做出任意意料之外的举动。

处理网络故障不一定意味着容忍：如果你的网络通常相当可靠，一种可行做法是网络出问题时直接给用户报错。但你必须知道软件会如何应对网络问题，并确保系统能从中恢复。故意制造网络问题来检验系统响应往往是值得的（见第 385 页"故障注入"）。

故障检测

许多系统需要自动检测有故障的节点。例如：

• 负载均衡器需要停止把请求发给已死的节点（也就是把它摘除）。
• 在采用单主复制的分布式数据库中，如果主节点失效，就需要把某个从节点提升为新主（见第 204 页"处理节点宕机"）。

可惜网络的不确定性使得"判断节点是否在工作"变得困难。在特定情境下你或许能拿到某种明确反馈，告诉你某件事不工作：

• 如果你能到达节点应当运行的那台机器，但目标端口上没有进程在监听（比如进程崩溃了），操作系统会贴心地用 RST 或 FIN 包关闭或拒绝该 TCP 连接。
• 如果节点上的进程崩溃（或被管理员杀掉），但节点的操作系统仍在运行，脚本可以把崩溃事件通知其他节点，让另一节点迅速接管，而不必等超时过期。HBase 就是这么做的 [26]。
• 如果你能访问数据中心交换机的管理界面，可以查询它们以在硬件层检测链路故障（如远端机器断电）。但当你通过公网连接、或在共享数据中心里接触不到交换机、或因网络问题进不了管理界面时，这条路就走不通。
• 如果路由器确定你想连的 IP 不可达，它可能回送 ICMP 目的不可达包。不过路由器自己也没什么神奇的故障检测能力；它与网络中其他参与者一样，受到同样的限制。

关于远端节点已挂的快速反馈固然有用，但不能指望。即便出错，也只是某层栈可能给出错误响应；通常你必须做最坏假设——根本不会得到响应。你可以重试若干次、等超时过期，最终若在超时前仍未听到回音就宣告该节点已死。由于节点也可能其实仍活着，你需要在误报与漏报之间权衡：超时设得太短会误把活着的节点当作死的；超时太长又要白等真正已死的节点。

超时与无界延迟

如果超时是检测故障的唯一可靠手段，超时究竟该多长？很遗憾没有简单答案。

长超时意味着要等很久才能宣告节点已死（这段时间用户可能要等待或看到错误）。短超时检测故障更快，却更容易把节点错判为已死——它可能只是临时变慢（如节点或网络上出现负载尖峰）。

过早宣告节点已死会带来问题。如果节点其实活着、还在做某件事的半途中（如发邮件），另一节点接管后，这件事可能被执行两次。第 371 页"知识、真理与谎言"以及第 10、12 章会更详细讨论这一问题。

宣告某节点已死时，它的职责需要转移到其他节点，给其他节点和网络增加额外负载。系统若本就处于高负载下，过早宣告死亡只会让问题雪上加霜。一个尤其常见的情形是：节点其实没死，只是因过载而响应变慢；把它的负载又转给其他节点，可能引发级联失效（极端情况下所有节点互相宣告对方已死，整个系统停摆——见第 38 页"过载系统不会自我恢复"）。

设想一个虚构系统：网络保证数据包的最大延迟——每个包要么在时间 d 内送达、要么丢失，绝不会超过 d。再假设健康节点总能在时间 r 内处理完请求。那么每次成功的请求都能在 2d + r 内拿到响应——若没在该时间内收到响应，就一定是网络或远端节点出了问题。这一前提下，2d + r 就是合理的超时值。

可惜我们日常使用的系统大多没有这两种保证：异步网络有无界延迟（它们尽量快传，但没有上限），多数服务器实现也无法保证在某最大时间内处理完请求（见第 369 页"提供响应时间保证"）。对故障检测而言，"系统大多数时候很快"还不够：超时若设得过低，偶发的往返时间尖峰就会让系统失衡。

网络拥塞与排队

开车时，路网上的行车时间变化最大的因素往往是交通拥堵。计算机网络中数据包延迟的变化也最常源于排队 [27]：

• 如果多个节点同时向同一目的地发包，网络交换机就必须把它们排队，再逐个送入目标网络链路（见图 9-2）。在繁忙链路上，包可能要等一会儿才能轮到（这就是网络拥塞）。一旦入流量大到塞满交换机队列，包会被丢弃，必须重发——尽管网络本身仍在工作。
• 包到达目的机器时，若所有 CPU 核或应用线程都在忙，入站请求就会被操作系统排队，等应用准备好后再处理。视机器负载而定，等待时间可以任意长 [28]。
• 在虚拟化环境中，运行中的操作系统常常会被暂停几十毫秒——因为另一个虚拟机正在使用某 CPU 核。这段时间里 VM 无法处理任何网络数据，入站数据被 VM 监视器排队缓冲 [29]，进一步加剧网络延迟的波动。
• 前面提到过，TCP 会限制发送速率以避免让网络过载，这意味着数据在进入网络前已经在发送端排过一次队。

图 9-2. 若多台机器向同一目的地发流量，交换机队列可能被塞满。图中端口 1、2、4 都试图把包发到端口 3。 此外，TCP 检测到丢包并自动重传时，应用看不到丢失本身，却能感受到由此产生的延迟（等待超时过期、再等重传包被确认）。

TCP vs UDP

一些对延迟敏感的应用（如视频会议、VoIP）使用 UDP 而非 TCP。这是在可靠性与延迟波动之间作的取舍：UDP 不做流控、也不重传丢包，因此规避了部分延迟波动来源（不过它仍受交换机排队与调度延迟影响）。

当延迟到的数据已无价值时，UDP 就是好选择。例如 VoIP 通话中，等重传包送到时也许已经过了应当播放的时刻；这种情况下重传毫无意义——应用只能用一段静音填补缺失包对应的时槽（造成声音短暂中断），然后继续流。重试由人来完成（"刚才能再说一遍吗？声音卡了一下。"）。

网络延迟的变异

所有这些因素都会影响网络延迟的波动。当系统接近最大容量时，排队延迟的变化尤其剧烈：容量充裕的系统能轻松排空队列，而高利用率系统中长队列会迅速堆积。

公有云与多租户数据中心中资源由众多客户共享：网络链路与交换机、每台机器的网络接口、运行 VM 时的 CPU 都是共享的。大量数据处理可能把网络链路占满（饱和）。由于你既无从控制也看不到他人的资源使用情况，若附近有人（所谓吵闹的邻居）用得很凶，网络延迟就可能极不稳定 [30, 31]。

这种环境下，超时只能凭经验确定：长期、跨多台机器测量网络往返时间的分布，了解预期的延迟波动；再结合应用特性，权衡故障检测延迟与过早超时的风险。

更好的办法是不用固定的常量超时，而让系统持续测量响应时间及其变化（抖动），并依据观察到的分布自动调整超时。Phi Accrual 故障检测器 [32]（被 Akka 与 Cassandra 采用 [33]）就是这样做的；TCP 的重传超时也类似 [5]。

同步网络与异步网络

如果网络能保证把数据包以固定的最大延迟送达、不丢包，分布式系统会简单得多。那为什么不能在硬件层面解决这一问题，让网络可靠到软件无须操心呢？

要回答这个问题，不妨把数据中心网络与传统固定电话网络（非蜂窝、非 VoIP）做个对比——后者极其可靠：延迟音频帧或掉线极少发生。打电话要求持续低延迟以及足够带宽来传输音频样本。要是计算机网络也有类似的可靠与可预测性那该多好。

打电话时网络会建立一条电路：通话路径上预留出固定带宽，并一直保持到通话结束 [34]。例如 ISDN 网络以 4000 帧/秒的固定速率运行；通话建立后，每个方向每帧分配 16 比特空间。因此整个通话期间，双方都被保证每 250 微秒可以发送 16 比特音频数据。

这种网络是同步的：即便数据穿过若干路由器，也不受排队影响，因为通话占用的下一跳 16 比特早已预留。没有排队就意味着网络的端到端最大延迟是固定的。我们称之为有界延迟。

我们能不能让网络延迟可预测？

请注意，电话网络中的电路与 TCP 连接相当不同：电路占用一份固定的预留带宽，连接期间无人能用；而 TCP 连接里的包则机会主义地利用任何可用带宽。你可以丢给 TCP 一段任意大小的数据（如一封邮件或一张网页），它会尽快把它传完。TCP 连接空闲时不占任何带宽（除了偶尔的 keepalive 包）。

如果数据中心网络与互联网是电路交换式的，那么建立电路时就能给出确定的最大往返时间保证。但事实并非如此：以太网与 IP 是分组交换协议，受排队之苦，因此网络延迟是无界的。这些协议根本没有电路这一概念。

数据中心网络与互联网为什么采用分组交换？答案是它们针对突发流量做了优化。电路适合音视频通话，整段时间内需要传输相对恒定数量的比特；而请求网页、发邮件、传文件没有特定的带宽需求——我们只希望它尽快完成。

如果用电路来传文件，你得估一个带宽分配：估低了传输会无谓变慢，留下网络容量未被利用；估高了电路根本建立不起来（网络无法承诺它无法保证的带宽）。相比之下，TCP 会把数据传输速率动态适配到可用网络容量上。

延迟与资源利用

更一般地，可变延迟可以看作动态资源分配的结果。

假设两台电话交换机之间有一根线缆（或光纤）至多能承载 10000 路并发通话，每路过线的电路占用一个槽位。这样这根线缆就相当于一种最多能被 10000 个用户同时共享的资源，且采用静态分配方式：哪怕你是当前唯一的通话者、其余 9999 个槽位都空着，你的电路仍占用同样固定的带宽。

互联网则是动态共享网络带宽。发送方互相争抢，希望尽快把包推过去，网络交换机时时刻刻决定下一个发哪个包（即如何分配带宽）。这种做法有排队的副作用，但好处是把线缆利用率最大化。线缆成本固定，利用率越高，每字节传输的成本就越低。

类似情形也出现在 CPU 上。多线程动态共享 CPU 核时，某个线程有时要在操作系统运行队列里等另一线程，可能被暂停不定时间 [36]。但这比给每个线程静态分配固定 CPU 周期更能充分利用硬件（见第 369 页"提供响应时间保证"）。多租户云平台在同一物理机上跑多个客户的 VM，也是出于更好利用硬件的考虑。

在采用静态资源分区（如专用硬件、独占带宽预留）的环境中可以做到延迟保证，代价是利用率下降——也就是更贵。相反，多租户配合动态资源分配能获得更高利用率与更低成本，代价则是延迟变得不可预测。

网络中的可变延迟并非自然法则，而是成本/收益权衡的结果。

结合电路与包交换

人们也尝试过构建同时支持电路与分组交换的混合网络。1980 年代的异步传输模式（ATM）曾是以太网的竞争对手，但除了电话网核心交换之外并未广泛普及。InfiniBand 与之有些相似 [37]：它在链路层实现端到端流控，减少了网络内部排队的需要，但链路拥塞时仍可能引起延迟 [38]。

通过精心使用服务质量（QoS）机制（如包优先级与调度）与接纳控制（限制发送方速率），可以在分组网络上模拟电路交换，或提供统计意义上有界的延迟 [27, 34]。Low Latency, Low Loss, and Scalable Throughput（L4S）等新算法尝试在客户端与路由器层面缓解排队与拥塞控制问题。Linux 的流量控制器（TC）也允许应用为 QoS 重设包优先级。

可惜在多租户数据中心、公有云或跨互联网通信时，这些 QoS 机制目前并未启用。当前部署的技术不能对网络延迟或可靠性做出保证，我们只能假定网络拥塞、排队与无界延迟都会发生——超时没有"正确"值，只能凭经验摸索。

互联网服务提供商之间的对等协议以及通过 BGP 建立的路由更接近电路交换，而非典型 IP 包路由——你可以在这一层面购买专用带宽。但互联网路由发生在网络级别而非主机之间，时间尺度也长得多。

不可靠的时钟

时钟与时间很重要。应用以多种方式依赖时钟，回答下列问题：

1. 该请求超时了吗？
2. 这个服务的 99 百分位响应时间是多少？
3. 过去 5 分钟内该服务平均每秒处理多少查询？
4. 用户在我们网站花了多长时间？
5. 这篇文章何时发表？
6. 提醒邮件应在何日何时发送？
7. 这条缓存项何时过期？
8. 日志文件里这条错误消息的时间戳是什么？

问题 1–4 度量持续时间（如请求发出与响应到达之间的时间间隔），问题 5–8 描述时间点（在某个特定日期、特定时间发生的事件）。

分布式系统中时间是一件棘手事，因为通信并非瞬时——消息从一台机器穿网络到达另一台需要时间。消息被接收的时刻总是晚于被发送的时刻，但由于网络延迟可变，我们并不知道晚了多少。这一事实使得多机协作时确定事件发生的先后变得相当困难。

此外，网络上每台机器都有自己的时钟——一种硬件设备，通常是石英晶振。这种设备并不完全精准，因此每台机器对"当前时间"都有自己的看法，可能比其他机器稍快或稍慢。在一定程度上可以让时钟同步；最常用的机制是网络时间协议（NTP），让计算机时钟根据一组服务器报告的时间进行调整 [39]，而这些服务器又从更精准的时源（如 GPS 接收器）取时。

单调时钟与时刻时钟

现代计算机至少有两种时钟：时刻时钟与单调时钟。两者都测量时间，但用途不同，必须区分。

时刻时钟

时刻时钟做的就是你直觉上想到的事：按日历返回当前日期与时间（也叫墙钟时间）。例如 Linux 的 clock_gettime(CLOCK_REALTIME)、Java 的 System.currentTimeMillis 返回自纪元（1970-01-01 UTC 午夜，按格里高利历，不含闰秒）以来的秒数或毫秒数；某些系统用其他日期作参考点。（Linux 的 CLOCK_REALTIME 与实时操作系统毫无关系，详见第 369 页"提供响应时间保证"。）

时刻时钟通常通过 NTP 同步——理想情况下，一台机器的时间戳与另一台是同义的。然而它有种种怪癖（下一节会讲）。特别是若本地时钟比 NTP 服务器领先得太多，它可能被强制回拨到较早时刻；这种跳变以及闰秒带来的类似跳变，使时刻时钟不适合用来测量时间间隔 [40]。

时刻时钟也会受夏令时启停影响，但只要统一使用 UTC（无 DST）就能避免。历史上这种时钟分辨率粗糙（如旧 Windows 系统以 10 ms 步进 [41]）；近期的系统问题不大。

单调时钟

单调时钟适合用来测量持续时间（时间间隔），如超时或服务响应时间；例如 Linux 的 clock_gettime(CLOCK_MONOTONIC) 或 clock_gettime(CLOCK_BOOTTIME)、Java 的 System.nanoTime 都使用单调时钟来测量时间。名字源于这种时钟保证只向前走（而时刻时钟可能回跳）。

你可以在某时点读一次单调时钟、做点事、再读一次，两值之差就是这两次读取之间经过的时间——它更像一只秒表，而不是日历钟。但单调时钟的绝对值毫无意义：可能是开机以来的纳秒数或类似的任意值。比较两台计算机的单调时钟值更是毫无意义，因为它们各自定义不同。

在多 CPU socket 的服务器上，每个 CPU 可能各有计时器，彼此未必同步 [43]。操作系统会补偿这一差异，对应用线程呈现一个单调视图——即使线程被调度到不同 CPU 上也是如此。但对这种单调性保证最好留一份戒心 [44]。

NTP 可以调整单调时钟前进的频率（若检测到本地石英比 NTP 服务器快或慢）——这一过程称为 slewing。默认 NTP 允许时钟速率被加快或放慢至多 0.05%，但不会让单调时钟向前跳或向后跳。单调时钟的分辨率通常相当不错：多数系统能测量微秒乃至更细的间隔。

分布式系统中用单调时钟测量经过时间（如超时）通常很合适——它不要求节点之间时钟同步，也对小幅测量误差不敏感。

时钟同步与精度

单调时钟不需要同步，但时刻时钟若要发挥用处，必须按 NTP 服务器或其他外部时源对齐。可惜，让时钟正确报时的方法远没你期望的那么可靠或精准——硬件时钟与 NTP 都可能令人头疼。举几例：

• 典型计算机的石英时钟并不很准：会发生漂移（比应有的速率快或慢）。漂移程度受机器温度影响。Google 假设其服务器时钟最大漂移为 200 ppm（百万分之二百）[45]，这相当于：每 30 秒重同步一次的时钟有 6 ms 漂移；每天重同步一次的时钟有 17 秒漂移。即便一切正常，这一漂移也限制了可达到的精度。
• 如果计算机时钟与 NTP 服务器差距太大，它可能拒绝同步或被强制重置 [39]。任何观察这台机器的应用，在重置前后可能看到时间倒退或突跳。
• 节点意外被防火墙挡住而联系不上 NTP 服务器时，这种配置错误可能一段时间内不被察觉；期间漂移会持续积累，最终与其他节点产生很大差异。轶事证据表明这种事在实践中确实发生过。
• NTP 同步精度受网络延迟限制，因此在拥塞、包延迟可变的网络下精度受限。一项实验显示通过互联网同步最佳可达约 35 ms 误差 [46]，偶尔的网络延迟尖峰会让误差升到 1 秒左右。视配置不同，大网络延迟还可能让 NTP 客户端干脆放弃。
• 一些 NTP 服务器自身有错或配置错误，报告的时间偏差几个小时 [47, 48]。NTP 客户端会查询多个服务器并忽略离群值以缓解，但把系统正确性赌在素未谋面的服务器上，仍让人不无忧虑。
• 闰秒导致一分钟出现 59 或 61 秒，这会扰乱未考虑闰秒的系统的时序假设 [49]。事实上闰秒已让多个大型系统崩过 [40, 50]，说明关于时钟的错误假设很容易潜入系统。处理闰秒最佳的做法是让 NTP 服务器"撒谎"，把闰秒在一整天里渐进涂抹掉（即所谓 smearing）[51, 52]，但实际中各家 NTP 服务器的做法五花八门 [53]。从 2035 年起将不再使用闰秒，因此这一问题幸运地终将消失。
• VM 中硬件时钟是虚拟化的，给需要精确计时的应用带来额外挑战 [54]。CPU 核在多个 VM 间共享时，每个 VM 在其他 VM 运行期间会被暂停几十毫秒；从应用看，仿佛 VM 一恢复运行时钟就突然向前跳 [29]。VM 内的 NTP 客户端并不知道发生了暂停，可能错报时钟精度 [55]。
• 在你无法完全控制的设备（手机、嵌入式设备等）上，硬件时钟基本不可信任：有些用户故意把设备硬件时钟设到错误日期时间（如游戏作弊）[56]。结果，时钟可能严重偏离正确时间。

只要你足够在意并愿意投入资源，达到非常高的时钟精度是可能的。例如欧盟金融监管法规 MiFID II 要求所有高频交易机构的时钟与 UTC 同步到 100 微秒以内，以便调试市场异常（如"闪崩"）并侦测市场操纵 [57]。

这种精度可以借助专用硬件（GPS 接收器和/或原子钟）、精确时间协议（PTP）以及精心的部署与监控来实现 [58, 59]。仅靠 GPS 风险较高，因为 GPS 信号容易被干扰；在某些地区（如军事设施附近）这种事时有发生 [60]。一些云厂商已开始为虚拟机提供高精度时钟同步 [61]，但时钟同步仍需谨慎对待——一旦 NTP 守护进程配置出错或防火墙挡住了 NTP 流量，由漂移积累而成的时钟误差很快就会变大。

依赖同步时钟

时钟的问题在于：它们看起来简单易用，却暗藏诸多陷阱。一天未必恰好 86400 秒；时刻时钟可能向后跳；一节点的时间与另一节点的时间也可能截然不同。

本章前面讨论过网络丢包与任意延迟。即便网络多数时候表现良好，软件也必须按"网络偶尔会出问题"来设计，并优雅地处理这些故障。时钟也是一样：尽管它们多数时候工作得相当好，但稳健的软件必须为时钟出错做好准备。

部分难处在于错误时钟很容易被忽视。机器 CPU 有缺陷或网络配错，多半压根就不工作，问题会很快被发现并修复；但石英晶体出问题或 NTP 客户端配错时，多数事情看上去仍正常运行，时钟却在逐渐偏离真实时间。一段依赖精确同步时钟的软件，更可能因此悄无声息地丢失数据，而不是戏剧性地崩溃 [62, 63]。

因此，如果你使用要求同步时钟的软件，就必须仔细监控集群所有机器间的时钟偏差。任何时钟与其他节点偏离过远的节点都应被宣告失效并移除。这种监控让你能在错误时钟造成太多损害之前及时察觉。

用时间戳为事件排序

下面看一个依赖时钟看似诱人却危险的场景：跨多节点为事件排序 [64]。比如两个客户端同时写一个分布式数据库——谁先到？哪一次写更新？

图 9-3 演示了在多主复制数据库中危险地使用时刻时钟（与图 6-8 类似）：客户端 A 在节点 1 上写入 x = 1；写被复制到节点 3；客户端 B 在节点 3 上自增 x（此时 x = 2）；最后两次写都被复制到节点 2。如图所示，写在被复制到其他节点时附带的是其发生节点的时刻时钟时间戳。例子中时钟同步很好；节点 1 与节点 3 的偏差小于 3 ms，已经比实践中通常水平更好。

由于自增建立在 x = 1 这次写之上，我们本期望写 x = 2 的时间戳更大。可惜图 9-3 中并非如此：写 x = 1 的时间戳是 42.004 秒，写 x = 2 的时间戳却是 42.003 秒——也就是说，客户端 B 的写在因果上晚于客户端 A 的写，时间戳却更小。

图 9-3. 依赖时间戳为事件排序，在时刻时钟同步不完美时会出问题。 如第 222 页"处理写入冲突"所述，解决不同节点上并发写入冲突的常见办法是 LWW（后写胜出）——对同一键保留时间戳最大的写、丢弃更旧的。图 9-3 中节点 2 收到这两个事件后会错误地认定 x = 1 更新，丢弃 x = 2——自增就这样丢失了。

可以加一道防线：覆盖某值时，新值的时间戳必须大于被覆盖值的时间戳，即便那需要把时间戳设得超前于写者本地时钟。但这要求多一次读以查找当前最大时间戳。某些系统（如 Cassandra 与 ScyllaDB）为省去这次额外往返，索性直接采用客户端时钟时间戳配合 LWW [62]。这种做法存在若干严重问题：

• 数据库写入可能神秘地消失：时钟落后的节点无法覆盖时钟更快节点先前写入的值，直到节点间的时钟偏差超过过期时间 [63, 65]。这种情形会导致任意数量的数据被无声地丢弃，而应用却收不到任何错误。
• LWW 无法区分时间上紧接着发生的顺序写入（如图 9-3 中客户端 B 的自增明显发生在客户端 A 的写之后）与真正的并发写入（双方都不知道对方）。要避免违反因果，需要额外的因果跟踪机制，例如版本向量（见第 237 页"检测并发写入"）。
• 两个节点可能独立产生时间戳相同的写入，尤其当时钟分辨率只到毫秒时；这就需要额外的破平值（可以是一个大随机数）来打破平局，但这种做法也可能违反因果 [62]。

因此，尽管"用'最近'的值覆盖、丢弃其他"这种冲突解决方式很有诱惑力，但你必须清楚："最近"的定义建立在本地时刻时钟之上，而它很可能并不正确。即便 NTP 同步紧密，你也可能在时间戳 100 ms（以发送方钟计）发出一个包，而它在时间戳 99 ms（以接收方钟计）到达——看上去包居然在发出之前就抵达了，这显然不可能。

NTP 同步能否精确到让这种错乱不再发生？基本不能。因为 NTP 同步精度本身受网络往返时间限制，再叠加石英漂移等误差源。要保证顺序正确，时钟误差就必须远小于网络延迟，而这并不现实。

所谓逻辑时钟[66]——基于自增计数器而非震荡石英——是为事件排序的更安全替代（见第 237 页"检测并发写入"）。逻辑时钟不测真实时间或经过秒数，只反映事件之间的相对顺序（一个事件早于还是晚于另一个）。相对地，测量真实经过时间的时刻时钟与单调时钟则称为物理时钟。第 417 页"ID 生成器与逻辑时钟"会更详细讨论逻辑时钟。

带置信区间的时钟读

你也许能从机器的时刻时钟读到微秒、甚至纳秒分辨率，但能读到这么细的数值，并不意味着它真的精确到那个分辨率——多半远没有这么准。前面提过，一台未精校的石英时钟即便每分钟和本地 NTP 服务器同步一次，也很容易出现几毫秒的漂移；用公网 NTP 服务器最好情况也就几十毫秒，网络拥塞时误差还能轻松冲过 100 ms。

因此，把时钟读取当作"一个时间点"是没意义的。它更像一个时间范围、一段置信区间——比如系统可能 95% 确信现在时间在过 X 分 10.3 到 10.5 秒之间，但更精确就不知道了 [67]。如果我们只知道时间在 ±100 ms 范围内，时间戳里的微秒位就基本没意义。

不确定区间可以根据时源推算。如果你有 GPS 接收器或原子钟直接接到电脑上，预期误差范围由设备厂商给出（GPS 还要看卫星信号质量）；若是从服务器取时间，则需把自上次同步以来的预期石英漂移、NTP 服务器自身的不确定、再加上到该服务器的网络往返时间相加（粗略计算，且假设你信任该服务器）。

可惜大多数系统并不暴露这种不确定性。例如调用 clock_gettime 时，返回值并不告诉你时间戳的预期误差，因此你既不知道置信区间是 5 毫秒还是 5 年。

也有例外：Google Spanner 的 TrueTime API [45] 与 Amazon 的 ClockBound 都显式报告本地时钟的置信区间。查询当前时间会返回一对值：[earliest, latest]，分别表示最早与最晚可能的时间戳。基于这一不确定度计算，时钟知道实际的当前时间位于这一区间之内。区间宽度取决于多个因素，例如本地石英自上次与更精准时源同步以来过了多久。

用同步时钟做全局快照

第 293 页"快照隔离与可重复读"讨论过 MVCC：它能让数据库同时支持小而快的读写事务，以及长时间运行的只读事务（如备份或分析），非常有用。MVCC 让只读事务看到数据库某一时刻的快照——一致状态——而无需加锁、也不阻塞读写事务。

通常 MVCC 需要单调递增的事务 ID。如果某次写发生在快照之后（即其事务 ID 比快照大），快照事务就不该看到该写。在单节点数据库里，简单的计数器就足以生成事务 ID。

但当数据库分布在多台机器、甚至跨多个数据中心时，全局单调递增的事务 ID（跨所有分片）就很难生成，因为需要协调。事务 ID 还必须反映因果：若事务 B 读取或覆盖了事务 A 写入的值，则 B 的事务 ID 必须更大——否则快照就不一致。在小而快的事务大量出现的场景下，分布式生成事务 ID 会成为难以承受的瓶颈（这类 ID 生成器将在第 417 页"ID 生成器与逻辑时钟"中讨论）。

我们能否把同步过的时刻时钟时间戳直接当事务 ID 用？只要同步够好，时间戳就具备所需性质：较晚的事务时间戳更大。问题在于时钟精度的不确定性。

Spanner 就是这样跨数据中心实现快照隔离的 [68, 69]。它利用 TrueTime API 报告的置信区间，基于以下观察：若有两个置信区间，每个由一对最早与最晚时间戳给出（A = [A_earliest, A_latest]，B = [B_earliest, B_latest]），且两区间不重叠（即 A_earliest < A_latest < B_earliest < B_latest），那么 B 必然发生在 A 之后——毫无疑问。只有当区间重叠时，我们才无法判定 A、B 的顺序。

为确保事务时间戳反映因果，Spanner 在提交读写事务前会故意等待一个置信区间的长度。这样，任何可能读到该数据的事务的时间都足够晚，置信区间不会与之重叠。为让等待尽量短，Spanner 必须把时钟不确定度压得尽量小；为此 Google 在每个数据中心都部署了 GPS 接收器或原子钟，把时钟同步到约 7 ms 之内 [45]。

原子钟与 GPS 接收器对 Spanner 来说并非严格必需，关键在于有置信区间——精准时源只是帮助把这一区间保持得小。其他系统也开始采用类似方法——例如 YugabyteDB 在 AWS 上可利用 ClockBound [70]；另有若干系统在不同程度上依赖时钟同步 [71, 72]。

进程暂停

下面再看一个分布式系统中危险使用时钟的例子。假设你有一个数据库，每个分片有一个单一主节点，只有主节点能接受写。某节点如何知道自己仍是主（未被他人宣告已死）、可以安全接受写？

一种做法是让主节点从其他节点处获取租约，相当于带超时的锁 [73]：任一时刻只能有一个节点持有租约，因此节点拿到租约后就知道自己在某段时间内是主，直到租约到期。要继续做主，节点必须在租约到期前周期性续约。如果节点失效、停止续约，另一节点便可在租约到期后接管。

请求处理循环大致可以这样写：

while (true) {
    request = getIncomingRequest();

    // 确保租约始终至少剩 10 秒
    if (lease.expiryTimeMillis - System.currentTimeMillis() < 10000) {
        lease = lease.renew();
    }

    if (lease.isValid()) {
        process(request);
    }
}

这段代码有什么问题？首先，它依赖同步时钟：租约的过期时间由另一台机器设置（如当前时间加 30 秒），却要与本地系统时钟比较。如果两边时钟相差几秒，这段代码就会出怪事。

其次，即便我们改协议、只用本地单调时钟，仍有另一个问题：代码假设从检查时间（System.currentTimeMillis()）到处理请求（process(request)）之间经过的时间很短。通常这段代码跑得很快，10 秒缓冲足以保证请求处理中途租约不会过期。

但程序执行中如果突然出现意料之外的暂停呢？比如线程在 lease.isValid 那行附近停了 15 秒才继续。这种情况下，请求被处理时租约多半已过期，另一节点已接管成主。然而没有任何机制告诉当前线程它被暂停了那么久，因此代码不会察觉租约过期——直到循环下一次迭代，但那时它可能已经做了不安全的事。

线程被暂停这么长真的合理吗？遗憾的是，是的，原因可能是：

• 对共享资源（如锁或队列）的争用可能让线程花大量时间等待——CPU 核数多的机器上往往更糟，且竞争问题难以诊断 [74]。
• 许多编程语言运行时（如 JVM）带有垃圾回收器，偶尔会停掉所有运行中的线程。过去这种"stop-the-world" 式 GC 暂停甚至能持续数分钟 [75]！现代 GC 算法已大幅改进，但 GC 暂停仍可察觉（见第 370 页"限制 GC 影响"）。
• 虚拟化环境下，VM 可以被挂起（停下所有进程并把内存写入磁盘）和恢复（重新加载内存继续运行）。这种暂停可在进程执行的任何时刻发生、持续任意时长。这一特性有时用于在不重启的情况下把 VM 从一台主机热迁移到另一台，暂停时长取决于进程写内存的速率 [76]。
• 在终端用户设备（笔记本、手机）上，执行也可能被任意暂停与恢复（比如用户合上笔记本盖子）。
• 操作系统切换上下文到另一线程，或虚拟化器切换到另一 VM 时，当前线程可在代码的任意位置被暂停。一台 VM 因 CPU 被其他 VM 占用而损失的时间称为 steal time。机器若处在重负载下——大量线程在排队等运行——被暂停的线程可能要等好一阵才能再次被调度。
• 应用执行同步磁盘访问时，线程可能在等待慢速磁盘 I/O 完成 [77]。许多语言里磁盘访问发生得令人意外——即便代码没明显写文件访问——例如 Java 类加载器在首次用到某类时才懒加载，这可能在程序执行的任意时点发生。I/O 暂停与 GC 暂停甚至可能叠加在一起 [78]。如果磁盘其实是网络文件系统或网络块设备（如 Amazon EBS），I/O 延迟还会受网络延迟波动影响 [31]。
• 如果操作系统允许换页到磁盘（paging），一次普通的内存访问可能引发缺页，需要从磁盘加载页到内存。线程在这次慢速 I/O 期间被暂停；在内存压力大时，可能还要先把另一页换出到磁盘。极端情况下操作系统大部分时间都花在内存页换入换出上，几乎做不了正经事（即所谓抖动）。为避免这一问题，服务器机器上往往禁用 paging（宁可杀进程释放内存，也不愿冒抖动风险）。
• Unix 进程可以通过 SIGSTOP 信号暂停——例如 shell 里按 Ctrl-Z。该信号会立即让进程不再获得 CPU，直到收到 SIGCONT 后从原处继续。即便平时不用 SIGSTOP，运维工程师也可能不慎发出。

上述所有情形都能在任意时点抢占线程并稍后恢复，而线程对此毫无察觉。这与单机多线程代码追求线程安全所面临的问题相似——你不能对时序作任何假设，因为任意上下文切换与并行都可能发生。

写单机多线程代码时我们有相当好的工具来保证线程安全：互斥、信号量、原子计数器、无锁数据结构、阻塞队列等等。可惜这些工具无法直接搬到分布式系统中，因为分布式系统没有共享内存——只有不可靠网络上的消息传递。

分布式系统中的节点必须假设：自己的执行可以在任意时点（甚至函数中途）被暂停相当长时间。暂停期间，世界仍在继续往前走，其他节点可能因为它没回应而把它宣告已死。最终被暂停的节点也许还会继续运行——它甚至意识不到自己"睡了一觉"，要等下次查看时钟才会发觉。

提供响应时间保证

刚才所述：在许多编程语言与操作系统中，线程与进程可被无界时长地暂停。不过只要肯下功夫，那些导致暂停的原因都可以消除。

某些软件运行的环境中，未能在指定时间内响应可能造成严重损害。控制飞机、火箭、机器人、汽车等物理对象的计算机必须对传感器输入做出快速且可预测的响应。在这些所谓硬实时系统中，软件必须在指定截止时刻前响应；未达截止可能让整套系统失败。

嵌入式系统中的实时指系统经过精心设计与测试，能在所有情形下满足指定的时序保证。这与网络中含义模糊的 real-time 不同——后者描述服务器把数据推给客户端的流处理（不带硬响应时间约束，见第 12 章）。

举个例子：车上传感器检测到碰撞正在发生时，你绝不希望气囊的释放被一次不合时宜的 GC 暂停拖延。

要给系统提供实时保证，需要软件栈各层的支持：保证进程能在指定时间间隔内分到 CPU 的实时操作系统（RTOS）；库函数必须文档化最差执行时间；动态内存分配可能受限甚至完全禁用（实时垃圾回收器是存在的，但应用仍要避免给它太多压力）；还要进行大量测试与测量以确保各项保证得以满足。

所有这些都意味着巨大的额外工作量，并极大缩小可用编程语言、库与工具的范围（多数都不提供实时保证）。因此开发实时系统代价高昂，主要用于安全关键的嵌入式设备。况且"实时"并不等于"高性能"——事实上实时系统吞吐往往更低，因为它必须把及时响应放在一切之上（见第 356 页"延迟与资源利用"）。

对绝大多数服务端数据处理系统而言，实时保证既不经济也不合适。因此这些系统不得不忍受非实时环境所带来的暂停与时钟不稳定。

限制 GC 的影响

GC 曾是进程暂停最大的元凶之一 [79]，但 GC 算法已大有改进。调好的 GC 通常能把进程暂停控制在几毫秒以内。Java 运行时提供 CMS（concurrent mark sweep）、G1（garbage-first）、ZGC（Z）、Epsilon、Shenandoah 等多种收集器，分别针对不同的内存特性（如对象创建频繁、大堆等）。Go 提供较简单的并发 mark-sweep GC，能自动调优。

要彻底规避 GC 暂停，可以选用没有 GC 的语言。例如 Swift 通过引用计数判断何时可释放内存；Rust 与 Mojo 则借助类型系统跟踪对象生命周期，让编译器知道每块内存的分配时长。

即便使用 GC 语言，也可以减轻 GC 暂停的影响：例如把对象放进池里复用而非丢弃、或把数据分配在堆外。更激进的做法是把 GC 暂停视作节点的一次短暂计划停机——让其他节点处理客户端请求，本节点专心收垃圾。如果运行时能预先告知应用"此节点即将需要 GC"，应用就可以停止把新请求发给它，等它处理完未完请求后再 GC。这一技巧把 GC 暂停对客户端隐藏起来，从而降低响应时间的高百分位 [80, 81]。

一种类似思路是：只对短命对象使用 GC（这些对象容易回收），并在长命对象积累到需要 full GC 之前周期性重启进程 [79, 82]。可以一次重启一个节点，重启前像滚动升级一样把流量从该节点切走（见第 5 章）。

这些措施虽不能完全消除 GC 暂停，但能有效减小其对应用的影响。

知识、真理与谎言

至此本章探讨了分布式系统与单机程序的种种不同：分布式系统没有共享内存，只能在延迟可变的不可靠网络上传递消息；它会出现部分失败、不可靠的时钟、进程暂停。

若你不习惯分布式系统，这些后果会让人晕头转向。网络中的节点无法确切知道关于其他节点的任何事情——它只能根据收到（或没收到）的消息去猜。一个节点要了解另一节点的状态（存了什么数据、是否正常），只能通过消息交换。一旦远端节点不响应，也无从判断它的状态——网络问题与节点问题根本无从区分。

讨论这些系统已开始接近哲学领域：在我们的系统里，什么算"真"、什么算"假"？如果感知与测量的机制本身就不可靠，我们对所谓"知识"还能有多少把握 [83]？软件系统是否需要像物理世界那样遵循因果之类的法则？

好在我们用不着追问到生命意义这么远的地步。在分布式系统中，我们可以陈述对系统行为的假设（系统模型），并设计真实系统去满足这些假设；算法则可以被证明在某种系统模型下能正确工作。这意味着即便底层系统模型提供的保证很少，我们仍能获得可靠行为。

不过，尽管在不可靠的系统模型上把软件做得"守规矩"在原则上可行，实际操作并不简单。本章余下部分将进一步探讨分布式系统中关于知识与真理的概念，帮助我们思考能作哪些假设、能提供哪些保证。第 10 章则会展示一些在特定假设下给出特定保证的分布式算法实例。

多数说了算

设想一个网络出现了非对称故障：节点能收到所有发给它的消息，但所有外发消息都被丢弃或延迟 [22]。即便这一节点工作良好、能收到请求，其他节点也听不到它的回应。超时之后，其他节点会宣告它已死——因为听不到它的消息。这情形像一场噩梦：半失联的节点被拖向坟墓，一边踢腿一边喊"我没死！"——可没人听得到它的呼喊，葬礼仍以斯多葛式的从容径直往下走。

不那么噩梦的情景下，半失联节点或许会注意到自己发出的消息没有被其他节点确认，从而意识到网络必定出了问题；但它仍会被其他节点错误地宣告已死，对此无能为力。

第三种情形：设某节点的执行被暂停了整整一分钟。这段时间里它既不处理请求、也不发响应；其他节点等待、重试、失去耐心，最终宣告它已死、把它装上灵车。最后暂停结束，被暂停节点的线程像什么都没发生一样继续。其他节点大吃一惊——以为已死的节点居然从棺材里坐起来，气色良好地开始和旁人愉快攀谈。被暂停的节点甚至没意识到整整一分钟已经过去——在它看来，距上一次与其他节点通话似乎没过多久。

这些故事的寓意是：节点不能轻易相信自己对情形的判断。分布式系统不能完全依赖任何单一节点，因为任何节点都可能在任意时刻失效，让系统卡死无法恢复。许多分布式算法因而依赖 quorum（节点间投票；见第 231 页"用 quorum 进行读写"）：要做某项决策，需获得若干节点的最少投票数，以减少对任一特定节点的依赖。

这其中也包括"宣告节点已死"这一决策。如果一个 quorum 的节点宣告某节点已死，那么它就必须被视为已死——哪怕它自己感觉好得很。该节点必须服从 quorum 的判决、退位。

最常见的 quorum 是绝对多数（过半节点），当然也存在其他类型的 quorum。多数 quorum 让系统能在少数节点失效时继续工作（三节点可容忍一节点失效；五节点可容忍两节点失效）；它同样安全，因为系统中只能存在一个"多数"——不可能同时有两组多数做出彼此冲突的决策。我们将在第 10 章讨论共识算法时更详细地谈 quorum 的使用。

分布式锁与租约

分布式应用中的锁与租约很容易被误用，常常是 bug 的来源 [84]。下面来看一种它们出错的具体情形。

第 366 页"进程暂停"中讲过：租约就是一种带超时的锁，原持有者停止响应（崩溃、暂停太久或网络断开）后，可以转交给新所有者。当系统要求某物只能存在一份时，就可以用租约。例如：

• 数据库分片只允许一个节点充当主节点，以避免脑裂（见第 204 页"处理节点宕机"）。
• 对某项资源或对象只允许一个事务或客户端更新，以防并发写带来损坏。
• 大型处理作业的某个输入文件只该被一个节点处理，避免多个节点重复做相同的工作。

值得仔细想想：如果多个节点同时以为自己持有租约（比如因为进程暂停）会怎样？第三个例子里，后果只是浪费些计算资源，不算大事；但前两个例子里，后果就可能是数据丢失或损坏，严重得多。

例如图 9-4 展示了一个由于加锁实现不当导致的数据损坏 bug（并非纸上谈兵；HBase 曾出现过此问题 [85, 86]）。假设你要确保存储服务中某文件任意时刻只能被一个客户端访问——多个客户端同时写就会破坏文件。你这样实现：客户端访问文件前先从锁服务获取租约。锁服务通常用共识算法实现，详见第 10 章。

问题正是第 366 页"进程暂停"中讨论过的那种：如果持有租约的客户端暂停太久，租约就会过期；另一客户端便可对同一文件获取租约并开始写。当被暂停的客户端醒来时，它（错误地）认为自己仍持有有效租约、继续写——脑裂便发生了：客户端的写入相互冲突，文件被损坏。

图 9-4. 分布式锁的错误实现：客户端 1 以为自己仍持有有效租约（实际上已过期），从而损坏了存储中的文件。 图 9-5 展示后果类似的另一种问题。这次不涉及进程暂停，只有客户端 1 的崩溃。崩溃前不久它向存储服务发出一次写请求，但请求在网络中被延迟了很久（回想第 350 页"实践中的网络故障"，包有时会被延迟一分钟以上）。当这次写请求到达存储服务时，客户端 1 的租约已过期，客户端 2 已经获得新租约并发起了自己的写。结果与图 9-4 类似——文件损坏。

图 9-5. 旧租约持有者的消息可能被长时间延迟，在另一节点接管租约后才到达。

隔离僵尸与延迟请求

僵尸（zombie）一词有时用来形容那些还没意识到自己已经失去租约、仍以租约持有者身份行事的旧持有者。既然无法彻底杜绝僵尸，我们就必须确保它们不会造成脑裂级别的损害——这就是fence（围栏）僵尸。

有些系统试图通过关停僵尸来实现 fence——比如把它们从网络断开 [9]、通过云厂商管理界面关掉 VM、乃至物理断电 [87]。这一做法有时被称为 STONITH（shoot the other node in the head）。我们其实不太喜欢这种暴力术语；况且这种做法效果也并不特别好：它防不住图 9-5 中那种大网络延迟；节点之间还可能互相把对方关掉 [19]；等检测到僵尸再关停时往往已经太晚——数据已经损坏。

一种更稳健、既能防御僵尸又能防御延迟请求的 fence 方案见图 9-6。

图 9-6. 只接受 fencing token 递增的写入，从而保证存储访问的安全。 假设锁服务每次授予锁或租约时都返回一个 fencing token——一个每次授锁都递增的数字（如由锁服务原子自增）。我们便可要求客户端每次向存储服务发起写请求时附上当前的 fencing token。

Fencing token 还有别的名字。Google 的锁服务 Chubby 里叫 sequencer [88]；Kafka 里叫 epoch number；共识算法中（第 10 章会讨论）Paxos 的 ballot number 与 Raft 的 term number 也起类似作用。

图 9-6 中，客户端 1 拿到租约时 token 是 33，随后陷入长暂停、租约过期。客户端 2 拿到 34（数字始终递增），并带着 token 34 向存储服务写。之后客户端 1 醒来，带着 token 33 向存储服务写。但存储服务记得已处理过更高 token（34）的写入，因此拒绝 token 33 的请求。刚拿到租约的客户端必须立即向存储服务做一次写——写完之后任何僵尸都被 fence 掉了，并可对并发控制失败的请求重试。这一过程类似第 318 页"悲观与乐观并发控制"中的乐观并发控制（OCC），区别在于 fencing 是永久的，而并发控制失败可以重试。

若你的锁服务是 ZooKeeper，可用事务 ID zxid 或节点版本号 cversion 作 fencing token [85]；etcd 的 revision number 配合租约 ID 也能起到类似作用 [89]；Hazelcast 的 FencedLock API 则显式生成 fencing token [90]。

这一机制要求存储服务能检查写入是否基于过时 token。一种替代做法是：仅当对象自当前客户端上次读取以来未被其他客户端修改时，写入才成功，类似原子 CAS 操作。例如对象存储服务就支持这种检查：Amazon S3 称之为条件写、Azure Blob Storage 称之为条件头、Google Cloud Storage 称之为请求前置条件。

多副本下的 fencing

如果你的客户端只往一个支持条件写的存储服务写入，那么锁服务就显得多余了 [91, 92]，因为租约分配本可以直接基于该存储服务实现 [93]。但一旦你有了 fencing token，就可以拿它对接多个服务或副本，并确保旧持有者在所有副本上都被 fence 掉。

例如，设想存储服务是一个带 LWW 冲突解决的无主复制键值存储（见第 229 页"无主复制"）。这种系统里客户端会把写直接发给每个副本，每个副本依据客户端所附的时间戳独立决定是否接受。

如图 9-7 所示，可以把写者的 fencing token 放在时间戳的最高位（或最高若干位数字）。这样能确保新持有者生成的任何时间戳都大于旧持有者的时间戳，即使旧持有者的写发生得更晚也不例外。

图 9-7. 用 fencing token 保护写入无主复制数据库的写。 图 9-7 中客户端 2 的 fencing token 是 34，因此它生成的所有以 34… 开头的时间戳都大于客户端 1 那些以 33… 开头的时间戳。客户端 2 成功写到一个 quorum 的副本，但无法触达副本 3。这意味着僵尸客户端 1 后来若仍想写，写在副本 3 上仍可能成功，即使被副本 1、2 拒绝。这并不构成问题——因为后续的 quorum 读会偏好客户端 2 那条更大时间戳的写，读修复或反熵机制最终也会覆盖客户端 1 写下的值。

正如这些例子所示，假设任意时刻只有一个节点持有租约并不安全。好在只要稍加小心，就能用 fencing token 防止僵尸与延迟请求造成损害。

拜占庭故障

Fencing token 能检测并阻止无意犯错的节点（例如它还没察觉自己的租约已过期）。但若节点蓄意破坏系统保证，那很容易办到——发带假 fencing token 的消息即可。

本书我们假设节点不可靠但诚实：它们可能因故障变慢或永不响应、可能因 GC 暂停或网络延迟而状态陈旧；但只要节点真的响应，它说的就是"真话"——以它所掌握的为准、依协议规则行事。

如果存在节点会"撒谎"的风险（发出任意伪造或损坏的响应）——例如某节点在同一次选举中投出相互矛盾的多票——那分布式系统的问题就难得多。这种行为称为拜占庭故障；在彼此不信任的环境中达成共识被称为拜占庭将军问题 [94]。

拜占庭将军问题

拜占庭将军问题是两将军问题 [95] 的推广——两位军中将军要就一项战斗计划达成一致。他们扎营两处，只能依靠信使通信，而信使有时会被延迟或丢失（如同网络中的包）。第 10 章会讨论这一共识问题。

拜占庭版本里 n 位将军要达成一致，但同伴中的叛徒会从中作梗。多数将军忠诚、消息真实；叛徒则可能发假/不实消息企图欺骗或迷惑他人。事先无法知道谁是叛徒。

拜占庭是一座古希腊城市，后来成为君士坦丁堡，也就是今天土耳其的伊斯坦布尔。没有历史证据显示拜占庭的将军们比别处的更善搞阴谋。"Byzantine" 这一名字源自其意为过分复杂、官僚、狡诈——这一含义早在计算机出现前就在政治用语中使用 [96]。Lamport 当时想选一个不冒犯任何读者的国名，被建议阿尔巴尼亚将军问题不是个好主意 [97]。

拜占庭容错的用途

系统若能在某些节点功能失常或攻击者干扰网络时仍正确运转，就称为拜占庭容错。这一关切在特定情形下才相关，例如：

• 在航天环境中，计算机内存或 CPU 寄存器可能被辐射损坏，导致节点以任意不可预测的方式与其他节点交互。一旦系统失败代价极高（飞机坠毁、火箭撞上国际空间站等），因此飞控系统必须能容忍拜占庭故障 [98, 99]。
• 多方共同参与的系统中，一些参与方可能想欺骗或诈骗他人。这种情况下节点不能简单地信任另一节点的消息——这些消息可能就是恶意发出的。比特币等加密货币以及其他基于区块链的系统所采用的共识机制，可被视为一种让彼此不信任的参与方就交易是否发生达成一致、且无须中心权威的方法 [100]。

不过对本书讨论的系统类型而言，我们通常可以放心假设没有拜占庭故障。数据中心里所有节点都由你的组织控制（应当可以信任）；辐射水平低到内存损坏不是大问题（不过轨道上的数据中心正在被考虑 [101]）。多租户系统中租户互不信任，但隔离靠的是防火墙、虚拟化与访问控制策略，而非拜占庭容错。让系统具备拜占庭容错能力的协议相当昂贵 [102]，容错嵌入式系统则依赖硬件层支持 [98]。在多数服务端数据系统中，部署拜占庭容错方案的成本让其并不实际。

Web 应用确实需要为来自终端用户控制的客户端（如浏览器）的任意恶意行为做好准备。这正是输入校验、消毒、输出转义如此重要的原因——以防 SQL 注入与 XSS 等。但这里我们通常不用拜占庭容错协议，而是让服务器作为客户端行为是否被允许的权威。在没有这种中心权威的对等网络中，拜占庭容错才更具相关性 [103, 104]。

软件 bug 也可视为一种拜占庭故障；但若把同一份软件部署到所有节点，拜占庭容错算法救不了你。多数拜占庭容错算法要求超过三分之二的节点正常工作（如四节点中至多一节点失常）。要拿它对付 bug，你得有同一软件的四个独立实现，并寄希望于某个 bug 只出现在其中一份里。

同理，要是有协议能保护我们免受漏洞、安全攻击与恶意行为就好了。可惜也并不现实——多数系统里，攻击者攻陷一台节点后，往往能攻陷所有节点，因为它们运行的多半是同一份软件。因此传统机制（身份认证、访问控制、加密、防火墙等）仍是抵御对手的主要手段。

弱形式的"撒谎"

虽然我们假设节点总体上诚实，但给软件加一些机制来防范弱形式的"撒谎"也是值得的——例如硬件问题、软件 bug、配置错误所产生的无效消息。这类保护机制并不是完整的拜占庭容错，无法抵御蓄意攻击者，但作为迈向更高可靠性的简单务实步骤，仍很有用。例如：

• 网络数据包有时会因硬件问题或操作系统、驱动、路由器等中的 bug 而损坏。这通常能被 TCP/UDP 内置的校验和捕获，但偶有漏检 [105, 106, 107]。一些简单的措施往往就足以防御此类损坏，比如在应用层协议里加入校验和；TLS 加密连接也能起到防损坏的作用。
• 面向公网的应用必须谨慎消毒任何用户输入——例如转义特定字符以防 SQL 注入、检查值是否在合理范围、限制字符串长度以防大内存分配引发拒绝服务。防火墙后的内部服务对输入校验可以稍宽松些，但协议解析器里加上基本检查依然是个好主意 [105]。
• NTP 客户端可以配置多个服务器地址。同步时客户端会联系所有这些服务器，估计它们各自的误差，并检查多数是否在同一时间范围内。只要多数服务器正常，配置错误、报告错误时间的 NTP 服务器就会被检出为离群值并从同步中排除 [39]。多服务器配置让 NTP 比单服务器更鲁棒。

系统模型与现实

许多算法被设计来解决分布式系统问题——例如第 10 章会研究共识问题的解。这些算法要派上用场，必须能容忍本章讨论过的各种故障。

算法必须以一种不过度依赖具体硬件与软件配置细节的方式来写。这反过来要求我们把系统中预期发生的故障以某种方式形式化。我们通过定义系统模型来做这件事——它是对算法假设的一种抽象描述。

关于时序假设，常用的有三种系统模型：

同步模型

假设网络延迟、进程暂停、时钟误差都是有界的。这并不意味着完全同步的时钟或零网络延迟，只是说网络延迟、暂停与时钟漂移永远不会超过某个固定上限 [108]。同步模型并不能很好地刻画大多数实际系统，因为（如本章所讨论）无界延迟与暂停会发生。

部分同步模型

部分同步意味着系统多数时候表现得像同步系统，但偶尔会超出网络延迟、进程暂停或时钟漂移的上限 [108]。这是许多实际系统的合理模型。多数时候网络与进程相当守规矩——否则我们什么也做不成——但必须考虑到时序假设偶尔会被打破：一旦发生，网络延迟、暂停和时钟误差都可能任意大。

异步模型

在该模型中，算法不允许作任何时序假设——事实上它甚至没有时钟（也用不了超时）。某些算法可以为异步模型设计，但限制很大。

除了时序问题，我们还要考虑节点故障。常见的节点系统模型如下：

崩溃停止故障

崩溃停止（或 fail-stop）模型中，算法可以假定节点只会以一种方式失败——崩溃 [109]。节点可能在任意时刻突然停止响应，此后那节点就一去不回了。

崩溃恢复故障

崩溃恢复模型假定节点可在任意时刻崩溃，未知时间后又重新开始响应。节点被假定具有稳定存储（即非易失的磁盘存储），其中数据可跨崩溃保留；而内存状态则被假定丢失。

性能下降与部分功能失效

除了崩溃与重启，节点也可能变慢。它们或许仍能响应健康检查请求，却慢到无法做任何实际工作。例如某块千兆网络接口可能因驱动 bug 突然降至 1 Kb/s [110]；内存压力下的进程可能大部分时间在 GC [111]；磨损的 SSD 性能不稳定；硬件还可能受高温、接触不良、机械振动、电源问题、固件 bug 影响。这种情形被称为 limping node、灰故障或 fail-slow [113]，比干净失效更难处理。相关问题还有：进程停止做某些事，却仍在做其他事——比如某个后台线程崩溃或死锁 [114]。

拜占庭（任意）故障

节点可能做任何事，包括试图欺骗其他节点（前面已述）。

为建模真实系统，部分同步模型搭配崩溃恢复故障通常最实用：它允许无界的网络延迟、进程暂停与慢节点。但分布式算法在这一模型下要如何应对？

定义算法的正确性

要定义"算法正确"意味着什么，可以通过描述它需满足的性质来表达。例如，排序算法的输出具备这样一条性质：对输出列表中的任意两个不同元素，左边那个比右边那个小——这其实就是"列表已排序"的形式化说法，是一条排序状态下的不变量。

类似地，我们也可以为分布式算法写下若干性质来定义"正确"。例如为锁生成 fencing token（见第 374 页"隔离僵尸与延迟请求"），算法可能需要满足：

唯一性

不存在两次 fencing token 请求返回相同值。

单调序列

若请求 x 返回 token t_x、请求 y 返回 token t_y，且 x 在 y 开始前完成，则 t_x < t_y。

可用性

任何请求 fencing token 且未崩溃的节点最终都会得到响应。

如果算法在系统模型允许的一切情形下都满足上述性质，那它在该系统模型下就是正确的。然而，若所有节点都崩溃、或所有网络延迟突然变得无限长，没有任何算法能做出有用的事。在允许彻底失败的系统模型下，我们要怎样才能仍然给出有用的保证？

区分安全与活性

为厘清这一点，值得区分两类性质：安全与活性。上面例子中，唯一性与单调序列是安全性质，可用性则是活性性质。

二者有何区别？一个显著的判别标志是：活性性质往往在定义中包含"最终"二字（你猜对了——最终一致性就是一条活性性质 [115]）。

安全常被非正式地定义为"没有坏事发生"，活性则是"好事最终发生"。但这些非正式定义最好别太较真——"好"与"坏"是价值判断，并不适用于算法。安全与活性的精确定义如下 [116]：

• 安全性质一旦被违反，可指出在某个具体时刻它被打破（例如唯一性被破坏时，可指出某次操作返回了重复 token）。安全性质一旦被违反，违反就不可撤销——损害已成定局。
• 活性性质则相反：它在某一时刻可能并不成立（例如某节点发出请求但还没收到响应），但仍可能在未来某个时刻被满足（即终于收到响应）。

区分安全与活性的好处是：它帮我们应对困难的系统模型。对分布式算法，我们通常要求安全性质在系统模型允许的所有情形下都始终成立 [108]——即便所有节点崩溃或整张网络失效，算法也必须确保不会返回错误结果（也就是安全性质仍然满足）。

而活性性质则允许附加条件——比如可以说"请求只在多数节点未崩溃、且网络最终从中断中恢复时才需收到响应"。部分同步模型的定义就要求系统最终回到同步状态——也就是说，任何网络中断都只持续有限时间随后被修复。

把系统模型映射到现实世界

安全/活性性质与系统模型对推理分布式算法的正确性非常有用。然而真要实现算法时，现实的混乱事实又会找上门来——你会清楚地意识到：系统模型只是对现实的简化抽象。

例如，崩溃恢复模型里的算法通常假定稳定存储中的数据跨崩溃保留。可若磁盘上的数据因硬件错误或配置错误被损坏甚至抹掉怎么办 [117]？若服务器固件 bug 让它在重启后识别不出本来已正确接好的硬盘怎么办 [118]？

quorum 算法（见第 231 页"用 quorum 进行读写"）依赖节点记得它自称存过的数据。若节点失忆、忘了之前存的数据，就违反了 quorum 条件，进而损害算法的正确性。也许需要引入新的系统模型，假定稳定存储多数情况下能跨崩溃存活、但偶尔会丢失——可这种模型推理起来更困难。

算法的理论描述可以宣称某些事情根本不会发生——在非拜占庭系统中我们确实必须对哪些故障会、哪些故障不会发生作出假设。然而真实实现可能仍需包含处理"假设不该发生的事却发生"的代码，哪怕这种处理只是 printf("Sucks to be you") 后 exit(666)——也就是让人工运维去收拾烂摊子 [119]。（这正是计算机科学与软件工程之间的一处差异。）

这并不是说理论性的、抽象的系统模型毫无价值——恰恰相反。它们能把真实系统的复杂性提炼为一组可推理的可控故障，因而极为有用，让我们得以理解问题并加以系统化地解决。

形式化方法与随机化测试

我们如何知道算法确实满足所需性质？由于并发、部分失效、网络延迟的存在，可能的状态数极其庞大。我们必须保证性质在所有可能状态下都成立，并且没有遗漏任何边角情形。

一种办法是形式化验证算法：用数学描述它，并用证明技术表明它在系统模型允许的所有情形下都满足所需性质。证明算法正确并不意味着它在真实系统上的实现总能表现正确，但这是个非常好的起点——因为理论分析能发现算法中那些可能在真实系统里潜伏很久、只有当你的假设（如时序假设）被异常情况打破时才暴露出来的问题。

把理论分析与经验测试相结合，以此验证实现是否符合预期，是审慎的做法。基于性质的测试、模糊测试、确定性模拟测试等技术利用随机化在广泛情境下测试系统。AWS、FoundationDB、TigerBeetle 等机构已经在多款产品上成功运用这些技术的组合 [120, 121, 122, 123]。

模型检查与规范语言

模型检查器是帮助验证算法或系统是否按预期行为的工具。算法规范用专门语言书写，如 TLA+、Gallina、FizzBee；这些语言便于把注意力放在算法行为上，不必为具体实现细节分心。模型检查器随后用这些模型，系统地尝试所有可能发生的情况，验证不变量在算法的全部状态下都成立。

模型检查并不能真正证明算法的不变量在所有可能状态下都成立，因为多数现实算法的状态空间是无限的。真正面向所有状态的验证需要形式证明——虽然可行，但通常比跑模型检查器更难。模型检查器鼓励你把算法模型简化为可被完整验证的近似，或对执行设个上限（如最大消息数）。在更长执行中才出现的 bug 因此可能找不到。

不过模型检查器在易用性与发现非显然 bug 之间取得了不错的平衡。CockroachDB、TiDB、Kafka 等许多分布式系统都借助模型规范发现并修复 bug [124, 125, 126]。例如借助 TLA+，研究者证明了 viewstamped replication（VR）算法散文描述中的歧义可能引发数据丢失 [127]。

设计上，模型检查器并不跑你的实际代码，而只跑一份仅描述协议核心思想的简化模型。这让系统地探索状态空间更易处理，但也存在规范与实现彼此偏离的风险 [128]。检查模型与真实实现是否行为等价是可能的，不过需要在真实实现中加入仪器 [129]。

故障注入

许多 bug 是机器与网络故障触发的。故障注入是一种有效（有时也令人胆颤）的技术，用于验证系统实现在出错时是否如预期表现。思路很简单：向运行中的系统环境注入故障，观察它如何反应。故障可以是网络故障、机器崩溃、磁盘损坏、暂停进程——任何你能想到的电脑出错方式。

故障注入测试通常在与生产环境十分相似的环境中运行；有些甚至直接把故障注入生产环境。Netflix 的 Chaos Monkey 工具让这种做法广为流行 [130]。生产故障注入通常被称为混沌工程，第 43 页"可靠性与容错"中讨论过。

跑故障注入测试时，被测系统先与故障注入协调器和脚本一起部署。协调器决定执行哪些故障、何时执行；本地或远程脚本负责把故障注入到具体节点或进程。注入脚本会借助多种工具触发故障：Linux 进程可用 kill 暂停或杀掉、磁盘可用 umount 卸载、网络连接可通过防火墙设置中断。注入故障的期间与之后，你都可以检查系统行为，确认是否如预期。

需要的工具种类繁多，使得故障注入测试编写起来很麻烦。常见做法是采用故障注入框架（如 Jepsen）来跑测试，这类框架自带各种操作系统集成与众多预制故障注入器 [131]。Jepsen 在许多被广泛使用的系统中发现关键 bug，效果显著 [132, 133]。

确定性模拟测试

另一种形式化技术——已成为模型检查与故障注入的流行补充——是确定性模拟测试（DST）。它采用与模型检查器类似的状态空间探索过程，但测试的是你的实际代码而非模型。

DST 中，仿真器会自动跑系统的大量随机化执行。仿真过程中，网络通信、I/O、时钟时序都被替换为模拟，仿真器可以控制事情发生的顺序——包括各种时序与故障情境。这让仿真器能探索的情况远比手写测试或故障注入多得多。若某次测试失败，可以原样重跑——因为仿真器记得触发失败的精确操作顺序；故障注入则做不到这种细粒度控制。

DST 要求仿真器能控制所有非确定性来源，如网络延迟与多线程代码里的线程调度。通常采用以下三种策略之一让代码可确定化：

应用层

有些系统从一开始就为便于确定性执行而构建。例如 DST 领域的先驱之一 FoundationDB 就是用一个叫 Flow 的异步通信库构建的，Flow 为开发者提供了把确定性网络模拟注入系统的插入点 [134]。同样，TigerBeetle 是一款一开始就具备 DST 支持的 OLTP 数据库；它把系统状态建模为状态机，所有变更都发生在单一事件循环中，再配合时钟等模拟确定性原语，整套架构便可被确定性运行 [135]。

运行时层

具备异步运行时与常用库的语言会提供引入确定性的插入点。单线程运行时被用来把所有异步代码强制按顺序运行。例如 FrostDB 修改 Go 运行时让 goroutine 按顺序执行 [136]；Rust 的 MadSim 库做法类似，为 Tokio 异步运行时 API、Amazon S3 库、Kafka 的 Rust 库等许多组件提供确定性实现；应用可换上这些确定性库与运行时，在不修改代码的前提下获得确定性的测试执行。

机器层

与其在运行时层打补丁，也可以让整台机器变得确定。这是一项细致活儿——需要让机器对所有本来非确定的调用都给出确定性响应。Antithesis 等工具的做法是构建一个定制的 hypervisor，把通常非确定的操作替换为确定操作。从时钟到网络与存储，方方面面都得照顾周全。一旦做到，开发者就能把整套分布式系统跑在该 hypervisor 中的一组容器里，得到一个完全确定的分布式系统。

DST 的好处远不止"可重放"。例如 Antithesis 在发现不常见行为时，会把一次测试执行分叉为多个子执行，借此尽量多地探索应用代码中的路径。而由于确定性测试常使用模拟时钟与网络调用，这类测试可以跑得比墙钟时间更快——例如 TigerBeetle 的时间抽象允许仿真去模拟网络延迟与超时，而无须真的等到那段时长才能触发超时。这些技术让仿真器能够更快地探索更多代码路径。

确定性的力量

非确定性正是本章所有分布式系统挑战的核心：并发、网络延迟、进程暂停、时钟跳变与崩溃都以不可预测的方式发生，每次系统运行的表现都各不相同。反过来，若你能把系统做成确定的，许多事情就能大大简化。

事实上，"让事情变确定"是分布式系统设计中反复出现、看似简单却威力强大的一种思想。除了确定性模拟测试，我们在前几章里也见过它的若干应用：

• 事件溯源（见第 101 页"事件溯源与 CQRS"）的关键优势之一是：你可以确定性地重放事件日志来重建派生的物化视图。
• 工作流引擎（见第 187 页"持久执行与工作流"）依赖工作流定义的确定性来提供持久执行语义。
• 状态机复制（将在第 433 页"使用共享日志"中讨论）通过让每个副本独立地以相同顺序执行同一串确定性事务来复制数据。这一思想我们已经见过两种变体：基于语句的复制（见第 206 页"复制日志的实现"），以及用存储过程做串行事务执行（见第 311 页"存储过程的优缺点"）。

然而把代码做到完全确定并不容易。即便你已经去除了全部并发、把 I/O、网络通信、时钟、随机数生成器都替换成确定性模拟，仍可能残留某些非确定因素。例如，某些编程语言中遍历哈希表元素的顺序可能本身就是非确定的；是否触碰资源上限（内存分配失败、栈溢出）也是非确定的。

总结

本章我们讨论了分布式系统中可能出现的诸多问题。例如：

• 每次试图通过网络发送数据包时，包都可能丢失或被任意延迟；同样，应答也可能丢失或延迟，因此一旦你没收到回复，便根本无从知晓消息是否真正送达。
• 节点时钟可能与其他节点严重不同步（哪怕你已尽力配置 NTP），并且可能突然向前或向后跳变；依赖它颇为危险，因为你多半无法准确度量自己时钟的置信区间。
• 某进程可能在执行的任意时刻被暂停相当长一段时间、被其他节点宣告死亡，之后又"活"过来——它自己甚至不知道刚刚被暂停过。

部分失败会发生——这正是分布式系统的根本特征。每当软件做任何涉及其他节点的事情，这次操作都可能偶尔失败、随机变慢、或干脆不响应（最终超时）。我们要做的，就是把对部分失败的容忍内建进软件，让整体在某些部件失效时仍能继续运转。

要容忍故障，第一步是检测故障，但这一步本身就不容易。多数系统并没有准确机制可以判定某节点是否已挂掉，因此多数分布式算法依赖超时来判断远端节点是否仍可达。然而超时无法区分网络故障与节点故障，可变的网络延迟还会让节点偶尔被误判为崩溃；至于那些仍在响应、却慢到几乎做不了正经事的"瘸腿节点"，更是难以处理。

一旦检测到故障，让系统能够容忍它也并不简单：节点之间没有全局变量、没有共享内存、没有共同知识，也没有任何形式的共享状态 [83]。节点们连"现在几点"都难达成一致，更别说更复杂的事情。信息在节点之间流通的唯一通道就是不可靠的网络。重大决策不能由单一节点安全地作出，因此我们需要协议借助其他节点的协助、试图让一个 quorum 达成一致。

如果你习惯在单台计算机理想化的数学完美中编程——同一操作总会确定性地返回同一结果——那么转入分布式系统这一杂乱的物理现实可能令人震撼。反过来，分布式系统工程师有时也会把那种"单机就能解决"的问题视为不值一提 [4]，而事实上单机如今也确实能做不少事。如果可以避免打开分布式这只潘多拉魔盒、把数据留在单机上（比如使用嵌入式存储引擎，见第 125 页"嵌入式存储引擎"），那通常就值得这么做。

然而如第 19 页"分布式 vs 单机系统"所讨论的，可扩展性并非采用分布式系统的唯一理由：容错以及低延迟（通过把数据放到地理上靠近用户的地方）同样重要——这些目标在单节点上是无法达成的。分布式系统的力量在于：原则上它们可以永远运行而不在服务层面被打断，因为所有故障与维护都可以在节点层面处理。（不过实践中，一次糟糕的配置变更只要被推送到所有节点，照样会让分布式系统跪下。）

本章我们还旁敲侧击地探讨了：网络、时钟与进程的不可靠是否是无法回避的自然法则？答案是否定的：要在网络中提供硬实时响应保证与有界延迟是可能的，只不过非常昂贵、且导致硬件资源利用率下降。多数对安全要求不那么严苛的系统会选择便宜而不可靠，而非昂贵而可靠。

本章满篇都在谈问题，呈现的图景颇为悲观。但我们也因此从经过大量测试、生产级的分布式系统中受益良多——它们替我们管理着这些问题。下一章我们将转向解决方案，讨论这些系统所采用的一些算法是如何应对这些问题的。

参考文献

[1] Mark Cavage. "There's Just No Getting Around It: You're Building a Distributed System." ACM Queue, volume 11, issue 4, pages 80–89, April 2013. doi:10.1145/2466486.2482856

[2] Jay Kreps. "Getting Real About Distributed System Reliability." blog.empathybox.com, March 2012. 归档于 perma.cc/9B5Q-AEBW

[3] Coda Hale. "You Can't Sacrifice Partition Tolerance." codahale.com, October 2010. 归档于 perma.cc/6GJU-X4G5

[4] Jeff Hodges. "Notes on Distributed Systems for Young Bloods." somethingsimilar.com, January 2013. 归档于 perma.cc/B636-62CE

[5] Van Jacobson. "Congestion Avoidance and Control." 见 ACM Symposium on Communications Architectures and Protocols (SIGCOMM), August 1988. doi:10.1145/52324.52356

[6] Bert Hubert. "The Ultimate SO_LINGER Page, or: Why Is My TCP Not Reliable." blog.netherlabs.nl, January 2009. 归档于 perma.cc/6HDX-L2RR

[7] Jerome H. Saltzer, David P. Reed, and David D. Clark. "End-To-End Arguments in System Design." ACM Transactions on Computer Systems, volume 2, issue 4, pages 277–288, November 1984. doi:10.1145/357401.357402

[8] Peter Bailis and Kyle Kingsbury. "The Network Is Reliable." ACM Queue, volume 12, issue 7, pages 48–55, July 2014. doi:10.1145/2639988.2639988

[9] Joshua B. Leners 等. "Taming Uncertainty in Distributed Systems with Help from the Network." 见 10th European Conference on Computer Systems (EuroSys), April 2015. doi:10.1145/2741948.2741976

[10] Phillipa Gill, Navendu Jain, and Nachiappan Nagappan. "Understanding Network Failures in Data Centers: Measurement, Analysis, and Implications." 见 ACM SIGCOMM Conference, August 2011. doi:10.1145/2018436.2018477

[11] Urs Hölzle. x.com, May 2020. 归档于 perma.cc/WX8X-ZZA5

[12] CBC News. "Hundreds Lose Internet Service in Northern B.C. After Beaver Chews Through Cable." cbc.ca, April 2021. 归档于 perma.cc/UW8C-H2MY

[13] Will Oremus. "The Global Internet Is Being Attacked by Sharks, Google Confirms." slate.com, August 2014. 归档于 perma.cc/P6F3-C6YG

[14] Jess Auerbach Jahajeeah. "Down to the Wire: The Ship Fixing Our Internet." continent.substack.com, November 2023. 归档于 perma.cc/DP7B-EQ7S

[15] Santosh Janardhan. "More Details About the October 4 Outage." engineering.fb.com, October 2021. 归档于 perma.cc/WW89-VSXH

[16] Tom Parfitt. "Georgian Woman Cuts off Web Access to Whole of Armenia." theguardian.com, April 2011. 归档于 perma.cc/KMC3-N3NZ

[17] Antonio Voce 等. "'Shadow Fleets' and Sub-aquatic Sabotage: Are Europe's Undersea Internet Cables Under Attack?" theguardian.com, March 2025. 归档于 perma.cc/HA7S-ZDBV

[18] Shengyun Liu 等. "XFT: Practical Fault Tolerance Beyond Crashes." 见 12th USENIX Symposium on Operating Systems Design and Implementation (OSDI), November 2016.

[19] Mark Imbriaco. "Downtime Last Saturday." github.blog, December 2012. 归档于 perma.cc/M7X5-E8SQ

[20] Tom Lianza and Chris Snook. "A Byzantine Failure in the Real World." blog.cloudflare.com, November 2020. 归档于 perma.cc/83EZ-ALCY

[21] Mohammed Alfatafta 等. "Toward a Generic Fault Tolerance Technique for Partial Network Partitioning." 见 14th USENIX Symposium on Operating Systems Design and Implementation (OSDI), November 2020.

[22] Marc A. Donges. "Re: bnx2 Cards Intermittantly Going Offline." Linux netdev mailing list, spinics.net, September 2012. 归档于 perma.cc/TXP6-H8R3

[23] Troy Toman. "Inside a CODE RED: Network Edition." signalvnoise.com, September 2020. 归档于 perma.cc/BET6-FY25

[24] Kyle Kingsbury. "Jepsen: Elasticsearch." aphyr.com, June 2014. 归档于 perma.cc/JK47-S89J

[25] Salvatore Sanfilippo. "A Few Arguments About Redis Sentinel Properties and Fail Scenarios." antirez.com, October 2014. 归档于 perma.cc/8XEU-CLM8

[26] Nicolas Liochon. "CAP: If All You Have Is a Timeout, Everything Looks Like a Partition." blog.thislongrun.com, May 2015. 归档于 perma.cc/FS57-V2PZ

[27] Matthew P. Grosvenor 等. "Queues Don't Matter When You Can JUMP Them!" 见 12th USENIX Symposium on Networked Systems Design and Implementation (NSDI), May 2015.

[28] Theo Julienne. "Debugging Network Stalls on Kubernetes." github.blog, November 2019. 归档于 perma.cc/K9M8-XVGL

[29] Guohui Wang and T. S. Eugene Ng. "The Impact of Virtualization on Network Performance of Amazon EC2 Data Center." 见 29th IEEE International Conference on Computer Communications (INFOCOM), March 2010. doi:10.1109/INFCOM.2010.5461931

[30] Brandon Philips. "etcd: Distributed Locking and Service Discovery." 见 Strange Loop, September 2014.

[31] Steve Newman. "A Systematic Look at EC2 I/O." blog.scalyr.com, October 2012. 归档于 perma.cc/FL4R-H2VE

[32] Naohiro Hayashibara 等. "The φ Accrual Failure Detector." Japan Advanced Institute of Science and Technology, IS-RR-2004-010, May 2004. 归档于 perma.cc/NSM2-TRYA

[33] Jeffrey Wang. "Phi Accrual Failure Detector." ternarysearch.blogspot.co.uk, August 2013. 归档于 perma.cc/L452-AMLV

[34] Srinivasan Keshav. An Engineering Approach to Computer Networking: ATM Networks, the Internet, and the Telephone Network. Addison-Wesley Professional, 1997. ISBN: 9780201634426

[35] Othmar Kyas. ATM Networks. International Thomson Publishing, 1995. ISBN: 9781850321286

[36] Jialin Li 等. "Tales of the Tail: Hardware, OS, and Application-level Sources of Tail Latency." 见 ACM Symposium on Cloud Computing (SOCC), November 2014. doi:10.1145/2670979.2670988

[37] Mellanox Technologies. "InfiniBand FAQ, Rev 1.3." network.nvidia.com, December 2014. 归档于 perma.cc/LQJ4-QZVK

[38] Jose Renato Santos, Yoshio Turner, and G. (John) Janakiraman. "End-to-End Congestion Control for InfiniBand." 见 22nd Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM), April 2003. doi:10.1109/INFCOM.2003.1208949

[39] Ulrich Windl 等. "The NTP FAQ and HOWTO." ntp.org, November 2006. 归档于 archive.org

[40] John Graham-Cumming. "How and Why the Leap Second Affected Cloudflare DNS." blog.cloudflare.com, January 2017. 归档于 archive.org

[41] David Holmes. "Inside the Hotspot VM: Clocks, Timers and Scheduling Events—Part I—Windows." blogs.oracle.com, October 2006. 归档于 archive.org

[42] Joran Dirk Greef. "Three Clocks Are Better than One." tigerbeetle.com, August 2021. 归档于 perma.cc/5RXG-EU6B

[43] Oliver Yang. "Pitfalls of TSC Usage." oliveryang.net, September 2015. 归档于 perma.cc/Z2QY-5FRA

[44] Steve Loughran. "Time on Multi-Core, Multi-Socket Servers." steveloughran.blogspot.co.uk, September 2015. 归档于 perma.cc/7M4S-D4U6

[45] James C. Corbett 等. "Spanner: Google's Globally-Distributed Database." 见 10th USENIX Symposium on Operating System Design and Implementation (OSDI), October 2012.

[46] M. Caporaloni and R. Ambrosini. "How Closely Can a Personal Computer Clock Track the UTC Timescale Via the Internet?" European Journal of Physics, volume 23, issue 4, pages L17–L21, June 2012. doi:10.1088/0143-0807/23/4/103

[47] Nelson Minar. "A Survey of the NTP Network." alumni.media.mit.edu, December 1999. 归档于 perma.cc/EV76-7ZV3

[48] Viliam Holub. "Synchronizing Clocks in a Cassandra Cluster Pt. 1—The Problem." blog.rapid7.com, March 2014. 归档于 perma.cc/N3RV-5LNL

[49] Poul-Henning Kamp. "The One-Second War (What Time Will You Die?)." ACM Queue, volume 9, issue 4, pages 44–48, April 2011. doi:10.1145/1966989.1967009

[50] Nelson Minar. "Leap Second Crashes Half the Internet." somebits.com, July 2012. 归档于 perma.cc/2WB8-D6EU

[51] Christopher Pascoe. "Time, Technology and Leaping Seconds." googleblog.blogspot.co.uk, September 2011. 归档于 perma.cc/U2JL-7E74

[52] Mingxue Zhao and Jeff Barr. "Look Before You Leap—The Coming Leap Second and AWS." aws.amazon.com, May 2015. 归档于 perma.cc/KPE9-XMFM

[53] Darryl Veitch and Kanthaiah Vijayalayan. "Network Timing and the 2015 Leap Second." 见 17th International Conference on Passive and Active Measurement (PAM), April 2016. doi:10.1007/978-3-319-30505-9_29

[54] VMware, Inc. "Timekeeping in VMware Virtual Machines." vmware.com, October 2008. 归档于 perma.cc/HM5R-T5NF

[55] Victor Yodaiken. "Clock Synchronization in Finance and Beyond." yodaiken.com, November 2017. 归档于 perma.cc/9XZD-8ZZN

[56] Mustafa Emre Acer 等. "Where the Wild Warnings Are: Root Causes of Chrome HTTPS Certificate Errors." 见 ACM SIGSAC Conference on Computer and Communications Security (CCS), October 2017. doi:10.1145/3133956.3134007

[57] European Securities and Markets Authority. "MiFID II / MiFIR: Regulatory Technical and Implementing Standards—Annex I." esma.europa.eu, Report ESMA/2015/1464, September 2015. 归档于 perma.cc/ZLX9-FGQ3

[58] Luke Bigum. "Solving MiFID II Clock Synchronisation with Minimum Spend (Part 1)." catach.blogspot.com, November 2015. 归档于 perma.cc/4J5W-FNM4

[59] Oleg Obleukhov and Ahmad Byagowi. "How Precision Time Protocol Is Being Deployed at Meta." engineering.fb.com, November 2022. 归档于 perma.cc/29G6-UJNW

[60] John Wiseman. "GPSJAM: Daily Maps of GPS Interference." gpsjam.org

[61] Josh Levinson, Julien Ridoux, and Chris Munns. "It's About Time: Microsecond-Accurate Clocks on Amazon EC2 Instances." aws.amazon.com, November 2023. 归档于 perma.cc/56M6-5VMZ

[62] Kyle Kingsbury. "Jepsen: Cassandra." aphyr.com, September 2013. 归档于 perma.cc/4MBR-J96V

[63] John Daily. "Clocks Are Bad, or, Welcome to the Wonderful World of Distributed Systems." riak.com, November 2013. 归档于 perma.cc/4XB5-UCXY

[64] Marc Brooker. "It's About Time!" brooker.co.za, November 2023. 归档于 perma.cc/N6YK-DRPA

[65] Kyle Kingsbury. "The Trouble with Timestamps." aphyr.com, October 2013. 归档于 perma.cc/W3AM-5VAV

[66] Leslie Lamport. "Time, Clocks, and the Ordering of Events in a Distributed System." Communications of the ACM, volume 21, issue 7, pages 558–565, July 1978. doi:10.1145/359545.359563

[67] Justin Sheehy. "There Is No Now: Problems With Simultaneity in Distributed Systems." ACM Queue, volume 13, issue 3, pages 36–41, March 2015. doi:10.1145/2733108

[68] Murat Demirbas. "Spanner: Google's Globally-Distributed Database." muratbuffalo.blogspot.co.uk, July 2013. 归档于 perma.cc/6VWR-C9WB

[69] Dahlia Malkhi and Jean-Philippe Martin. "Spanner's Concurrency Control." ACM SIGACT News, volume 44, issue 3, pages 73–77, September 2013. doi:10.1145/2527748.2527767

[70] Franck Pachot. "Achieving Precise Clock Synchronization on AWS." yugabyte.com, December 2024. 归档于 perma.cc/UYM6-RNBS

[71] Spencer Kimball. "Living Without Atomic Clocks: Where CockroachDB and Spanner Diverge." cockroachlabs.com, January 2022. 归档于 perma.cc/AWZ7-RXFT

[72] Murat Demirbas. "Use of Time in Distributed Databases (Part 4): Synchronized Clocks in Production Databases." muratbuffalo.blogspot.com, January 2025. 归档于 perma.cc/9WNX-Q9U3

[73] Cary G. Gray and David R. Cheriton. "Leases: An Efficient Fault-Tolerant Mechanism for Distributed File Cache Consistency." 见 12th ACM Symposium on Operating Systems Principles (SOSP), December 1989. doi:10.1145/74850.74870

[74] Daniel Sturman 等. "Roblox Return to Service." corp.roblox.com, January 2022. 归档于 perma.cc/8ALT-WAS4

[75] Todd Lipcon. "Avoiding Full GCs with MemStore-Local Allocation Buffers." slideshare.net, February 2011. 归档于 perma.cc/CH62-2EWJ

[76] Christopher Clark 等. "Live Migration of Virtual Machines." 见 2nd USENIX Symposium on Networked Systems Design & Implementation (NSDI), May 2005.

[77] Mike Shaver. "fsyncers and Curveballs." shaver.off.net, May 2008. 归档于 archive.org

[78] Zhenyun Zhuang and Cuong Tran. "Eliminating Large JVM GC Pauses Caused by Background IO Traffic." engineering.linkedin.com, February 2016. 归档于 perma.cc/ML2M-X9XT

[79] Martin Thompson. "Java Garbage Collection Distilled." mechanical-sympathy.blogspot.co.uk, July 2013. 归档于 perma.cc/DJT3-NQLQ

[80] David Terei and Amit Levy. "Blade: A Data Center Garbage Collector." arXiv:1504.02578, April 2015.

[81] Martin Maas 等. "Trash Day: Coordinating Garbage Collection in Distributed Systems." 见 15th USENIX Workshop on Hot Topics in Operating Systems (HotOS), May 2015.

[82] Martin Fowler. "The LMAX Architecture." martinfowler.com, July 2011. 归档于 perma.cc/5AV4-N6RJ

[83] Joseph Y. Halpern and Yoram Moses. "Knowledge and Common Knowledge in a Distributed Environment." Journal of the ACM, volume 37, issue 3, pages 549–587, July 1990. doi:10.1145/79147.79161

[84] Chuzhe Tang 等. "Ad Hoc Transactions in Web Applications: The Good, the Bad, and the Ugly." 见 ACM International Conference on Management of Data (SIGMOD), June 2022. doi:10.1145/3514221.3526120

[85] Flavio P. Junqueira and Benjamin Reed. ZooKeeper: Distributed Process Coordination. O'Reilly Media, 2013. ISBN: 9781449361303

[86] Enis Söztutar. "HBase and HDFS: Understanding Filesystem Usage in HBase." 见 HBaseCon, June 2013. 归档于 perma.cc/4DXR-9P88

[87] SUSE LLC. "SUSE Linux Enterprise High Availability 15 SP6 Administration Guide, Section 12: Fencing and STONITH." documentation.suse.com, March 2025. 归档于 perma.cc/8LAR-EL9D

[88] Mike Burrows. "The Chubby Lock Service for Loosely-Coupled Distributed Systems." 见 7th USENIX Symposium on Operating System Design and Implementation (OSDI), November 2006.

[89] Kyle Kingsbury. "etcd 3.4.3." jepsen.io, January 2020. 归档于 perma.cc/2P3Y-MPWU

[90] Ensar Basri Kahveci. "Distributed Locks Are Dead; Long Live Distributed Locks!" hazelcast.com, April 2019. 归档于 perma.cc/7FS5-LDXE

[91] Martin Kleppmann. "How to Do Distributed Locking." martin.kleppmann.com, February 2016. 归档于 perma.cc/Y24W-YQ5L

[92] Salvatore Sanfilippo. "Is Redlock Safe?" antirez.com, February 2016. 归档于 perma.cc/B6GA-9Q6A

[93] Gunnar Morling. "Leader Election with S3 Conditional Writes." morling.dev, August 2024. 归档于 perma.cc/7V2N-J78Y

[94] Leslie Lamport, Robert Shostak, and Marshall Pease. "The Byzantine Generals Problem." ACM Transactions on Programming Languages and Systems, volume 4, issue 3, pages 382–401, July 1982. doi:10.1145/357172.357176

[95] Jim N. Gray. "Notes on Data Base Operating Systems." 见 Operating Systems: An Advanced Course, Lecture Notes in Computer Science, volume 60, edited by R. Bayer, R. M. Graham, and G. Seegmüller, pages 393–481, Springer-Verlag, 1978. ISBN: 9783540087557. 归档于 perma.cc/7S9M-2LZU

[96] Brian Palmer. "How Complicated Was the Byzantine Empire?" slate.com, October 2011. 归档于 perma.cc/AN7X-FL3N

[97] Leslie Lamport. "My Writings." lamport.azurewebsites.net, December 2014. 归档于 perma.cc/5NNM-SQGR

[98] John Rushby. "Bus Architectures for Safety-Critical Embedded Systems." 见 1st International Workshop on Embedded Software (EMSOFT), October 2001. doi:10.1007/3-540-45449-7_22

[99] Jake Edge. "ELC: SpaceX Lessons Learned." lwn.net, March 2013. 归档于 perma.cc/AYX8-QP5X

[100] Shehar Bano 等. "SoK: Consensus in the Age of Blockchains." 见 1st ACM Conference on Advances in Financial Technologies (AFT), October 2019. doi:10.1145/3318041.3355458

[101] Ezra Feilden, Adi Oltean, and Philip Johnston. "Why We Should Train AI in Space." 白皮书，starcloud.com, September 2024. 归档于 perma.cc/7Y3S-8UB6

[102] James Mickens. "The Saddest Moment." USENIX ;login, May 2013. 归档于 perma.cc/T7BZ-XCFR

[103] Martin Kleppmann and Heidi Howard. "Byzantine Eventual Consistency and the Fundamental Limits of Peer-to-Peer Databases." arXiv:2012.00472, December 2020.

[104] Martin Kleppmann. "Making CRDTs Byzantine Fault Tolerant." 见 9th Workshop on Principles and Practice of Consistency for Distributed Data (PaPoC), April 2022. doi:10.1145/3517209.3524042

[105] Evan Gilman. "The Discovery of Apache ZooKeeper's Poison Packet." pagerduty.com, May 2015. 归档于 perma.cc/RV6L-Y5CQ

[106] Jonathan Stone and Craig Partridge. "When the CRC and TCP Checksum Disagree." 见 ACM Conference on Applications, Technologies, Architectures, and Protocols for Computer Communication (SIGCOMM), August 2000. doi:10.1145/347059.347561

[107] Evan Jones. "How Both TCP and Ethernet Checksums Fail." evanjones.ca, October 2015. 归档于 perma.cc/9T5V-B8X5

[108] Cynthia Dwork, Nancy Lynch, and Larry Stockmeyer. "Consensus in the Presence of Partial Synchrony." Journal of the ACM, volume 35, issue 2, pages 288–323, April 1988. doi:10.1145/42282.42283

[109] Richard D. Schlichting and Fred B. Schneider. "Fail-Stop Processors: An Approach to Designing Fault-Tolerant Computing Systems." ACM Transactions on Computer Systems (TOCS), volume 1, issue 3, pages 222–238, August 1983. doi:10.1145/357369.357371

[110] Thanh Do 等. "Limplock: Understanding the Impact of Limpware on Scale-out Cloud Systems." 见 4th ACM Symposium on Cloud Computing (SoCC), October 2013. doi:10.1145/2523616.2523627

[111] Josh Snyder and Joseph Lynch. "Garbage Collecting Unhealthy JVMs, a Proactive Approach." netflixtechblog.medium.com, November 2019. 归档于 perma.cc/8BTA-N3YB

[112] Haryadi S. Gunawi 等. "Fail-Slow at Scale: Evidence of Hardware Performance Faults in Large Production Systems." 见 16th USENIX Conference on File and Storage Technologies, February 2018.

[113] Peng Huang 等. "Gray Failure: The Achilles' Heel of Cloud-Scale Systems." 见 16th Workshop on Hot Topics in Operating Systems (HotOS), May 2017. doi:10.1145/3102980.3103005

[114] Chang Lou, Peng Huang, and Scott Smith. "Understanding, Detecting and Localizing Partial Failures in Large System Software." 见 17th USENIX Symposium on Networked Systems Design and Implementation (NSDI), February 2020.

[115] Peter Bailis and Ali Ghodsi. "Eventual Consistency Today: Limitations, Extensions, and Beyond." ACM Queue, volume 11, issue 3, pages 55–63, March 2013. doi:10.1145/2460276.2462076

[116] Bowen Alpern and Fred B. Schneider. "Defining Liveness." Information Processing Letters, volume 21, issue 4, pages 181–185, October 1985. doi:10.1016/0020-0190(85)90056-0

[117] Flavio P. Junqueira. "Dude, Where's My Metadata?" fpj.me, May 2015. 归档于 perma.cc/D2EU-Y9S5

[118] Scott Sanders. "January 28th Incident Report." github.com, February 2016. 归档于 perma.cc/5GZR-88TV

[119] Jay Kreps. "A Few Notes on Kafka and Jepsen." blog.empathybox.com, September 2013. 归档于 perma.cc/XJ5C-F583

[120] Marc Brooker and Ankush Desai. "Systems Correctness Practices at AWS." ACM Queue, volume 22, issue 6, pages 79–96, November/December 2024. doi:10.1145/3712057

[121] Andrey Satarin. "Testing Distributed Systems: Curated list of Resources on Testing Distributed Systems." asatarin.github.io. 归档于 perma.cc/U5V8-XP24

[122] Phil Eaton and Joran Dirk Greef. "We Put a Distributed Database in the Browser—And Made a Game of It!" tigerbeetle.com, June 2023. 归档于 perma.cc/L7M7-X4HD

[123] Apple, Inc. and FoundationDB project authors. "FoundationDB—Simulation and Testing." apple.github.io. 归档于 perma.cc/4C4L-AUH3

[124] Jack Vanlightly. "Verifying Kafka Transactions—Diary Entry 2—Writing an Initial TLA+ Spec." jack-vanlightly.com, December 2024. 归档于 perma.cc/NSQ8-MQ5N

[125] Siddon Tang. "From Chaos to Order—Tools and Techniques for Testing TiDB, A Distributed NewSQL Database." pingcap.com, April 2018. 归档于 perma.cc/5EJB-R29F

[126] Nathan VanBenschoten. "Parallel Commits: An Atomic Commit Protocol for Globally Distributed Transactions." cockroachlabs.com, November 2019. 归档于 perma.cc/5FZ7-QK6J

[127] Jack Vanlightly. "Paper: VR Revisited—State Transfer (Part 3)." jack-vanlightly.com, December 2022. 归档于 perma.cc/KNK3-K6WS

[128] Hillel Wayne. "What If the Spec Doesn't Match the Code?" buttondown.com, March 2024. 归档于 perma.cc/8HEZ-KHER

[129] Lingzhi Ouyang 等. "Multi-Grained Specifications for Distributed System Model Checking and Verification." 见 20th European Conference on Computer Systems (EuroSys), March 2025. doi:10.1145/3689031.3696069

[130] Yury Izrailevsky and Ariel Tseitlin. "The Netflix Simian Army." netflixtechblog.com, July 2011. 归档于 perma.cc/M3NY-FJW6

[131] Kyle Kingsbury. "Jepsen: On the Perils of Network Partitions." aphyr.com, May 2013. 归档于 perma.cc/W98G-6HQP

[132] Kyle Kingsbury. "Analyses." jepsen.io, 2024. 归档于 perma.cc/8LDN-D2T8

[133] Rupak Majumdar and Filip Niksic. "Why Is Random Testing Effective for Partition Tolerance Bugs?" Proceedings of the ACM on Programming Languages (PACMPL), volume 2, issue POPL, article no. 46, December 2017. doi:10.1145/3158134

[134] FoundationDB project authors. "Simulation and Testing." apple.github.io. 归档于 perma.cc/NQ3L-PM4C

[135] Alex Kladov. "Simulation Testing for Liveness." tigerbeetle.com, July 2023. 归档于 perma.cc/RKD4-HGCR

[136] Alfonso Subiotto Marqués. "(Mostly) Deterministic Simulation Testing in Go." polarsignals.com, May 2024. 归档于 perma.cc/ULD6-TSA4