Raft

分布式共识算法

CAP理论(Consistency-Availability-Partition tolerance Theory)是一个经典的分布式系统理论

• Consitency，一致性

强调数据的正确性. 具体而言，每次读操作，要么读到最新，要么读失败. 这要求整个分布式系统像是一个不可拆分的整体，写操作作用于集群像作用于单机一样，具有广义的“原子性”.

• Availability，可用性

强调用户使用服务的体验.客户端的请求能够得到响应，不发生错误，也不能出现过长的等待时间.

• Partition tolerance，分区容错性

分区容错性强调的是，在网络环境不可靠的背景下，整个系统仍然是正常运作的，不至于出现系统崩溃或者秩序混乱的局面.

CAP 理论强调的是，一个系统中，C、A、P 三项性质至多只能满足其二，即每个系统依据其架构设计会具有 CP、AP 或者 CA 的倾向性.

对于分布式系统而言, P 是必须得到保证的，否则这就违背了“分布式”的语义. 那么分布式系统会分为两种流派：

1. CP：强调系统数据的正确性，但由于建立保证不同节点间保证数据严格一致的机制，可能会牺牲系统的可用性（所有节点数据同步成功之后，master才返回ack）
2. AP：强调系统的可用性，那就必须在数据一致性上做出妥协退让.如client发起写入请求，master节点先返回ACK，再异步同步数据到其他节点。

raft 算法概念

RAFT算法是一种CP类型的分布式一致性算法。

多数派原则 贯穿 raft 算法的始终，不论是数据的同步，还是领导者的选举，只需要达到群体总数的一半以上的认可，就可即时采纳结果，同时处于拒绝态或者未响应态的少数派在随后感知到该决断已经被集群多数派认同后，最终也会执行采纳.

多数派原则是提高分布式系统可用性的关键. 对于整个系统而言，执行一项操作要求全员共同响应以实现强一致性是过于苛刻的，因为我们无法保证所有节点都能健康运作

但是倘若退而求其次，只要多数派达成共识即可正常决断和响应，这样下限就提高很多了. 由全员响应进化为多数派共识，这将把一种底线思维下的随机性问题进化为一个数学期望问题.

多数派原则大大提升了系统可用性，那么接下来的讨论重点就在于，raft 算法如何在多数派这一框架下，达成一致性的要求.

两阶段提交

1. leader 将写请求添加到本地的预写日志中，并向集群中其他节点广播同步这笔写请求. 这个过程可以称之为提议(proposal)；

2. 集群中各节点接收到同步请求后，会一套检验机制判断是否能执行同步（添加到预写日志），倘若集群总计半数以上的节点（包括 leader 自身）都将这笔请求添加预写日志，并给予了 leader 肯定的答复（ack），那么 leader 此时会提交(commit)这个请求，并给予客户端写请求已成功处理的响应；

3. 其他节点在随后的时段中，会通过与 leader 的交互（心跳或其他同步数据的请求）感知到提交动作，最终也在预写日志中提交这笔请求；

4. 被提交的预写日志具备了被应用到状态机的资格. 但应用的时机取决于实现方式，倘若只追求最终一致性，可以选择异步应用；倘若追求立即一致性，则会要求 leader 先应用到状态机，才能给予客户端 ack.

上述流程中，提议阶段（proposal）和 提交阶段（commit）两者相加，构成了所谓的两阶段提交的流程.

术语解释

中文	英文	含义
领导者	leader	节点的三种角色之一. 集群的首脑，负责发起”提议“、”提交“被多数派认可的决断.
跟随者	follower	节点的三种角色之一. 需要对 leader 的 ”提议“ 、”提交“和 candidate 的 ”竞选“ 进行响应.
候选人	candidate	节点的三种角色之一. 是一种处于竞选流程中的临时状态，根据多数派投票的结果会切为 leader 或 follower 的稳定态.
最终一致性	finnal consistency	中强一致性. 对于写请求，服务端保证最终一定能提供出正确的结果，但需要同步时间. 同步期间，可能被读到不一致的老数据.
即时一次性	immediate consistency	强一致性. 服务端要求做到写入立即可读.
预写日志	write ahead log	记录写请求明细的日志.（单指 raft 算法下狭义的预写日志）
状态机	state machine	节点内存储数据的介质.
提议	proposal	两阶段提交的第一个阶段. 指的是 leader 向所有节点发起日志同步请求的过程.
提交	commit	两阶段提交的第二个阶段. 指的是 leader 认可一笔写请求已经被系统采纳的动作.
应用	apply	指的是将预写日志记录内记录的写操作应用到状态机的过程.
任期	term	任期是用于标识 leader 更迭的概念. 每个任期内至多只允许有一个 leader.
日志索引	index	日志在预写日志数组中的位置.
脑裂	brain split	同一任期内，集群出现两个 leader，导致秩序崩盘.

leader

领导者是写请求的统一入口，在接收到来自客户端的写请求时，会开启“两阶段提交”的流程：

（1）广播 proposal，向所有节点同步这一请求；

（2）当请求得到多数派的赞同后，才会提交这一请求.

leader 还需要周期性地向集群中所有节点发送自己的心跳，告知自己的健康状况，用途包括：

（1）让 follower 重置心跳检测定时器，避免其切换成 candidate 发起竞选；

（2）在心跳请求中携带上 leader 最新已提交日志的标识 id（term index），推动 follower 更新日志提交进度.

follower

（1）负责同步 leader 传来的写请求，此时也有一个参与民主反馈的过程，倘若同步成功，会给予 leader 正向反馈，当 leader 的同步请求收到半数以上的认可时，会提交日志；

（2）通过接收 leader 心跳的方式，获取到携带的 commitIndex 信息，及时完成已被多数派认可的预写日志的提交，以推进其写入状态机的进度. 这一项相当于做到了数据的备份，也被读请求最终一致性提供了保证;

（3）负责为参与竞选 candidate 的投票，决定赞同与否的判断机制见 5.3 小节；

（4）通过心跳检测定时器时时关注 leader 的健康状态，当超时未收到心跳时，会切换为 candidate 发起竞选.

candidate

（1）candidate 是一个临时态，倘若 follower 切为 candidate，会将当前任期加1，作为竞选任期；

（2）会将自身的一票投给自己；

（3）广播向所有节点拉票；

（4）倘若拉票请求超时前，得到多数派认可，则上位为 leader；

（5）倘若拉票请求超时前，遭到多数派拒绝，则老实退回 follower；

（6）倘若拉票请求超时前，收到了任期大于等于自身竞选任期的 leader 的请求，则老实退回 follower；

（7）倘若拉票请求超时，则竞选任期加 1，发起新一轮竞选拉票请求.

raft算法下节点的角色流转

LEADER选举

一个节点只会处于Follower， Candidate， Leader三种状态中的一种

选举过程

时间被划分为一个个的 Term(任期)， 任期开始于一次选举， 选举成功后， Leader 会管理整个集群直到任期结束

1. 如果 FOLLOWER 在一段时间内，没有收到 LEADER 的消息，会进入选举超时，给他随机设置一个超时时间，在 150ms - 300ms 之间，这可以避免多个　FOLLOWER　同时成为　CANDIDATE
2. 选举超时之后，该　FOLLOWER　自动成为　CANDIDATE，并发开始新的任期，然后发送投票信息请求其他节点，同时也会给自己投一票
3. 其他节点在收到请求后，如果在这段时间内没有投票，那么会投票给该节点，并重置自己的超时时间，更新任期
4. 如果一个　CANDIDATE　得到了超过一半的选票，他就会成为新的　LEADER
5. LEADER 开始每隔一段时间向其他的 FOLLOWER 发送追加条目信息（心跳），FOLLOWER 在收到心跳之后，重置自己的选举超时时间

选举限制 Raft 使用了一种更加简单的方法，它可以保证选举出的新 Leader 拥有所有之前任期中已经提交的日志，而不需要传送这些日志条目给领导人。这意味着日志条目的传送是单向的，只从领导人传给跟随者，并且领导人从不会覆盖自身本地日志中已经存在的条目。

拒绝投票 在候选人选举过程中，如果追随者收到一个候选人的投票请求，那么追随者会检查候选人的日志信息，如果日志比自己的更新或者相同，则投票给它，反之如果日志信息都没有自己的新，那么追随者就会拒绝投票

注意，在 raft 算法的设定中，已提交的日志就认为是写入成功了，是绝对不允许被回滚的，这种极端 case 就会 raft 算法的公信力造成破坏.于是为解决这一问题，raft 算法中新增了一项限制，新上任的 leader 需要至少完成一笔本任期内的写请求，才能够执行提交动作.

角色流转

leader -> follower

倘若 leader 发现当前系统中出现了更大的任期，则会进行“禅让”，主动退位成 follower.

这里 leader 发现更大任期的方式包括: I 向 follower 提交日志同步请求时,从 follower 的响应参数中获得; II 收到了来自新任 leader 的心跳或者同步日志请求; III 收到了任期更大的 candidate 的拉票请求.

follower -> candidate

leader 需要定期向 follower 发送心跳，告知自己仍健在的消息.

倘若 follower 超过一定时长没收到 leader 心跳时，会将状态切换为 candidate ，在当前任期的基础上加 1 作为竞选任期，发起竞选尝试补位.

candidate -> follower

candidate 参与竞选过程中，出现以下两种情形时会退回 follower：

I 多数派投了反对票；

II 竞选期间，收到了任期大于等于自身竞选任期的 leader 传来的请求.

candidate -> leader

candidate 竞选时，倘若多数派投了赞同票，则切换为 leader.

candidate -> candidate

candidate 的竞选流程有一个时间阈值. 倘若超时仍未形成有效结论（多数派赞同或拒绝），则会维持 candidate 身份，将竞选任期加1，发起新一轮竞选.

内部请求链路梳理

日志同步

所有对系统的更改都会通过　leader　进行，一旦有leader 被选举出来，需要复制所有的系统更改到其他节点，通过心跳的相同附加条目消息实现的

client 向 leader 发送更改信息，leader收到后向其他节点同步预写日志(proposal).

• 倘若多数派都完成了日志同步，leader 会提交这笔日志；

• 倘若某个节点拒绝了同步请求，并回复了一个更新的任期，leader 会退位回 follower，并更新任期；

• 倘若某个节点拒绝了同步请求，但回复了相同的任期，leader 会递归发送前一条日志给该节点，直到其接受同步请求为止；

• 倘若一个节点超时未给 leader 回复，leader 会重发这笔同步日志的请求.

心跳&提交同步请求

leader 周期性广播心跳证明自己还健在；同时日志提交的进度.

follower 重置 leader 心跳检测计时器. 查看 leaderCommit, 看是否有预写日志可以被提交.

外部请求链路梳理

写入

1. 写操作需要由 leader 统一收口. 倘若 follower 接收到了写请求，则会告知客户端 leader 的所在位置（节点 id），让客户端重新将写请求发送给 leader 处理；

2. leader 接收到写请求后，会先将请求抽象成一笔预写日志，追加到预写日志数组的末尾；

3. leader 会广播向集群中所有节点发送同步这笔日志的请求，即第一阶段的提议

4. follower 将日志同步到本机的预写日志数组后，会给 leader 回复一个“同步成功”的ack；

5. leader 发现这笔请求对应的预写日志已经被集群中的多数派（包括自身）完成同步时，会”提交“该日志，并向客户端回复“写请求成功”的 ack.

6.在后续的发送心跳的过程中，leader会带上最新的commit index，follower接收到之后更新自己的commit index

leader 任期滞后.

在第（4）步中，倘若 follower 发现当前 leader 的 term 小于自己记录的最新任期，follower 会拒绝 leader 的这次同步请求，并在响应中告知 leader 当前最新的 term；leader 感知到新 term 的存在后，也会识相地主动完成退位.

follower 日志滞后.

同样在第（4）步中，此时虽然 leader 的 term 是最新的，但是在这笔最新同步日志之前， follower 的预写日志数据还存在缺失的数据，此时 follower 会拒绝 leader 的同步请求；leader 发现 follower 响应的任期与自身相同却又拒绝同步，会递归尝试向 follower 同步预写日志数组中的前一笔日志，直到补齐 follower 缺失的全部日志后，流程则会回归到正常的轨道.

follower 日志”超前“.

同样在第（4）步中，leader 的 term 是最新的，但是 follower 在 leader 最新同步日志的索引及其之后已存在日志，且日志内容还与当前 leader 不一致. 此时 follower 需要移除这部分”超前“的日志，然后同步 leader 传送的日志，向当前在任 leader 看齐.

读

raft 标准模型中，客户端的读请求可以被集群中的任意节点处理，最终会取状态机中的数据进行响应. 由于预写日志 二阶段提交 多数派原则的机制保证了被提交的日志具有最终一致性，而只有被提交的日志才有资格被应用到状态机，因此状态机的数据也必然具有最终一致性，倘若想要升级为 即时一致性，就需要在写流程和读流程中都做些额外的处理.

• appliedIndex 校验：每次 leader 处理写请求后，会把最晚一笔应用到状态机的日志索引 appliedIndex 反馈给客户端. 后续客户端和 follower 交互时，会携带 appliedIndex. 倘若 follower 发现自身的 appliedIndex 落后于客户端的 appliedIndex，说明本机存在数据滞后，则拒绝这笔请求，由客户端发送到其他节点进行处理.

• 强制读主：follower 收到读请求时，也统一转发给 leader 处理. 只要 leader 处理写请求时，保证先写状态机，后给客户端响应，那么状态机的数据可以保证即时一致性. 但是这样的弊端就是 leader 的压力过大，其他 follower 节点只沦为备份数据副本的配角.

同时，这种强制读主的方案还存在一个问题，就是领导者在处理读请求时，需要额外对自己做一次合法性身份证明. 这是因为倘若当前网络出现分区情况，而 leader 仍坐落于小分区，那么此时提供的读服务就无法保证即时一致性，会退化为最终一致性.解决这个问题的方案是，leader 提供读服务时，需要额外向集群所有节点发起一轮广播，当得到多数派的认可，证明自己身份仍然合法时，才会对读请求进行响应.

集群变更

1. leader 发起提议（proposal），将配置变更的日志广播给集群中的所有节点. 配置变更的明细参数形如 ${变更前集群的节点名单}_${新加入的集群节点名单}，需要能明确标识出哪些节点是原有的老节点，哪些节点是新加入的节点；

2. 当配置变更的提议要被老节点中的多数派认可时，leader 才会提交（commit）配置变更动作，在配置参数中将新老两部分节点的名单合并到一起；

3. 在配置变更期间，leader 选举时，需要获得老节点中多数派的赞同票，才能当选；

4. 配置变更期间，处理写请求时，需要在提议阶段获得老节点中多数派的认可，才能进行提交.

脑裂

动画演示

当出现网络分区时，Raft 可以避免脑裂

这篇好文章是转载于：学新通技术网