Lecture 7-11
Fault Tolerance in Active Replication

RMs work as replicated state machines, playing equivalent roles. That is, each responds to a given series of requests in the same way. This is achieved by running the same program code at all RMs. If any RM crashes, state is maintained by other correct RMs. This system implements sequential consistency
Lecture 7-13
Recovery Stable Storage
a) b) c)
Stable Storage Crash after drive 1 is updated Bad spot
Lecture 7-14
7.2.2 故障—停止处理器
当一个处理器失效，最可能的是它不进行任何不正确的操 作，并且简单地停止运行，这样的处理器被称为故障 — 停 止处理器，一个故障—停止处理器由多个处理器组成。 失效的效果：当出现一个故障时，故障—停止处理器会有以 下效果： (a)处理器停止运行； (b)易失性存储器的内容丢失， 而坚固存储器不受影响；(c)任何其他处理器均可以检测到故 障—停止处理器的失效状态。 故障—停止处理器的实现：现有一个可靠的坚固存储器、一 个可靠的存储处理器(控制存储媒介的处理器)以及k+1个处理 器，将它们转变成故障 — 停止处理器的方法如下： k+1 个处 理器中的每一个都运行同样的程序并通过存储处理器访问同 一个坚固存储器。如果任何一个请求是不同的，或者任何一 个请求没有在指定的期间到达，则意味着检测到一个失效事 件，因而应该丢弃所有请求。因为系统表现为一个故障 —停 止处理器，这一方法产生一个 k— 故障 — 停止处理器，除非 系统中k+1个或更多的部件失效。
Lecture 7-7
7.1.3 故障的基本处理方法(进程容错机制)：
(1) 主动复制。所有的复制模块协同进行，并且它们的状态紧密 同步。用到了错误屏蔽的概念——隐藏出现的故障或防止故 障造成错误。把相同进程的集合组织到一个平等组中。在分 布式系统中使用主动复制相对比较昂贵。 编组故障屏蔽 (2) 被动复制。以等级方式组织进程组，其中只有一个模块（主 进程）处于动态，其他模块的交互状态由这一模块的检查点 定期更新。如果主进程崩溃，后备进程执行选举算法选择一 个新的主进程。动态方法 层次故障屏蔽 (3) 半主动复制。是主动复制和被动复制的混合方法。此种方法 所需的恢复开销相对较低。
Lecture 7-5
7.1.2 基本的故障模型
故障类 故障子类
失忆型崩溃 中顿型崩溃 停机型崩溃
故障分类 (与语义有关)
故 障 语 义
崩溃故障
服务器崩溃(停机) ，但停机前工作正常 服务器只能从初始状态启动，遗忘了崩溃前的状态 服务器可以从崩溃前的状态启动
服务器完全停机
服务器对输入的请求没有响应
req-id and response to all backup RMs.

Response: primary sends to the front end
Lecture 7-9
Fault Tolerance in Passive Replication
The system implements linearizability, since the primary sequences operations in order. If the primary fails, a backup becomes primary by leader election, and the replica managers that survive agree on which operations had been performed at the point when the new primary takes over.
result since they are running the same program, i.e., they are replicated protocols or replicated state machines) Agreement: No agreement phase is needed, because of multicast delivery semantics of requests
Lecture 7-2
7.1 分布式系统中的故障模型
7.1.1 基本概念
属性： • 可用性 • 可靠性 • 安全性 • 可维护性 • 保密性 • 完整性
什么是“可 信赖的系 统”？
如何区分各 种故障？
后果： • 失效 • 错误 • 故障
如何处理 故障？
策略： • 防止故障 • 故障容错 • 故障恢复 • 故障预报
Lecture 7-12
7.2 容错系统的基本构件
7.2.1 坚固存储器（稳定存储器，Lampson提出）
坚固存储器是对一个可以经受系统失效的特定存储器的逻辑抽 象，也就是说，坚固存储器里的内容不会被一个失效所毁坏。
坚固存储器的实现技术： 磁盘镜像：坚固存储器可以用一对普通磁盘来实现。坚固 存储器中的每一个块由两个独立的磁盘块组成，分别位于 不同的驱动器上，使得它们同时由于硬件故障受到损坏的 机会最小。 RAID：另一种实现坚固存储器的方法是使用廉价磁盘冗余 阵列(RAID)。RAID是通过运用位交错技术将数据分布到多 个磁盘中，从而提供高 I/O 性能。可以用一个或几个磁盘 来检测或屏蔽错误，RAID与传统磁盘相比有显著的优点， 并可承受多个失效。
Lecture 7-3
可信赖系统的性质
1) 可用性：可用性反映的是系统随时可被用户使用的特性。
2) 可靠性：一个系统可以无故障持续运行的程度。与可用性相
反，可靠性以时间周期为基准，而不是以某个时刻为基准。 也就是说，一个高度可靠的系统在相当长的时间周期里可以
无间断地为用户提供服务
3) 安全性：安全性指的是在系统出现暂时错误的情况下，不出 现灾难性后果的能力。 4) 可维护性：可维护性指的是系统一旦出现故障，系统易于修 复的能力。 5) 保密性：保密性要求系统资源不被非法用户访问。
Client Front End
primary
RM
Backup
….
Client Front End
RM
RM
RM
Backup
Backup

Request Communication: the request is issued to the
primary RM and carries a unique request id. checks id (resends response if not new id.)
失职故障 （遗漏故障）
接收型失职
发送型失职 返回值故障
服务器无法接收信件 服务器无法发送信件 服务器对服务请求做出错误反应 返回值出现错误 服务器偏离正确的运行轨迹 服务器反应迟缓，超出规定的时间间隔 服务器在任意时间产生的随意错误
应答故障
状态变迁故障
时序故障 随意故障
拜占庭故障
Lecture 7-6
Coordination: Primary takes requests atomically, in order,
Execution: Primary executes & stores the response Agreement: If update, primary sends updated state/result,
要建立可靠系统就必须控制故障。对用户来讲最重要的 哺乳动物的两只眼睛、两 是容错，即系统发生故障时也能提供服务（对其他进程 个耳朵、两个肾， 747 飞 隐藏故障的发生）。容错是建立在冗余的基础上的 ,冗余 机的四个引擎只用了三个， 多个体育裁判 类型有四种：




硬件冗余 使用多个硬件 物理冗余 软件冗余 使用多个软件 信息冗余 海明(Hamming) 校验 检查和 奇偶位 时间冗余 超时重发技术 ：如原子操作和原子事务处理 重复计算
multicast to all by a reliable totally ordered multicast. in the same order (but may be at different times!).
Coordination: Group comm. ensures that requests are delivered to each RM
Lecture 7-4
• 当系统不能提供所承诺的服务时就认为系统失效
• 一个系统在正常工作时会在若干种运行状态之间变 迁，一旦出现异常，则该系统进入错误(Error) 状态。 一个系统的错误状态可能是导致系统失效的原因 • 造成错误的原因称为故障。
故障
导致
错误
归于
失效
故障的种类繁多，软件和硬件都有可能产生故障，而 且在某些场合下，与系统无关的外部环境也可能引发 故障。通常分为 ：暂 时性的 (transient) 、间歇性 的 (intermittent)和永ts are FIFO-total ordered. But if clients are multithreaded and communicate with one another while waiting for responses from the service, we may need to incorporate causaltotal ordering