Raft论文研读 Ⅰ

地址：知网

引用：[1]李佳臻. 基于改进Raft算法区块链共识机制研究与验证[D].西安工业大学,2023.

期刊：西安工业大学（硕士论文）

作者：李佳臻

日期：2023年

{/collapse-item}
{collapse-item label=" 1.2 文章主要创新点 "}

通过阅读本文，该作者提出了改进Raft算法的两个创新点。

①引入预备候选者的Raft共识优化

解决的问题：在传统Raft共识算法中，由于网络问题，某个节点有时会被“隔离”在整个集群之外。这种隔离情况可能会对集群的正常运行状态造成破坏，导致新一轮的领导者选举的发生。

①若Follower因网络问题而失联，由于其没有收到任何来自Leader的RPC消息，它会反复超时，就会不断的自己开始发起新的领导者选举，但是由于它只能得到自己的一票，无法获得大多数的票数，所以会导致选举一直失败，即便选举失败但还是依然在不断的选举，进而导致选举任期值不断随之增加，直到和失联的集群重新恢复连接。

②在“被隔离”的过程中，它的term值一直在增加，因此它的Term值一般来说会比集群中其他节点的Term值都要大。在该节点重新恢复连接后大概率会成为Leader，它会强制其他节点更新其任期，其他的节点则会成为该节点在该任期下的Follower。

③当Candidate在与集群失联以后，由于得不到大多数节点的投票，所以角色状态就会自动降为Follower，其情况与上述的Follower的失联是完全相同的。

解决方案：设计一个预备候选者角色。

区别于原算法直接转换为候选者节点前任期自增的动作，转换为预备候选者角色前不会改变节点的Term值。随后进入资格审查阶段，预备候选者向集群中的其他节点发送资格审查消息，用来检测节点自身是否因网络隔离而成为过时节点，避免其扰乱集群的正常运行状态。

②基于跟随者子群划分的Raft共识优化

解决的问题：在Raft算法中，必须由领导者节点先处理来自客户端的写入请求，然后再转发给其他跟随者节点，不仅如此，领导者节点还承担了日志复制和发送心跳消息的工作，这样就会造成领导者节点负载过高。且在系统内部不能充分利用现有集群中其他节点的空闲资源，某种意义上来说，造成了资源的严重失衡。

解决方案：分组、领导者分发所有组长、组长再分发

①在Raft算法完成领导者选举之后，使用K-Means聚类算法将系统中的所有跟随者节点按照节点间距离划分成若干个子群。

②每个子群的内部也划分为“主-从”节点的模式来进行局部共识，子群内节点采用基于节点行为和波达计数法的选主策略，旨在选出符合性能优越的节点来担任子群内主节点（Master Node）。

③将原来Leader --> Follower的两级共识模式转变为Leader --> Master --> Follower的三级共识模式，从而实现分担领导者节点的负载，提升系统的共识效率。

{/collapse-item}

{collapse-item label=" 1.3 启发和总结 "}

{/collapse-item}

地址：知网

引用：[1]吴奕,仲盛.区块链共识算法Raft研究[J].信息网络安全,2021,21(06):36-44.

期刊：信息网络安全（北大核心）

作者：吴奕，仲盛

基金项目：国家重点研发计划

日期：2021年

{/collapse-item}
{collapse-item label=" 2.2 文章主要创新点 "}

①创新点一：Raft算法的选主改进

解决的问题：随着系统节点数的增加，各节点随机固定的超时时间的重复几率也会增加，加上众多节点间的网络延时，必然会导致整个系统的分区化，即同时在各分区产生一个伪Leader（得到部分投票但不满足当选Leader所必须投票数量）分票，从而导致这一轮选主失败，进入下一轮重新选举。

解决方案：为每个节点增加1 bit的标志数据位（简称“C标志位”，0表示不可以从Follower切换到Candidate，1表示可以从Follower切换到Candidate，初始值为1），表征该节点因没有收到Leader发送的心跳包而超时后是否具有从Follower切换到Candidate的资格。

运行过程：

①系统第一次启动，此时没有Leader，所有节点都为Follower且C标志位为1，即可以从Follower切换到Candidate。此时可以使用Raft算法选出Leader。

②选出Leader后，通过测试每个节点的通信延时，可将所有节点分为2个子集（O子集，回复较快的节点子集；Z子集，回复较慢的节点子集）。通过Leader发送的心跳包逐一设置其他节点的C标志位，O子集节点C标志位为1，Z子集节点C标志位为0。通过Leader任期内每次心跳包和对应的应答时间戳决定Follower节点的归属子集，然后利用下次心跳包设置其他节点的C标志位，Leader的C标志位不变。

③当新的节点加入系统时，节点的C标志位为1。只要Leader存在，就可以通过心跳包及时设置C标志位，从而避免因发生身份切换而发起选举。

②创新点二：潜在恶意节点防御改进

解决的问题：Raft算法中的Leader是强领导者，只要Leader收到多数的应答回复便会提交日志，而Follower节点必须执行指令。如果Leader节点是恶意节点或被劫持，Follower节点仅仅被动执行会产生安全问题。本文通过添加区块验证标志位Q改善这种情况。

解决方案：为每个节点设置一个1 bit的区块验证标志位Q，记录区块验证结果。Q为0表示验证通过，Q为1表示验证失败，初始值为0。

①当系统第一次启动，此时没有Leader，所有节点都为Follower且Q标志位为0，即没有验证错误。

②选出Leader后，通过发送的心跳包，在Leader中附加待提交的新区块的验证并签名。Follower节点也可以计算新区块并验证Leader签名，从而确定Leader的验证是否正确，如果正确，Q标志位置0，同时将正常的心跳回复发送给Leader；否则，Q标志位置1，不回复心跳包，等待Leader重发心跳包；如果仍然验证错误，则放弃现任Leader，不重置选主定时器，等待重新选主。

{/collapse-item}
{collapse-item label=" 2.3 启发 "}

{/collapse-item}

地址：知网

引用：[1]王谨东,李强.基于Raft算法改进的实用拜占庭容错共识算法[J].计算机应用,2023,43(01):122-129.

期刊：计算机应用（北大核心）

作者：王谨东，李强

基金项目：国家重点研发计划

日期：2023年

{/collapse-item}
{collapse-item label=" 3.2 文章主要创新点 "}

①Raft与PBFT结合

解决的问题：解决PBFT通信开销问题

解决方案：先分片、全局共识改为多中心共识、分片的小组组长采用PBFT、内部采用Raft。

①以节点之间的通信时延作为欧氏距离(衡量欧几里得空间中两个点之间的直线距离)，利用K-medoids聚类算法将区块链分片；

②每个分片的主节点之间使用PBFT算法进行共识，在分片内部使用基于监督节点改进的Raft算法进行共识。

{/collapse-item}
{collapse-item label=" 3.3 启发 "}

{/collapse-item}

地址：知网

引用：[1]荣宝俊,郑朝晖.FL＿Raft:基于联邦学习模型的选举共识方案[J/OL].计算机科学:1-16[2023-09-03].

期刊：计算机科学 Computer Science（北大核心）

作者：荣宝俊，郑朝晖

基金项目：国家重点研发计划

日期：2021年

{/collapse-item}
{collapse-item label=" 4.2 文章主要创新点 "}

①机器学习算法与Raft进行结合

解决的问题：一是投票分裂问题，多个候选者平分投票，迟迟无法选出领导者，导致一段时间内的集群不可用。二是选举出的领导者具有随机性，无法保证其性能是最优的，若其性能较差，则会产生频繁下线或网络分裂的问题，影响集群的稳定性。

解决方案：加入联邦学习模型和权益选举过程，添加准领导节点角色。

联邦学习：通过收集集群中每个节点的特征数据（属性值：任期(Term)、最新的日志索引(Log_Index)、运行时长(Run_Time)、投票时延(Voting_Delay)、状态类型(State)），训练出可预测领导者功能的模型。

• 1.集群稳定运行情况下，若领导者在线则跳转步骤2，否则跳转步骤4。
• 2.若是第一次联邦学习过程，则服务端首先广播初始模型，否则跳转步骤3。
• 3.执行正常的联邦学习过程，客户端使用本地数据集进行模型训练，并将更新参数发送给服务端，在收集到充分的更新参数后服务端j进行聚合过程，并将新的全局模型广播给集群中所有客户端，客户端更新本地模型。
• 4.当领导者不在线时，若集群中不存在准领导者，则跳转步骤5，否则准领导者成为领导者，跳转步骤6。

• 5.该步骤分为两点：候选者和准领导者的选举。

  1)候选者。跟随者等待选举超时，将状态设为候选者，为自己投一票，并向集群中的其余节点发起投票请求，其余跟随者若任期和日志条目均小于等于候选者，则向该候选者投一票，在候选者收集到超过集群总节点数一半的票数时，成为领导者，否则在投票超时后重新发起投票，等待新一轮的选举。

  2)准领导者。跟随者i利用本地的模型和数据集进行模型选举过程，选举出的节点进入权益等待队列，然后中的节点进行权益选举过程，排名第一的节点成为准领导者，上述过程也可发生在领导者在线状态，以缩短领导者下线后的选举时间。按照pQ队列中的顺序发起新一轮投票，在收到超过集群一半数量的票数后成为领导者，否则替换准领导者重新发起选举，若都已选举完仍无法选出领导者，则等待新一轮选举。

• 6.领导者上线，启动心跳，接收日志并进行共识过程，同时各节点收集训练所需数据集。

{/collapse-item}
{collapse-item label=" 4.3 启发 "}

{/collapse-item}

地址：知网

引用：[1]李淑芝,邹懿杰,邓小鸿等.RB-Raft:一种抗拜占庭节点的Raft共识算法[J].计算机应用研究,2022,39(09):2591-2596.

期刊：计算机应用研究（北大核心）

作者：李淑芝，邹懿杰，邓小鸿

基金项目：国家自然科学基金资助项目

日期：2022年

{/collapse-item}
{collapse-item label=" 5.2 文章主要创新点 "}

①基于哈希链的动态日志验证机制

解决的问题：防止领导者是恶意节点。在Raft算法中，领导者具有最高的权力，当领导者是恶意节点时就可能发生日志错误问题。所以确保日志内容不被伪造、不被窜改对于抵抗拜占庭节点算法来说至关重要。

解决方案：

①哈希链通过哈希函数对密码进行多次迭代加密，具有良好的抗干扰性，且服务器端只需保存最后一次加密的密文即可验证全部密文序列。

②当需要对日志进行校验时，Follower节点将自身所存储的日志做哈希链计算得出最后一块日志块的Proof，Proof代表了本节点所有的日志块，然后将最后一块日志块序号作为请求参数发送给客户端，客户端返回相应的Proof，节点与其进行对比，假如对比失败，两者完全不相同，说明自身日志与客户端发送过的日志存在不一致。

③当日志对比失败后首先需要对日志进行回滚，回滚到上一层Proof再次进行对比，不一致的话就继续回滚，直到Proof一致则不再进行回滚，错误Proof的日志块将会被删除，并且向客户端获取同步错误的日志块。

②遗书机制

解决的问题：在Raft算法中，当Leader节点宕机后，Follower节点会根据任期大小来选择是否投出选票。这个任期的大小是通过接收Leader节点的心跳信号来确定的。然而，这种机制容易受到拜占庭节点的利用。拜占庭节点通过调节自己的任期大小从而影响选举。

解决方案：设计遗书机制，在节点成为Leader时产生一份遗书（立下遗嘱），其他节点获取到遗书内容才有资格向follower节点拉取选票（分配财产），而遗书内容只能当Leader节点宕机后才可以打开。

{/collapse-item}

欧氏距离是在数学和统计学中常用的一种度量距离的方法。它用于衡量欧几里得空间中两个点之间的直线距离。

对于二维平面上的两个点 (x1, y1) 和 (x2, y2)，欧氏距离可以通过以下公式计算：

d = √((x2 - x1)^2 + (y2 - y1)^2)

其中，√表示开方运算。这个公式实际上是由勾股定理推导出来的。

在更高维度的欧几里得空间中，欧氏距离的计算方式类似。对于n维空间中的两个点 (x₁, x₂, ..., xₙ) 和 (y₁, y₂, ..., yₙ)，欧氏距离可以计算为：

d = √((x₁ - y₁)² + (x₂ - y₂)² + ... + (xₙ - yₙ)²)

欧氏距离常被用于数据挖掘、机器学习和模式识别等领域。它可以帮助我们比较和衡量不同数据样本之间的相似性或差异性。通过计算欧氏距离，我们可以找到最近邻数据点，进行聚类分析，或者构建分类和回归模型等。

需要注意的是，欧氏距离在应用时要注意数据的特征缩放问题。如果数据在不同维度上具有不同的尺度或重要性，可能需要对数据进行预处理以消除这些影响，例如标准化或归一化。

{/collapse-item}
{collapse-item label=" 6.2 K-medoids聚类算法 "}

K-medoids是一种常见的聚类算法，用于将数据集中的样本划分为具有相似特征的多个聚类。

在K-medoids算法中，每个聚类由一个代表点（medoid）来表示。与K-means算法不同，K-medoids选择的代表点必须是实际数据点中的观测值，而不仅仅是均值或其他统计量。

以下是K-medoids算法的基本步骤：

1. 初始化：选择k个初始的medoids作为每个聚类的代表点。
2. 分配阶段：对于每个数据点，计算其与各个medoid之间的距离，并将其分配到距离最近的medoid所代表的聚类。
3. 更新阶段：对于每个聚类，计算当前所有数据点到该聚类内其他点的总距离，然后选择替换当前medoid并计算新的总距离，以使得总距离最小化。如果新的medoid可以改进总距离，则进行更新。
4. 重复步骤2和3，直到达到收敛条件，例如当没有更改聚类分配或达到最大迭代次数时。

K-medoids算法的优点包括能够处理非欧几里得距离度量、对离群点比较鲁棒，以及不受初始聚类中心的选择影响。然而，与K-means相比，K-medoids需要进行更多的计算来更新medoid，并且在大型数据集上可能会变得较慢。

K-medoids算法的一个常见应用是图像分析，例如图像分割和特征提取。它还可以用于社交网络分析、基因组学、客户细分等领域，以发现数据中的隐藏模式和结构。

{/collapse-item}

{collapse-item label=" 6.3 联邦学习 "}

联邦学习（Federated Learning）是一种分布式机器学习方法，旨在让多个参与方共同训练一个模型，而无需将原始数据集集中存储在单个地方。它允许参与方在保护隐私的前提下分享和整合各自的本地数据，从而实现模型的全局训练。

以下是联邦学习的基本工作流程和关键概念：

1. 分布式参与方：联邦学习涉及多个参与方（例如设备、终端或云服务器），每个参与方都拥有本地的数据集。
2. 模型初始化和定义：在开始联邦学习之前，需要定义一个初始模型，并将其发送给所有参与方。通常使用某种标准机器学习模型，例如神经网络。
3. 本地迭代训练：每个参与方使用自己的本地数据对初始模型进行训练。这些本地训练过程可能是根据特定算法（例如随机梯度下降）进行的多个轮次的迭代。
4. 模型聚合：参与方将本地训练后的模型参数（或者梯度更新）发送给中央服务器（或者有选择性地与其他参与方共享）。中央服务器负责聚合所有参与方的模型参数，生成一个全局更新。
5. 全局模型更新：中央服务器使用聚合的模型参数更新来更新全局模型。这个过程可能包括进一步的迭代和优化。
6. 重复本地训练和模型聚合：上述步骤在多个轮次中重复进行，直到达到预设的停止条件，例如达到最大迭代次数或模型收敛。

联邦学习的优点之一是能够保护个体数据的隐私，因为原始数据不需要共享给其他参与方或中央服务器。相反，只有模型参数或梯度等聚合信息被交换，从而降低了数据泄露的风险。

联邦学习广泛应用于医疗保健、物联网、金融服务以及其他需要处理敏感数据的领域。它提供了一种能够同时享受分布式计算和隐私保护好处的解决方案，使得各方能够从其他参与方的数据中获益并做出更准确的预测或决策，而无需暴露私密信息。

{/collapse-item}

{collapse-item label=" 6.4 哈希链 "}

哈希链（Hash Chain）是一种基于哈希函数构建的密码学工具，用于实现数据完整性和防篡改的验证机制。它由一系列经过哈希函数处理的数据块组成，每个数据块都包含前一个数据块的哈希值。

以下是哈希链的基本原理：

1. 初始块：哈希链的第一个数据块称为初始块（Genesis Block），它是在系统初始化时创建的。
2. 数据块生成：每个后续的数据块都通过将前一个数据块的哈希值作为输入，再次应用哈希函数来生成。这样，每个数据块都依赖于前一个数据块的哈希值，并且形成了一个连续的链式结构。
3. 验证数据完整性：要验证哈希链中的数据是否完整和未被篡改，只需按顺序计算每个数据块的哈希值，并确保与链中保存的哈希值匹配。如果任何一个数据块被修改，其哈希值将会发生变化，从而破坏了整个链的完整性。
4. 保护数据安全性：哈希链的安全性来自于哈希函数的特性，即输出的哈希值非常难以逆向计算和修改。即使对输入进行微小的更改，也将导致输出完全不同的哈希值。因此，如果有人试图更改链中的任何数据块，其后续数据块的哈希值将无法与之匹配，从而暴露篡改行为。

哈希链在密码学和区块链等领域得到广泛应用。它可以用于确保数据的完整性、防止篡改和验证身份。哈希链的特性使其成为实现数字签名、密码验证、数据校验和区块链技术中区块连接的关键组成部分。

{/collapse-item}