基于Raft算法的飞行控制系统余度管理应用

机载计算机（Airborn Computer）在飞机上的主要应用领域为飞行控制系统、飞行控制系统和机电管理系统。将飞行控制系统中的计算机称为飞行控制系统计算机，即飞控计算机。飞控计算机是面向飞行控制应用的计算机，主要任务是完成飞机运行中的控制律计算、余度管理和机内自检测，对飞行安全起着至关重要的作用。

一方面 ，飞行控制系统是一个安全关键系统（SafetyCritical System， SCS），它的安全问题会对生命财产甚至国家安全问题造成巨大威胁，因此飞行控制计算机的安全性和可靠性具有极高的要求。另一方面，飞行控制系统计算机作为机载计算机与通用计算机并不相同，它需要配合不同的电子设备应用到不同的任务场景中，所以还应该具有良好的可扩展性和灵活性。

基于上述两方面的目的，众多研究学者纷纷将关注度转向分布式的余度结构，通过恰当的余度管理办法来实现飞控计算机的容错功能。

然而，目前绝大多数分布式余度管理办法的实现都依赖于故障检测技术，如 SIO 单元自检、FlexRay 总线故障检测等机制，并没有利用到分布式结构本身的特点。除此之外，目前众多的余度管理办法都是针对宕机故障错误考虑，没有讨论拜占庭错误对分布式集群的影响。

Raft算法是一个典型的一致性算法，自被 Stanford 大学的 Diego 于 2013 年提出以来，由于具有易理解性和强落地性等特点而被广泛应用到实际业务中，如CoreOS团队的Etcd项目、PingCAP公司的TiDB等。它依赖主节点和副节点之间的通信保持一致，只要满足大多数节点可用就可以对外提供强一致性的算法。

因此，本文研究应用 Raft 一致性算法在存在拜占庭节点的情况下，实现分布式余度管理结构的强一致性，并根据机载环境的在计算、通信等指标受限的情况下优化Raft算法，使它更适合飞控系统的应用。

本文主要研究内容如下：

1）应用Raft一致性算法解决分布式余度结构的拜占庭错误问题，使飞行控制系统具有超高的可靠性和良好的可扩展性；

2）考虑机载环境的特殊性，机载计算机具有一定的要求，优化Raft算法的余度管理应用方案，使它更适应飞行控制系统的需求。

1. 1　余度管理办法　

典型的余度管理办法主要有两种：主从备份结构和多处理机结构，或者是这两种结构的结合。

主从备份结构中，将一个或多个与主处理机具有相同结构和功能的计算机作为从处理机，通过故障检测监察故障的发生，一旦发现问题可以及时切换到从处理机，由从处理机代替主处理机工作，如图 1 所示。该方案的关键是故障检测机制，若不能及时检测到故障并切换到从处理机，或产生错误报警，则会影响系统的可用性。目前最常用的故障检测技术仍然不能达到 100% 的自检覆盖率，并且存在一定的切换时间和误报概率，极大地影响了系统运行。此外，该方案中从处理机长时间处于备份中会对整个机载资源造成浪费。

多处理机结构运用故障掩盖技术，通过多个通道间的实时比较监控实现容错功能，如图 2 所示。该方案的关键在于输入输出表决机制，用于实时监控比较，核心思想不是发现错误，而是即使出现了错误系统仍然可以得到正确的结果，执行正确的行为。因此该方案可能存在潜在故障，需要配合故障检查和隔离方法，并且需要额外设计比较机制以便获得正确结果。

随着机载计算机的发展，国内外在新一代的民用飞机和军用飞机的开发和研制中，飞控系统都采用了新的容错计算机系统结构，即分布式结构。

分布式余度结构中，多个余度计算机之间构成分布式集群，通过总线进行连接，并配合相应的故障检测和处理机制实现容错，如图 3 所示。该方案能够提高飞控系统的可靠性和可扩展性，但并没有利用分布式结构本身的特点，仍然是利用故障检测技术实现故障发现和排除。因此目前有许多方法都是对分布式中故障检测技术进行研究。

1. 2 Raft一致性算法

Raft 算法衍生自 1998 年 Lamport 提出的 Paxos 协议，但相较于Paxos协议难以理解和缺少细节支撑的问题，Raft算法不仅具有直截了当的表现形式，还给出了代码实现的相关逻辑，因此具有更好的可理解性和更高的落地性。

近年来，伴随着区块链技术的发展，共识问题得到了极大的推动，针对多种多样的场景人们提出了许多的共识算法，但Raft 算法仍然是抗故障错误算法中的一颗璀璨明珠，仍然得到了广泛的应用，如 hyperledger fabric、Ethereum联盟链EEA等区块链平台都有接入和使用该算法，足以说明 Raft算法的优秀。

Raft 算法由两个主要的协议构成：领导者选举协议和一致性协议。领导者选举协议用于在创建系统或当前领导者失效的时候选举出新的领导者，领导者需要完成客户端的请求并反馈消息给客户端，通过领导者协议保证领导者和系统的活性。一致性协议用于让不同的节点按照相同的顺序执行客户端的请求，保证系统的一致性。

Raft 算法将整个系统中的节点分成了两类：诚实节点和故障节点，它们的区别在于能否及时响应正确消息。Raft 算法能允许网络中发生故障的节点数小于全网节点数的一半，但不能排除拜占庭故障的影响。然而飞控系统使用的机载计算机可能会受到敌方的干扰和控制，导致分布式集群中部分通道紊乱，产生破坏系统安全的行为，如执行得到错误结果或发送矛盾信息等。

Raft 算法本身能够处理宕机故障，但无法解决拜占庭错误导致的系统紊乱问题，本文将对此展开研究。

1. 3　门限签名算法　

门限签名方案（Threshold Signature Scheme， TSS）属于一种特殊的数字签名方案，也是一种基于安全多方计算（Secure Multi-Party Computation， MPC），一般借用Shamir 秘密共享技术实现，它将一对公私钥(P，K ) 分成 n 个不同的私钥分量和可验证密钥集，n个不同的私钥分量由集群中n个节点自己保留，并且当集群中节点收集到的签名数达到门限 t时，节点可以代表群体签名，得到群体签名结果 Sigshare，其他所有节点都可以用公钥P进行验签。这就是本文利用门限签名方案降低计算和通信开销的重要数学依据。

目 前 常 用 的 门 限 签 名 算 法 主 要 有 BLS（Boneh-Lynn Shacham）、椭 圆 曲 线 数 字 签 名 算 法（Elliptic Curve DigitalSignature Algorithm， ECDSA）、Schenorr等算法，其中 BLS算法运算时间较短，对签名和密钥聚合非常友好，并且过程具有确定性，不依赖于随机数生成器，已经被 Ethereum、Algorand、Dfinity 等多种区块链采用，因此本文也选用 BLS 作为优化方案的门限签名算法。

BLS 聚合签名算法是目前常用的一种门限签名算法，新了这个签名方案，BLS 算法利用了基于双线性映射的椭圆曲线配对技术来实现签名验证与聚合，非常适合运用在签名次数较少但验签次数相对较多的应用场景，用于减少验签次数，降低计算开销。

该算法最早是由 Stanford 大学的 Dan Boneh 等在 2001 年提出的，2018 年 Boneh 教授与 IBM 研究机构的 Manu Drijvers等更新了这个签名方案，BLS 算法利用了基于双线性映射的椭圆曲线配对技术来实现签名验证与聚合，非常适合运用在签名次数较少但验签次数相对较多的应用场景，用于减少验签次数，降低计算开销。

2. 1　总体架构

本文采用分布式余度管理结构，利用作为核心技术的一致性算法实现容错特性，不需要配合故障检查机制完成容错，在有效提高可靠性与安全性的同时，能增强可扩展性和灵活性，适应飞控系统各类应用场景的使用。Raft 一致性算法的应用方案如图4所示。

以四余度飞控计算机系统为例，如图 5 所示为系统结构框图。由数字飞控计算机构成分布式余度集群，为系统提供高可靠性和可扩展性。

图6所示为一致性流程示意图。传感器将自己获得的数据发送给分布式集群中的主处理机，主处理机根据感知数据进行控制律计算和分析处理，最终得到相应的执行动作和控制指令，并将执行结果发送给余度集群中的所有从处理机，从处理机验证该处理结果是否正确，若符合规范则投出赞同票认可主处理机的操作结果，反之投出反对票不认可主处理机的操作结果；主处理机根据自己收到的票形，判断是否有超过n/2个正确签名（n表示飞控系统的余度，即余度集群节点数），并对执行机构进行控制。

在该过程中存在两个问题：

1）主处理机负责接收、处理和输出执行控制指令，关键性不言而喻，若主处理机发生故障，则整个系统都处于不可用状态，因此必须有相应的操作可以在主处理机发生宕机故障时，将从处理机切换为主处理机，并使原来的主处理机转变为从

处理机状态。

2）主处理机可能被敌方干扰和影响，导致系统发生紊乱，表现为主处理机能力范围内的任意操作，如停止之后在未来某个时刻重新启动，发送矛盾信息给不同的从处理机，这可能导致集群产生两种结果导致不一致的情况，因此若飞控系统考虑拜占庭弹性问题，则应该有相应的机制排除主处理机发生错误的影响。

2. 2　主处理机故障

针对主处理机故障问题，可以采用 Raft 算法的领导者选举机制，重新切换主处理机，保障系统的可用性。如图7所示为主处理机切换机制的详细过程。

Raft 一致性算法将时间划分为一个个的任期 Term，并且在每个任期开始时选举出一个主处理机作为本 Term 的Leader，正常情况下 Leader 定期向所有从处理机发送心跳heartbeat 维持自己的地位，从处理机接收到 heartbeat 后会重置自己的计时器，若从处理机在一段时间内没有接收到heartbeat，导致计时器超时，则会向集群请求自己成为新的主处理机。

通过领导者选举机制可以有效解决主处理机受到干扰或发生故障时系统不可用的问题，提升飞控系统的安全性和可靠性。

2. 3　主处理机错误　

针对主处理机错误问题，可以利用飞控系统传感器多连接方式解决，将传感器的数据直接交给每个通道，避免主处理机的作恶行为。如图8所示为多连接方式的示意图。

若从处理机发生拜占庭错误，不能对系统的一致性造成影响，最多会造成该处理机本身不能得到正确结果，不会影响到其他处理机。但是主处理机承担着向其他节点发出请求的责任，若主处理机发生拜占庭故障，可能会向不同的目的地发送矛盾的信息，导致整个系统的一致性遭到破坏，如图 9所示。

假设飞控系统中当前任期的主处理机被敌方控制，导致它出现拜占庭故障，主处理机将会向从处理机 1、2 发送错误信息，向从处理机 3、4 发送正确信息。这时收到错误信息的处理机将发送出错误数据并签名，收到正确信息的处理机执行正常操作得到正确结果并签名，它们都将自己的结果发送给主处理机。主处理机就可以签名自己的正确结果和错误结果，并利用收到的签名一起打包成正确和错误的两种执行指令，这两种执行指令都拥有超过n/2个正确签名的集合。将这两种结果分别发送到不同的从处理机，最终就会导致处理机出现分叉，破坏系统的一致性。

如图 10 所示，采用传感器多连接方式后，每个通道都从总线中单独获取感知信息，不再使用主处理机发送的传感器数据，避免自己出现错误行为，并且飞控系统本身的架构更适合采用总线的连接方式，更贴合实际应用环境。

Raft 算法利用飞控系统本身的结构来实现拜占庭容错，在飞控系统的应用场景下相较于当前区块链系统中的拜占庭容错共识算法，如实用拜占庭容错（Practical Byzantine Fault Tolerance， PBFT）算法、Tendermint 算法等，在通信开销、系统性能等方面具有更多的优势，因此也更适合于机载环境下的应用。

2. 4　方案分析

本文利用Raft一致性算法和飞控系统应用场景的特点实现飞控系统的拜占庭弹性，对提高飞控系统的安全性和可靠性具有深刻意义。

然而，相较于 PBFT 算法、工作量证明（Proof of Work，PoW）算法等其他算法，即使Raft算法具有很低的通信和计算开销，但考虑机载计算机应用环境，如对体积重量功耗等方面的限制，应当追求用最小的通信开销和计算开销实现拜占庭容错，如图11所示为Raft算法的计算开销和通信开销的分析结果。由此可以看出，要想实现高余度飞控计算机的拜占庭弹性，它对计算量和通信量的需求也呈线性上升，这限制了该方案在小型机载环境的使用，更适合在大中型的机载环境下应用，尤其是针对计算和通信开销约束较少的大型机载环境。

为尽可能减少计算量和通信量导致应用场景受限制的情况发生，研究利用 BLS 签名算法降低通信量和计算量的优化方案。

Raft算法主要的通信开销为在主处理机和从处理机之间发送投票信息的过程产生的通信量，主处理机在收集到足够的签名后将会打包所有签名，并把它发送到集群中所有节点，这部分签名信息会占用较大的带宽。想要降低通信开销主要的办法是减少通信次数和减小消息长度，由于投票和收集过程不可避免，因此可以采用压缩的方式将打包的签名集合的消息长度减小。如图12所示为签名打包方案的示意图。

Raft算法的主要计算开销是每个处理机的签名和验签操作，尤其是验签过程为系统带来了巨大的计算开销，每个处理器在接收到主处理机打包的签名集合后，都会一一验证所有签名是否正确。

经过分析可以发现，Raft 一致性算法通信和计算开销的主要症结在于主处理机打包的签名集合，若有办法能够压缩该签名集合为一个固定长度的签名，那么主处理机发送的消息长度大幅减小，从处理机验证签名的次数也降低为一次，对降低Raft算法的通信量和计算量影响显著。

当前Raft算法中主要采用普通签名方案实现签名和验签操作，即传统系统中普遍使用的公钥基础设施（Public KeyInfrastructure， PKI）技术，如 RSA（Rivest-Shamir-Adleman）数字签名体制、ELGamal 型数字签名体制以及椭圆曲线数字签名算法（ECDSA）等，这些签名算法都无法实现将多个签名聚合为一个签名的目的。因此，本文采用 BLS 签名算法构建门限签名方案实现签名聚合的目的，达到降低通信量和计算量的目的。

BLS门限签名的过程分为以下4个阶段：

1）预备阶段：设 G1，G2 是阶为 p 的乘法循环群，生成元分

别是 g1 和 g2，e 表示双线性映射：G1 × G2 → GT，安全 hash 函数：h：{ 0，1}* → G1，公开参数(G1，G2，GT，e，g1，g2，p，h)。

2）密钥生成：系统主私钥为 MSK = x，其中 x 为系统选择的随机数，系统主公钥为MPK = v = gx2 ∈ G2，随机选择一个Zp上的t - 1阶多项式P，满足P(0) = x，计算xi = P(i)，得到签名者 ui 的私钥 xi；公钥 vi = gxi2，公开主公钥MPK及所有节点公钥。

3）签名阶段：节点ui对消息M的签名：sigi = h(M )xi，广播sigi，节点 uj 在收到 ui 的签名后，首先验证签名的正确性：e(sigi，g2 ) = e(h(M )，vi )，等到收集到门限 t个不同节点的正确签名后，可以聚合得到完整的签名：

使用 BLS 算法对主处理机接收到的超过 n/2 个签名进行聚合，得到一个整体签名结果，主处理机只需要传送一个签名，从处理机也只需要验证一个签名，这大幅降低了Raft算法的计算成本和通信成本。图13为聚合签名方案示意图。

本文研究 Raft 算法在飞控系统中的应用，并根据机载环境的实际情况和约束限制对应用方案进行优化。通过实验模拟三余度飞行控制计算机系统，比较分析 Raft应用方案和优化 Raft应用方案在计算开销和通信开销上的差别，并测试其吞吐量、请求平均时延和拜占庭弹性等指标。

本实验使用 Docker容器技术模拟分布式集群，具体实验环境如表1所示。

4. 1　通信开销与计算开销

经过前面的分析，优化应用方案主要通过降低通信消息长度的方式降低通信开销，因此本文采用的通信开销计算方式为：从传感器将数据传输到分布式集群，到执行机构接收到控制指令过程中的通信次数，并将 n 个签名打包的集合视为传输了n次。同理，Raft方案主要的计算开销是处理机签名和验签操作带来的开销，因此本文采用的计算开销的计算方式为：从传感器将数据传输到分布式集群，到输出控制指令过程中的签名和验签次数。通信开销与计算开销对比如图 14 所示。经过对比可以发现，优化后的算法对通信和计算的要求降低了，这不但适用于本文提出的机载环境下的飞控系统，同样适用于在其他应用场景中降低Raft算法的通信开销和计算开销。

4. 3　普通签名与门限签名

对比不采用门限签名的普通签名和门限签名在飞控计算机签名和验签阶段的消息长度和时间开销，本文所用到的普通签名方案使用了 GitHub 上应用 Golang 编写的 crypto/ecdsa包中的 P256 椭圆曲线，基于 BLS 的门限签名方案使用的是DEDIS 高 级 加 密 库 提 供 的 kyber 包 中 的 BN256 曲 线 。如图 16（a）、（b）所示分别为 Raft算法中主处理机将自己收集到的投票传送给其他处理机的签名大小和验签次数的对比。从图 16 中可以看出，普通签名方案将所有签名进行打包，所以签名大小随着节点数量的增加而线性增长，而门限签名方案会将更多的签名压缩为一个聚合签名，所以花费一定的聚合时间将签名集合压缩为一个门限签名，减小了消息长度、减少了验签次数。

4. 4　拜占庭弹性与稳定性

在传统的飞控系统中，使用的都是基于失效模型与影响分析（Failure Mode and Effect Analysis， FMEA）的方法，即分析系统失效的可能性和预测其失效产生的影响，并针对每一种

失效模式开发出适当的容错技术，整个过程不但费时费力费成本还存在故障覆盖不全面的问题，而拜占庭弹性能够在不考虑任意事先假设的情况下实现系统的安全性。因此，拜占庭弹性也是体现飞控系统安全性和可靠性的一个重要特性。

拜占庭弹性的测试方式为模拟飞控系统集群中存在拜占庭故障，控制故障节点随意行动，如不发送消息、发送错误消息、发送不同消息、联合其他故障处理机破坏系统等。经过多次测试后，验证飞控系统最大能容忍多少个故障节点，测试结果如图17所示。

本文应用Raft一致性算法使飞行控制系统中发生宕机故障或拜占庭错误时，分布式余度集群仍然保持一致地向执行机构发出正确指令，完成正确操作；并根据飞控系统对机载计算机应用环境的限制，设计了基于门限签名的优化方案，降低Raft 应用方案的计算开销和通信开销。经过实验模拟，测试Raft 应用方案的吞吐量和平均延迟等指标，并模拟验证飞控系统的拜占庭弹性和稳定性。

（文章来源于《计算机应用》，作者单位：中国电子科技集团公司 第十研究所航空电子系统重点技术实验室，作者：左力）

 本篇文章来源于微信公众号:                 航电科技圈