第8章 分布式系统的可靠性.ppt

第8章分布式系统的可靠性 分布式系统 八 08 05 2 基本模型 分布式系统的一个重要目标是获取高度的可依赖性 Dependability 可依赖性的概念包括以下三个方面 可靠性 在错误存在的情况下持续服务的能力 安全性 不出现灾难性错误的能力 保密性 指避免 或承受对系统进行的故意性攻击的能力 本章重点关注可依赖性中的可靠性 即故障 错误或失效 faults errors orfailures 这些概念通用 的检测和处理 分布式系统 八 08 05 3 基本模型 分布式系统可靠性的目标是当故障发生时 确保系统的全局一致性 即确保系统具备容错能力 故障来源于如下4类 节点 硬件 故障 物理硬件故障 程序 软件 故障 软件设计或编码错误 通讯故障 通信介质故障 时序故障 物理故障导致运行时序错误 分布式系统 八 08 05 4 基本模型 要确保系统具备容错能力 通常使用冗余技术 有四种冗余类型 硬件冗余 如额外的PE I O系统等 软件冗余 如软件模块的额外版本 信息冗余 如使用了额外位数的错误检测代码 时间冗余 如用来完成系统功能的附加时间 分布式系统 八 08 05 5 基本模型 有三种基本的处理故障的方法 主动复制 所有的复制模块协同进行 并且它们的状态紧密同步 被动复制 由唯一的一个处于主动的模块设定定期检查点 定期更新其它模块的交互状态 半主动复制 是主动复制和被动复制的混合 此种方法所需的恢复开销相对较低 主动复制用到了错误屏蔽的概念 即隐藏出现的故障或防止故障造成错误结果 被动复制 又称为动态方法 它通过从系统中检测错误的存在 并采取一定措施转移错误元件来获得容错 分布式系统 八 08 05 6 基本模型 故障检测可被分为两类 外部检测 将检测节点失效的职责赋予节点的外部附件 或其它节点 但需防止检测者本身故障 检测者和被检测者间通信故障时导致的误检 误报 内部检测将检测机制置于一个节点内部 自检 通常假定内部有一个可以完全信赖的 硬核 hardcore 检测元件 硬核 不受节点故障的冲击 完全做到这一点其实是很难的 通常结合使用外部检测方法和内部检测方法 以得到一个有效的故障检测方案 故障检测的技术实施手段包括 通信应答超时 编码校验 结果比较等 分布式系统 八 08 05 7 基本模型 处理软件故障通常采用两个软件模型 基于进程的模型 一个应用程序由一连串协同作业的进程组成 如 P1 P2 Pn 基于对象的模型 一个应用程序由一连串对象组成 每一个对象都是一个独立的原子操作 通过很好定义的界面访问 就可以获得对象的封装 我们的讨论中 以基于进程的模型为例 分布式系统 八 08 05 8 容错系统设计的构件模块 具备容错能力的 可靠的分布式系统中涉及到三种逻辑实体 包括二种构件模块 稳定存储器故障 停止处理器和一个用于构件模块的 原子操作 分布式系统 八 08 05 9 稳定存储器 稳定存储器是在系统失效的情况下 可以躲过系统错误的特定存储空间的抽象概念 也就是说 稳定存储器空间里的内容不被一个失效所摧毁 存储器的两个基本操作是读和写 稳定存储器的目标是在系统失效的情况下 屏蔽不希望的事件 正确地执行读 写操作 分布式系统 八 08 05 10 稳定存储器 对于读read address a 来说 返回 status goodorbad data d 其不希望结果包括 a是好的 但读取返回bad 同上 而且后来的读也返回bad a是坏的 但读取返回good 或者a是good 但读取返回不同的数据d 对于写write address a data d 来说 其不希望的结果 a保持不变 而d变为不同的数据d a变为 bad d 一个理想的稳定存储器 读总是返回正确的结果 写总是成功 分布式系统 八 08 05 11 稳定存储器 RAID 获得适宜的稳定存储器的一个方法是使用RAID技术 RedundantArraysofInexpensiveDisks 廉价磁盘冗余阵列 目前常用的有下列RAID技术 分布式系统 八 08 05 12 故障 停止处理器 一个处理器故障时 最好的结果是不进行任何不正确的操作 而简单地停止工作 这样的处理器称为故障 停止处理器 一个故障 停止处理器有以下特性 a 处理器停止运行 b 暂态存储丢失 而稳态存储不受影响 c 任何处理器均可检测到故障 停止处理器的失效状态 分布式系统 八 08 05 13 故障 停止处理器 可以使用下面的方法使一个非故障 停止处理器变成一个故障 停止处理器 使用稳定存储器和一个可靠的存储处理器 一个控制存储媒介的处理器 以及k 1个处理器 这k 1个处理器都运行同样的程序并通过存储处理器访问同一个稳定存储器 如果存储处理器发现任何一个请求是不同的 或者任何一个请求没有在指定的期间到达存储处理器 则意味着检测到一个失效事件 因而应该丢弃所有请求 这个故障 停止处理器是一个k 故障 停止处理器 当系统中有 k个元件失效时 仍然可以满足故障 停止处理器的要求 分布式系统 八 08 05 14 原子操作 一个原子操作就是由硬件独立执行的一系列动作 即每一个动作或者被完全彻底地执行 或者系统的状态保持不变 动作根本没有执行 每一个动作都是孤立的 当执行这一动作时 在进程中感觉不到外界活动的存在 也意识不到外界状态的变化 同样 任何外界的进程均感觉不到一个孤立的原子操作的内在状态的变化 即原子操作具有 全或无 性质 许多应用都需要原子操作 如 对信号量操作 对数据库的访问等 分布式系统 八 08 05 15 故障的处理 节点故障的处理拜占庭式故障的处理通信故障的处理软件故障的处理 分布式系统 八 08 05 16 节点故障的处理 使用主动复制的方法处理节点故障 相对来说比较简单和容易 但其代价较大 处理 永久 故障的硬件冗余比较昂贵 处理 暂时 故障的时间冗余 重试 其效率受到较大影响 我们讨论被动复制的方法 在被动复制中可以使用向前式恢复或向后式恢复 向前式恢复中 假定系统中故障和损失的性质可被完全准确地获知 这样就可能去掉这些故障以使系统继续向前运行 看似简单 实现困难 向后式恢复适用于当故障的性质无法预知及去掉时 系统要定时地记录系统状态 这样当失效导致系统处于不相容的状态时 系统可以重新恢复到从前没发生故障的状态 比较可行 分布式系统 八 08 05 17 向后式恢复 检查点 Check point 进程执行中设定的 记录当时进程状态的 用于以后节点故障时进程向后恢复回来的点被称为 检查点 有两种方法来保存检查点 每个检查点被传送到每一个被动 备份 模块 每个检查点被存储在当地的稳定存储器中 系统总是保存最近 最新的一个检查点 当进程无故障地运行到一个新的检查点时 就需要进行新旧检查点保存的替换 检查点保存的替换必须是原子操作 即要么保存替换为新检查点 要么保留旧检查点 分布式系统 八 08 05 18 向后式恢复 一个进行新旧检查点保存替换的方案 Sequoia 使用2个处于稳定存储器中的内存库 A库和B库 作为检查点的双份保存 在对新检查点状态信息进行保存以刷新旧检查点状态信息时 同时写入4个固定 相同的时戳 A库 刷新前Ta1 刷新后Ta2 B库 刷新前Tb1 刷新后Tb2 通过分析替换操作后的时戳结果 确定下一步的措施 以及是否导致替换操作成功 例中假设先刷新A库 若相反 则类似 分布式系统 八 08 05 19 向后式恢复 如果4个时戳相等 则新旧检查点保存替换操作完全成功 如果一个库中只写下刷新前的时戳 如Ta1 则失效发生在向该库 A库 刷新的过程中 即该库 A库 中新检查点是不完全的 此时需用另一个旧库 B库 中的旧检查点信息将该库 A库 恢复 一旦有一个库刷新成功 如Ta1 Ta2 则可以复制这个新库 A库 中的新检查点信息到旧库 B库 中 而使整个新旧检查点保存替换操作成功 分布式系统 八 08 05 20 节点故障的处理 当检测到节点模块 如PE 出现故障时 使用被动复制的向后式恢复方法 可以这样处理 对于 永久性 故障 用后备冗余模块替换故障模块 替换上来的模块从稳定存储器中获得上一个检查点 最近的 的系统状态 从该处重新执行 硬件冗余 对于 暂时性 故障 使用原来的模块从稳定存储器中获得上一个检查点 最近的 的系统状态 从该处重新执行 时间冗余 分布式系统 八 08 05 21 前卷式恢复 一个向前式恢复策略是前卷式恢复 它是半主动复制的一个特例 其主要的思路是 一个进程 任务 的初始备份 或上一个正确的检查点开始 由不同的处理器来运行 这些版本的结果在检查点进行表决 或比较 如果表决结果是成功的 则可以获得一个储存在稳定存储器中的正确结果 在这个结果的基础上 再执行下一项任务的备份 如果表决结果是失败的 非故障处理器就在以前的任务的每一个结果的基础上执行下一项任务的备份 与此同时 后备处理器替换故障处理器对以前的任务执行一次回卷运行 即在后备处理器上再运行以前的任务 目的是获得正确的结果 稳定存储器只保存基于以前的任务项的正确版本的经过表决后正确的结果 而抛弃掉其他结果 所有版本都失效 或后备处理器重新运行以前的任务也不能获得正确的结果 回卷是不可避免的 但这种最坏情况发生的可能性很小 因此前卷式恢复仍然可以节省很多的回卷时间 分布式系统 八 08 05 22 前卷式恢复 Pradhan和Vaidya提出有2个验证间隔的前卷式恢复方案 Long Fuchs和Abraham提出有1个验证间隔的前卷式恢复方案 P171 P172 需要参考相关文献 分布式系统 八 08 05 23 向后恢复中的问题 考虑向后恢复中的两个特殊问题 检查点的存储 讨论检查点存储的策略 检查点方法 讨论设置检查点的方法 分布式系统 八 08 05 24 检查点的存储 向后恢复式的系统中 将系统的数据分为2类 活动数据 进程执行中的数据 检查点数据 检查点时刻保存的数据 系统存储器可以分为3个层次 第一层 寄存器 register 和高速缓存 cache 易失性的 如失电丢失 第二层 内存 memory 易失性的或非易失性的 如闪存flashmemory 或自供电内存 第三层 磁盘 disk 非易失性的 3个层次的存储器其访问速度依次指数级降低 成本依次指数级降低 容量依次指数级增大 分布式系统 八 08 05 25 检查点的存储 可能的检查点存储的分配方案有 在第一层 寄存器和高速缓存 存储活动数据 在第二层 非易失性内存 和第三层 磁盘 存储检查点 在第一层和第二层 易失性内存 存储活动数据 在第三层存储检查点 总之 检查点数据必须存储在稳定存储器中 前一种方案检查点存储的效率较高 分布式系统 八 08 05 26 检查点的存储 一个方案 基于高速缓存的检查点方案活动数据存储在CPU的寄存器和高速缓存中 检查点数据存储在内存中 检查点和回卷的要求如下 在检查点将局部状态 CPU寄存器 保存在一个特殊的内存区域 将更改过的高速缓存中的数据写到内存中 回卷时从特殊的内存区域装入CPU寄存器 将高速缓存中的所有被更改的数据设定为使无效 高速缓存中不能命中 从而强制从内存中读取检查点数据 分布式系统 八 08 05 27 检查点的存储 此方案的另一个重要问题是活动数据不能全部在高速缓存时 需要保持更改过的高速缓存中的数据与内存的一致 有2种方法 写通 write through 高速缓存方法 高速缓存被更改时 改变将立刻写入内存 写回 write back 高速缓存方法 只有高速缓存失效 退出 时才进行更新内存 在写回方法中 因为在处理器失效的情况下没有必要改写内存 因此恢复时会更快 分布式系统 八 08 05 28 检查点的存储 另一个方案 双胞胎页面方案活动数据存储和检查点数据存储映射到存储等级的两块区域 当使用新的检查点时 它们就彼此交换角色 即 活动数据变成检查点数据 检查点数据区域用于活动数据 两块区域的分配策略有 将活动数据存储和检查点数据存储映射到同一个等级 如第二层或第三层 将活动数据存储和检查点数据存储映射到相邻的等级 如第一层和第二层或第二层和第三层 分布式系统 八 08 05 29 检查点方法 一个全局状态的定义是一系列局部状态 检查点 的集合 每个局部进程有一个局部状态 而各局部进程设置局部检查点是独立的 这就可能出现两种不好的状态 丢失的消息 进程Pi的状态 当前检查点 显示它给进程Pj发送了消息m 但是进程Pj并没有关于这个消息的记录 孤儿消息 进程Pj的状态显示它收到了一个来自进程Pi的消息m 但是进程Pi的状态显示它从来没有向Pj发送过m 分布式系统 八 08 05 30 检查点方法 丢失消息这个状态出现的可能性 消息真的丢失了 通信链路的故障 消息没有丢失 正在传输中 但全局状态中Pi和Pj的检查点设置不合理 如下图a 消息被收到了 但接收者在收到消息后但在开始下一个检查点之前崩溃了 如下图b 通过设置接收者日志可以追查到这个消息 当前检查点 当前检查点 Pi Pj m a 当前检查点 当前检查点 Pi Pj m b 下一个检查点 接收者日志 分布式系统 八 08 05 31 检查点方法 孤儿消息这个状态出现的可能性 发送者在发送完消息后失效 被卷回到前一个检查点 如下图 通过设置发送者日志可以追查到这个消息 为了解决孤儿消息 接收者回卷到上一个检查点 并且清除对孤儿消息的记录 当前检查点 当前检查点 Pi Pj m 下一个检查点 发送者日志 Pi记录了消息m的接收 但Pj没有记录消息的发送 分布式系统 八 08 05 32 检查点方法 然而 这样可能会导致多米诺效应 dominoeffect 当前检查点 当前检查点 Pi Pj n 下一个检查点 m 分布式系统 八 08 05 33 检查点方法 几个概念 非常一致的 强一致的 stronglyconsistent 检查点集合 一系列的没有孤儿或丢失的消息的局部检查点的集合 显然 在这些检查点的中间时段 进程间没有信息流动 一致的 consistent 检查点集合 一系列的没有孤儿消息的局部检查点的集合 如果每个进程都在发送一个消息之后就马上生成一个检查点 则最近的检查点的集合将永远是一致的 但并非强一致的 分布式系统 八 08 05 34 检查点方法 检查点的设置可以是同步的 异步的 也可以是二者的混合 另外也可以选择要不要对一个进程发送或接收的消息做日志 同步检查点 有关的进程协调它们的局部检查点行为 确保所有的最近的检查点都是一致的 如 接收进程对消息的接收设置了检查点 则该消息的发送进程对消息的发送要设置检查点 显然 同步检查点的设置需要一些额外的开销 异步检查点 每个进程都在没有任何协调的情况下设置最自己的检查点 异步检查点情况下 可以通过间隔 时间 依赖图来判断一个检查点集合是否一致 当且仅当不存在i和j满足LCi LCj Pi是发送进程 Pj是接收进程 即 所有的发送进程Pi和接收进程Pj之间不存在孤儿消息 分布式系统 八 08 05 35 检查点方法 混合检查点 更好地利用了同步和异步检查点的方法 在一个较长的时间中使用同步检查点 在这些同步时段里 会有一些异步时段 这样既可以有效地控制回卷 又不会在建立检查点的过程中引入很多开销 检查点日志 对所有的发送和接收消息都记录下来 发送者日志和接收者日志 这样在一致的状态下 可以利用接收者日志减少回卷工作量 即只需将收到的消息重放一遍 这也可以有效地控制多米诺效应 当前检查点 当前检查点 Pi Pj m 下一个检查点 接收者日志 分布式系统 八 08 05 36 检查点方法 在没有其它处理器故障的前提下 发送者日志可以提供无需回卷的恢复 即 下图中发送者Pj根据发送日志 不需要再发送消息m 当前检查点 当前检查点 Pi Pj m 下一个检查点 发送者日志 分布式系统 八 08 05 37 处理拜占庭故障 故障 停止处理器模型的其它情况 一个有故障的处理器可能会向不同的处理器做出一些恶意的行为 如提供一些不同的 不可信的结果 或发送不同的令其它处理器费解的消息 这种不稳定的 变幻莫测的故障叫做拜占庭故障 Byzantinefault 处理拜占庭故障一个重要的应用是一致协议 agree mentprotocol 一个进程 处理器 集合需要在部分进程 处理器 发生拜占庭故障时 能够产生一个一致的 正确的 结果 分布式系统 八 08 05 38 同步系统中的一致协议 更确切的说 一个一致协议需要满足 一致性 所有 正确的 进程取得一致的结果 而且是最后的结果 合法性 所有进程同意的结果必须来自某个 正确的 进程的输入 有限性 每个进程在有限的步数内取得一个结果 分布式系统 八 08 05 39 同步系统中的一致协议 拜占庭将军问题 Byzantinegeneralproblem 拜占庭军队的几个师围在一个敌军军营周围 每个师都有自己的将军领导 每个将军可以通过信使与其它将军传递消息 但某些将军可能是叛徒 在对敌军进行考察后 将军们必须决定一个战略计划 这个计划由一个将军 称为commandinggeneral 发送给其他的将军 称为lieutenant 必须设计一个算法 满足 1 所有忠诚的lieutenant得到相同的命令 2 如果commandinggeneral是忠诚的 那么每一个忠诚的lieutenant必须得到commandinggeneral正确的命令 分布式系统 八 08 05 40 对一个发送者的一致 系统中的每个非出错进程都使用来自进程Pi的结果来进行决策 这样 一致性将军问题就变为系统中的进程都同意一个进程 比如P0的结果 确切地说 所有非出错进程都使用来自进程P0同样的值v0 如果发送进程P0是非出错的 那么所有非出错进程都使用P0发送的 正确的结果 这个要求叫做交互一致性 interactiveconsistency 达到上述要求的困难之处在于一个进程发往另一个进程的消息是不可轻信的 所以 为了同意一个进程发送的值 除了从那个进程取得值以外 还需要从其它进程取得其收到的值 然后进行确认 少数服从多数的决策 以确定它是原来的值 分布式系统 八 08 05 41 对一个发送者的一致 交互一致性算法 条件 一个发送者 k个出错节点 至少3k 1个进程总数 具体算法 算法共k 1步 IC l l k 初始时 l 0 S S 发送者列表 1 发送者将它的值和发送者列表发送给其它的进程 共 n l 1 个消息 2 设vi是进程Pi从发送者接收到的值或者是如果没有收到值时使用的缺省值 在IC l 1 k 进程Pi作为发送者 将结果vi和发送者列表S Pi 发送给其它不在发送者列表中的n l 2个进程 如果l 1 k 则调用IC k 3 对每个进程Pi 设vj是从进程Pj接收到的值 由Pj转发给Pi 即IC l 1 的结果 节点使用值majority vi vj j S IC k 1 发送者将它的值发送给其它n k 1个进程 2 每个进程使用它从其它至少2k个接收者发送来的 加上自己收到的 然后进行majority的值 或者是如果没有收到值时使用的缺省值 分布式系统 八 08 05 42 对一个发送者的一致 算法说明 每个进程都可以和其它任何一个进程通信 第一个发送者可能是出错进程 算法总结 是一个递归算法 算法经过k 1轮的消息交换 算法被交换的消息总数是 n 1 n 2 n k 1 个 算法的复杂度是O nk 算法例 一个有7个进程的例子 P178 参考 拜占庭将军问题资料 分布式系统 八 08 05 43 多个发送者的一致 系统中有多个消息发送者 可以通过对每个发送者都重复同样的协议将交互一致扩展到多个发送者的情况 已经证明 当且仅当n 3k 1时 这个问题才时可解的 n是进程总数 k是故障进程数 解决这个问题的算法需要至少k 1轮的消息交换 Fisher lynch和Merritt证明了 在3个进程中 最多有1个进程出错的情况下 另外2个进程不可能达成一致 P179一个例证 分布式系统 八 08 05 44 多个发送者的一致 算法实例 n 4 k 1 通过2轮消息交换 1 每个进程将它的局部值发给其他3个进程 2 每个进程将它从第1轮收到的消息发给其他所有的进程 3 每个进程对自己的专用值和在上2步收到的值执行一个决策过程 少数服从多数 结果见P180表8 2 其中vi是进程Pi的专用值 vik表示不同类型的故障值 表示空值 假设P1是故障进程 其他3个正确的进程P2 P3和P4可以通过对每列的4个向量进行多数投票获得相同的结果向量 v18 v2 v3 v4 分布式系统 八 08 05 45 不同模型下的一致 Turek和Shasha提出了不同模型下关于一致问题的一些参数 系统是同步的 A 1 还是异步的 A 0 通信延迟是有限的 B 1 还是无限的 B 0 消息是有序的 C 1 还是无序的 C 0 传输机制是点对点的 D 0 还是广播 D 1 经过证明 不同模型下取得一致的条件是 AB AC CD True即 1 AB 1 处理器是同步的 通信延迟是有限的 2 AC 1 处理器是同步的 消息是有序的 3 CD 1 消息是有序的 传输机制是广播 其它的条件下 如异步 点对点系统 两军问题 不可能达到一致 分布式系统 八 08 05 46 被鉴别消息的一致 一个有故障的接收者可能会将一个消息的不同值转发出去 但在接收者不能改变消息的情况下 问题就简单了 可以通过给消息增加一个数字签名来实现这一点 每个消息m都附加一个发送者签名的列表S P181 182 书上错误 P182 P i 中 的位置 S i 分布式系统 八 08 05 47 处理通信故障 解决通信故障的最简单的方法就是使用应答和超时机制 如果发送者没有收到来自接收者的应答信号 发送者就会重新发送这个消息 如果认为错误是临时性的 就采用相同的路径 如果认为错误是永久性的 就选择另外一个点分离的路径 永久性故障环境下的超时方法 success F i 1 success i number of node disjoint path setup t sendmessagemtoreceiveralongtheithpath receiveackfromreceive success