一致性算法 - Raft协议总述

原创

林淮川

修改于 2020-07-30 09:56:33

1.6K0

Raft协议起源于 2013 年斯坦福 Diego Ongaro和John Ousterhout的论文《In Search of an Understandable Consensus Algorithm》。作者表示因为Paxos 晦涩难懂且缺乏工程实现，所以要设计个既容易实现又利于学生学习的一致性算法。Raft 的数据一致性等价于 Multi Paxos，可以用于取代Paxos，并且证明可以提供与Paxos相同的容错性以及性能。

Raft协议是一种基于日志复制的一致性算法，通过选举领袖的方式来实现的。Raft协议设计首要目标是易于理解，所以采用了分解法（Raft流程可分解为选主、日志复制和安全）和状态空间简化（相较于 Paxos，Raft 减少了未定状态的数量）。

在Raft集群里，服务器可能会是这三种身份其中一个：

Leader(领袖者)：所有请求的处理者，Leader 接受 client的更新请求，本地处理后再同步至多个其他节点；
Follower(追随者) ：请求的被动更新者，从Leader接受更新请求，然后写入本地日志文件 Candidate(候选人) ：节点处于候选状态，正在竞选 Leader。

在正常情况下只会有一个领袖者节点，其他都是追随者节点。而领袖节点会负责所有外部的请求，如果是非领袖节点收到时，请求会被转发到领袖节点。

领袖节点会定时跟所有追随者节点发送心跳请求，让追随者知道集群领袖还在运作。而每个追随者都有一个倒计时器，当超过一定时间没有收到心跳，集群就会进入选举状态。

为了更好的理解Raft协议，我们讲Raft 协议常见的几个名词先优先解释下

2.1 任期

Raft协议将时间分成了一些任意长度的时间片，每个时间片称为term(任期)，term使用连续递增的编号的进行识别。任期出现切换的流程如下：

追随者节点将自己维护的current_term_id加1。
将自己的状态转成Candidate
发送RequestVote RPC消息(带上current_term_id) 给其它所有节点进行拉。

2.2 消息类型

RequestVote RPC：由选举过程中的候选人节点发起，用于拉取选票
AppendEntries RPC：由领袖者节点发起，用于复制日志或者发送心跳信号。

2.3 倒计时器

追随者节点自身会维护一个倒计时器，用于监测跟领袖者节点的心跳，本质是一种超时机制的实现。倒计时器有以下特点：

每个节点都有自己的倒计时器，且时间随机。
追随者节点每次收到心跳后都会重置倒计时器

2.4 复制状态机模型

在Raft协议中，复制状态机用于描述日志的变化，即：相同的初始状态 + 相同的输入 = 相同的结束状态。用于因此，在复制状态机模型下，只要保证了操作日志的一致性，我们就能保证该分布式系统状态的一致性。

Raft协议将一致性问题拆成数个子问题分开解决，让我们更容易理解和解决一致性问题：

领袖选举（英语：Leader Election）
- 通过选举机制，对Raft集群的节点进行领袖节点选举
日志复制（英语：Log Replication）
- 领袖节点接受来自client的命令，记录为日志；并复制给集群中的所有的追随者，并强制追随者的日志与leader保持一致。
安全性（英语：Safety）
- 通过一些措施确保系统的安全性，如确保所有状态机按照相同顺序执行相同命令的措施。

Raft协议通过复制状态机模型保证操作日志的一致性，为了保证数据一致性，上述三个问题的处理需要额外增加对应的规则约束：

选举安全性(Election Safty)
- 每一个任期内只能有一个领袖节点
日志叠加性(Leader Append-Only)
- 领袖节点只能追加日志，不能重写或者删除日志
日志匹配性(Log Maching)
- 领袖节点：发送的AppendEntry RPC消息携带 preLogIndex和preLogTerm两个信息
- 追随节点：收到消息时，首先判断它最新日志的index和term是否和rpc中的一样，如果一样，才会append.
日志完整性(Leader Completeness)
- 如果某个指令在某个任期中存储成功，则保证存在于领袖该任期之后的记录中。
- 不同节点，某个位置上日志相同，那么这个位置之前的所有日志一定是相同的。
状态安全性(State Machine Safety)
- 如果节点将某一位置的日志应用到了状态机，那么其他节点在同一位置不能应用不同的日志。