2.2.3 冗余
2.2.3.1 冗余定义
星载嵌入式计算机是星上采用计算机网络技术，将星载电子设备互连，实现卫星内部信息共享和综合利用、功能集成、资源重组优化的信息处理和传输系统。因此，有必要在已采取常规可靠性措施的情况下进一步进行冗余设计，采用高可靠多余度容错计算机技术来提高计算机系统的可靠性。
20世纪50年代，冯·诺依曼最早提出了采用冗余的思想来解决容错的问题。经过几十年的发展，目前冗余已经成为容错的基本方法。
从硬件冗余来讲，按照备份方式可将其分为热备份、冷备份；按照冗余的数量，可分为双机备份、多机备份；按照故障恢复方式，可分为静态冗余、动态冗余。选取何种冗余方式，主要是根据系统的实际要求确定。在航天器计算机系统中，决定冗余的方式包括系统的可靠性、自主性、寿命、重量、功耗和体积等因素。对于故障处理实时性、可靠性和安全性要求高的系统，一般采用静态冗余方式，典型的有“三取二”表决方式，如返回式卫星控制计算机；对于寿命要求高的系统，可采用冷备份方式，如高轨通信卫星；对于可靠性要求特别高的系统，可采用混合冗余的方式，即静态和动态相结合的方式，如“神舟”飞船姿轨控计算机。
2.2.3.2 冗余设计
按照所利用资源的不同，可将冗余分为空间冗余、时间冗余、混合冗余。
（1）空间冗余。指通过占用额外的空间资源如器件、函数或数据来实现容错。根据占用冗余资源的不同，空间冗余包括硬件冗余（如三模冗余）、软件冗余（如多版本）和信息冗余（如纠删码）。
（2）时间冗余。指通过占用更多时间包括重复计算或数据恢复等来实现容错。
（3）混合冗余。指将空间冗余和时间冗余结合起来，利用两者优势来实现的容错技术，如基于故障预测的进程迁移技术等。
容错方法分类如图2- 7所示。
图2-7 容错方法分类
1）空间冗余容错技术
（1）三模冗余（triple modular redundancy，TMR）。为典型的空间冗余技术，其通过增加硬件的方式，达到容错的目的。TMR是N模冗余的特例（N＝3），由于TMR可靠性较高且实现简单，得到了广泛的应用。图2-8所示为基本TMR系统的运行原理，系统在运行过程中完成实际任务的部分通常由三套独立且相同的模块组成，三个模块接收相同的输入，产生的三个结果送入多数投票器进行表决。当送入投票器的三个结果相同时，投票器认为运行正常并输出该结果；当送入投票器的结果只有两个相同时，投票器认为一个模块出现故障，投票器输出正常的多数模块的结果；只有三个模块得到结果均不相同时，投票器判断系统全部出现故障并重启计算。换句话说，三模冗余结构，只有在大于等于二模正常的情况下能够得到正常结果。因此，三模冗余可在单一时刻实现对单一故障的屏蔽。
图2-8 基本TMR系统的运行原理
星载嵌入式计算机的表决包括两部分：输入数据的表决和输出数据的表决。输入数据的表决由软件按“三取二”的原则来实现；输出部分的表决由软硬件协同实现。表决器实现原理如图2- 9所示。
图2-9 表决器实现原理
①软件部分。每块CPU板的软体通过读取双口RAM中相应各个CPU模块运算的结果进行全量表决，其表决的原则为“三取二”；同时，在CPU空闲时进行自检。软件的表决输出是软件表决与自检信息处理后形成2位结果（2位信息00，01，10，11，表示CPU1，CPU2，CPU3输出或都不正常），并将此信息传递给硬件表决器FPGA。
②硬件部分。表决各块CPU板传送过来的表决结果，最终形成3个开关信号来控制CPU板的输出；硬件表决器的实现由FPGA完成，便于系统调试。
由于输出部分的软件表决是在3块CPU上同时运行的，理论上3块CPU输出数据都是正确的，因此不管输出哪块CPU板的数据，其结果都是正确的。即使硬件表决暂时有错误，最终的输出也是正确的。同时，为了保持数据的连贯性，切换的原则不是简单地按照“三取二”，而是根据原则的表决结果累计当前选择的CPU板错误的次数，只有当连续错误的次数超过一定量后才切换到另一块CPU板。
由于硬件表决器本身就是一个单点，因此系统对此进行了旁路设计。硬件表决器本身可以自检，如果硬件表决器出现暂时的输出错误（如不应同时选择打开2个CPU板或3个CPU板）或表决器无法正常启动，系统默认选择第1块CPU板的输出数据。当然，在冗余计算机工作之前，应对硬件表决器进行全面测试，确保表决器工作正常。
（2）拜占庭冗余。拜占庭将军问题是一种对现实世界的模型化，尤指网络当中由于软硬件错误、网络阻塞及恶意攻击导致的各种未知行为。拜占庭容错系统要解决的是分布式系统中存在恶意节点（即拜占庭节点）时，系统的一致性、正确性等问题。
假设分布式系统拥有n台节点，并假设整个系统拜占庭节点不超过m台（n≥3m+1），拜占庭容错系统需要满足如下两个条件：
①所有非拜占庭节点使用相同的输入信息，产生同样的结果；
②如果输入的信息正确，那么所有非拜占庭节点必须接收这个消息，并计算相应的结果。
另外，拜占庭容错系统需要达成如下两个指标：
①安全性。任何已经完成的请求都不会被更改，它可以在以后请求中看到。
②活性。可以接受并且执行非拜占庭客户端的请求，不会被任何因素影响而导致非拜占庭客户端的请求不能执行。
在分析拜占庭问题的时候，假设信道是可信的。拓展开来，在拜占庭容错系统普遍采用的假设条件包括：
①拜占庭节点的行为可以是任意的，拜占庭节点之间可以共谋；
②节点之间的错误是不相关的；
③节点之间通过异步网络连接，网络中的消息可能丢失、乱序并延时到达，但大部分协议假设消息在有限的时间内能传达到目的地；
④节点之间传递的信息，第三方可以嗅探到，但是不能篡改、伪造信息的内容和破坏信息的完整性。
注意：并非所有的缺陷或故障节点都称为拜占庭节点，拜占庭节点的行为有不可预测、任意性的特点，例如遭黑客破坏、中木马的服务器就是一个拜占庭服务器。
（3）算法容错。另一种典型的空间冗余容错技术是算法相关的容错方法。该方法通过开发具有容错能力的算法来完成容错，其需要针对并行算法的特点来完成容错设计，使得算法具有天然容错的能力。美国圣地亚国家实验室最先开展了该类算法的研究，提出了包括异步并行直接搜索（asynchronous parallel direct search）等具有容错能力的算法，这些算法可保证计算任务在小部分数据丢失的情况下仍能正确执行，而不需要进行故障处理或恢复。另有部分算法研究成果，虽然必须恢复故障丢失的数据才能正确运行，但其数据恢复方法非常高效。还有一类针对矩阵运算应用的算法，其可以针对计算数据进行编码，在算法执行过程中通过检查保留的编码，来判断是否发生了错误。这些算法相关的容错方法通常具有较低的容错开销，但对程序员提出了较高的要求，需要充分利用应用特点或数据特点精心设计独特而高效的容错方案，因而缺乏通用性，难以推广。
2）时间冗余容错技术
当前已有的典型时间冗余容错技术包括并行复算（parallel recomputing）和回滚恢复（rollback-recovery）。
由中国国防科技大学杨学军等人提出的并行复算，是一种具有快速故障恢复能力的容错技术。其核心思想如图2-10所示：当某进程发生故障时，将故障结点因故障丢失的负载分配到其余的无故障结点上进行并行的重算，而无须将全部进程回滚，因此能够有效加快故障恢复速度。并行复算采用时间冗余的方法，利用现有硬件资源，在不要求额外增加资源的情况下加速故障恢复。该方法适用于计算密集型应用，对需要较多通信的应用，并行复算的优势并不明显。
回滚恢复的基本思想是：在计算过程中周期性地保存计算状态，当故障发生后，应用程序回滚到之前保存的某个状态处重新开始执行。回滚恢复方法要求重复执行从故障前的某个状态到故障发生处之间的计算过程，虽然这种方法通常会要求额外的存储空间保存恢复所需的计算状态数据，但在保存和恢复的过程中关键的开销为时间开销，因此在这里仍将回滚恢复方法作为时间冗余容错技术。在分布式和并行计算领域，回滚恢复方法得到普遍关注、使用最为广泛。
图2-10 并行复算基本原理
3）混合冗余容错技术
对于空间冗余，为了完成同样的计算任务，需要占用更多的计算资源，降低了计算资源的利用率；对于时间冗余来说，冗余机制需要引入额外的计算时间来消除错误的影响，机制本身引入了时间开销。随着并行应用规模的不断增大，单纯的空间冗余或时间冗余，其弊端越来越明显。因此，可有效结合两者优点，通过引入故障预测机制，采用较少的空间冗余，配合时间冗余技术，从而有效提高并行计算的容错效率。
基于故障预测机制的容错技术，通常具有主动触发的特点，常被称为主动容错技术。而传统的容错技术如checkpointing技术，则通常被称为被动容错技术。由于故障预测目前无法达到对故障完全准确预测的程度，单纯的主动容错技术仅基于故障预测机制进行容错，当遇到未预测到的故障或者是已预测到但未来得及采取容错措施的故障时，系统可能面临较大的损失。因此，现有的主动容错技术常和被动容错技术结合起来，使得不仅能够利用主动容错技术的优势，而且能够避免故障预测不完全的缺点。
主动容错技术研究的关键在于故障预测方法准确率的高低。现有故障预测方法主要可分为两大类：基于模型的故障预测和基于数据驱动的故障预测。
基于模型的故障预测，需要事先假设系统故障符合某种模型，对于小规模系统中某些类型的故障，采用基于模型的预测方法能够获得较好的预测效果，但是对于由数十万以上部件构成的超级计算机系统，故障建模十分复杂，难以用模型准确描述系统的故障特征。
基于数据驱动的故障预测，主要利用数据挖掘、机器学习等技术对历史数据进行学习，获取故障发生的规律，然后利用学习的结果对所监测系统的实时状态数据进行分析，预测是否有故障发生。