paxos协议之衍生协议：Raft协议的简述、协议模型、一致性算法、脑裂问题处理、选举流程、数据同步流程、安全原则

raft简述

raft协议中的节点有三种状态：leader、follower、candidate(候选人)，leader复制日志的管理，客户端的新更新请求，然后复制到follower节点。如果leader出现故障，follower将重新选举。如果follower接收新的操作，将重定向转移到leader，follower只负责客户端的阅读请求。有两种状态将follower转换为候选人。首先，当集群初始化时，所有节点都是follower，所有节点都会随机睡觉，然后唤醒候选人发起选举。有两种状态将follower转换为候选人。首先，当集群初始化时，所有节点都是follower，所有节点都会随机睡觉，然后唤醒候选人发起选举。第二，当follower长时间没有收到leader的心跳时，选举将从follower节点转变为候选人节点。

term 任期概念

每个任期只有一个leader。folllower被选为leader后，任期ID将交给folllower。每个信息通信都必须携带任期ID，任期ID是自添加的。

两个RPC 通讯

1、RequestVote RPC：负责选举，包括lastindex参数、lastTerm。

当follower进行选举时，他们将自己的状态改为候选人。在拉票请求中，他们应该携带状态计算机中最后一个数据的索引和当地维护的任期ID。如果参与投票的follower发现自己状态计算机中最后一个数据的索引小于候选人传递的lastindex，并且当地维护的任期ID小于leader传递的任期ID，则将进行投票。

2、AppendEntries RPC：负责数据交互。

通过一致性协议算法，每个节点保持一个持久的log，以确保每个节点中的log保存一致并按顺序存储，使客户端能够在每个节点中读取相同的数据。

日志序列同步到大多数节点，leader将日志提交到状态机，并在下一次心跳通知中告诉所有节点，提交状态机

注意

1、所有的写作操作只能通过Leader进行，如果Follower收到写作操作页面，则只能重新定向Leader。

2、Leader收到数据后，将日志写入日志序列，然后同步到Follower节点。

3、Folllower通知Leader成功写入。

4、Leader将向状态机提交这部分数据。

5、下次发送心跳数据时，会告诉Follwer需要向状态机提交哪些日志序列。

当follower网络分区出现故障时，follower不能被选为leader。当leader停机或网络分区时，其他follower节点长时间未收到leader节点的心跳，将将其follower状态改为候选人状态，然后选择新的leader，如果older leader网络恢复，通过与follower节点的通信，如果leader发现本地维护的任期ID小于follower节点传输信息携带的任期ID，则将自己的状态改为follower

选举过程：选举节点角度1、将节点本地term添加到candidate状态2、在其他节点投票逻辑： 每个节点最多只能在同一任期内投票，候选人不能比自己知道更少的信息（通过复制日志和安全机制），先来先得3、并将RequestVote并行发送到其他节点 RPCs(选举请求)、包括term参数4、等待回复4.1、收到majority的投票，赢得选举，切换到leader状态，并立即向所有节点发送心跳信息4.2、被告知他人当选，切换到follower状态。(原来的leader比term大，转换为follower状态)4.3、有一段时间没有收到majority和leader的心跳通知，保持candidater、重新发布选举

当一个follower节点率先醒来时，它将首先生成任期ID，然后将自己的状态切换到候选人，然后投票发起选举RPC请求。该请求携带任期ID和状态机中最后一个数据的索引。如果follower发现候选人的数据索引大于自己的数据索引，它将投票给候选人，如果你得到超过一半节点的投票，你将把状态切换成领导者，然后立即将心跳发送到所有节点。如果其他节点收到领导者发送的心跳，候选人将被切换为领导者。如果你长时间没有收到超过一半的投票或领导者的心跳，你将重新启动选举。

当leader数据同步时，它将携带最后一个同步索引，也可以理解为最后一个同步数据索引和最后一个同步携带的任期ID。folllower接受数据并做出判断。如果索引条件能够匹配任期ID条件，则添加到日志序列中，直到下一个leader心跳发送，然后确定这些数据提交到状态机，如果不匹配，则判断是大于当前节点数据索引还是小于，如果大于，则拒绝要求。leader将减少index，然后再次发送给follower。如果它仍然大于，它将循环此操作，直到匹配并完成匹配后的数据同步。如果leader传输的索引小于当前节点的索引，则删除当前节点超出的部分。这些新数据发送到follower满足半数后，leader将数据提交到状态机。

注：如果follower有上一任期的数据，则必须让当前leader生成新的日志数据，follower才能将上一任期的数据提交到状态机，否则会出现覆盖。

下图显示了Leader term1 就是old Leader，当所有数据都写入follower时，F1出现网络分区故障，F2被选为新的Leader，但F3、F4、状态机无法提交F5数据。

如下图所示，当newleader提交数据时，只有将心跳通知follower发送到状态机，才能提交新数据。

注：若经过多次选举： F2newleader存在AAA数据，F3假设存在CCC数据，这两个数据在各自的节点上索引假设为1，F3数据将被覆盖。

1、选举安全原则:任期内只有一个Leader，由每次通信携带的任期ID保证。如果老Leader与Folllower通信，发现Follwer传递的任期ID大于老Leader，老Leader将将状态切换到Follower。

2、状态机安全原则:如果Leader已经向状态机中索引1的位置提交了数据，那么其他节点就不会在这个位置提交不同的日志。

3、Leader的完整原则:如果一个任期的数据已经提交，那么这个数据肯定会被最新的Leader拥有。

4、Leader添加原则：Leader只会提出新的请求，不会删除或覆盖自己的日志。

5、日志匹配原则：如果两个节点相同的日志索引位置上的日志数据任期相同，则视为同步。