raft共识算法解析,raft共识算法论文

　　

　　我是改善建筑的方法。点击上方“关注”，坚持每天为你分享技术干货。我会私信回复“01”，送你程序员成长进阶包。 　　

　　

　　 　　

　　

　　1.Raft算法概述当我们只有一个服务节点时，不存在节点一致性的问题。当有很多不同的服务节点时，就会引入分布式一致性的问题。 　　

　　

　　Raft是一种分布式共识协议。所谓共识，就是很多节点在某件事情上达成一致，即使有些节点失效，网络延迟，网络分裂。 　　

　　

　　主要应用场景： 　　

　　

　　Redsentinel的选举领袖主要是关于共享配置和服务发现，使用Raft算法加密货币(比特币，区块链)的共识算法主要解决什么问题？实现一致性。 　　

　　

　　分布式存储系统通常通过维护多个副本来提高系统的可用性，而成本是分布式存储系统的核心问题之一：维护多个副本的数据一致性。 　　

　　

　　二。Raft算法的实现过程为了提高理解，Raft将一致性算法分为几个部分，包括首领选择、日志复制和安全，用更强的一致性来减少必须考虑的状态。 　　

　　

　　本文以一个小故事为例，方便大家快速理解。 　　

　　

　　2.1领导人选举部门需要成立一个新的服务小组。现在有A，B，c三个同学。 　　

　　

　　为了方便后期统一分配资源和管理需要，需要从三个学生中选一个小组长。 　　

　　

　　当A觉得自己有能力当领导的时候，他对B和C说：“快来投我一票，我要当领导。”这时，A成为候选人，提前投了自己一票。 　　

　　

　　1)如果B和C之前都没想过自己当领袖，那就说“好吧，投你一票” A获得3票，当选领袖。 　　

　　

　　2)如果B之前有想过当领导，B投自己，C投A A得2票(3人过半)，当选领导。 　　

　　

　　3)如果B、C已经投了自己的票 A、B、C各得一票，选举失败重新发起。 　　

　　

　　4)如果B之前想过当领导，C已经投了B B得2票(3人过半)，当选领导。 　　

　　

　　 　　

　　

　　从上面的选举过程可以发现，节点在任何时刻都必须处于以下三种状态之一： 　　

　　

　　领导者追随者候选人这三个状态的转移过程如下图所示： 　　

　　

　　 　　

　　

　　选举过程 　　

　　

　　第一步：追随者成为候选人。 　　

　　

　　如果追随者听不到领导者的意见，他们可以成为候选人。 　　

　　

　　第二步：候选人争取选票。 　　

　　

　　为自己投票，并将投票请求发送给其他节点，节点收到请求后会做出响应。 　　

　　

　　第三步：等待其他节点回复。 　　

　　

　　如果候选人获得超过半数的节点选票(包括他自己的选票)，他就成为领先者。 　　

　　

　　如果候选人被告知领导者已经生成，他会自己切换到追随者。 　　

　　

　　在一段时间内没有收到过半数的选票，因此维持候选人地位，重新开始选举。 　　

　　

　　第四步：候选人赢得选举。 　　

　　

　　新的领导者将立即向所有节点发送消息，以防止其他节点触发新的选举。 　　

　　

　　2.2日志同步在上面2.1中的领导者选举之后，组的领导者已经被选定。这里，我们假设A已经被选为领导者。可以承接一些对口同学提出的操作任务(称为客户端)。 　　

　　

　　规定每次需求对接都要经过组长。员工提出操作请求，领导收到后记录，并同步到组内其他同学。直到其他同学确认了这个需求，领导才会确认操作，并将执行结果同步给员工(追随者节点)。 　　

　　

　　 　　

　　

　　Log Replication（日志复制） 　　

　　

　　领袖选举过程结束后，一个新的领袖节点被创建，系统的所有改变都必须通过领袖节点来实现。 　　

　　

　　第一步：领导追加日志条目。 　　

　　

　　系统的每次更改都会作为一个条目添加到节点中。 　　

志中

　　

第二步：Leader并行发出append Entries RPC，并等待响应

　　

Leader会一直等到超半数节点都写入entry，Leader节点提交，然后Leader通知Follower entry已提交。

　　

第三步：Leader得到大多数回应，向状态机应用entry

　　

状态机：可理解为一个确定的应用程序，所谓确定是指只要是相同的输入，那么任何状态机都会计算出相同的输出。

　　

第四步：Leader回复Client，同时通知Follower应用log

　　

目前集群已就系统状态达成了共识

　　

log-based replicated state machine示意图：

　　

　　

　　

关于应用过程中的几个问题

　　

Q1：假如Client 请求访问到了Follower节点怎么办？

　　

解答：Follower节点会转发请求到Leader节点。

　　

Q2：当Leader与Follower的日志不一致，需要如何处理？

　　

解答：

　　

1）Leader通过强制Followers复制它的日志来处理日志的不一致，Followers上的不一致的日志会被Leader的日志覆盖。

　　

2）Leader为了使Followers的日志同自己的一致，Leader需要找到Followers同它的日志一致的地方，然后覆盖Followers在该位置之后的条目。

　　

3）Leader会从后往前试，每次appendEntries失败后尝试前一个日志条目，直到成功找到每个Follower的日志一致位点，然后向后逐条覆盖Followers在该位置之后的条目。

　　

　　

2.3 安全性保障为了保证团队运行的稳定，有几个默认的要求：

　　

2.3.1 选举安全

　　

即任一任期内最多一个leader被选出。假如系统中同时有多于一个leader，被称之为脑裂（brain split），这会导致数据的覆盖丢失。

　　

一个团队某个时期内仅允许存在一个Leader（选举失败情况特殊情况除外），否则多个Leader同时处理需求发号施令，容易造成团队内步调不一致情况。

　　

在raft中，两点保证了这个属性：

　　

1）一个节点某一任期内最多只能投一票；

　　

2）只有获得majority投票的节点才会成为leader。

　　

　　

2.3.2 Log 匹配完整性

　　

同一团队内两名同学假如目前手头负责的事务是一致的，那之前他们的工作记录应该也是一致的。即：相同的初始状态 相同的操作=相同的结束状态

　　

Leader将客户端请求封装到一个个的log entry，将这些log entries复制到其他Follower节点，大家按顺序应用这些请求，那最终状态肯定是一致的。

　　

Raft日志同步结论：

　　

1）如果不同日志中的两个条目有着相同的索引和任期号（term），则它们所存储的命令是相同的。

　　

2）如果不同日志中的两个条目有着相同的索引和任期号（term），则它们之前的所有条目都是完全一样的。

　　

2.3.3 leader数据完整性

　　

团队内后继的leader，肯定应该知晓这个团队之前的工作内容，因为所有Leader任期内的工作记录是会做交接的。

　　

如果一个log entry 在某个任期被提交，那么这条log一定会出现在所有更高term的leader的日志里面。

　　

Raft日志覆盖规则：

　　

1）一个日志被复制到majority节点才算committed

　　

2）一个节点得到majority的投票才能成为leader，而节点A给节点B投票的其中一个前提是，B的日志不能比A的日志旧。

　　

三、总结所有的算法实现原理，其实都是真实社会工作模式的影射，联系生活中的实际案例来理解复杂的一致性算法，可以让我们达到事半功倍的效果。

　　

本文是让大家对raft协议有一个简单了解入门，如有兴趣去更深入了解，推荐给大家两个不错的链接：

　　

1）Raft可视化测试以及各语言版本实现的Raft：https://raft.github.io/

　　

2）Raft算法-动画演示（很好的入门教程）：http://thesecretlivesofdata.com/raft/

　　

　　

　　

　　

- END -

　　

作者：架构精进之路，专注软件架构研究，技术学习与个人成长，关注并私信我回复“01”，送你一份程序员成长进阶大礼包。

　　

　　

Thanks for reading!

以上就是帮企客小编为大家带来的全部内容，希望可以帮助到大家。