分布式系统的挑战

故障与部分失效

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

正是由于这种不确定性和部分失效大大提高了分布式系统的复杂性。要使分布式系统可靠工作，就必然面临部分失效，这就需要依靠软件系统来提供容错机制。换句话说，我们需要在不可靠的组件之上构建可靠的系统。

不可靠的网络

互联网和数据中心中的大多数内部网络都是异步分组网络（asynchronous packet networks）。在这种网络中，一个节点可以向另一个节点发送一个消息，但是网络不能保证它什么时候到达，甚至是能否到达。发送之后等待响应过程中，有很多事情可能会出错：

请求可能已经丢失（可能有人拔掉了网线）。
请求可能正在排队，稍后将交付（也许网络或接收方过载）。
远程节点可能已经失效（比如是崩溃或关机）。
远程节点可能暂时停止了响应（遇到长时间的垃圾回收）。
远程节点可能已经处理了请求，但是网络上的响应已经丢失（可能是网络交换机配置错误）。
远程节点可能已经处理了请求，但是响应被延迟处理（可能是网络或者你自己的机器过载）。

发送者甚至不清楚数据包是否完成了发送，只能选择让接收者来回复响应消息，但回复也有可能丟失或延迟。这些问题在一个异步网络中无法明确区分，发送者拥有的唯一信息是，尚未收到响应，但却无法判定具体原因。

处理这个问题通常采用超时机制，即在等待一段时间之后，如果仍然没有收到回复则选择放弃，并且认为响应不会到达。 但是，即使判定超时，仍然并不清楚远程节点是否收到了请求（一种情况，请求仍然在某个地方排队，即使发送者放弃了，但最终请求会发送到接收者)。

那如何确定这个超时时间呢？

较长的超时值意味着更长时间的等待，才能宣告节点失效。而在此期间，用户只能等待或者拿到错误信息。
较短的超时设置可以帮助快速检测故障，但可能会出现误判，例如实际上节点只是出现暂时的性能波动(由于节点或网络上的高负载峰值，结果却被错误地宣布为失效。

这并没有一个标准的答案，而需要结合具体的业务场景来进行分析。 通常通过实验的方式来一步步设置超时。先在多台机器上，多次测量网络往返时间，以确定延迟的大概范围，然后结合应用特点，在故障检测与过早超时风险之间选择一个合适的中间值。

超时设置并不是一个不变的常量，而是需要持续测量响应时间及其变化，然后根据最新的响应时间分布来自动调整。 可以用 Phi Accrual 故障检测器完成，该检测器目前已在 Akka 和 Cassandra 中使用。TCP的重传超时也采用了类似的机制。

不可靠的时钟

在分布式系统中，时间总是件棘手的问题，由于跨节点通信不可能即时完成，消息由网络从一台机器到另一台机器总是需要花费时间。收到消息的时间应该晚于发送的时间，但是由于网络的不确定延迟，精确测量面临着很多挑战。这些情况使得多节点通信时很难确定事情发生的先后顺序。

同时，网络上的每台机器都有自己的时钟硬件设备。这些设备并非绝对准确，即每台机器都维护自己本地的时间版本，可能比其他机器稍快或更慢。

时钟

现代计算机内部至少有两种不同的时钟，一个是日历时钟（time-of-day clock），另一个是单调时钟（monotonic clock）。虽然它们都可以衡量时间，但要仔细区分二者，本质上他们是服务于不同的目的。

日历时钟

日历时钟会根据某个日历返回当前的日期与时间。 例如，Linux 上的 clock_gettime(CLOCK_REALTIME) 会返回自纪元 1970 年 1 月 1 日（ UTC ）以来的秒数和毫秒数，不含闺秒。而有些系统则使用其他日期作为参考点。

日历时钟通常与 NTP 服务器同步，这意味着来自一台机器的时间戳（理想情况下）与另一台机器上的时间戳相同。但是，如果本地时钟远远快于 NTP 服务器，则它可能会被强制重置，跳回到先前的某个时间点。这种跳跃经常忽略闰秒，导致其不太适合测量时间间隔。可以在一定程度上同步机器之间的时钟，最常用的方法也是网络时间协议 NTP （Network Time Protocl），它可以根据组专门的时间服务器来调整本地时间，时间服务器则从精确更高的时间源获取高精度时间。

单调时钟

单调时钟适用于测量持续时间（时间间隔），例如超时或服务的响应时间。Linux 上的 clock_gettime(CLOCK_MONOTONIC) 返回的即是单调时钟。单调时钟的名字来源于它们保证总是向前走（日历时钟会出现的回拨现象）。

可以在一个时间点读取单调时钟的值，完成某项工作，然后再次检查时钟。时钟值之间的差值即两次检查之间的时间间隔。==注意，单调时钟的绝对值井没有任何意义，它可能是电脑启动以后经历的纳秒数或者其他含义。因此比较不同节点上的单调时钟值毫无意义，它们没有任何相同的基准==。

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

进程暂停

在分布式环境中，进程暂停有时会引起意想不到的时钟问题。

假如有这样一个场景，主节点从其他节点获得一个租约，类似一个带有超时的锁。为了维持主节点的身份，节点必须在到期之前定期去更新租约。如果节点发生了故障，则续约失败，这样另一个节点到期之后就可以接管。代码逻辑如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


while (true) {
  request = getIncomingRequest();
  // 确保租约还剩下至少10秒
  if (lease.expiryTimeMillis - System.currentTimeMillis() < 10000){
    lease = lease.renew();
  }

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

上述代码依赖于同步的时钟，即租约到期时间由另一台机器所设置，并和本地时钟进行比较。如果时钟之间有超过几秒的差异，这段代码会出现些奇怪的事情。

即使我们改为仅使用本地单调时钟，还有另一个问题：代码假定时间检查点 System.currentTimeMillis() 与请求处理 process(request) 间隔很短，通常代码运行足够快，所以设置 10 秒的缓冲区来确保在请求处理过程中租约不会过期。

如果程序执行中出现了某些意外的暂停呢？假设线程在 lease.isValid() 消耗了了整 15 秒。那么当开始处理请求时，租约已经过期，而另一个节点已经接管了主节点。可惜我们无告有效通知线程暂停了这么长时间了，后续代码也不会注意到租约已经到期，除非运行到下一个循环迭代。不过，到那个时候它已经做了不安全的请求处理。

那什么原因会带来这么长时间的暂停呢？可能会存在以下事件

许多编程语言都有垃圾收集器（ GC ），有时运行期间会暂停所有正在运行的线程。
在虚拟化环境中，可能会暂停虚拟机（暂停所有执行进程并将内存状态保存到磁盘）然后继续（从内存中加载数据然后继续执行）。
运行在终端用户设备时，执行也可能发生暂停。例如用户关机脑或休眠。
当操作系统执行线程上下文切换时，或者虚拟机管理程序切换到另一个虚拟机时，正在运行的线程可能会在代码的任意位置被暂停。
如果应用程序执行同步磁盘访问，则线程可能暂停，直到缓慢的磁盘 I/O 操作完成。
如果操作系统配置了基于磁盘的内存交换分区，内存访问可能触发缺页中断，进而需要从磁盘中加载内存页。当 I/O 进行时线程为暂停。
发送 SIGSTOP 信号来暂停 UNIX 进程，例如通过在 shell 中按下 Ctrl+Z。这个信号立即阻止进程继续执行更多的 CPU 周期，直到 SIGCONT 恢复为止，此时它才会继续运行。

所有这些事件都可以随时抢占正在运行的线程，并在稍后的时间恢复运行，而线程甚至不会注意到这一点。这个问题类似于在单个机器上使多线程代码线程安全，因此你不能对时序做任何假设，因为随时可能发生上下文切换，或者出现并行运行。

所以分布式系统中的每个节点都必须假定，执行过程中的任何时刻都可能被暂停相当长一段时间，即使是运行在某个函数中间。 暂停期间，整个集群的其他部分都在照常运行，甚至会一致将暂停的节点宣告为故障节点。最终，暂停的节点可能会回来继续运行，除非再次检查时钟，否则它对刚刚过去的暂停一无所知。

知识、真相与谎言

真相由多数决定

假定在一个发生了非对称故障的网络环境中，即某节点能够收到发送给它的消息，但是该节点发出的所有消息要么被丢弃，要么被推迟发送。即使该节点本身运行良好，可以接收来自其他节点的请求，但其他节点却无法顺利收到响应。当消息超时之后，由于都收不到回复，其他节点就会一致声明上述节点发生失效。

综上所述，节点不能根据自己的信息来判断自身的状态。分布式系统不能完全依赖单个节点，因为节点可能随时失效，也可能暂停或者假死，甚至最终无法恢复。目前许多分布式算法都依赖于法定人数，即在节点之间进行投票。任何决策都需要来自多个节点的最小投票数，以减少对于某个特定节点的依赖。

最常见的法定人数是取系统节点半数以上。如果某些节点发生故障，quorum 机制可以使系统继续工作（对于三个节点的系统，可以容忍一个节点失效）。由于系统只可能存在一个多数，绝不会有两个多数在同时做出相互冲突的决定，因此系统的决议是可靠的 （防止脑裂）。

拜占庭故障

如果节点存在撒谎的情况（即故意发送错误的或破坏性的响应），那么分布式系统处理的难度就上了一个台阶。例如，节点明明没有收到某条消息，但却对外声称收到了。这种行为称为拜占庭故障，在这样不信任的环境中需要达成共识的问题也被称为拜占庭将军问题。

拜占庭将军问题

拜占庭将军问题是所谓“两将军问题”的更抽象标识，后者假定有两名将军需要就战斗计划达成一致。由于他们在两个不同的地点建立了营地，中间只能通过信使进行沟通，而信使在传递消息时可能会出现延迟或丢失（就像网络中的信息包一样）。

而在拜占庭版本中，有 n 位将军需要达成共识，并且其中存在一些叛徒试图阻挠共识的达成，即使大多数的将军都是忠诚的，发出了真实的信息，但是叛徒则试图通过发送虚假或不真实的信息来欺骗和混淆他人（同时努力隐藏自己）。而且大家事先并不知道叛徒是谁。

如果某个系统中即使发生部分节点故障，甚至不遵从协议，或者恶意攻击、干扰网络，但仍可继续正常运行，那么我们称之为拜占庭式容错系统。这种担忧在某些场景下是合理的：

在航空航天领域，计算机内存或 CPU 寄存器中的数据可能会被辐射而发生故障，导致以不可预知的方式响应其他节点。这种情况下如果将系统下线，代价将异常昂贵（例如，可能出现飞机撞毁或致使火箭与国际空间站相撞等），飞行控制系统必须做到容忍拜占庭故障。
在有多个参与者的系统中，某些参与者可能会作弊或者欺骗他人。这时节点不能完全相信另一个节点所发送的消息，它可能就是恶意的。例如，像比特币和其他区块链一样的点对点网络就是让互不信任的当事方就某项交易达成一致，且不依赖于集中的机制。

大多数拜占庭容错算法要求系统超过三分之二的节点功能正常，例如有四个节点，则最多允许一台发生故障）。要采用这类算法对付 bug ，必须有四种不同的软件实现，然后希望该 bug 只出现在四个实现中的一个。但这并不现实，通常如果攻击者可以入侵一个节点，则很可能会攻陷几乎所有节点（由于运行相同的软件）。因此，传统的安全措施如认证、访问控制、加密、防火墙等仍是防范攻击的主要保护机制。

理论系统模型与现实

目前分布式系统方面已有许多不错的具体算法（如共识算法 Raft、Paxos 等），而算法的实现不能过分依赖特定的硬件和软件配置。这就要求我们需要对预期的系统错误进行形式化描述。我们通过定义一些系统模型来形式化描述算法的前提条件。

关于计时方面有三种常见的系统模型：

同步模型：假设网络延迟、进程暂停和和时钟误差都是受限的。这并不意味着完全同步的时钟或网络延迟为零。这只意味着你清楚了解网络延迟、进程暂停和时钟漂移将永远不会超过某个固定的上限。大多数实际系统的现实模型并不是同步模型，因为无限延迟和暂停确实会发生。
部分同步模型：意味着一个系统在大多数情况下像一个同步系统一样运行，但有时候会超出网络延迟、进程暂停和时钟漂移的界限。这是一个比较现实的模型，大多数情况下，网络和进程表现良好（否则无法持续提供服务），但是我们必须承认，在任何时刻都存在时序假设偶然被破坏的事实。而一旦发生这种情况，网络延迟、暂停和时钟错误可能会变得相当大。
异步模型：在这个模型中，一个算法不允许对时序做任何假设——事实上它甚至没有时钟（所以它不能使用超时）。一些算法被设计为可用于异步模型，但非常受限。

除了时机之外，我们还需要考虑节点失效。有以下三种最常见的节点失效系统模型：

崩溃-中止：在崩溃-中止模型中，算法假设一个节点只能以一种方式发生故障，即遭遇系统

崩溃。这意味着节点可能在任何时候突然停止响应，且该节点以后永远消失，无法恢复。
崩溃-恢复：节点可能会在任何时候发生崩溃，且可能会在一段时间之后得到恢复并再次响应。在崩溃－恢复模型中，节点上持久性存储的数据会在崩溃之后得以保存，而内存中状态可能会丢失。
拜占庭（任意）故障：节点可以做任何事情，包括试图戏弄和欺骗其他节点。

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

为了定义算法的正确性，我们可以描述它的一些属性信息。如果针对某个系统模型的算法在各种情况下都能满足定义好的属性要求，那么我们称这个算法是正确的。而其中最重要的两种属性是安全性与活性。安全性通常可以理解为没有发生意外，而活性则类似预期的事情最终一定会发生（如最终一致性）。

对于分布式算法，要求在所有可能的系统模型下，都必须符合安全属性。也就是说，即使所有节点都发生崩溃，或者整个网络中断，算法确保不会返回错误的结果。 而对于活性，则存在一些必要条件。例如，只有在多数节点没有崩溃，以及网络最终可以恢复的前提下，我们才能保证最终可以收到响应。 部分同步模型的定义即要求任何网络中断只会持续一段有限的时间，然后得到了修复，系统最终返回到同步的一致状态。