分布式系统的挑战

本章对分布式系统可能出现的故障做了一个全面、近乎悲观的总结。故障可能来自网络问题、时钟时序问题等，并讨论这些问题的可控程度。

故障与部分失效

计算机设计一个非常谨慎的选择是：如果发生了某种内部错误，宁愿使计算机全部崩溃，而不是返回一个错误的结果，错误的结果往往更难处理。计算机隐藏了一切模糊的物理世界，呈现一个理想化的物理模型，以数学的方式完美运行。

但是涉及到多个节点时，情况发生了根本性的变化。对于这种分布式系统，理想化的标准模型不再适用，我们必须面对一个可能混乱的现实：在一个现实世界中，各种各样的事情都可能出错。

在分布式系统中，可能出现系统的一部分工作正常，但其他某些部分出现难以预测的故障，我们称之为「部分失效」。问题的难点就在于这种失效是不确定性的：如果涉及多个节点和网络，几乎肯定会碰到有时候网络正常，有时候则莫名的失败，这种不确定性和部分失效大大提高了分布式系统的复杂性

云计算和超算

关于如何构建大规模计算系统有以下几种不同的思路：

• 规模的一个极端是高性能计算（HPC）。包含成千上万个CPU的超级计算机构建出一个庞大的集群，通常用于计算密集型的科学任务
• 另一个极端是云计算。虽然云计算的定义并非那么明确，但是通常他具有一下特征：
  • 多租户数据中心
  • 通用计算机
  • 用 IP 以太网链接
  • 弹性/按需资源分配
• 传统企业一般处于这两个极端之间

不同集群构建方式所对应的错误处理方法也不同，对于高性能计算，通常会定期对任务进行快照，然后保存在持久性存储上，当某个节点出现故障，就干脆让系统停下来，等故障节点修复之后，从最近的快照点继续执行，

本书重点是基于互联网的服务系统，这些系统与高性能计算有许多不同之处：

• 我们的互联网服务都是在线的，需要随时（7X24h）不间断运行，为用户提供低延迟服务，任何服务不可用的情况，都是不可取的。相比之下，对于高性能计算，比如天气模拟这种离线任务则可以暂停下来然后重启，影响相对较小
• 高性能计算通常采用专有硬件，每个节点的可靠性很高，节点之间主要通过共享内存来进行通信，或者远程内存直接访问（RDMA）等技术进行通信。而云计算中的节点大多数是由通用机器构建，且成本相对低廉
• 大型数据中心通常基于IP和以太网，采用 Clos 拓扑结构提供等分带宽。他们可以为 HPC 特定工作负载提供了更好的性能。
• 系统越大，其中局部组件失效的概率就越大，在长时间运行期间，我们几乎总是可以假定某些东西发生了失效。
• 如果系统可以容忍某些失败的节点，而使整体继续工作，则对系统运行帮助极大，例如：支持滚动升级（我们目前就是这样做的）
• 对于全球分散部署的多数据中心，通信需要经过广域网，与本地网络相比，速度更慢且更加不可靠，而高性能计算通常假设所有节点位置靠近，紧密相连。

要是分布式系统可靠工作，就必然面临部分失效，这就需要依靠系统软件系统来提供容错机制。在分布式系统中，怀疑，悲观和偏执狂才能生存。

不可靠的网络

本书主要关注分布式无共享系统，即通过网络连接多个节点。所以有以下几点假定：

• 网络是跨节点通信的唯一路径
• 每台机器都有自己的内存和磁盘
• 一个机器不能直接访问另一台机器的内存或磁盘，除非通过网络发起请求

互联网以及大多数数据中心的内部网络都是异步网络，这种网络中，一个节点可以发送消息到另一个节点，但是网络并不保证它什么时候到达，甚至一定到达。发送之后，有很多事情可能出错：

1. 请求可能已经丢失（比如有人拔掉网线）
2. 请求可能正在某个队列中等待，无法马上发送
3. 远程节点已经失效
4. 远程接收节点可能暂时无法响应
5. 远程接收节点已经完成了请求处理，但是回复却在网络中 丢失/延迟

处理这种问题，我们一般采用超时机制：在等待了一段时间后，如果仍旧没有收到回复则放弃，并且认为响应不会到达。但是，即使判断他超时，仍然不清楚远程节点是否接收到了请求

现实中的网络故障

一些系统研究和大量的侧面证据表明，网络问题出人意料的普遍，包括哪些由公司运营的数据中心。一家中型数据中心完成的调查发现，没有有12次网络故障，其中有一半涉及单台机器。一家中型数据中心调查发现，每月大约有12次网络故障。

在头条内部，我们也经常经历由机房故障导致的网络不可用，服务报警等。。大家应该也遇到很多次了

我们必须处理或者测试网络故障，例如：集群可能死锁，即使网络恢复了也无法提供服务，甚至可能误删数据。如果触发了一些软件未定义的情形，则发生了任何意外都不奇怪。

处理网络故障并不意味着总是需要复杂的容错设施：假定你的网络非常可靠，而万一出现问题，一种简单的方法是向用户提供错误信息。前提是，必须非常清楚接下来软件应该如何应对，以确保系统最终可以恢复。

我们推荐人为有计划的触发网络问题，以测试系统的反应。

在字节内部，我们总是进行容灾演练，这一点做的还是不错的

检测故障

许多系统都需要自动检测节点失效这样的功能，例如：

• 负载均衡器需要避免向已失效的节点继续分发请求
• 对于主从复制的分布式数据库，如果主节点失效，我们需要将某个节点提升成主节点。但，网络的不准确性很难准确判断节点是否失效
• 由于网络的不准确性使得判断节点是否失效变的非常困难，而只有在某些特定场景下，获取可以明确的知道哪里错了
• 假设可以登录节点，但发现服务器上没有监听目标端口（可能进程挂了），那操作系统会返回 RST 或 FIN 标志的数据包来辅助关闭或拒绝 TCP 链接。如果节点在处理请求的过程中发生了崩溃，就很难知道节点处理了多少数据
• 如果服务进程崩溃，但是os仍在运行，可以通过脚本通知其他节点，以便新节点能快速接管而跳过等待超时。HBase 使用了这种方法

总之，如果出了问题，你可能会在应用堆栈的某个级别拿到了一个关于错误的回复，但是最好假定最终收不到任何错误报告，接下来尝试重试，等待超时之后，如果还是没有收到响应，则最终声明节点已经失效。

超时与无限期的延迟

如果超时是故障检测唯一的方法，那么超时时间应该设置多长呢？不信的是，没有标准答案。

设置较长的超时意味着更长时间的等待，才能宣告节点失败，但是可能会误判，例如实际上节点只是出现暂时性的波动，被错误的宣布为失效。

设想一个虚拟的系统，其网络可以保证数据包的最大延迟在一定范围内：要么在时间 d 内完成交付，要么丢失。此外，假定一个非故障节点总能够在一段时间 r 内完成请求处理。此时，可以确定成功的请求总能够在 2d+r 时间内收到响应，如果在此事件内没有收到响应，则可以推断该网络发生了失效，那么 2d+r 是一个理想的设置。

事实上，绝大多数系统都没有类似的保证：异步网络理论延迟无限大，多数服务端也不能保证在给定的时间内一定完成请求处理，如果超时时间太小，只需要一个短暂的网络延迟尖峰就会导致包超时进而将系统标记为失效。

网络拥塞与排队

就像驾车时有时候会交通堵塞一样，同样，计算机网络上的数据包延迟的变化根源往往在于排队。

• 不同节点同时发送数据包到相同的目标节点时，网络交换机会出现排队，然后依次将数据包转发到目标网络。如果网络负载过重，数据包可能必须等待一段时间才能获得发送机会。如果数据量太大，交换机队列塞满，之后的数据包则会被丢弃，网络还在运转，但会引发大量数据包重传。
• 数据包到达目标机器后，如果所有 CPU 核都处于繁忙状态，则网络数据包请求会被操作系统排队，直到应用程序能被处理。根据不同机器配置，这里也会引入一段等待时间。
• 虚拟化环境下，CPU 核会切换虚拟机，从而导致正在运行的虚拟机系统会暂停几十毫秒。这段时间中，客户虚机无法从网络中接收任何数据，入向的包会被虚拟机管理器排队缓冲，进一步增加了网络的不确定性。
• TCP 执行拥塞控制时，节点会主动限制自己的发送速率以免加重网络链路接收节点负载。这意味着数据甚至在进入网络之前，已经在发送方开始了排队

所有以上的人为因素都会造成网络延迟的变化和不确定性。当系统还有足够的处理能力，排队之后可以快速处理；但当系统接近其最大设计上限时，系统负载过高，队列深度显著增大，排队对延迟的影响特别明显。

更好的做法是，超时设置并不是一个不变的常量，而是持续测量响应时间及抖动，根据最新的响应时间自动调整。

同步和异步网络

如果网络层可以在规定的时间内保证数据包的发送，且不会丢弃数据包，那么分布式系统就会简单很多。为什么我们不能考虑在硬件层解决这个问题呢？使网络足够可靠，然后软件就无需为此担心。

我们可以将数据中心网络与传统的固定电话网络（非移动蜂窝）进行对比分析，前者非常可靠，语音延迟和掉话的现象极为罕见，这样的固定电话网络需要持续的端到端低延迟和足够的带宽来传输音频数据。计算机网络能否实现类似的高可靠性和确定性？

当通过电话打电话时，系统会动态建立一条电路：在整个线路上为呼叫分配一个固定的、带宽有保证的通信链路，该电路一直维持到通话结束。

这种网络本质是同步的：即使数据中间经过了多个路由器，16bit 空间在电路建立时已经得到预留，不会受到排队的影响，由于没有排队，网络最大的端到端的延迟是固定的，我们称为有界延迟。

这里就体现了固定电话和TCP连接的不同：电路方式总是预留固定带宽，在电路建立之后其他人无法使用，而TCP连接的数据包则会尝试使用所有可用的网络带宽。TCP可传送任意大小可变的数据块。

如果数据中心网络和互联网是电路交换网络，那么在建立电路时就可以建立一个受保证的最大往返时间。但是，它们并不是：以太网和IP是分组交换协议，不得不忍受排队的折磨，及其导致的网络无限延迟。这些协议没有电路的概念。

为什么数据中心网络和互联网使用分组交换？答案是，它们针对 **突发流量（bursty traffic）**进行了优化。一个电路适用于音频或视频通话，在通话期间需要每秒传送相当数量的比特。另一方面，请求网页，发送电子邮件或传输文件没有任何特定的带宽要求——我们只是希望它尽快完成。

如果想通过电路传输文件，你得预测一个带宽分配。如果你猜的太低，传输速度会不必要的太慢，导致网络容量闲置。如果你猜的太高，电路就无法建立（因为如果无法保证其带宽分配，网络不能建立电路）。因此，将电路用于突发数据传输会浪费网络容量，并且使传输不必要地缓慢。相比之下，TCP动态调整数据传输速率以适应可用的网络容量。

不可靠的时钟

时钟和计时器非常重要，有许多应用程序以各种方式依赖于时钟，例如：

1. 某个请求是否超时了？
2. 某项服务的 99% 的响应时间是多少？
3. 过去 5 分钟内，服务平均每天处理多少个查询？
4. 用户在我们网站上浏览花了多长时间？
5. 这篇文章什么时候发表？
6. 什么时间发送提醒邮件？
7. 这个缓存条目什么时候过期？
8. 日志错误信息的时间戳是多少

上述 1-4 测量持续时间（请求发送与接收响应的时间间隔），5-8 描述具体的某个时间点（在特定日期，特定时间发生的事件）

在分布式系统中，时间是一个棘手的问题，由于跨节点通信不可能即时完成，消息经由网络从一台机器到另一台机器总是花费时间，但是网络有不确定性延迟，精确测量有很多不确定的挑战，这些情况使得多节点通信时很难确定先后顺序。

网络上的每台机器都有自己的时钟硬件设备，通常是石英晶体震荡器。这些设备并非绝对准确。即每台机器维护自己本地时间版本，可能比其他机器稍快或更慢。我们通常用网络时间协议 NTP 去互联网同步时间，时间服务器则从精确度更高的时间源获取高精度时间

单调时钟与墙上时钟

现代计算机内部至少有两种不同的时钟：一个是墙上时钟，一个是单调时钟。他们都可以衡量时间，但是我们要理解他们的不同。

墙上时钟

根据某个日历（也叫墙上时间）返回当前的日期与实践，例如，Linux 中的 clock_gettime(CLOCK_REALTIME) 会返回 1970年1月1日到现在以来的秒数和毫秒数，这就是时间戳，我们写程序应该经常使用到。

墙上时钟可以和 NTP 同步，但是还存在一些其他问题，特别是如果本地时钟远远快于 NTP 服务器，强行重置之后会跳到某个之前的时间点。这种绿跳跃以及经常忽略闰秒，导致不适合测量时间间隔、

单调时钟

单调时钟更适合测量时间间隔，比如 Linux 中的 clock_gettime(CLOCK_MONTONIC)。单调时钟名字来源于他们总是保证向前。

在分布式系统中可以使用单调时钟测量一段任务的持续时间。

时钟同步与准确性

单调时钟不需要同步，墙上时钟需要根据 NTP 服务器或其他外部时间源做必要的调整，硬件和NTP服务器同步的过程中可能会出现一些莫名其妙的现象：

1. 计算机中的石英钟不够精确，存在漂移现象（运行速度会加快或者减慢）。时钟嫖一主要取决于机器的温度。谷歌假设其服务器的时钟便宜为200ppm（百万分之一），相当于如果每 30s 与服务器重新同步一次，则可能出现最大偏差为 6ms
2. 如果时钟与 NTP 服务器时钟差别太大，可能会出现拒绝同步，或者本地时钟将被强制性重置。在重置前后应用程序可能会时间突然倒退或者跳跃的现象。
3. 某些原因，与NTP服务器链接失败，会导致同步失败，往往不被注意到
4. NTP同步如果网络有延迟，则同步的数据可能不准确
5. NTP服务本身可能故障
6. 在虚拟机中，硬件时钟也是被虚拟化的，这对于需要精确时间的应用程序提供了额外的挑战。当虚拟机共享一个CPU核时，每个虚拟机会有数十毫秒的暂停。

依赖同步的时钟

如果应用要精确的使用时钟，就需要仔细监控所有节点上的时钟偏差。

时间戳与时间顺序

如果两个客户端同时写入分布式数据库，谁先到达，哪一个是最新的呢？

有可能出现由于时间戳的不精确导致数据库误操作。

这种冲突的解决办法被称为 最后写入获胜（LWW），在多主节点以及无主节点复制数据库中广泛使用。有些实现会在客户端生成时间戳而非服务器端，但是无论如何没有改变根本问题：

• 数据库写入可能会奇怪的丢失：后续发生的写操作却没法覆盖一个更早的值，原因是后者时钟太快了
• LWW 无法区分连续快速方发生的连续写操作（上图客户端A写入后才发生了客户端B的增量操作）和并发写入（每个写操作不依赖于其他写）。需要额外的因果关系跟踪机制（例如版本向量）来防止因果冲突。
• 由于时钟精度的限制，两个节点可能各自独立产生了完全相同的时间戳。为了解决这种冲突，需要一个额外的仲裁值（简单理解为引入一个大随机数），但是该方法无法区分因果关系。

对于排序来讲，基于递增计数器而不是振荡石英晶体的逻辑时钟是更可靠的方式。逻辑时钟并不测量一天的某个时间点或者时间间隔，而是事件的相对顺序（事件发生的前后关系）。与之对应的，墙上时钟和单调时钟都属于物理时钟。

时钟的置信区间

墙上时钟会返回几微妙甚至纳秒级别的信息，但是这种精度的测量值可能并不可信。因为有偏差。

因此我们不应该将时钟读数视为一个准确的时间点，而更应该视为带有置信区间的时间范围。例如，系统可能有 95% 的置信度认为当前时间介于 10.3-10.5 之间。

这个值是人为估的，没有准确值

全局快照的同步时钟

在“快照隔离和可重复读”中，我们讨论了快照隔离，这是数据库中非常有用的功能，需要支持小型快速读写事务和大型长时间运行的只读事务（用于备份或分析）。它允许只读事务看到特定时间点的处于一致状态的数据库，且不会锁定和干扰读写事务。

快照隔离最常见的实现需要单调递增的事务ID。如果写入比快照晚（即，写入具有比快照更大的事务ID），则该写入对于快照事务是不可见的。在单节点数据库上，一个简单的计数器就足以生成事务ID。

但是当数据库分布在许多机器上，也许可能在多个数据中心中时，由于需要协调，（跨所有分区）全局单调递增的事务ID会很难生成。事务ID必须反映因果关系：如果事务B读取由事务A写入的值，则B必须具有比A更大的事务ID，否则快照就无法保持一致。在有大量的小规模、高频率的事务情景下，在分布式系统中创建事务ID成为一个难以处理的瓶颈

我们可以使用同步时钟的时间戳作为事务ID吗？如果我们能够获得足够好的同步性，那么这种方法将具有很合适的属性：更晚的事务会有更大的时间戳。当然，问题在于时钟精度的不确定性。

为了确保事务时间戳反映因果关系，在提交读写事务之前，Spanner在提交读写事务时，会故意等待置信区间长度的时间。通过这样，它可以确保任何可能读取数据的事务处于足够晚的时间，因此它们的置信区间不会重叠。为了保持尽可能短的等待时间，Spanner需要保持尽可能小的时钟不确定性，为此，Google在每个数据中心都部署了一个GPS接收器或原子钟，这允许时钟同步到大约7毫秒以内

进程暂停

另一个分布式中危险使用时钟的例子：假设数据库分区只有一个主节点，只有主节点接受写入，那么其他节点如何确信该主节点没有被宣告失效，可以安全写入呢？

一种思路是主节点从其他节点获得一个租约，类似于一个带有超时的锁。某一个时间内只有一个节点可以拿到租约，某节点获得租约之后，在租约到期之前，他就是这段时间内的主节点。为了维持主节点的身份，节点必须在到期之前就定期更新租约，如果节点发生了故障，则续约失败，这样另一个节点到期之后就可以接管。

流程可以如下所示：

1
2
3
4
5
6
7
8
9

while(true){
    req = 获取租约();
    if (租约截止时间 - 系统当前时间 < 10秒) {
        刷新租约截止时间;
    }
    if (租约有效) {
        执行请求;
    }
}

这段代码，依赖于同步的时钟，租约到期时间由另一台机器设置（例如，另一台机器的当前时间+30s得到租约到期时间），并和本地时钟进行比较，如果时钟之间有超过几秒的差异，这段代码可能会出问题。

如果我们改为本地单调时钟，还有一个问题：代码假定时间检查点与请求处理时间间隔很短，通常代码运行足够快，所以设置 10s 的缓冲区来确保在请求处理过程中租约不会到期。

如果程序运行过程中出现了暂停，比如线程在执行请求用了 15s,，这时候租约已经过期，另一个节点接管了主节点就会产生问题。

那么一个线程会暂停这么多时间吗，产生的原因都可能有什么？

1. 很多编程语言有 GC，在运行期间会暂停正在运行的进程，这些GC可能甚至让程序暂停运行数分钟
2. 虚拟化环境中，可能会暂停虚拟机
3. 运行在终端用户设备（如笔记本电脑），执行也可能发生暂停
4. 操作系统执行线程上下文切换时，可能会产生GC
5. 操作系统配置了基于磁盘的内存交换分区，内存访问可能造成缺页中断，进而需要从磁盘中加载页。
6. 通过发送 SIGSTOP 信号来暂停 UNIX 进程。

分布式中的一个节点，必须假定，执行过程中的任何时刻都可能被暂停相当长一段时间，包括在运行函数的中间。

响应时间保证

某些软件如果在指定时间无法响应会造成严重后果，如：飞机、火箭、机器人，汽车和其他需要对输入传感器快速做出响应的组件等，这就是所谓的硬实时系统。

要保证实时，需要来自多个层面的硬件支持，首先是一个实时操作系统，保证进程在给定的时间间隔内完成CPU时间片的调度分配。其次，库函数也必须考虑最坏的执行时间。然后，动态内存分配很可能受限，或者被完全禁止。

调整垃圾回收影响

为了减少 GC 对程序造成的影响，现在一个较新的想法是把GC暂停视为节点的一个计划内的临时离线，当节点启动垃圾回收时，通知其他节点来接管客户端请求。此外，系统可以提前发出预警，让新请求不在来这个机器，这样此机器可以在无影响的情况下进行GC，对客户端隐藏了垃圾回收。

这些措施虽然不能完全规避 GC 带来的影响，但是可以有效减少对应用层的影响。

知识、真相与谎言

一个哲学问题，在分布式系统中，我们如何分别从分布式系统中来的信息哪些是真实的，哪些是假的，如果感知和测量的手段都不可靠，那么获得的信息有多大可信度。

真相由多数决定

假定一个发生非对称故障的网络环境，即某节点可以收到消息，但是它发出的消息要么被丢弃，要么被延迟发送。即使该节点本身运行良好，但其他节点无法顺利接受到响应，其他节点一直收不到他发的消息，就对网络宣布，该节点失效。

接下来是一个情况稍好的场景，半断开的节点可能会注意到其发送的消息没有被其他节点确认，因此意识到网络一定发生了某种故障。但是其他节点还是会认为他发生了故障，宣布该节点失效。

第三种情况，此节点的应用程序一直在 GC，所以无法处理其他节点的请求，其他节点得不到回应，就宣布此节点失效。

这几个故事的寓意是，节点不能根据自己的信息来判断自身状态，分布式系统不能依赖于单个节点。目前，许多分布式算法都依赖投票，任何决策都需要来自多个节点的最小投票数，从而减少对特定节点的依赖。

主节点与锁

很多情况，我们需要在系统范围内只能有一个实例，例如：

• 只允许一个节点作为数据库分区的主节点，以防止出现脑裂

(脑裂（split-brain）：指在一个高可用（HA）系统中，当联系着的两个节点断开联系时，本来为一个整体的系统，分裂为两个独立节点，这时两个节点开始争抢共享资源，结果会导致系统混乱，数据损坏。 对于无状态服务的HA，无所谓脑裂不脑裂；但对有状态服务(比如MySQL)的HA，必须要严格防止脑裂。)

• 只允许一个事务或者客户端持有特定资源的锁，以防止同时写入从而导致数据被破坏。
• 只允许一个用户使用特定用户名，确保用户名可以唯一标识用户

在分布式系统实现过程需要注意，即使某个节点自认为他是 唯一的那个（例如分区的主节点，锁的持有者，成功拿走用户名的请求），但不一定获得了系统法定票数同意。

当多数节点声明该节点已失效，而该节点还在充当唯一的那个，如果系统设计不周就会导致负面后果，该节点向其他节点继续发送消息，如果其他节点还选择相信他，就会出现错误行为。

Fencing令牌

当使用锁和租约机制来保护资源并发访问时，必须确保过期的节点不影响其他部分。要实现这个目标，采用一种相当简单的技术。

我们假设每次锁服务在授予锁和租约，都会返回一个令牌，该令牌每授予一次就会递增。客户端要求每次向存储发送写入请求时，都必须包含持有的令牌。

拜占庭将军问题

https://zh.wikipedia.org/zh/%E6%8B%9C%E5%8D%A0%E5%BA%AD%E5%B0%86%E5%86%9B%E9%97%AE%E9%A2%98

防护令牌可以检测和阻止无意中发生错误的节点（例如，因为它尚未发现其租约已过期）。但是，如果节点有意破坏系统的保证，则可以通过使用假防护令牌发送消息来轻松完成此操作。

在本书中，我们假设节点是不可靠但诚实的：它们可能很慢或者从不响应（由于故障），并且它们的状态可能已经过时（由于GC暂停或网络延迟），但是我们假设如果节点它做出了回应，它正在说出“真相”：尽其所知，它正在按照协议的规则扮演其角色。

如果存在节点可能“撒谎”（发送任意错误或损坏的响应）的风险，则分布式系统的问题变得更困难了——例如，如果节点可能声称其实际上没有收到特定的消息。这种行为被称为拜占庭故障（Byzantine fault），在不信任的环境中达成共识的问题被称为拜占庭将军问题

当一个系统在部分节点发生故障、不遵守协议、甚至恶意攻击、扰乱网络时仍然能继续正确工作，称之为**拜占庭容错（Byzantine fault-tolerant）**的，在特定场景下，这种担忧在是有意义的：

• 在航空航天环境中，计算机内存或CPU寄存器中的数据可能被辐射破坏，导致其以任意不可预知的方式响应其他节点。由于系统故障非常昂贵（例如，飞机撞毁和炸死船上所有人员，或火箭与国际空间站相撞），飞行控制系统必须容忍拜占庭故障

• 在多个参与组织的系统中，一些参与者可能会试图欺骗或欺骗他人。在这种情况下，节点仅仅信任另一个节点的消息是不安全的，因为它们可能是出于恶意的目的而被发送的。例如，像比特币和其他区块链一样的对等网络可以被认为是让互不信任的各方同意交易是否发生的一种方式，而不依赖于中心机构（central authority）

然而，在本书讨论的那些系统中，我们通常可以安全地假设没有拜占庭式的错误。在你的数据中心里，所有的节点都是由你的组织控制的（所以他们可以信任），辐射水平足够低，内存损坏不是一个大问题。制作拜占庭容错系统的协议相当复杂，而容错嵌入式系统依赖于硬件层面的支持。在大多数服务器端数据系统中，部署拜占庭容错解决方案的成本使其变得不切实际。

弱谎言形式

尽管我们假设节点通常是诚实的，但值得向软件中添加防止“撒谎”弱形式的机制——例如，由硬件问题导致的无效消息，软件错误和错误配置。这种保护机制并不是完全的拜占庭容错，因为它们不能抵挡决心坚定的对手，但它们仍然是简单而实用的步骤，以提高可靠性。例如：

• 由于硬件问题或操作系统、驱动程序、路由器等中的错误，网络数据包有时会受到损坏。通常，损坏的数据包会被内建于TCP和UDP中的校验和所俘获，但有时它们也会逃脱检测 。要对付这种破坏通常使用简单的方法就可以做到，例如应用程序级协议中的校验和。

• 可公开访问的应用程序必须仔细清理来自用户的任何输入，例如检查值是否在合理的范围内，并限制字符串的大小以防止通过大内存分配的拒绝服务。防火墙后面的内部服务对于输入也许可以只采取一些不那么严格的检查，但是采取一些基本的合理性检查（例如，在协议解析中）仍然是一个好主意。

• NTP客户端可以配置多个服务器地址。同步时，客户端联系所有的服务器，估计它们的误差，并检查大多数服务器是否对某个时间范围达成一致。只要大多数的服务器没问题，一个配置错误的NTP服务器报告的时间会被当成特异值从同步中排除。使用多个服务器使NTP更健壮（比起只用单个服务器来）。

理论系统模型与现实

已经有很多算法被设计以解决分布式系统问题——例如，我们将在第九章讨论共识问题的解决方案。为了有用，这些算法需要容忍我们在本章中讨论的分布式系统的各种故障。

算法的编写方式不应该过分依赖于运行的硬件和软件配置的细节。这就要求我们以某种方式将我们期望在系统中发生的错误形式化。我们通过定义一个系统模型来做到这一点，这个模型是一个抽象，描述一个算法可以假设的事情。

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

1. 同步模型：同步模型假定有上界的网络延迟，有上界的进程暂停和有上界的时钟误差。这并不意味着完全同步的时钟或者网络延迟为零。只是意味着你清楚的了解网络延迟、暂停和时漂移不会超过某个固定额上限。
2. 部分同步模型：部分同步意味着系统在大多数情况下像一个同步的系统运行，但是有时候会超出网络延迟，进程暂停和时钟漂移的预期上界。这是一个比较现实的模型：大多数情况下，网络和进程比较稳定，但是我们必须考虑到任何关于时机的假设都有偶尔违背的情况。
3. 异步模型：在这个模型中一个算法不会对时机做任何假设，甚至里面根本没有时钟。某些算法可以支持纯异步模型。

有以下三种最常见的节点失效系统模型：

1. 崩溃-中止模型：算法假设一个节点只能以一种方式发生故障，即遭遇系统崩溃。这意味着节点可能在任何时刻突然停止运行，且该节点以后永远消失，无法恢复。
2. 崩溃-恢复模型：节点可能在任意时刻发生崩溃，且可能会在一段未知的时间之后得到恢复并再次响应
3. 拜占庭（任意）失效模型：如上一节所示，节点可能发生任何事情，包括试图作弊和欺骗其他节点。

算法的正确性

定义算法的正确性，我们可以描述它的属性信息。例如：排序算法的输出具有以下特性：对于输出列表中的任何两个不同的元素，左边的元素小于右边的元素，这就是对一个列表进行排序的正确性描述。

类似的思路，我们可以通过描述目标分布式算法的相关属性来定义其正确性。例如：对于锁服务的 fencing 令牌生成算法，要求算法必须具有以下属性：

• 唯一性：两个令牌请求不能获得相同的值
• 单调递增：如果请求 x 返回了令牌 tx， 请求 y 返回了令牌 ty ,且 x 在 y 开始之前先完成，那么 tx < ty.
• 可用性：请求令牌的节点如果不发生崩溃则一定会收到最终的响应。

如果针对某个系统模型的算法在各种情况下都能满足定义好的属性要求，那么我们称这个算法是正确的。它的意义是，我们换一个角度来看一种极端情况，所有节点全部崩溃，或者所有的网络延迟变得无限长，那么所有的算法都不可能完成其预期功能。

安全与活性

我们需要区分两个属性：安全性 和 活性。在上面的例子中，唯一性和单调递增属于安全属性，而可用性属于活性。

这两种性质的区别是，活性的定义中通常会包含暗示「最终」一致性。

安全性通常可以理解为「没有发生意外」，而活性则类似「预期的的事情最终一定会发生」。这个非正式定义中，有很多主观因素，不用过度解读。安全性和活性是有准确和数学化的描述。

• 如果违反了安全属性，我们可以明确指向发生的特定时间点（例如，唯一性如果被违反，我们可以定位到具体哪个操作产生了重复的令牌）。且一旦违反安全属性，违规行为无法撤销，破坏已实际发生。
• 活性则反过来，可能无法明确某个具体的时间点（例如一个节点发送了一个请求，但还没有收到响应），但总希望在未来某个时间点可以满足要求。

区分安全性和活性的一个好处是可以帮助简化处理一些具有挑战性的系统模型。通常对于分布式算法，要求在所有可能的系统模型下，都必须符合安全属性。也就是即使所有的节点发生崩溃，或者整个网络终端，算法确保不会返回错误的结果。

对于活性，则存在一些必要条件。我们可以说，只有多数节点没有崩溃，以及网络最终可以恢复的前提下，我们才能保证最终可以收到响应。部分同步模型的定义即要求任何网络终端只会持续一段有限的时间，然后得到了修复。系统最终返回到同步的一致状态。

小结

本章讨论了分布式系统中可能发生的各种典型问题，包括：

• 当通过网络发送数据包时，数据包可能会丢失或者延迟；同样，回复也能丢失或者延迟。所以如果没有收到回复，并不能确定消息是否发送成功。
• 节点的时钟可能会与其他节点存在明显的不同步（尽管尽最大努力设置了NTP服务器），时钟还是可能会突然向前跳跃或者倒退，依靠精确的时钟存在一些风险，没有特别简单的办法来精确测量时钟的偏差范围。
• 进程可能在执行过程中任意时候，遭遇长度未知的暂停（一个重要的原因是垃圾回收），结果他被其他节点宣告为失效，尽管后来又恢复执行，却对中间的暂停一无所知。

部分失效可能是分布式系统的关键特征，只要软件试图跨节点做任何事情，就有可能出现失败，或者随机变慢，或者根本无应答。对于分布式环境，我们的目标是简历容忍部分失效的软件系统，这样即使某些部件失效，系统还是可以继续运行。

为了容忍错误，第一步是检测错误，但是多数系统没有检测节点是否发生故障的准确机制，因此分布式算法更多依靠超时来确定远程节点是否可用。但是，超时无法区分网络和节点故障，且可变的网络延迟有时会导致节点被误认为发生崩溃。

检测到错误之后，让系统容忍失效也不容易。在典型的分布式环境下，没有全局变量，没有共享内存，没有约定的尝试或跨其他节点的共享状态。节点甚至不清楚现在的准确时间，更别提其他更高级的了。信息从一个节点流动到另一个节点只能是通过不可靠的网络来发送，单个节点无法安全的做出任意决策，而是需要多个节点之间的公式协议，并争取达到法定票数。

如果习惯与编写单机环境理想化环境运行的软件，当转向分布式时，种种看似凌乱的现实可能着实让人震惊。相反，如果单节点上即可解决问题，那么对于一个分布式系统工程师通常会被认为该问题微不足道。

可扩展性并不是使用分布式系统的唯一原因。容错与低延迟也是同样重要的目标，而后两者无法靠单节点来实现。

我们也探讨了网络、时钟和进程的不可靠性是否是不可避免的自然规律，我们对此给出的结论是否定的：的确有可能在网络中提供硬实时的延迟保证或者具有上确界的延迟，但代价昂贵，且硬件资源利用很低。除了安全关键场景，目前绝大多数都选择了低成本。

我们还探讨了高性能计算，他们采用更可靠的组件，发生故障时完全停止系统，之后重启。相比之下，分布式系统会长时间不间断运行，以避免影响服务级别。故障处理和系统维护多以节点为单位进行处理，或者理论上如此。

这样看起来本章全是在揭露安全问题，前景黯淡。下一章，我们会讨论解决方案，重点是针对这些问题而设计的相关分布式算法。

最后修改于 2021-09-09