这是对分布式系统中的一个全面的、近乎悲观的总结。故障可能来源于网络问题，时钟与时序问题。

故障与部分失效

我们期望的情况是要不功能正常，要不完全失效，不会介于这两者之间。因此我们宁可让计算机崩溃，也不能返回一个错误的结果。

但这种情况在涉及多个节点时，理想化的标准正确模型就很难再适用。可能系统的一部分正常工作，一部分出现难以预料的故障，称之为部分失效。

不可靠的网络

互联网以及大多数数据中心的内部网络（通常是以太网）都是异步网络。一个节点发消息到另一个节点，但网络不能保证它什么时候到达。而且在这个过程中，很多事情可能出错：

  1. 请求可能已经丢失（可能有人拔掉了网线）。
  2. 请求可能正在排队，稍后将交付（也许网络或接收方超载）。
  3. 远程节点可能已经失效（可能是崩溃或关机）。
  4. 远程节点可能暂时停止了响应（可能会遇到长时间的垃圾回收暂停）。
  5. 远程节点可能已经处理了请求，但是网络上的响应已经丢失（可能是网络交换机配置错误）。
  6. 远程节点可能已经处理了请求，但是响应已经被延迟，并且稍后将被传递（可能是网络或者发送方过载）。

处理这个问题通常是超时机制：等待一段时间后，如果仍然没有收到恢复则选择放弃，并且认为响应不会到达。但即使判定超时，仍然不知道远程节点是否收到了请求。

检测故障

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

  • 负载均衡器需要停止向已死亡的节点转发请求（即下线处理）。
  • 在单主复制功能的分布式数据库中，如果主库失效，则需要将从库之一升级为新主库，但是由于网络的不确定性很难准确判断节点是否确实失效。
  • 节点在处理请求时崩溃，很难直到处理了多少数据。
  • 如果服务进程崩溃，但操作系统正常，可以通过脚本通知其他节点。以便新节点快速接管而跳过等待超时。HBase采用这个。

相反，如果出了什么问题，你可能会在堆栈的某个层次上得到一个错误响应，但总的来说，你必须假设你根本就没有得到任何回应。您可以重试几次（TCP重试是透明的，但是您也可以在应用程序级别重试），等待超时过期，并且如果在超时时间内没有收到响应，则最终声明节点已经死亡。

超时与无期限的延迟

超时时间的设置很难，时间长的超时值意味着更长时间的等待，在此期间用户会收到异常信息。较短的超时时间可能会出现误判，比如出现网络波动。

如果节点实际上活着，过早声明为失效，新节点尝试接管，则可能操作在两个节点执行两次。

节点被宣告失效，承担的责任会移交给其他节点，如果系统已经处于高负荷状态，节点因为负载过高而出现响应缓慢，转移负载到其他节点可能会导致失效扩散。

如果一个网络延迟控制在时间d内，要不完成交付，要不丢失，非故障节点在时间r内完成处理，那么成功请求在2d+r内收到响应，那么2d+r是一个理想的超时设置。

但绝大多数系统没有类似的保证：异步网络理论上延迟无限大，多数服务端无法保证给定的某个时间内一定完成处理请求。

网络拥塞和排队

  • 当多个不同节点同时发送数据包到相同节点时，网络交换机会排队，依次发送数据库包到目标网络。如果网络负担重，可能需要等一会，如果交换机队列塞满，则数据包可能被丢弃，引发大量重传。
  • 数据包到达目标机器后，如果cpu繁忙，请求被操作系统排队，直到程序处理。
  • 虚拟化环境中，cpu会切换虚拟机，导致操作系统会突然暂停几十毫秒。这段时间，客户虚拟机无法从网络接受任何数据。
  • TCP执行流量控制时，节点会主动限制自己的发送速率以避免加大网络负载。意味着在发送方排队。

以上因素会导致网络延迟的变化。当系统有足够处理能力，排队会被处理，但接近系统最大涉及上限时，排队对延迟的影响就变得明显。

更好的办法是，超时设置并不是一个不变的常量，而是持续测量响应时间及其变化，然后根据最新的响应时间分布来自动调整。这可以通过Phi Accrual故障检测器来完成，该检测器在例如Akka和Cassandra中使用。 TCP超时重传机制也同样起作用。

同步与异步网络

传统的固话网络是同步的，语音延迟和掉话现象极为罕见。在电话拨通时，系统会动态的建立一条电路：在整个线路上为呼叫分配一个固定的，带宽有保证的通信链路，一直到通信结束。即使数据中间经过多个路由器，16bit空间在电路建立时已经在网络中保留，不会受到排队影响。没有排队，端到端延迟是固定的，称为有界延迟。

不可靠的时钟

网络上的每台机器都有自己的时钟硬件设备，通常是石英晶体震荡器。这些设备不是绝对精确的，每台机器都维护自己本地的时间副本，可能比其他机器稍快或更慢。可以在一定程度上同步时钟：最常用的机制是网络时间协议（NTP），它可以根据一组专门的时间服务器来调整本地时间。时间服务器则从精确度更高的时间源（如GPS接收机）获取高精度时间。

单调时钟与墙上时钟

现代计算机内部至少有两种不同的时钟：一个是墙上时钟（钟表时间），一个是单调时钟。

墙上时钟

根据某个日历来返回当前的日期与时间。比如Linux的clock_gettime(CLOCK_REALTIME)和Java中的System.currentTimeMillis()返回自epoch以来的秒数（或毫秒），根据公历日历，不包括闰秒。有些系统使用其他日期作为参考点。

墙上时钟可以与NTP同步。

单调时钟

单调时钟更适合测量时间间隔。Linux上的clock_gettime(CLOCK_MONOTONIC)，和Java中的System.nanoTime()都是单调时钟。单调时钟能保证他们总是向前。

单调时钟的绝对值没有任何意义，它可能是电脑启动以后经历的纳秒数或其他含义。比较不同节点的单调时钟值没有任何意义。

如果有多个cpu，每个cpu可能有单独的计时器，不与其他cpu同步。应用程序的线程可能在不同cpu上，操作系统会补偿多个计时器的偏差，从而为应用层提供统一的单调递增计时。

在分布式系统中，可以采用单调时钟测量一段任务的持续时间，它不假定节点间有任何的时钟同步，且可以容忍轻微的测量误差。

时钟同步与准确性

单调时钟不需要同步，墙上时钟需要根据NTP服务器或其他时间源来同步。

但计算机的石英钟不够精确，存在漂移现象。时钟漂移主要取决于机器的温度。如果时钟与NTP服务器差别太大，可能出现拒绝同步，或本地时钟将被强制同步。同步过程也会受网络影响。

另外闰秒也会产生一分钟为59秒或61秒的现象，这会使一些对闰秒无防范的系统出现混乱。处理闰秒的推荐方案是在NTP服务器汇报时间时故意做些调整，目的是在一天的周期内逐步调整闰秒。

虚拟机中，当虚拟机共享一个cpu内核时，每个虚拟机会出现数十毫秒的暂停以切换虚拟机。应用角度看就会时钟向前发生了跳跃。

有的场景需要高精度的时钟，比如金融操作，需要在100微秒内同步时钟。采用GPS接收机，精确时间协议（PTP）。

依赖同步的时钟

时钟问题是不容易及时发现的，如果需要精确同步的时钟，最好仔细监控所有节点的时钟偏差。如果某个节点的时钟漂移超出上限，应将其宣告为失败，从集群移除。这样确保在造成重大影响前尽早发现并处理问题。

时间戳与事件顺序

在多个节点对事件进行排序，如果它依赖时钟，就有一定的技术风险。

上图是在一个多领导者复制的数据库中，客户A写到节点1，节点1异步复制到2和3，客户B进行同样的操作，给x加一，但节点2收到两个事件时，会根据时间戳错误判断x=1是新的值，然后导致客户B的增量操作丢失。

这种冲突解决测量叫最后写入获胜（LWW），在多主和无主节点复制中广泛使用。LWW的根本问题是：

  • 数据库写入可能会神秘地消失：后续发生的写操作没法覆盖一个较早的值，因为后者节点时钟太快了，导致一些数据丢弃并且没有报告任何错误。
  • LWW无法区分高频顺序写入和真正并发写入（写操作不依赖其他写）。需要额外的因果关系跟踪机制（例如版本向量），以防止因果关系的冲突。
  • 由于时钟精度的限制（比如毫秒级），两个节点可能独立产生了相同时间戳。为了解决这样的冲突，需要一个额外的仲裁值（可能是大的随机数），但无法区分因果关系。

这种错误的顺序问题很难避免，除了石英漂移等误差来源，NTP同步精度也收到网络影响。

时钟的置信区间

墙上时钟或许会返回微秒甚至纳秒的信息，但这种精度的测量值是不可信的。因为随便一个误差就会高达几毫米甚至几十毫秒。

因此，我们将时钟读数视为一个带有置信区间的时间范围。比如系统有95%的置信度任务事件介于10.3-10.5之间，那么时间戳中那些微秒级的读数毫无意义。

但大多数系统不提供这种误差查询接口。当调用clock_gettime()的时候，返回值没有误差信息，不知道置信区间。

但谷歌的Spanner中的TrueTime API可以明确报告本地时钟的置信区间。查询时间时会返回两个值，【不早于，不晚于】。时间间隔范围主要取决于本地石英钟最后于高精时钟源同步后所经历的时间长短。

全局快照的同步时钟

快照隔离需要单调递增的事务ID，如果数据库分布在多台机器上，就需要一个全局单调递增的事务ID。事务ID要求必须反映因果关系：事务B如果要读取事务A写入的值，则B的事务ID必须大于A的事务ID，否则快照将不一致。如果有很多的小数据包，则分布式系统中创建事务ID会引入瓶颈。

如果能将墙上时钟进行同步，则用时间戳来衡量事务ID更方便。Google Spanner的True Time API，如果有两个置信区间，$A = [A_{earliest}, A_{latest}]$， $B=[B_{earliest}, B_{latest}]$， 这两个区间如果不重叠（即：$A_{earliest} < A_{latest} < B_{earliest} < B_{latest}$），则B一定在A之后。为此，Google在每个数据中心部署了一个GPS接收器或原子钟，保证所有时间同步在约7ms内完成。

借助时钟同步来处理分布式事务语义处理Google意外，主流数据库还没有更多实现，但整个领域很活跃和有趣。

进程暂停

关于主从复制中如何判断主节点存活，有这样一种思路：主节点从其他节点获取一个租约（类似带时间的锁），只有一个节点能获取租约，某节点获取租约后，要在超时前定期去续约。如果节点发生故障，则续约失败，其他节点接管。

这种方案，依赖同步的时钟，租约到期时间是另一个节点设置，但和本地时钟进行比较。如果时钟有几秒的差异，可能就会出现问题。

通常判断是否过期与请求处理间隔很短，但如果进程执行出现意外的暂停，那就会出问题。导致进程暂停的原因有很多：

  • GC暂停，即使所谓的并发垃圾收集器也不能完全与应用代码并行运行。
  • 虚拟化环境，可能暂停虚拟机（比如将内存状态保存到磁盘）然后继续。通常用于实时迁移，把虚拟机迁移到另一个主机但不用重启。
  • 运行在终端设备（笔记本），可能由于用户关机或休眠而暂停。
  • 执行线程上下文切换或在虚拟化环境进行虚拟机切换，如果负载很高，可能需要暂停一段时间。
  • 同步磁盘IO
  • 操作系统触发缺页中断，内存压力很大时，可能花大量时间在内存换入换出上（称为抖动）。通常在服务器禁止页面调度，宁愿干掉一个进程来释放内存，也不愿意冒抖动风险。
  • 可以通过发送SIGSTOP信号来暂停Unix进程，例如通过在shell中按下Ctrl-Z。 这个信号立即阻止进程继续执行更多的CPU周期，直到SIGCONT恢复为止，此时它将继续运行。 即使你的环境通常不使用SIGSTOP，也可能由运维工程师意外发送。

这些情况都可能抢占一个正在运行的线程，而且线程一无所知。分布式系统任何节点必须假定，执行中可能会暂停一段时间，暂停时集群其他部分照常运行。最终，暂停的节点可能会回来继续运行，除非再次检查时钟，否则它对刚刚的暂停毫无知觉。

响应时间保证

线程和进程虽然可能会暂停相当长的时间，但如果对系统进行一些配置，这些原因是可以消除的。

有些软件如果在指定时间内无法响应会造成相当严重后果，比如飞机上对输入传感器快速做出响应的组件等。对这种系统，软件必须有一个做出响应的上限，如果不满足，就会有系统级的故障。这就是所谓的硬实时（hard real-time）系统。

但实时系统往往有很多限制，比如编程语言等，往往吞吐率低，而且造价高昂。对大多数服务器并不适用。

调整垃圾回收的影响

可能把GC暂停视为节点的一个计划内的临时离线，当节点启动垃圾回收时，通知其他节点来接管客户端请求。目前一些延迟敏感的系统（如金融交易系统）已经采用这种方法。

知识、真相与谎言

分布式系统中，节点只能通过消息交换来获得其他节点当前的状态，如果远程节点没有响应，没法区分网络问题还是节点问题，就不知道节点处于什么状态。

真相由多数决定

如果某个节点可以收到别的节点的消息，但发出去的消息要么丢弃，要么延迟发送。其他节点就会一致声明上述节点失效。比如可能垃圾收集运行很长时间。

节点不能根据自己的信息来判断自己的状态，由于节点可能随时失效或暂停-假死，因此分布式系统不能完全依赖某个节点。许多分布式算法都依靠法定票数，即节点间投票。

主节点与锁

有时，我们需要在系统范围内只能有一个实例：

  • 只允许一个节点作为分区主节点，防止脑裂。
  • 只允许一个事务或客户端持有锁。
  • 只允许一个用户来使用特定的用户名，从而确保用户名可以唯一标识用户。

另外，一个节点即使自认为它是 ”唯一“ 的主节点，但不一定获得了系统法定票数同意。它可能以前是主节点，但其他节点已经宣布它失效并选出另外的主节点。

比如下面的例子：

持有租约的客户端被暂停太久直到租约到期，另一个客户端获取租约，并写了文件，当暂停的客户端回来时，它仍错误的认为合法持有锁并尝试写文件，导致客户2的文件被破坏。

fencing令牌

假设每次锁服务在授予锁或租约时，还会同时返回一个 fencing 令牌，该令牌（数字）没授予一次就会递增。然后要求客户端每次向存储系统发送写请求时，都必须包含所持有的 fencing 令牌。

使用 ZooKeeper 作为锁服务时，可以用事务标识 zxid 或节点版本 cversion 来充当 fencing 令牌，这两个都可以满足单调递增要求。

这种令牌检查通常在服务端进行，虽然看起来复杂，但这可以防止一些客户端的滥用情况。

拜占庭故障

fencing 令牌可以防止那些误操作，但节点试图破坏系统，发送消息时可以简单的伪造令牌。

之前的假设是节点不可靠，但一定是诚实的，但如果节点出现 ”撒谎“ 的情况，分布式难度就上升一个台阶。例如节点明明没收到某条消息，但对外声称它收到了，这就是拜占庭故障。在这样不信任的环境中需要达到共识的问题也叫拜占庭将军问题。

如果某个系统即使发生部分节点故障，甚至不遵从协议，故意攻击，干扰网络，仍可继续正常运行，我们称之为拜占庭式容错系统。比如：

  • 航天领域，内存或 CPU 寄存器中的数据可能会被辐射而发生故障，导致以不可预知的方式响应其他节点。
  • 有多个参与者的系统中，某些参与者可能会作弊或欺骗他人。比如比特币和其他区块链一样的点对点网络就是让互不信任的当事方就某项交易达成一致，且不依赖于集中的机制。

但在数据中心中，所有节点都由一个组织集中控制（可信任），辐射水平也可以忽略。绝大多数服务器端数据系统中，部署拜占庭容错解决方案基本不太可行。

软件的bug可以被认为是拜占庭故障，但如果将相同软件部署到所有节点，拜占庭式的容错算法也没办法解决问题。因为大多数容错算法要求系统超过三分之二的节点是功能正常的。

弱的谎言形式

就算假定节点是诚实的，但依然推荐增加必要的机制来防范一些不那么恶意的 ”谎言“。虽然不是完整的拜占庭容错，但简单实用，提高系统的可靠性和健壮性。比如由于硬件或操作系统等错误，导致网络数据包出现损坏，一些简单的防范措施就是在应用层添加校验和。另一个是需要对公众开放的应用检查用户是所有输入，比如检查输入值大小，字符串大小，防止分配超大内存。

理论系统模型与现实

分布式系统的算法不能过分依赖特定的硬件和软件配置。这要求我们需要对预期的系统错误进行形式化描述。我们通过定义一些系统模型来形式化描述这些算法的前提条件。

关于时间方面，有三种常见的模型：

  • 同步模型：同步模型假定有上界的网络延迟，有上界的进程暂停和有上界的时钟误差。就是这些不会超过一个界限。大多数实际系统的实际模型并非同步模型，因为无限延迟和暂停确实可能发生。
  • 部分同步模型：大多数情况下像一个同步系统一样运行，但有时候会超出网络延迟，进程在那头和时钟漂移的预期上界。这是个比较现实的模型。
  • 异步模型：算法不会对时机做出任何假设，甚至里面根本没有时钟。某些算法支持异步模型，但并不常见。

除了时间外，还要节点失效。这有三种最常见的节点失效系统模型：

  • 崩溃-中止模型：算法假设一个节点只能以一种方式发生故障，即遭遇系统崩溃。意味着节点可能在任何时候突然停止响应，且节点以后永远消失，无法恢复。
  • 崩溃-恢复模型：节点可能在任何时候发生崩溃，但可能在一段时间后得到恢复并再次响应。节点上持久性存储的数据在崩溃中得以保存，但内存的状态可能丢失。
  • 拜占庭失效模型：节点可能发生任何事情，包括试图作弊和欺骗其他节点。

真是系统的建模，最普遍用的就是崩溃-恢复模型结合部分同步模型。

算法的正确性

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

比如前面锁服务的 fencing 令牌算法，属性有：

  • 唯一性：两个令牌请求不能获得相同的值。
  • 单调递增
  • 可用性：请求令牌的节点不发生崩溃最终一定会收到响应。

如果针对某个系统模型的算法在各种情况下都能满足定义好的属性要求，那么我们称这个算法是正确的。

安全性和活性

在上面令牌算法中，唯一性和单调递增就是安全性，可用性则属于活性。

安全性可以理解为 ”没有发生意外“，而活性则类似 ”预期的事情最终一定会发生“。

  • 如果违反了安全性，我们可以明确的指向发生的特定的时间点。且一旦违法安全属性，违规行为无法撤销，破坏已经发生。
  • 活性则反过来，可能无法明确某个具体的时间点，但总是希望在未来某个时间点能满足要求。

通常对于分布式算法，要求所有可能的系统模型下，都符合安全性。对于活性，则存在一些必要条件，比如只有在大多数节点没有崩溃的情况下，只有当网络最终从中断中恢复时，我们才可以说请求需要接收响应。