目录

声明

论文精度系列文章，是笔者个人对论文内容的私有解读，可能会在部分引用的基础上进行大量的个人理解与阐述，很可能会歪解论文原本的含义，因此推荐读者阅读论文原文，下方会提供地址链接。

前言

• 时间：2021 年
• 期刊：计算机研究与发展
• 论文：https://crad.ict.ac.cn/CN/10.7544/issn1000-1239.2021.20190723

《基于在网计算加速的拜占庭容错算法》（Accelerating Byzantine Fault Tolerance with In-Network Computing）

摘要

拜占庭容错算法是一类能够容忍各种形式的软件错误和安全漏洞的容错算法，对云计算的可靠性保障有着重要意义。与其他容错算法相比，拜占庭容错算法稳定性更高，但是其性能表现低下，不能满足当前系统对高吞吐、低延时的需求。

在网计算是一种以数据为中心的体系结构，它用网络承担部分计算功能，使数据在流动过程中获得处理，从而提高系统性能。

为解决拜占庭容错系统的问题，提出了一种基于在网计算的拜占庭容忍共识算法优化方案，将算法的一部分处理任务卸载到网卡上执行，利用网卡和处理器形成的多级流水线提升系统吞吐量。由于仅使用在网计算的方案在特定场景下效果不佳，因此，使用多线程方法来提升优化方案的可扩展性。

同时，对算法进行了详细的系统评测，实验结果表明：相对于普通的拜占庭容错系统，使用在网计算与多线程结合的优化方案能够获得 46% 的吞吐率提升以及 65% 的延迟下降，证明了基于在网计算的拜占庭容忍共识算法优化方案的可行性与有效性。

开篇

随着计算机网络和分布式应用的不断发展，网络中充斥着越来越多的恶意攻击，应用的复杂度越来越高，稳定性受到严重威胁。为了给分布式应用提供可靠性保障，人们提出了拜占庭容错技术，该技术能够容忍包括人为失误、软件故障和安全漏洞等各种形式的错误和攻击[1]，因此被广泛应用于区块链、数据库等对系统稳定性、安全性有着高要求的分布式系统中。

实用拜占庭容错算法（practical Byzantine fault tolerance，PBFT）[2]是最具代表性的拜占庭容错技术之一。该技术以多副本形式保证对错误的容忍，使用 3 阶段的共识过程来保证各副本能够以相同顺序执行相同的客户端请求，系统在受到部分节点的恶意干扰时也不会出错。与工作量证明（proof-of-work，PoW）[3]、权益证明（proof-of-stake，PoS）[4]等其他拜占庭容错算法相比，该算法具有高吞吐、低延迟的
优点；

而与非拜占庭容错算法（non-Byzantine fault tolerant，NBFT）相比，其稳定性较高，但是性能却较为低下。因此，在实际使用中，人们在选择使用不同的算法时往往需要在稳定性和高性能之间做出取舍。

表 1 给出了各种共识算法的优劣对比。

为了兼顾系统的稳定性和高性能，人们提出了各项针对实用拜占庭容错算法的优化技术。我们将其分为 3 个方面：

1. 优化算法设计：尽可能简化算法的一致性协议，使得算法在没有恶意节点干扰的情况下提供高性能服务。
2. 降低算法开销：算法执行过程中包含大量的密码学相关的计算，降低这些计算的开销有助于提升整体性能。
3. 提高算法并行度：充分利用多核处理器的优势，使用多线程技术提升执行效率。

现有研究工作主要着力于上述 3 种方案的某一方面，而缺少三者的协同优化设计。本文尝试从在网计算的角度提出一种新的实用拜占庭容错算法的优化方案，同时兼顾降低算法开销和提升算法并行度。

该方案主要使用在网计算的方式将 PBFT 算法中共识过程中的部分计算任务卸载到网卡上去完成。

1. 一方面网卡强大的流式处理能力有助于降低延迟开销；
2. 另一方面网卡和处理器组成的多级处理流水线能够提高算法的吞吐量。

同时，我们使用多线程方法进一步提高算法并行度，扩展了优化方案的适用场景。实验表明基于在网计算的拜占庭容错算法最多能够获得 46% 的吞吐量提升以及 65% 的延迟下降。

正文

背景介绍

实用拜占庭容错算法

实用拜占庭容错算法广泛应用于大规模分布式系统中，为系统安全性和稳定性提供保障。该算法能够容忍不超过节点总数 1/3 的恶意节点；换言之，当系统节点总数为 n，恶意节点数为 f 时，只要满足 n ≥ 3f+1，系统就能够对外界表现出正常的工作状态。在后续论述中我们将沿用这些参数定义。

使用该算法的系统中包含 2 类节点：

1. 主节点：负责为客户端请求选择序号，并向各备份节点广播请求。
2. 备份节点：各节点按序执行客户端请求。

节点通过运行 3 种基本协议进行协同工作，包括：

1. 一致性协议（Agreement）：负责节点间的共识。
2. 检查点协议（Checkpoint）：负责生成节点的稳定状态。
3. 视图更换协议（Viewchange）：负责主节点的切换。

其中，一致性协议是算法的主体执行部分，占据了绝大部分的时间开销，因此我们将重点介绍一致性协议，而对后两者略去不表。

一致性协议运行在主节点为非恶意节点的情况下，该协议通过 Pre-Prepare、Prepare、Commit 这 3 阶段完成备份节点之间的共识，使得每个节点能够按相同顺序收到相同的请求，并执行相同的操作，从而保证副本之间的一致性。

在一致性协议中，客户端与节点之间通过 Request 和 Reply 操作完成交互：客户端向主节点提交 Request，并收集节点返回的 Reply。当客户端收到 f+1 条相同的 Reply 后，便表示 Request 已经在系统中成功提交并执行。整个算法流程分 5 个阶段执行：

1. 客户端向主节点发送 Request；
2. 主节点在收到了客户端的 Request 后进入 Pre-Prepare 阶段，将 Request 广播给主节点及其他备份节点；
3. 备份节点收到 Request 后，进入 Prepare 阶段，将 Request 广播给主节点及其他备份节点。
4. 主节点及备份节点收到广播消息后，首先进行消息验证以保证消息的完整性与不可否认性，然后保存消息以作为节点当前状态的凭证，最后将其与 Pre-Prepare 阶段的 Request 进行匹配，以判断本节点与其他节点是否可以就请求序号和请求内容达成一致，当节点收到 2f 条匹配的消息后，进入 Commit 阶段，将 Request 广播给其他节点；
5. 所有节点重复 Prepare 阶段的消息接收与验证，并在收到 2f 条匹配的消息后按照序号所规定的顺序依次执行各请求，在请求执行完成后向客户端返回 Reply。

图 1 给出了一致性协议的详细执行过程，其中节点 1 是主节点，其余节点是备份节点。分析可知，在一致性协议的执行过程中，一条客户端请求的成功执行至少需要进行 6f**2 + 6f 次节点间的通信，且每次通信过程都包含消息验证、消息保存等操作，因此降低这些操作的开销对提升算法的性能有着重要意义。

在网计算

在网计算是一种以数据为中心的计算模式[5]，其核心思想是将一部分流式计算任务卸载到网络设备上执行，以达到提升计算效率、减少网络流量的目的。

当前，在网计算已经成为优化分布式应用的重要手段之一。例如 Dang 等人[6-7]提出的 NetPaxos 使用可编程交换机对非拜占庭容错算法 Paxos 进行优化，István 等人[8]提出了基于可编程网卡的原子广播优化。

通过分析我们发现，拜占庭容错算法与在网计算有着极佳的适配性。

1. 一方面，消息验证与消息保存操作都可以在网卡上以专用硬件结构实现，其处理效率高于通用处理器；
2. 另一方面，网卡和处理器构成了多级处理流水线，能够提升算法执行的并行度。

设计与分析

本节着重介绍系统的整体设计方案以及设计中的考量与取舍。如引言所述，对 PBFT 的优化主要有 3 个方面：

1. 减少算法执行开销
2. 提高并行度
3. 简化算法设计

系统整体设计

本文设计并实现了一种软硬件协同的实用拜占庭容错算法优化方案。

算法的一致性协议中，特别是 Prepare 和 Commit 阶段，节点对消息的处理可以分为 4 个阶段：

1. 消息验证
2. 消息保存
3. 消息计数
4. 请求执行（或生成新消息）

不同的执行阶段被分配到系统中不同的组件上执行，这样的设计方案带来了 2 个方面的显著优势：

1. 算法的密码学验证与消息保存被卸载到专用硬件网卡上执行，大大降低了处理时间开销；
2. 多个组件协同完成整个处理过程，形成了多级流水线，提升了系统的吞吐率。

图 2 和图 3 分别给出了软硬件流水线示意和系统的软硬件架构图。硬件部分的核心组件是消息保存模块及消息验证模块。其中，消息验证模块从以太网模块中获取网络数据，并使用密码学方法对消息进行安全验证，将通过验证的消息传递给消息保存模块；

消息保存模块使用散列表将以键值形式组织的消息存储到主存中供拜占庭容错算法使用。软件方面，基于实用拜占庭容错算法，本文借助多线程方法，由不同线程负责客户端请求的共识和已共识请求的执行。

网卡硬件加速的优势

与仅使用多线程进行优化的方式相比，使用专用硬件执行算法能够带来显著的性能提升，这种收益来自于 2 个方面：

1. 与通用处理器相比，专用硬件针对算法特征做了定制化设计，避免了处理器中繁琐的取指译码等流程，执行效率更高。例如：使用定制化的电路可以在几个时钟周期内完成密码学验证、散列等复杂的计算。
2. 多个线程主要通过共享内存的方式进行数据交互，频繁的通信过程会带来较大的内存读写开销。而硬件模块之间可以通过硬件队列和信号进行数据传递，时间开销较低。

为进一步说明这一点，本文分别使用 FPGA 和通用处理器进行 32B 数据的 SHA-256 运算，其中硬件电路的频率为 200MHz，处理器使用Intel Xeon CPU E3。图 4 给出了 2 种计算模式的延迟对比。可以看到，使用硬件加速方案相对于通用处理器减少了 95% 的延迟开销。

使用加速器能够在一定程度上减少计算开销，但目前的加速器[9-10]大部分采用的是主从模式，这种模式存在较大的数据拷贝开销。以图 5 为例，网络数据首先被搬移到主存，然后处理器通知加速卡获取待处理数据。当加速卡计算完成后，主处理器读回处理结果，整个过程包含了多次数据搬移．而可编程网卡天然位于网络数据路径上，当数据从网卡流经内存就已经完成了处理，不会带来额外的数据拷贝开销。因此，在网卡上对算法流程进行卸载是较好的选择。

表 2 给出了我们对网卡硬件加速与多线程和普通加速卡的优劣对比。

多线程的必要性

使用网卡硬件进行计算卸载需要满足一个先决条件，即：数据包的处理应当能够达到线速，否则有可能造成网络丢包。为满足这一限制条件，我们抽象了 2 个特征对不同的计算任务进行筛选：

1. 没有循环计算；
2. 没有数据依赖。
   具备这 2 种特征的计算任务被称为流式计算。

基于上述分析，我们提取了算法中各个执行阶段的计算特征，如表 3 所示：

通过分析我们发现，算法中的消息验证与消息保存的核心是散列计算，是一种典型的流式计算，因此，这 2 部分的计算被卸载到网卡上执行。而算法中的消息计数，客户端请求的执行涉及到内存访问及循环操作，更适合在通用处理器上以更灵活的多线程方式实现。

简化算法的一致性协议

简化算法的一致性协议是拜占庭容错算法的一种重要的优化手段，许多工作使用这种方式获得了显著的优化效果，如：Zyzzyva[11]，fastBFT[12]，SBFT[13]。

在简化算法一致性协议方面，通常是引入 1 个或多个收集节点，由该节点收集其他节点消息并广播统计情况，将多对多的消息传递转化为多对一和一对多消息传递，以降低系统的消息复杂度。

Zyzzyva，fastBFT，SBFT 等都不同程度上使用了这一手段，Zyzzyva 选择使用客户端作为收集节点，而 fastBFT 和 SBFT 则从备份节点中选拔收集节点。

使用收集节点虽然能够简化算法一致性协议，但也会带来一些负面影响。首先，它会让算法的其他部分变得复杂，如 Zyzzyva 虽然在理想情况下可以将一致性协议的消息复杂度由 O(n２) 降低至 O(n)，但付出的代价是需要一个更为复杂的视图更换协议，而且这种更为复杂的视图更换协议有可能存在被攻击的漏洞[14]。其次，使用收集节点会为算法引入更为复杂的密码学操作，如 fastBFT 和 SBFT 使用多签名的方式来保证收集节点所广播消息的可信度。

简化算法的一致性协议虽然能够降低系统消息复杂度，但也有其自身的局限性，因此我们并没有采用这种优化方式。

实现

定制化消息格式

为了将计算任务嵌入到网络数据流的处理过程中，我们需要对消息进行标识，网卡通过识别消息中的特殊标志位后进行相应的处理。因此，我们对消息格式进行了定制化设计。

如图 6 所示，消息被划分为 3 个部分：

1. 消息头（header）：主要提供消息的长度信息，以便网卡对消息负载进行界定和处理；
2. 消息键（key）：消息键承载了消息的特征信息，包括消息类型、源节点序号、请求序号、视图号，用于消息保存中的散列值计算。
3. 消息值（value）：消息值则包含了客户端请求摘要、消息验证码向量。其中，消息验证码向量可以保证消息在传播过程中的完整性与不可否认性，它由一组面向不同接收节点的消息验证码组成。

基于网卡的消息验证模块

消息验证模块被卸载到网卡硬件上执行，它提供了基于 SHA-256 安全散列算法的消息验证功能。

如图 7 所示，该模块通过消息预处理、验证码提取、安全散列值计算、验证码对比等操作完成消息的验证。其中消息预处理模块提取出消息的长度信息、源节点信息以及消息验证向量，将其传递给验证码提取模块使用，同时，将消息的负载传递给安全散列计算模块进行密码学运算；

• 安全散列计算模块：实现了 SHA256 安全散列算法，该算法根据消息和对应密钥计算目标验证码；
• 验证码提取模块：则从消息所携带的验证码向量中提取出与本节点对应的验证码。
• 验证码对比模块：将消息携带的验证码与安全散列计算得到的目标验证码对比，决定是否向后续模块传递该信息。

其中，安全散列计算的处理过程较为复杂，这里对其设计方案进行详细说明。

基于网卡的消息保存

如前所述，消息保存功能也被卸载到网卡上执行。

如图 10 所示，消息保存模块由散列计算、冲突管理、数据上传这 3 个子模块组成。节点收到的消息通过散列表的方式进行保存。我们在板载 DRAM 中保存散列表的元数据，在主存中保存实际数据。

1. 散列计算模块负责提取消息键并计算散列值，散列值决定了消息所占用的散列表项；
2. 冲突管理模块负责解决散列冲突问题；
3. 数据上传模块负责将消息封装为 PCIe 事务包并上传。

接下来阐述 3 个模块的详细设计。

文章来源: is-cloud.blog.csdn.net，作者：范桂飓，版权归原作者所有，如需转载，请联系作者。

原文链接：is-cloud.blog.csdn.net/article/details/125783825