Fault Tolerance

容错一节，意为讨论分布式系统、大数据系统中的故障容忍机制。

Outline

• 有哪些故障
• 什么是故障容忍
• 故障容忍算法
• 故障容忍下的共识
• 故障容忍的其他主题

Fault

下面讨论的Fault（故障）仅针对分布式系统、大数据系统中出现的故障。

Fault is Common in Complex Systems

• 假设计算机上存在一个孤立运行的程序，我们通常认为它的运行是可预测的。
• 现代的应用软件通常运行在不同的操作系统上，使用不同的硬件设备，通过互联网通信，与不同的用户交互；这时，内核panic、外设连接松动、网络拥塞、未考虑的用户输入，各个环节的出错都可能导致软件不正常工作。
• 庞大的多处理器系统中，前述可能出错的因素有更高量级的规模，混乱更加普遍；分布式系统中，我们涉入其中的角色往往是作为其中的某个节点，此时需要更悲观地看待故障。

Fault can be Non-deterministic

• 我们了解的计算机系统模型是理想化的，存在着各种简化过的数学抽象，而实际上的物理实现则不是这么完美，主板上各个组件的电压无法任意精确地固定在某个值，存储介质无法保证每一位都永不出错，网络的不稳定状况甚至是肉眼可见的。
• 在分布式系统中，我们即使可以检验到本地系统的工作正常，也很难保证其他子系统不存在未知的损坏；在部分失效（partial failure）的情况下，整个分布式系统有时可能正常工作，有时则不然，即系统的失效与否与工作结果的正常之间没有确定性关联。

单机系统上，我们能用追根溯源的手段去发现故障原因，从源头解决故障；分布式系统中，传统手段难以覆盖各种部分失效的场景，那又如何去解决系统故障问题？

Tolerant Fault

Fault Handling

单机系统中的故障处理哲学时，对于难以解决的故障，我们直接制造整个系统故障，然后从上个检查点开始重新运行，比如操作系统内核的panic。
高性能计算（HPC）领域中，计算机系统使用上千个核心的众核（many-core）微架构来解决计算密集型任务；这种多处理器系统采用类似单机系统的故障处理——作业被不断地持久化到外部存储中，在部分失效时会让故障升级为完全失效，等故障节点修复后再从检查点继续执行。

云计算是分布式系统的典型场景，它是实现在互联网服务上的一种计算机系统，它有着与单机系统和HPC使用的超级计算机不同的容错要求：

• 更高的可用性要求
• 更低成本、更高故障率的硬件
• 不稳定的网络环境
• 单节点的快速失败、滚动更新

云计算场景下的故障处理哲学是，要使分布式系统工作，就要接受部分故障的可能性，要建立能容忍故障发生的软件系统。

Build a Reliable System from Unreliable Components

如果我们按木板原理来理解“可靠的”（Reliable），那软件系统注定“像其最不可靠的组件一样可靠”。
事实上，我们关注的可靠不是物理实现层面上的绝对可靠性，而是在较高层次下的软件抽象的可靠——这意味着我们有可能能用不可靠的组件构建出较可靠的系统。

例如，在计算机网络的层次结构中，数据链路层需要提供的差错控制，即使用纠错码，容忍信道中的部分数字传输错误。
另一方面，我们也能从上述案例中看出，这类容错/故障容忍机制能提供的可靠性是有限的，比如，不同类型的检错码/纠错码的查错、纠错能力是有限的。

利用容错/故障容忍机制，不那么可靠的组件也能构建出较可靠的软件系统。

Unreliable Components

Network

互联网和数据中心大多使用异步分组网络（asynchronous packet networks），网络中一个节点向另一节点发包，但不保证数据包是否到达、什么时候到达。
当一个请求被发送并等待响应，网络层面上能发生的故障有多种：

• 请求可能已经丢失（可能有人拔掉了网线）；
• 请求可能正在排队，稍后将交付（也许网络或收件人超载）；
• 远程节点可能已经失效（可能是崩溃或关机）；
• 远程节点可能暂时停止了响应（可能会遇到长时间的垃圾回收暂停；参阅“暂停进程”），但稍后会再次响应；
• 远程节点可能已经处理了请求，但是网络上的响应已经丢失（可能是网络交换机配置错误）；
• 远程节点可能已经处理了请求，但是响应已经被延迟，并且稍后将被传递（可能是网络或者你自己的机器过载）。

此时，请求者甚至难以分辨数据包是否已经发送出去（可以要求接收者回复ack消息来确认，但该消息依然可能丢包、延迟）；唯一信息是，现在没有收到响应。
使用超时能避免请求发出后一直忙等，但发生超时时仍无法确认远程节点是否收到了消息，意味着消息请求者无法简单地认为消息丢包了，远程节点可能收到了消息并做了非幂等的操作。

出现网络故障的原因有多种，比如物理设备上的损坏、网络拥塞、软件崩溃等。
尽管现有网络在传输层的TCP协议上增加了流控制来避免拥塞、并让数据包的丢失重传对用户透明，但用户依然可以看到延迟；而在一些对延迟敏感的场景中，不保证可靠传输的UDP协议更受青睐。

当前部署的技术不允许我们对网络的延迟或可靠性作出任何保证：我们必须假设网络拥塞，排队和无限的延迟总是会发生。

Clock

时钟：返回挂钟时间，通常与网络时间协议（Network Time Protocol）同步。
单调钟：可能是计算机启动以来的纳秒数，适用于测量时间间隔；比较不同计算机的单调钟的值是无意义的。

时钟同步的准确性是有限的。

具体可以参考Martin Kleppman（也是本书DDIA的作者）讲CRDT和Consistency的视频。

Paused Process

这部分从一个主从软件系统的租约（lease）维护的例子讲起。
租约类似一个带超时的锁，任一时刻只有一个节点可以持有。
当一个节点获得一个租约时，它知道它在某段时间内自己是leader，直到租约到期。为了保持领导地位，节点必须在周期性地在租约过期前续期。

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

• 如果本地时钟与远程节点的时钟超过几秒不同步，分支走向则不一定在预期内。
• 只采用本地的单调时钟的情况，如果线程在if(lease.isValid())这行以前由于各种原因（比如JVM的GC机制）阻塞了很久，外部节点可能认为它的租约已经过期，而它自己无法判断，这就有多个leader的情况。

类似于单机系统下的线程安全，但分布式系统下没有共享内存，没法直接将单机的同步原语转化利用，只能靠不可靠的网络传递消息。
所以，分布式系统中的节点，必须假定其执行可能在任意时刻暂停相当长的时间，即使是在某个函数的中间。
在暂停期间，其它部分在继续运转，甚至可能因为该节点没有响应，而宣告暂停节点的死亡。最终暂停的节点可能会继续运行，在再次检查自己的时钟之前，甚至可能不会意识到自己进入了睡眠。

Reliability

可靠性是指系统在困境（adversity，包括硬件故障、软件故障、人为错误）中仍可正常工作（正确完成功能，并能达到期望的性能水准）的能力。
目前我们看到，分布式系统上不可靠的因素很多，故障的概率不可能降到零。为了避免整个系统从部分功能的故障（fault）蔓延为完全的失效（failure），就需要把容忍故障的能力，即可靠性，作为系统设计的主要命题之一。

Fault Tolerance Algorithm

分布式系统下，没有单机系统那样的共享内存，只能通过可变延迟的不可靠网络传递的消息；系统可能遭受部分失效，不可靠的时钟和处理暂停。
所以说，这里我们会基于系统模型提供的假设——即使这些假设只保证了较少的可靠性——来实现可靠的行为。

Majority Defines the Truth

我们不妨从下面的小故事开始：

设想一个具有不对称故障的网络：一个节点能够接收发送给它的所有消息，但是来自该节点的任何传出消息被丢弃或延迟。即使该节点运行良好，并且正在接收来自其他节点的请求，其他节点也无法听到其响应。经过一段时间后，其他节点宣布它已经死亡，因为他们没有听到节点的消息。这种情况就像梦魇一样：半断开（semi-disconnected）的节点被拖向墓地，敲打尖叫道“我没死！” ——但是由于没有人能听到它的尖叫，葬礼队伍继续以坚忍的决心继续行进。
在一个稍微不那么梦魇的场景中，半断开的节点可能会注意到它发送的消息没有被其他节点确认，因此意识到网络中必定存在故障。尽管如此，节点被其他节点错误地宣告为死亡，而半连接的节点对此无能为力。
第三种情况，想象一个经历了一个长时间停止世界垃圾收集暂停（stop-the-world GC Pause）的节点。节点的所有线程被GC抢占并暂停一分钟，因此没有请求被处理，也没有响应被发送。其他节点等待，重试，不耐烦，并最终宣布节点死亡，并将其丢到灵车上。最后，GC完成，节点的线程继续，好像什么也没有发生。其他节点感到惊讶，因为所谓的死亡节点突然从棺材中抬起头来，身体健康，开始和旁观者高兴地聊天。GC后的节点最初甚至没有意识到已经经过了整整一分钟，而且自己已被宣告死亡。从它自己的角度来看，从最后一次与其他节点交谈以来，几乎没有经过任何时间。

这个故事，说明“节点自己的判断”不一定是值得相信的，因而整个系统的决策不能完全依赖单个节点。
事实上，许多分布式系统都使用了Quorum的算法，这是一种让节点们通过投票来减少对某个特定节点依赖的方法（Cassandra就采用了该算法）。

Quorum-based Voting for Replica Control

Note: Quorum算法实际上是对Transaction Atomicity的解决方案，而非针对Fault Tolerance的，只不过这里我们从故障容忍的角度去切入它。

在使用replica的分布式存储系统当中，冗余数据对象会在不同的机器之间存放多份副本。
同一时刻一个数据对象的多份副本只能用于读或者用于写。

如果我们采用这样的方案来保证数据存储的可靠性（比如防止因为某个节点的数据被破坏而促使整个数据库失效），那么就要面对读写事务的原子性问题。
例如，某一时刻向这样的分布式数据库系统中写入数据，为了保证多副本数据的一致性，naïve的想法是向所有副本都写入，等所有副本都回复了ack之类的确认消息，就完成了一次原子性的写入。
对于写操作频繁的系统，上述操作会带来不小的性能瓶颈。除此之外，如果某个副本所对应的节点故障了，那么这次操作将无法完成——事实上，前面我们了解到，节点故障难以避免，如果不能容忍部分节点的出错，那么该数据库将拥有较低的可用性（availability），甚至能让人怀疑冗余拷贝的必要性。

Quorum算法可以不必每次都对所有节点做出确认，并保证同一份数据对象的多份副本不会被超过两个访问对象读写。

分布式系统中的每一份数据副本对象都被赋予一票。每一个读操作获得的票数必须大于最小读票数（read quorum）Vr，每个写操作获得的票数必须大于最小写票数（write quorum）Vw才能读或者写。如果系统有V票，即一个数据对象有V份冗余拷贝，那么最小读写票数(quorum)应满足如下限制：

• Vr + Vw > V
• Vw > V/2

第一条规则保证了一个数据不会被同时读写。当一个写操作请求过来的时候，它必须要获得Vw个冗余拷贝的许可。而剩下的数量是V - Vw < Vr，因此不能再有读请求过来了。同理，当读请求已经获得了Vr个冗余拷贝的许可时，写请求就无法获得许可了。
第二条规则保证了数据的串行化修改。一份数据的冗余拷贝不可能同时被两个写请求修改。

基于上述描述，对于V = 5的情况，Quorum算法可以让写操作只要写完3个副本就返回。剩下的由系统内部缓慢同步完成。而读操作，则需要也至少读3个副本，才能保证至少可以读到一个最新的数据。

Quorum的读写最小票数允许系统在读、写性能方面做出trade-off。写票数Vw越大，则读票数Vr越小，这时候系统读的开销就小。反之则写的开销就小。

Reach a Consensus with Fault Tolerance

Fencing Token: Tolerant Inadvertent Fault

计算机系统中，很多类型的事物都同时只能存在一个：

• 数据库分区的领导者只能有一个节点，以避免脑裂（split brain）。
• 特定资源的锁或对象只允许一个事务/客户端持有，以防同时写入和损坏。
• 一个特定的用户名只能被一个用户所注册，因为用户名必须唯一标识一个用户。

在分布式系统中，这个问题会比想象中复杂，即使一个节点认为它是一个leader节点，即分区的负责人、锁的持有者或成功获取用户名的用户的请求处理程序，但这并不一定意味着有它此时满足Quorum算法的票数需求——或者说，一个节点可能以前是leader，但是如果其他节点在此期间“宣布”它的死亡（例如，由于网络中断或GC暂停），则它可能已被降级，且系统中已经选出了另一个leader。

The Byzantine Generals Problem

屏蔽令牌（fencing token）可以阻止无意中出现的租约过期问题，但如果某个节点蓄意破坏整个系统呢？
前面所有例子中，我们假设节点不可靠，但确是“诚实”的——它可能响应较慢或者从不响应，或者证明身份的租约已经过时，而当它做出合法回应时，就认为它回答了“真相”。
但是如果节点不再诚实呢？

不妨考虑节点会“撒谎”的场景，在租约的例子中，如果某个节点知道了token生成的规则，主动生成合法（更大）的token，依然可以通过Storage层面的认证；
更广义来讲，节点可能会对外声称它收到了某个消息A，而实际却并没有收到的消息A，

拜占庭将军问题，便是这样一个考虑不可信环境下达成共识的问题。

拜占庭问题中，n位将军分别率领一支军队共同围困一座城市。
这n位将军需要对之后军队的策略达成共识，即进攻或撤退。
但他们其中有一些叛徒，会阻碍这个达成共识的过程。
大多数的将军都是忠诚的，会向其他人发出真实的信息，但是叛徒可能会试图通过发送虚假或不真实的信息来欺骗和混淆他人（在试图保持未被发现的同时）。
而且，这些将军事先并不知道谁是叛徒。

Note: The Byzantine Generals Problem由图灵奖得主Leslie Lamport在1982年提出，整个故事当然是虚构的，起名“拜占庭”是因为Lamport觉得这样不会冒犯任何读者。

Reduction: BGP with Oral Messages

基于口头消息的BGP，即消息内容完全由发送者控制，存在以下假设：

• 每一个消息都会被正确地发送
• 接收者可以准确知道谁发送了消息
• 如果消息没有被接收到可以被监测出来

简化问题的结论：基于口头消息的拜占庭将军问题（BGP），3m+1个将军的解决方案中允许m个叛徒。

解决方案：

• 算法OM(m): (m is the number of traitors)
  • 发令官向所有副官发送命令；
  • 每个副官再作为OM(m-1)算法中的发令官，向其他m-1个副官重复命令；
  • 每个副官收集收到的所有消息，以多数为准

递归一致性的要求：

• 所有忠诚的副官会重复和收到命令一致的命令；
• 如果发令官是忠诚的，那么所有忠诚的副官会遵循它发出的命令。

Our Tolerance

现实的分布式系统中，我们仍假设数据中心这样由同一组织管理的环境是受信的，即假设没有拜占庭式的错误；更重要的是，制作拜占庭容错系统的协议相当复杂，容错嵌入式系统依赖于硬件层面的支持，实现、部署拜占庭容错的解决方案需要很高的成本。

在Web应用程序中，用户确实可能制造任意恶意的行为，但是我们通常只做输入验证和输出转义，防止SQL注入和XSS，而非使用拜占庭容错。因为这里服务器是授权的中心，能决定什么样的客户端行为被允许，而拜占庭容错往往出现在对等网络中。

尽管现在假设节点通常是诚实的，但仍不妨在软件中加上防止“撒谎”弱形式的机制——例如，由硬件问题导致的无效消息，软件错误和错误配置。
这样的保护机制并不是完全的拜占庭容错，因为不能抵挡有决心的对手，但这仍是一种能以低成本提高可靠性的手段。

Topics not Covered

• 混沌工程
• 我们不一定是分布式数据库的设计者，但分布式系统与我们息息相关

Reference

1. Design Data-Intenstive Application, Martin Kleppmann
2. The Thrilling Adventures of Lovelace and Babbage: The (Mostly) True Story of the First Computer, Sydney Padua
3. Weighted Voting for Replicated Data, David K. Gifford
4. Quorum, Wikipedia
5. The Byzantine Generals Problem, Lamport, L.; Shostak, R.; Pease, M.