1.5 容错性

集中式系统中任何一个组件的故障，都会导致整个系统无法正常使用。这就是为什么集中式系统的主机往往要求有比较高的性能。而分布式系统区别于集中式系统的一个特性是它容许部分失效。

分布式系统设计中的一个重要目标是以这样的方式构建系统：它可以从部分失效中自动恢复，而且不会严重地影响整体性能。特别是当故障发生时，分布式系统应该在进行恢复的同时继续以可接受的方式进行操作，也就是说，它应该能容忍错误，在发生错误时在某种程度上可以继续操作。

1.5.1 基本概念

容错往往与可靠的系统紧密相关，而可靠的系统需要满足以下要求。

● 可用性（Availability）：用来描述系统在给定时刻可以正确地工作。

● 可靠性（Reliability）：指系统可以无故障地连续运行。与可用性相反，可靠性是根据时间间隔而不是任何时刻来进行定义的。如果系统在每小时中崩溃的时间为1ms，那么它的可用性就超过99.9999%，但它还是高度不可靠的。与之相反，如果一个系统从来不崩溃，但是要在每年8月停机两个星期，那么它是高度可靠的，但是它的可用性只有98%。因此，这两种属性并不相同。

● 安全性（Safety）：指系统在偶然出现故障的情况下能正确操作而不会造成任何灾难。

● 可维护性（Maintainability）：发生故障的系统被恢复的难易程度。

容错，意味着即使系统发生了故障，还能正常提供服务。

1.5.2 故障分类

故障通常被分为三类。

● 暂时故障（Transient Fault）：只发生一次，然后就消失了，不再重现该故障。

● 间歇故障（Intermittent Fault）：发生，消失不见，而后再次发生，如此反复进行。

● 持久故障（Permanent Fault）：那些直到故障组件被修复之前持续存在的故障。

分布式系统中的典型故障模式可以分为以下几种。

● 崩溃性故障（Crash Failure）：服务器停机，但是在停机之前工作正常。

● 遗漏性故障（Omission Failure）：服务器不能响应到来的请求。可以细分为服务器不能接收到来的消息，以及服务器不能发送消息。

● 定时性故障（Timing Failure）：服务器对请求响应得过快或者过慢。

● 响应性故障（Response Failure）：服务器对请求以错误的方式进行了响应。

● 任意性故障（Arbitrary Failure）：服务器可能在任意的时间产生任意类型的故障。其中，任意性故障是最严重的故障，也称为拜占庭故障（Byzantine Failure）。当发生故障时，服务器可能产生它从来没有产生过的输出，但是又不能检测出错误。更坏的情况是，发生故障的服务器与其他服务器共同工作来产生恶意的错误结果。Windows系统“蓝屏”正是为了尽可能避免这种情况而设计的。这种情况也说明了为什么谈到可靠系统时安全被认为是一个重要的需求。

随意性故障与崩溃性故障紧密相关。崩溃性故障的一个典型的例子就是操作系统崩溃，此时的解决办法只有一个：重新启动。与人们的期望相反，PC经常遭遇崩溃性故障，最终导致设计者把复位按钮从机箱背后移到前面。

1.5.3 使用冗余来掩盖故障

如果系统是容错的，那么它能做的最好的事情就是对其他进程隐藏故障。关键技术是使用冗余来掩盖故障。有三种可能：信息冗余、时间冗余和物理冗余。

在信息冗余中，添加额外的位可以使错乱的位恢复正常。例如，可以在传输的数据中添加一段Hamming码来从传输线路上的噪声中恢复数据。可以利用信息冗余进行错误检测和纠正。

在时间冗余中，执行一个动作，如果需要就再次执行。使用事务就是这种方法的一个例子。如果一个事务中止，那么它就可以无害地重新执行。当发生临时性或间歇性的错误时，时间冗余特别有用。TCP/IP协议中的重传机制是另外一个例子。

在物理冗余中，通过添加额外的装备或进程使系统作为一个整体来容忍部分组件的失效或故障成为可能。物理冗余可以在硬件上也可以在软件上进行。其中，一种著名的设计是TMR（Triple Modular Redundancy，三倍模块冗余）。在包括TMR的系统中，每个关键模块中的部件都被复制了三份，采用多数表决的方法，确保当某些模块中的单个部件发生故障时，系统还可以正确地运行。

1.5.4 分布式提交

在分布式系统中，事务往往包含多个参与者的活动，单个参与者的活动是能够保证原子性的，而保证多个参与者之间原子性则需要通过两阶段提交或三阶段提交算法实现。

1．两阶段提交

两阶段提交协议（Two-phase Commit Protocol,2PC）的过程涉及协调者和参与者。协调者可以看作事务的发起者，同时是事务的一个参与者。对于一个分布式事务来说，一个事务是涉及多个参与者的。两阶段提交的具体过程如下。

第一阶段（准备阶段）

● 协调者节点向所有参与者节点询问是否可以执行提交操作（vote），并开始等待各参与者节点的响应。

● 参与者节点执行所有事务操作，并将Undo信息和Redo信息写入日志（注意：若成功这里其实每个参与者已经执行了事务操作）。

● 各参与者节点响应协调者节点发起的询问。如果参与者节点的事务操作实际执行成功，则它返回一个“同意”消息；如果参与者节点的事务操作实际执行失败，则它返回一个“中止”消息。

第二阶段（提交阶段）

如果协调者收到了参与者的失败消息或超时，则直接给每个参与者发送回滚（rollback）消息；否则，发送提交（commit）消息；参与者根据协调者的指令执行提交或回滚操作，释放所有事务处理过程中使用的锁资源（注意：必须在最后阶段释放锁资源）。

● 当协调者节点从所有参与者节点处获得的相应消息都为“同意”时：

○ 协调者节点向所有参与者节点发出“正式提交（commit）”的请求。

○ 参与者节点正式完成操作，并释放在整个事务期间内占用的资源。

○ 参与者节点向协调者节点发送“完成”消息。

● 如果任一参与者节点在第一阶段返回的响应消息为“中止”，或者协调者节点在第一阶段的询问在超时之前无法获取所有参与者节点的响应消息时：

○ 协调者节点向所有参与者节点发出“回滚操作（rollback）”的请求。

○ 参与者节点利用之前写入的Undo信息执行回滚，并释放在整个事务期间占用的资源。

○ 参与者节点向协调者节点发送“回滚完成”消息。

○ 协调者节点收到所有参与者节点反馈的“回滚完成”消息后，取消事务。

○ 协调者节点收到所有参与者节点反馈的“完成”消息后，完成事务。

不管最后结果如何，第二阶段都会结束当前事务。

两段式提交协议的优缺点如下。

优点：原理简单，实现方便。

缺点：

● 同步阻塞问题。在执行过程中，所有参与节点都是事务阻塞型的。

● 单点故障。由于协调者的重要性，一旦协调者发生故障，参与者会一直阻塞下去。尤其在第二阶段，协调者发生故障，那么所有的参与者都还处于锁定事务资源的状态，而无法继续完成事务操作。

● 数据不一致。在阶段二中，当协调者向参与者发送commit请求之后，发生了局部网络异常，或者在发送commit请求过程中协调者发生了故障，这会导致只有一部分参与者接收到了commit请求。而在这部分参与者接收到commit请求之后就会执行commit操作，但是其他部分未接收到commit请求的机器则无法执行事务提交操作。于是整个分布式系统便出现了数据不一致性的现象。

● 两阶段无法解决的问题：协调者再发出commit消息之后宕机，而唯一接收到这条消息的参与者同时也宕机了，那么即使协调者通过选举协议产生了新的协调者，这条事务的状态也是不确定的，没人知道事务是否已经被提交。

为了解决两阶段提交协议的种种问题，研究者在两阶段提交的基础上做了改进，提出了三阶段提交。

2．三阶段提交

三阶段提交协议（Three-phase Commit Protocol,3PC）是两阶段提交（2PC）的改进版本。与两阶段提交相比，三阶段提交有两点改动：

● 引入超时机制，同时在协调者和参与者中都引入超时机制。

● 在第一阶段和第二阶段中插入一个准备阶段，保证在最后提交阶段之前各参与节点的状态是一致的。

即3PC把2PC的准备阶段再次一分为二，这样三阶段提交就有CanCommit、PreCommit和DoCommit三个阶段。

CanCommit阶段

CanCommit阶段其实和2PC的准备阶段很像。协调者向参与者发送commit请求，参与者如果可以提交就返回yes响应，否则返回no响应。

● 事务询问：协调者向参与者发送CanCommit请求，询问是否可以执行事务提交操作，然后开始等待参与者的响应。

● 响应反馈：参与者接收到CanCommit请求之后，在正常情况下，如果其自身认为可以顺利执行事务，则返回yes响应，并进入预备状态，否则返回no响应。

PreCommit阶段

协调者根据参与者的反应情况来决定是否执行事务的PreCommit操作。根据响应情况，有以下两种可能。

● 假如协调者从所有的参与者处获得的反馈都是yes响应，那么就会执行事务的预执行。

○ 发送预提交请求：协调者向参与者发送PreCommit请求，并进入Prepared阶段。

○ 事务预提交：参与者接收到PreCommit请求后，会执行事务操作，并将undo和redo信息记录到事务日志中。

○ 响应反馈：如果参与者成功地执行了事务操作，则返回ACK响应，同时开始等待最终指令。

● 假如任何一个参与者向协调者发送了no响应，或者等待超时之后，协调者都没有接收到参与者的响应，那么就执行事务的中断操作。

● 发送中断请求：协调者向所有参与者发送abort请求。

● 中断事务：参与者接收到来自协调者的abort请求之后（或超时之后，仍未收到协调者的请求），执行事务的中断操作。

doCommit阶段

该阶段进行真正的事务提交，也可以分为以下两种情况。

● 执行提交

○ 发送提交请求：协调者接收到参与者发送的ACK响应，那么它将从预提交状态进入提交状态，并向所有参与者发送doCommit请求。

○ 事务提交：参与者接收到doCommit请求之后，正式进行事务提交，并在完成事务提交之后释放所有事务资源。

○ 响应反馈：事务提交完之后，向协调者发送ACK响应。

○ 完成事务：协调者接收到所有参与者的ACK响应之后，完成事务。

● 中断事务：协调者没有接收到参与者发送的ACK响应（可能是接收者发送的不是ACK响应，也可能响应超时），那么就会执行中断事务操作。

○ 发送中断请求：协调者向所有参与者发送abort请求。

○ 事务回滚：参与者接收到abort请求之后，利用其在阶段二记录的undo信息来执行事务的回滚操作，并在完成回滚之后释放所有的事务资源。

○ 反馈结果：参与者完成事务回滚之后，向协调者发送ACK消息。

○ 中断事务：协调者接收到参与者反馈的ACK消息之后，执行事务的中断操作。

在doCommit阶段，如果参与者无法及时接收到来自协调者的doCommit或rebort请求，则会在等待超时之后，继续进行事务的提交。即当进入第三阶段时，由于网络超时等原因，虽然参与者没有接收到commit或abort响应，事务仍然会提交。

三阶段提交不会一直持有事务资源并处于阻塞状态。但是这种机制也会导致数据一致性问题，因为，如果协调者发送的abort响应由于网络原因没有及时被参与者接收到，那么参与者在等待超时之后执行了commit操作，这样就和其他接到abort命令并执行回滚的参与者之间存在数据不一致的情况。

3．Paxos算法

Paxos算法是Leslie Lamport于1990年提出的一种基于消息传递且具有高度容错特性的一致性算法。Paxos算法目前在Google的Chubby、MegaStore、Spanner等系统中得到了应用，Hadoop中的ZooKeeper也使用了Paxos算法。

在Paxos算法中有4种角色。

● Proposer：提议者；

● Acceptor：决策者；

● Client：产生议题者；

● Learner：最终决策学习者。

算法可以分两个阶段执行。

阶段1

● Proposer：选择一个议案编号n，向Acceptor的多数派发送编号也为n的prepare请求。

● Acceptor：如果接收到的prepare请求的编号n大于它已经回应的任何prepare请求，则它就回应已经批准的编号最高的议案（如果有的话），并承诺不再回应任何编号小于n的议案。

阶段2

● Proposer：如果收到了多数Acceptor对prepare请求（编号为n）的回应，则它就向这些Acceptor发送议案{n, v}的accept请求，其中v是所有回应中编号最高的议案的决议，或者是Proposer选择的值，如果响应中不包含议案，那么它就是任意值。

● Acceptor：如果收到了议案{n, v}的accept请求，则它就批准该议案，除非它已经回应了一个编号大于n的议案。

● Proposer可以提出多个议案，只要它遵循上面的算法。它可以在任何时刻放弃一个议案（这不会破坏正确性，即使在议案被放弃后议案的请求或回应消息才到达目标）。如果其他Proposer已经开始提出更高编号的议案，那么最好能放弃当前的议案。因此，如果Acceptor忽略一个prepare或accept请求（因为已经收到了更高编号的prepare请求），则它应该告知Proposer放弃议案。这是一个性能优化，而不影响正确性。

该算法的详细描述可以在线参阅http://research.microsoft.com/en-us/um/people/lamport/pubs/lamport-paxos.pdf。