Raft毕业设计——基于Raft+区块链的共识算法Raft设计与实现（毕业论文+程序源码）——共识算法Raft

基于Raft+区块链的共识算法Raft设计与实现（毕业论文+程序源码）

大家好，今天给大家介绍基于Raft+区块链的共识算法Raft设计与实现，文章末尾附有本毕业设计的论文和源码下载地址哦。需要下载开题报告PPT模板及论文答辩PPT模板等的小伙伴，可以进入我的博客主页查看左侧最下面栏目中的自助下载方法哦

文章目录：

• 基于Raft+区块链的共识算法Raft设计与实现（毕业论文+程序源码）
• • 1、项目简介
  • 2、资源详情
  • 3、关键词
  • 4、毕设简介
  • 5、资源下载

1、项目简介

1. 区块链，作为目前火热的比特币的底层支撑技术，融合了分布式数据存储，P2P传输，共识算法，加密等各种计算机技术。这其中最为重要的就是共识算法，对于共有链等开放的网络环境往往使用PoW，而对于私有链等相对封闭的网络环境，由于所有节点都是可信任的，往往使用Raft或者Paxos。本文就主要围绕区块链共识算法这一点来对比常用算法的异同以及使用场景，并就Raft给出具体实现以便于理解区块链在分布式环境下如何达成共识。其中实现了Raft的两个核心模块：领导选举和日志复制。

2、资源详情

项目难度：中等难度
适用场景：相关题目的毕业设计
配套论文字数：12940个字30页
包含内容：全套源码+配整论文
开题报告、论文答辩、课题报告等ppt模板推荐下载方式：

3、关键词

Raft，区块链，共识算法，领导选举，日志复制

4、毕设简介

提示：以下为毕业论文的简略介绍，项目完整源码及完整毕业论文下载地址见文末。

1 绪论
1.1 区块链简介
区块链技术起源于2008年“中本聪”的一篇论文《比特币: 一种点对点电子现金系统》，目前还未形成行业公认的严格的区块链定义。但是从狭义上来看，它就是一种按照时间顺序将数据区块以顺序相连的方式组合成的一种链式数据结构，有点类似于计算机科学里面的链表这样的数据结构，只不过链表的每个节点（这里被称作区块）的结构更加复杂，每个节点的连接方式也与链表不同。而从广义上来看，区块链实际是利用块链式数据结构来验证与存储数据、利用分布式节点共识算法来生成和更新数据、利用密码学的方式保证数据传输和访问的安全、利用由自动化脚本代码组成的智能合约来编程和操作数据的一种全新的分布式基础架构与计算方式。

通俗一点理解的话，区块链就是一个去中心化的分布式数据库，为什么说它是数据库呢？因为它的主要作用就是存储信息，任何需要保存的信息，都可以写入区块链，也可以从里面读取，可读可写因此区块链是个数据库。为什么说它是去中心化的呢？因为任何人都可以架设服务器，加入区块链网络，成为里面的一个节点，不同于现在的很多网络都有个管理者，区块链从设计之初就保证了没有任何管理者，也不能被任何人控制，在这个网络中没有任何中心节点，每个节点都是平等的，保存着整个数据库，你可以向任何一个节点读写数据，最后所有节点都会同步从而保持区块链网络最终一致。

区块链示意图，每个区块遍布在世界各地，依靠网络连接成链

区块链是由一个个区块组成的，它们连接成链，那么每个区块究竟是什么样的呢？它们又是如何连接成链的呢？
在区块链网络中，数据会以文件的形式被永久记录，我们称这些文件为区块。一个区块是一些或所有最新比特币交易的记录集，且未被其他先前的区块记录。它的具体结构如下图所示：

每个区块都包括了一个被称为魔法数的常数、区块的大小、区块头、区块所包含的交易数量及部分或所有的近期新交易。在每个区块中，对整个区块链起决定作用的是区块头。区块头的结构如下图所示：

概括来说，每个区块主要包含两部分，一个是区块头，也就是上面这张图，它记录着当前区块的元信息，另一个是区块体，记录着实际数据。每个区块头里面都包含着前一区块的Hash，这样子每次新来一个区块，这个新区块就通过这个Hash指向前一个区块从来达到相连接成链的效果。

前面说过，区块头包含很多内容，其中有当前区块体的哈希，还有上一个区块的哈希。这意味着，如果当前区块体的内容变了，或者上一个区块的哈希变了，一定会引起当前区块的哈希改变。这一点对区块链有重大意义。如果有人修改了一个区块，该区块的哈希就变了。为了让后面的区块还能连到它（因为下一个区块包含上一个区块的哈希），该人必须依次修改后面所有的区块，否则被改掉的区块就脱离区块链了。由于区块链中设计的计算很耗时，短时间内修改多个区块几乎不可能发生，除非有人掌握了全网51%以上的计算能力。因此，区块链保证了自己的可靠性，数据一旦写入，就无法被篡改。

正是因为上面介绍的种种技术特点，区块链才能支撑起以比特币为代表的数字加密货币体系。对于区块链来说，它的核心优势是去中心化, 能够通过运用数据加密、共识算法、分布式数据存储和经济激励等手段, 在分布式系统中实现基于去中心化信用的点对点交易，从而为中心化机构普遍存在的高成本、低效率和数据存储不安全等问题提供了解决方案。随着比特币近年来的快速发展与普及, 区块链技术的研究与应用也呈现爆发性增长趋势，被认为是下一代云计算的雏形, 有望像互联网一样彻底重塑人类社会活动形态, 并实现从目前的信息互联网向价值互联网的转变。

1.2 论文内容安排
对于区块链来说，它的基础架构模型如下图所示：

一般来说，区块链系统由数据层、网络层、共识层、激励层、合约层和应用层组成。其中, 数据层封装了底层数据块和相关的数据加密等技术; 网络层则包括分布式组网机制、数据传播和验证机制等; 共识层主要封装节点的各类共识算法; 激励层将经济因素集成到区块链技术体系中来, 主要包括经济激励的发行机制和分配机制等; 合约层主要封装各类脚本、 算法和智能合约, 是区块链可编程特性的基础; 应用层则封装了区块链的各种应用场景和案例。
本文是基于区块链的共识算法Raft的实现，主要关注的就是区块链中最为重要的共识层，至于其他合约层，应用层等不会涉及到。论文的主要安排如下：
第一章介绍区块链的整体情况，主要涉及了区块链的相关技术和发展情况。
第二章会重点关注区块链的共识层，主要包括了共有链，私有链等常用的共识算法，对比分析各类共识算法的异同以及适用场景。
第三章会详细介绍共识算法中的Raft，并给出Raft的具体的设计与实现，最后通过MIT的测试框架对Raft进行了整体的测试并衡量其性能。
第四章对项目与进行了总结，主要列出了在学习实现Raft遇到的一些问题以及如何解决的方案，总结了还有哪些需要改进的地方。

2共识算法
区块链首先是一个分布式系统，由传统的单节点结构（CS模型）演变到多机的分布式系统，最为重要的一个问题就是如何保证多机的数据一致性，从而保证系统达成共识。而这些往往是通过某些协议（或者是共识算法）来保证的。一般来说，共识算法可分为传统的分布式一致性算法以及区块链独创的共识算法，在某些特定的场景下比如私有区块链，使用传统的分布式一致性算法效率会更高，效果会更好。因此，从某种意义上来说，传统分布式一致性算法也是共识算法的子集，本章主要会讨论以Raft，PBFT为代表的传统分布式一致性共识算法和Pow，PoS等区块链独有共识算法的异同，以及他们分别适用于区块链的什么场景。
2.1 传统分布式一致性共识算法和区块链独有共识算法异同
相同点：
Append Only，数据一旦写入不可修改，只追加写日志或者添加新区块
少数服从多数原则，一旦大多数节点达成共识便可以判定系统达成共识，对于分离覆盖的问题，一般都是长链覆盖短链，多节点覆盖少数节点日志

不同点：
传统分布式一致性算法大多不考虑拜占庭容错(Byzanetine Paxos除外)，即假设所有节点只发生宕机、网络故障等非人为问题，并不考虑恶意节点篡改数据的问题，而区块链独有共识算法几乎都考虑了拜占庭容错
传统分布式一致性算法是面向日志（数据库）的，即更通用的情况，而区块链共识模型面向交易的，所以从某种程度上来说，传统分布式一致性共识算法有时候也可以算作区块链共识模型的下面一层。

2.2 适用场景
区块链分为三类，在货币发行的《区块链：定义未来金融与经济新格局》一书中就有详细介绍。主要共有链，私有链，行业链（联盟链）。其中：
共有链：
开放生态的网络，世界上任何个体或者团体都可以发送交易，且交易能够获得该区块链的有效确认，任何人都可以参与其共识过程。公有区块链是最早的区块链，也是应用最广泛的区块链，各大bitcoins系列的虚拟数字货币均基于公有区块链。

私有链：
封闭生态的网络，仅仅使用区块链的总账技术进行记账，可以是一个公司，也可以是个人，独享该区块链的写入权限，本链与其他的分布式存储方案没有太大区别。

行业链（联盟链）：
半封闭生态的网络，由某个群体内部指定多个预选的节点为记账人，每个块的生成由所有的预选节点共同决定（预选节点参与共识过程），其他接入节点可以参与交易，但不过问记账过程(本质上还是托管记账，只是变成分布式记账，预选节点的多少，如何决定每个块的记账者成为该区块链的主要风险点），其他任何人可以通过该区块链开放的API进行限定查询。

由于私有链是封闭生态的网络，也就是说使用传统分布式一致性共识算法应该是最优的。而对于联盟行业链其半封闭半开放特性，使用Delegated Proof of Stake是最优的，也可以考虑以传统一致性算法作为基础加入拜占庭容错/安全防护机制进行改进。公有链PoW，PoS应该是比较优秀的选择，比特币就采用PoW共识算法。

2.3 各种共识算法
前面提过，对于私有链而言，由于是封闭生态的网络，里面的每个节点都是可信的，采用类似PoW，PoS等算法效率并不高，而采用Raft，PBFT，Paxos这样传统的分布式一致性共识算法往往会更好。对于传统的分布式一致性共识算法，下面主要介绍Raft和PBFT，而对于Paxos，尽管也属于传统的分布式一致性共识算法，但是由于它难以理解，应用于工程化，并且Raft算法本身就是对Paxos的一种简化改进，有很多类似之处，因此Paxos不做介绍，有兴趣的可以自己查阅相关资料。
类似于比特币这样子加密货币体系运行的环境往往是共有链，他们是全球开发生态的网络，所要面临的问题便异常的复杂，传统的分布式一致性共识算法往往满足不了，因此会使用PoW，PoS，DPOS等共识算法，我们仅对最常见的算法做简单的介绍。
2.3.1 Raft
Raft是通过复制状态机将状态的一致性转化为日志的一致性，简单来说，就是对于N个数据库，如果他们的初始状态一致，以后进行的操作一致性，那么最终的数据也肯定能保持一致性。
如下图所示，复制状态机是通过复制日志来实现的。每一台服务器保存着一份日志，日志中包含一系列的命令（比如x = 3， y = x等），状态机会按顺序执行这些命令。因为每一台计算机的状态机都是确定的，所以每个状态机的状态都是相同的，执行的命令是相同的，最后的执行结果也就是一样的了。

复制状态机

Raft将服务器分为三种角色：Leader，Follower，Candidate，并且可以互相转换，它主要分为两个过程，一个是领导人选举，另一个日志复制。当一个分布式系统启动时，Raft选举出一个领导人，一旦领导人选举好了，他便负责从客户端接收日志并且将日志复制到其他机器上以保证分布式系统的一致性。对于Raft的更多细节，包括领导人宕机，网络分割等等一系列问题会在第三章Raft的实现给出详细介绍。

2.3.2 PBFT
对于Raft来说，它有个前提就是，不考虑拜占庭容错，所谓的拜占庭问题讨论的是一个系统里面存在少数节点作恶（也就是消息可能伪造）如何保持分布式系统达成共识。
在介绍该算法前，先简单了解一下拜占庭问题，它是Leslie Lamport提出用来解释一致性问题的一个虚构模型。拜占庭是古代东罗马帝国的首都，由于地域宽广，守卫边境的多个将军（相当于系统中的多个节点）需要通过信使来传递消息，达成某些一致的决定。但由于将军中可能存在叛徒（系统中节点出错），这些叛徒将努力向不同的将军发送不同的消息，试图会干扰一致性的达成。BFT算法便是用来解决以上问题的，只不过这个算法的复杂度过高一直受人诟病，直到PBFT算法将复杂度用指数级降到多项式级别才得到广泛应用。这个算法能够保证失效节点不超过总数的1/3的情况下保证Safety和Liveness，即n >= 3f+1，其中n是系统中的总节点数，f是允许出现故障的节点数。
举个例子来说，有4个参与者，一个被选举为军长，3个师长。军长接到总司令命令：向前行军500公里。军长就会给3个师长发命令该命令。3个师长收到消息后会执行命令，并汇报结果。A，B师长说我在首都东500公里， C师长说我在首都东100公里。军长总结3个师长的汇报，发现首都以东500公里占多数（2票>1票），所以就会忽略C师长的汇报结果，给总司令汇报说，好了，现在部队是在首都东500公里了。这就是PBFT算法。

client：请求（request）自愿者，上例中指总司令。
replica：副本，所有参与提供服务的节点，上例指军长和师长
primary：承担起提供服务主要职责的节点，上例是军长
backup：其他副本，但相对于primary角色。上例指师长。
view：处于存在primary-bakup场景中的相对稳定的关系，叫视图。

1.request阶段：client向primary节点发送请求，比如总司令给军长下命令。
2.pre-prepare阶段：primary节点向所有backup节点发送预准备消息，比如军长对各位师长说：现在是我的时代（视图），我是军长，所有人都得听我的，现在公布总司令的命令。
3.prepare阶段：backup节点i接受了预准备消息，则进入准备阶段。在准备阶段的同时，该节点向所有replica节点发送准备消息，并且将预准备消息和准备消息写入自己的消息日志。
4.commit阶段：replica节点收到2f个从不同副本节点发来一致的预准备消息，一共2f+1个一致的预准备消息确认了消息的正确性，然后按照序号n依次执行请求。

5 reply阶段：结果反馈。

2.3.3 PoW
前面提到的Raft和PBFT算法往往应用于私有链，而当面对情况异常复杂的共有链的时候，往往采用基于概率，经济博弈的共识，在理论上共识是可能被推翻的，只是攻击者要付出的代价随着时间越来越大，例如比特币网络中所有矿工都必须付出挖矿的代价，进行算力消耗，一旦失败，这些算力都会成为沉默成本。以PoW等代表的就是这样的共识算法。PoW共识算法要求通过计算来猜测一个数值（nonce），使得交易数据的内容Hash满足规定的条件。一个符合要求的Hash由N个前导零构成，零的个数取决于网络调节的难度值。要得到合理的Hash需要经过大量尝试计算，计算时间取决于机器的哈希运算速度。当某个节点提供出一个合理的Hash值，说明该节点确实经过了大量的尝试计算，这样的机制能够保证整个系统只有极少数的节点能够写入新区块，如果有人想要恶意破坏，需要付出大量的经济成本，这几乎是超过了可能带来的好处，从而保证数据的一致性。如果同一时间遇到数据分叉，也就是不止一个数据写入，区块链能够自动保证选择长的那条链继续进行下去，而抛弃短链，这样子就保证了区块链的最长链一致性。
2.3.4 PoS
PoW能够解决区块链中的共识问题，但是有一点，为了获取那个满足要求的Hash，只能进行大量的无意义的暴力计算，这十分浪费计算机资源。为了改进这个缺点，引入了PoS算法。它有点类似于现实生活中的股东机制，拥有股份越多的人越容易获得记账权。典型的过程是通过保证金来对赌合法的块成为新区块，收益为抵押资本的利息和交易服务费，提供的保证金越多获得的记账权的概率越大，合法记账者获得收益。

2.3.5 DPoS
PoS避免了无意义的计算导致的资源浪费，但依据权益结余来选择，会导致首富账户的权力过大，可能支配记账权。DPOS与POS原理相同，主要区别在于节点选举若干代理人，由代理人验证和记账。它的中文名叫做股份授权证明机制（又称受托人机制），原理是让每一个持有比特股的人进行投票，由此产生101位代表 , 任何一个持币用户都可以参与到投票和竞选受托人这两个过程中。用户可以随时投票、撤票，每个用户投票的权重和自己的持币量成正比。投票和撤票可以随时进行，在每一轮(round)选举结束后，得票率最高的101（一般为101，也可以是其他数字）个用户则成为该项目的受托人，负责打包区块、维持系统的运转并获得相应的奖励。
选举的根本目的，是通过每个人的投票选举出社区里对项目发展和运行最有利的101个用户。这101个用户的服务器节点既可以高效维护系统的运转，而他们也会贡献自己的能力促进区块链项目的发展，这有点类似于我国的‘人民代表’制度（但是周期更短、效率更高）。通过这种方式，既达到了去中心化的选举共识，又保证了整个系统的运行效率和减少能源浪费。

3 Raft的设计，实现和测试
第二章对于区块链各种常见的共识算法做了一个简单概括，并分析了他们的应用场景以及异同。这一章会详细介绍其中的一种共识算法Raft，并给出具体的设计，实现和测试方案。
3.1算法介绍
Raft源自于2013年的一篇论文《In Search of an Understandable Consensus Algorithm(Extended Version)》，它主要解决了在分布式环境下如何保证数据的一致性从而让系统达成共识。在这之前，Paxos算法在分布式环境一致性相关问题占领了统治地位，绝大多数的一致性实现都是基于Paxos或者受其影响。然而Paxos的算法最大的缺点就是难以理解并且难以运用于工程实践，而Raft算法正是在这种情况下应运而生。它不仅能满足分布式环境一致性的需求，更重要的是它比其他算法更简单且更易于理解，能广泛的应用于工程实践，同时它的安全性和效率与其他算法也不相上下。
为了满足算法的可理解性和可实践性，Raft算法使用了两种通用的技术。第一个技术就是问题分解：将复杂的问题分解成几个相对独立的，可被解决的和可理解的子问题。例如，Raft 算法被分成领导选举，日志复制，安全性等几个子问题。第二个方法是通过减少状态的数量来简化状态空间，使得系统更加连贯并且尽可能消除不确定性，比如 Raft 限制了使日志之间不一致的方式。

服务器的状态图

一个 Raft 集群包括n台服务器，必须保证至少n/2+1台机器正常，比如对于一个5 服务器集群，最多能够容忍 2 台机器不能正常工作，剩余的3台机器必须正常，这样子整个系统才能保持正常服务。在任意的时间，每一个服务器一定会处于以下三种状态中的一个：领导人（Leader）、候选人（Candidate）、追随者（Follower）。在正常情况下，只有一个服务器是领导人，剩下的服务器是追随者。追随者们是被动的：他们不会发送任何请求，只是响应来自领导人和候选人的请求。如果追随者没有收到任何消息，它会成为一个候选人并且开始一次选举，收到大多数服务器投票的候选人会成为新的领导人。而对于领导人， 他会来处理所有来自客户端的请求（如果一个客户端与追随者进行通信，追随者会将信息发送给领导人）。领导人会一直保持领导人的状态直到它宕机，这样子会重新开始一次选举选出领导人重复以上过程。上面服务器的状态图很好的说明了这个过程。

如上图所示，Raft 算法将时间划分成为任意不同长度的任期（term）。任期用连续的数字进行表示。每一个任期的开始都是领导选举（election），在成功选举之后，一个领导人会在任期内管理整个集群（normal operation）。在某些情况下（no emerging leader），选票会被瓜分，有可能没有选出领导人，那么，将会开始另一个任期，并且立刻开始下一次选举。Raft 算法保证在给定的一个任期最少要有一个领导人。
Raft中的服务器通过RPC来通信，基本的 Raft仅需要 2 种 RPC。RequestVote RPC 是候选人在选举过程中触发的，AppendEntries RPC 是领导人触发的。
3.1.1 领导选举
Raft 使用心跳机制（heartbeat）来触发领导人的选取。当服务器启动时，所有服务器会初始化为追随者状态。服务器会一直保持这样的状态只要它们能够收到来自领导人或者候选人的有效 RPC。领导人会向所有追随者周期性发送心跳（heartbeat，没有日志项的 AppendEntries RPC）来避免其他人选举。如果某个追随者在一个周期内没有收到心跳信息，就叫做选举超时（election timeout）,然后它就会假设没有领导人并且开始一次选举来选出一个新的领导人。
为了开始选举，一个追随者会自增它的当前任期并且转换状态为候选人。然后，它会给自己投票并且给集群中的其他服务器发送 RequestVote RPC。有以下下列三种可能性会发生：
1.它赢得了选举；
2.另一台服务器赢得了选举；
3.一段时间后没有任何一台服务器赢得了选举
对于1，一个候选人如果在一个任期内收到了来自集群中大多数服务器的投票就会赢得选举。在一个任期内，一台服务器最多能给一个候选人投票。一旦有候选人赢得了选举，它就会成为领导人。然后它会像其他服务器发送心跳信息来建立自己的领导地位。
对于2，当一个候选人等待别人的选票时，它有可能会收到来自其他服务器发来的声明其为领导人的 AppendEntries RPC。如果这个领导人的任期比当前候选人的当前任期要大，则候选人认为该领导人合法，并且转换自己的状态为追随者。如果在这个 RPC 中的任期小于候选人的当前任期，则候选人会拒绝此次 RPC， 继续保持候选人状态。
对于3，一个候选人既没有赢得选举也没有输掉选举：如果许多追随者在同一时刻都成为了候选人，选票会被分散，可能没有候选人能获得大多数的选票。当这种情形发生时，每一个候选人都会超时，并且通过自增任期号和发起另一轮 RequestVote RPC 来开始一轮新的选举。为了尽量避免这种情况发生甚至无限循环下去，Raft 使用随机的选举超时时间来保证。选举超时时间是在一个固定的间隔内随机选出来的（例如，150~300ms）。这种机制使得在大多数情况下只有一个服务器会率先超时，它会在其它服务器超时之前赢得选举并且向其它服务器发送心跳信息。同样的机制被用于选票一开始被瓜分的情况下。每一个候选人在开始一次选举的时候会重置一个随机的选举超时时间，在超时进行下一次选举之前一直等待。这能够减小在新的选举中一开始选票就被瓜分的可能性。
3.1.2 日志复制
一旦选出了领导人，它就开始接收客户端的请求。每一个客户端请求都包含一条需要被复制状态机（replicated state machine）执行的命令（command）。领导人把这条命令写入到日志中去，然后并行的向其他服务器发起 AppendEntries RPC ，要求其它服务器复制这个条目。一旦这个条目被安全的复制之后，领导人会将这个条目应用到它的状态机中并且会向客户端返回执行结果。
每个日志条目存储着一条被状态机执行的命令和当这条日志条目被领导人接收时的任期号。日志条目中的任期号用来检测在不同服务器上日志的不一致性，它用于检测日志条目的是否是最新的。每个日志条目也包含一个整数索引来表示它在日志中的位置。具体如下图所示：

日志图

领导人决定什么时候将日志条目应用到状态机是安全的；这种条目被称为可被提交状态（commited）。Raft 保证可被提交（commited）的日志条目是持久化的并且最终会被所有可用状态机执行。一旦被领导人创建的条目已经复制到了大多数的服务器上，这个条目就称为commited状态。
Raft对于日志必须要满足以下两个特性：第一，如果不同日志中的两个条目拥有相同的索引和任期号，那么他们存储了相同的指令。第二，如果不同日志中的两个条目拥有相同的索引和任期号，那么他们之前的所有日志条目也都相同。这是通过AppendEntries RPC执行的一致性检查实现的，在发送 AppendEntries RPC 的时候，领导者会将前一个日志条目的索引位置和任期号包含在里面。如果 跟随者在它的日志中找不到包含相同索引位置和任期号的条目，那么他就会拒绝该新的日志条目。因此，每当 AppendEntries RPC 返回成功时，leader 就知道 follower 的日志一定和自己相同。
对于正常情况下，leader 和 follower 的日志总会保持一致，然而一旦领导人崩溃就会可能导致日志不一致。为了保证跟随者和领导的日志一致性，领导者需要找到追随者同它的日志一致的地方，然后删除追随者在该位置之后的条目，然后将自己在该位置之后的条目发送给追随者。这些操作都在 AppendEntries RPC 进行一致性检查时完成。领导人给每一个追随者维护了一个nextIndex，它表示领导人将要发送给该追随者的下一条日志条目的索引。当一个领导人被选举出来时，它会将nextIndex初始化为它的最新的日志条目索引数+1。如果一个追随者的日志和领导者的不一致，AppendEntries 一致性检查会在下一次 AppendEntries RPC 时返回失败。在失败之后，领导人会将nextIndex递减然后重试 AppendEntries RPC。最终nextIndex会达到一个领导人和追随者日志一致的地方。这时会删除追随者中冲突的日志条目，并且添加所缺少的领导人的日志条目。这样子 AppendEntries 一旦返回成功，追随者和领导人的日志就保持一致了。

3.2算法设计与实现
3.2.1准备工作
Raft算法可以使用多种语言来实现，比如C++，Go，Python，Java等等，在这里，我们使用Go语言来实现，原因如下：Go是一门自带垃圾回收，类型安全的语言，它对多线程有着良好的支持（Goroutine），还包含着一个十分精简的RPC库可以直接使用，这些能够帮助我们更好的实现Raft专注于算法逻辑而不必过分的操心诸如申请释放内存，网络通信，并发编程的很多细节。同时，MIT6.824课程提供一套基于Go语言的Raft测试框架，这套测试框架提供了算法实现的关键接口说明，因此这能够减小算法实现和测试的难度，也提高了算法测试的准确性。
所以，基于上述原因，最后实验的环境是Linux采用Go语言设计，实现和测试Raft算法，同时需要下载配置MIT6.824课程自带的一套测试框架。我们需要完成如下几步：

1. 安装Go语言和Git
   sudo apt-get install golang-go
   sudo apt-get install git
2. 下载和配置Raft测试框架
   git clone git://g.csail.mit.edu/6.824-golabs-2018 6.824
   cd 6.824
   export “GOPATH=$PWD“cd“$GOPATH/src/raft”
   上述步骤执行成功之后，基本的开发环境就配置好了。在Raft算法具体实现之前我们需要再做一些准备工作。Raft算法是用来保证分布式系统的多台机器的一致性的共识算法，这其中必不可少的就是网络编程和并发编程，Go语言对这两点有着非常好的支持，这也就是为什么使用Go语言来完成Raft的重要原因。
   Raft使用RPC来完成网络通信，RPC叫远程过程调用，它能够让我们像调用本地服务一样调用远程服务，屏蔽了网络通信这些细节，MIT6.824的测试框架提供了一套简洁的RPC接口，而不需要自己实现，在Raft中如果需要使用AppendEntries RPC或者RequestVote RPC只需要这样调用：

func (rf *Raft) sendRequestVote(server int, args RequestVoteArgs, reply *RequestVoteReply) bool {ok := rf.peers[server].Call("Raft.RequestVote", args, reply)return ok}func (rf *Raft) sendAppendEntries(server int, args AppendEntryArgs, reply *AppendEntryReply) bool {ok := rf.peers[server].Call("Raft.AppendEntries", args, reply)return ok}

其中，sever定位具体哪个sever发出的RPC请求,args表示请求参数，reply表示回复结果，Call表示调用RPC接口，第一个字符串参数表示调用的函数名。
Raft中另一个重要的基础知识就是并发编程，Go语言提供了很好的支持。在多线程环境下，如何避免临界区，一个常见的方法就是加锁，但是Go提供了一套类似C++RAII的自动管理资源的方式：
mutex.Lock()
defer mutex.Unlock()
// 此处是多线程环境下需要读写的数比如i++
这样子能够避免了程序异常Crash可能的死锁，同时Go自己还独具特色的提供了一套Goroutine和Channel机制来保证多线程之间共享变量的控制。

func Say(str string, done chan int) {fmt.Println(str) time.Sleep(3 * time.Second)done<-1}func main() {done := make(chan int)go Say("hello", done)<-done}

在Go语言，开启一个线程执行相应的操作，十分简洁，只需要写go fun()，每个线程操作着自己的变量，因此无需同步，如果需要操作共享变量，则通过channel来传递，Go的设计哲学就在于此：不要通过共享内存来通信，而应通过通信来共享内存。在上面的例子，主线程在main函数中执行，通过go Say开启另一个线程执行，打印str并且sleep 3s然后通过done告诉主线程完成，主线程的channel通过<-done保证其他线程已经执行完，如果其他线程没有执行完就一直阻塞。
3.2.2 具体设计与实现
Raft算法的基本流程是初始化各个节点（Raft结构），开始领导选举，一旦领导选举成功，接受客户端请求，分发日志要求各节点复制日志，最后达成commited状态，一旦领导者宕机就需要重新选举，重复以上过程。流程图如下：

首先是Raft的初始化，根据论文上的说明，一个Raft节点至少需要保存以下状态：

因此，Raft的数据结构定义为如下：

type Raft struct {musync.Mutex peers []*labrpc.ClientEnd // 用于保存集群里的所有机器的数组persister *Persister // 用于持久化meint // 自己// Persistent state on all serverscurrentTerm intvotedForintlogs[]LogEntry// Volatile state on all serverscommitIndex intlastApplied int // Volatile state on leadersnextIndex[]intmatchIndex []int voteNum int // 统计投票的票数state stringapplyCh chan ApplyMsgtimer *time.Timer // 用于设置定时器}

刚开始需要调用Make函数初始化Raft结构，初始化完毕，此时所有的节点状态都处于跟随者，经过一段时间（一般是150ms到300ms的某个随机值），就会有一个节点开始发起选举，它先回切换到候选人的身份，然后并行的向集群内的多个节点发送RequestVote RPC。关键代码如下：

rf.state = CANDIDATErf.currentTerm += 1rf.votedFor = rf.merf.voteNum = 1rf.persist()for server := 0; server < len(rf.peers); server++ {if server == rf.me {continue}// ……// 每个节点开启一个线程发送RPC请求go func(server int, args RequestVoteArgs) {var reply RequestVoteReplyok := rf.sendRequestVote(server, args, &reply)if ok {rf.handleVoteResult(reply)}}(server, args)}

一旦领导选举成功后，整个Raft集群就处于服务状态，如果有client发送一次请求，比如x = 8，此时领导将这条命令写入Log，并在下一次AppendEntries RPC中分发到各个节点要求它们复制，一旦大多数节点复制成功，这条日志就会处于commited状态。

func (rf *Raft) Start(command interface{}) (int, int, bool) {rf.mu.Lock()defer rf.mu.Unlock()index := -1term := -1isLeader := falsenlog := LogEntry{command, rf.currentTerm}if rf.state != LEADER {return index, term, isLeader}isLeader = (rf.state == LEADER)rf.logs = append(rf.logs, nlog)index = len(rf.logs)term = rf.currentTermrf.persist()return index, term, isLeader}

如上，Leader调用Start函数接受一条命令并写入日志后，并在下一次AppendEntries RPC中将这条日志分发到所有的跟随者。

func (rf *Raft) sendAppendEntriesToAllFollowers() {for i := 0; i < len(rf.peers); i++ {if i == rf.me {continue}// ……// 每个节点开启一个线程发送RPC请求go func(server int, args AppendEntryArgs) {var reply AppendEntryReplyok := rf.sendAppendEntries(server, args, &reply)if ok {rf.handleAppendEntries(server, reply)}}(i, args)}}

在这里，sendAppendEntries(server, args, &reply)用于发送个某个sever的AppendEntries RPC请求，它调用了AppendEntries函数，保证了日志的一致性。

3.3算法的测试
在前一节，完成了算法的设计和实现，并给出了关键部分的代码，在这一节，主要给出了Raft算法的测试，在这里使用MIT 6.824提供的一套测试框架，因为Raft算法如果要应用于分布式系统的话，不得不面对网络通信，RPC框架，并发编程等等这些细节，这给算法的测试带来了很多的不确定性，同时，在一个大规模的分布式系统，网络是异常复杂的，出现的问题很多时候是很难以模拟的，测试的覆盖率也是很难保证的，因此为了专注于算法的设计与实现，MIT6.824提供的这套测试框架为我们模拟一套基于channel机制的RPC框架，这样不仅避免重复造轮子编写RPC框架，同时基于channel模拟的RPC框架能够尽量模拟出复杂的网络动态，比如机器的宕机重启，网络分割等等。
在测试之前，需要对于分布式环境进行模拟，构建出一套多台服务器的集群以测试Raft算法。测试框架提供了以下接口：
省略

4 结论
这次毕业设计的出发点是为了工作做打下基础，我所在的部门是做分布式CDN的，今年将开始做区块链相关的内容，因此本次毕设定下的题目就是基于区块链的Raft共识算法的实现，当然Raft不仅仅应用于私有链，更广泛运用于分布式系统。
通过这次毕业设计，我学到了很多东西，最为基础的就是学习了Raft算法，然而在学习的过程中，让我对分布式系统的基础知识有了一些初步的了解，同时在实现Raft算法的过程中，学习到了Go语言的网络编程，并发编程，RPC等，通过Raft算法以点到面的让我了解了区块链的各种共识机制以及对应的应用场景。
当然，限于时间和能力所限，我只完成了Raft算法的两个核心部分，领导选举和日志复制，而日志压缩和配置更新只是简单了解，并未实现，希望能在以后继续完善并且优化。
总体来说，这是一次对我意志力、学习能力的考验，是对我编程技能和解决问题能力的一次提升，会对我将来学习和工作生活有非常大的帮助。

致 谢
省略

参 考 文 献
[1] Robert Morris, Malte Schwarzkopf . MIT 6.824: Distributed Systems 2018.2
https://pdos.csail.mit.edu/6.824/
[2] 杨保华, 陈昌. 区块链原理、设计与应用[M]. 机械工业出版社, 2017.8
[3] 蒋勇. 白话区块链[M]. 机械工业出版社, 2017.10
[4] Nakamoto S. Bitcoin. a peer-to-peer electronic cash system
https://bitcoin.org/bitcoin.pdf, 2009.1
[5] Diego Ongaro, John Ousterhout. In Search of Understandable Consensus Algorithm 2013
[6] 袁勇，王飞跃. 区块链技术发展现状与发展 2016.4

5、资源下载

本项目源码及完整论文如下，有需要的朋友可以点击进行下载。如果链接失效可点击下方卡片扫码自助下载。