分布式系统（8） - 容错

分布式系统的设计目标之一是允许部分失效。

任何提供共享数据的网络相连的系统只能提供以下CAP中的两者：

• 一致性(consistency)
• 可用性(availability)
• 分区容错性：对于进程组划分(partitioning)的容错

容错性概述

容错即让系统可依赖(dependable)：软件组件为了为用户提供服务，可能需要来自其他组件的服务（服务依赖），即组件可能依赖于其他组件

• 可用性(availability)：系统已准备好
• 可靠性(reliability)：可无故障持续执行
• 安全性(safety)：在偶然出现故障情况下也能正确操作
• 可维护性(maintainability)：发生故障的系统被恢复的难易程度

传统的度量标准：

• 平均失效时间(MTTF)：直到组件失效的平均时间
• 平均恢复时间(MTTR)：恢复一个组件的平均时间
• 两次失效的平均时间(MTBF)：MTTF + MTTR

可靠性与可用性区别

• 可靠性：组件 C 从开始时刻 T = 0起，经历\([0, t)\)一段时间仍然能够提供正常功能的条件概率，包括平均失效MTTF、平均恢复MTTR、两次失效平均时间MTBF=MTTF+MTTR
• 可用性：在 [0, t) 时间段内，组件 C 可用的时间比例 \(A=MTTF/MTBF\)

分清下列三个概念：

• 失效(failure)：一个系统不能兑现它的承诺，e.g.崩溃的程序
• 错误(error)：系统状态的一部分，e.g.程序中的bug
• 故障(fault)：造成错误的原因，e.g.马虎的程序员

失效模型

• 崩溃(Crash)失效：一旦服务器停机，就不再提供任何服务，解决方案重启
• 遗漏(Omission)失效：回应/收取/发出消息失败，无法对请求进行响应
• 定时(Timing)失效：回应超时
• 响应(Response)失效：回应不正确
  • 数值失效：如搜索引擎返回了与搜索项无关的页面
  • 状态转换失效：服务器对到来的请求做出意想不到的响应
• 随意性(Arbitrary)/拜占庭(Byzantine)失效：在任意时间产生任意回应

冗余来掩盖故障

• 信息冗余：在数据单元中添加额外的位数据使错乱的位恢复正常
• 时间冗余：如果系统出错，一个动作可以再次执行（事务处理）
• 物理冗余：通过添加额外的装备或进程使系统作为一个整体来容忍部分组件的失效或故障

进程恢复

K-容错组：当一个组可以屏蔽任何\(K\)个并发的成员失效（\(K\)称为容错度）

• 重要假设：
  • 所有成员都是同质的
  • 所有成员以相同的顺序处理命令
• 如果发生的是停止失效(crash/omission)，我们需要\(K+1\)成员数保证结果的有效输出
• 如果发生的随意失效（拜占庭失效），我们需要\(2k + 1\)个成员才能保证结果的正确输出

失效检测

每个进程都有一个失效检测模块，探针(probe)检测另一个进程是否存在响应(ping)/心跳信息

• 如果没有在规定时间内收到心跳，则怀疑对方失效
• 如果对方稍后发出消息并被接收，则停止怀疑并增加timeout时间

可靠的通信方式

可靠的 RPC 通信机制

• 至少一次语义：操作至少执行一次
• 至多一次语义：操作至多执行一次

丢失应答信息

• 设计服务器时，让其操作都是幂等的(idempotent)即重复多次执行与执行一次的结果是相同的
  • 纯粹的读操作
  • 严格的写覆盖操作
• 但是实际上很多操作天然就不是幂等的，例如银行事务系统

客户端崩溃

服务器还在工作，并且持有资源但是没有客户端需要结果（称为孤儿计算）。

解决方案：

• 孤儿消灭(extermination)：当客户端恢复时杀死孤儿
• 再生：把时间分为顺序编号的时期，客户端恢复后，向所有的服务器广播新时期的开始，由服务器杀死与客户端相关的“孤儿”
• 优雅再生：服务器检查远程调用，如果找不到拥有者则杀死计算
• 到期：每个RPC都被给定一个标准的时间量 T 来进行工作，抛弃原有的过时的计算

可靠多播

• 可靠多播：消息发送和接收按照发送者发送的顺序进行，一个消息可以传递到所有参与者
• 问题：如果存在N的接收方，会导致大量返回 N 个确认信息，如果数量很大，发送方会被反馈消息淹没，形成反馈拥塞
• 简单方案：
  • 接收方不对消息进行反馈，而只是在消息丢失时才返回一个反馈
  • 存在问题：需要缓存大量陈旧信息

恢复

• 回退恢复：设置检查点回滚
  • 恢复线路：假定每一个进程都会周期性记录检查点，最近一次的全局一致的检查点就是恢复线路
  • 独立检查点：进程独立设置本地检查点，可能导致多米诺效应
  • 协调检查点：所有进程同步将其状态写到本地稳定存储中
• 前向恢复：继续执行导向新状态
• 擦除修正(erasure correction)：从其他成功传送的分组中建立丢失的分组

检查点的代价过高，通过“重放(replay)”的方式达到一个全局一致的状态而不需要从持久存储中恢复该状态，可通过在日志(log)中持久化消息实现。