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

raft简述

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

term 任期概念

每一个任期只会有一个leader，follower被选举为leader后会将任期Id给follower，每一次信息通讯都要携带任期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、Follower通知Leader写入成功。

4、Leader将会把这部分数据提交到状态机中。

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

reft如何保证集群中只有一个leader/脑裂问题

当follower网络分区故障，一个follower无法当选leader，当leader宕机或网络分区，其他follower节点长时间没有收到leader节点的心跳，就会将自身的的follower状态变更为候选者状态，然后选举出新的leader，若old 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的心跳通知，则保持candidate、重新发出选举

个人理解

当某个follower节点率先苏醒，首先会生成任期Id，然后将自身状态切换到候选人，然后投自己一票发起选举RPC请求，这个请求携带了自身节点维护的任期ID以及状态机中最后一条数据的索引，若follower发现候选者的数据索引比自身的要大才会投票给候选者，若得到了半数以上节点的投票则将状态切换为leader然后立刻向所有节点发送心跳，其他节点若收到leader所发送的心跳则将候选者切换成follower，若长时间没有收到半数以上的投票或leader的心跳则重新发起选举。

数据同步流程

leader数据同步时会携带上一次同步的索引也可以理解为近期同步的数据最后一条数据的索引以及上一次同步所携带的任期ID，follower接受数据并且进行判断，若索引条件与任期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与Follower通信，发现Follwer所传递的任期Id大于老Leader的任期Id，老Leader就会将状态切换到Follower。

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

3、Leader完全原则：某个任期的数据已经被提交，那么这个数据肯定会被最新的Leader所拥有。

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

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