🪴 Quartz 4.0

Raft 简介

10 min read

1-Intro

基于 Multi-Paxos, Raft 的原理 更容易理解.

首先, Raft 认为一个一致性协议可以拆分为了三个大问题:

  1. 主从选举
  2. 日志的复制
  3. 安全性问题

2-Implementation

2-1 Leader Election

Raft 的实现有以下的关键点

  • 心跳和随机超时
  • 先来先服务
  • major
  • 一个 Term 中只能有一个 Leader

有3种角色，状态，任何一个 Node 在某个时间点，只能出于一种状态

  • Leader:
  • Candidate: 候选人
  • Follower:

有2类 Rpc:

  • RequestVote: 候选人给所有其他的节点发起投票
  • AppendEntries : Leader 发起, 用来复制日志

先举个例子.

假设这个时候的 term=1 , 一个 Node1 挂了

  • Node1 : 150ms 挂了
  • Node2: 200ms, 第一个发现，提升 term=2, 投给自己, 发送 RequestVote 请求给其他的
  • Node3: 300ms, 收到了请求, 发现了他的 term=2 更大，而且日志条目也不比自己要差, 就同意了 Node2, 所以 Node2 获取了 2票成功当选.

然后 Node=1 的恢复了，认为自己是 Leader, 发请求给 Node2, Node3

  • 由于 term=1 比当前的 2要小, 所以被二者拒绝
  • 同时 发现了自己落后，就剥夺自己的 leader 身份，直接降级为 follower, 开始去同步数据

基本理解之后，补充一些细节

  1. 领导者 周期性地向所有跟随者发送心跳消息（即不包含日志项的日志复制 RPC 消息），通知大家我是领导者，阻止跟随者发起新的选举。
  2. 如果在指定时间内，跟随者没有接收到来自领导者的消息，那么它就认为当前没有领导者，推举自己为候选人，发起领导者选举。? 只能推举自己 或者接收别人的请求
  3. 在一次选举中，赢得大多数选票的候选人，将晋升为领导者。? 多数即可,意味着奇数好一点
  4. 在一个任期内，领导者一直都会是领导者，直到它自身出现问题（比如宕机），或者因为网络延迟，其他节点发起一轮新的选举。
  5. 在一次选举中，每一个服务器节点最多会对一个任期编号投出一张选票，并且按照“先来先服务”的原则进行投票。比如节点 C 的任期编号为 3，先收到了 1 个包含任期编号为 4 的投票请求（来自节点 A），然后又收到了 1 个包含任期编号为 4 的投票请求（来自节点 B）。那么节点 C 将会把唯一一张选票投给节点 A，当再收到节点 B 的投票请求 RPC 消息时，对于编号为 4 的任期，已没有选票可投了。
  6. 日志完整性高的跟随者（也就是最后一条日志项对应的任期编号值更大，索引号更大），拒绝投票给日志完整性低的候选人。比如节点 B 的任期编号为 3，节点 C 的任期编号是 4，节点 B 的最后一条日志项对应的任期编号为 3，而节点 C 为 2，那么当节点 C 请求节点 B 投票给自己时，节点 B 将拒绝投票。
  7. 同一任期内，多个候选人同时发起选举，导致选票被瓜分，选举失败。那么在 Raft 算法中，如何避免这个问题呢？答案就是随机超时时间。

2-2 Log Copy

Raft 做了一个简化，是要求日志必须是连续的，比如说条目必须是 1,2,3,4,5,6

  • 类似 TCP, 一个流里面的强连续性
  • 如下图, 一个 LogEntries 包含如下字段

流程是这样的

• 日志复制：当领导者收到来自客户端的请求之后，它首先将该请求作为一个新的日志条目添加到自己的日志中（此时状态为未提交）。然后通过AppendEntries RPC将这个新的日志条目发送给所有其他的跟随者节点。

• 日志条目提交：当领导者从大多数（包含自身）的跟随者节点收到了对该日志条目的成功响应后，它会将该日志条目标记为已提交，并更新提交索引。接着它会再次通过AppendEntries RPC将这个最新的提交索引发送给所有的跟随者节点。

• 日志条目的应用：当领导者或跟随者的已提交索引大于等于某个条目的索引时，就说明这个条目已被提交，接下来可以安全地应用这个日志条目到状态机了。

理解

第一个 AppendEntries RPC 用来复制内容 第二个 是更新 CommitIndex 是所有的节点达成了基本的一致，按照这个顺序去更新

所以 Raft 实现是所谓的线性一致性，确保了所有的 节点复制日志和应用日志的顺序一定是一样的.

  1. 如果 client 仅仅和 leader 打交道，就是强 一致性
  2. 如果 client 去读取 follower, 就是线性 一致性

2-3 Consistency

一切想 leader 看齐，必须实现强连续的语义，一旦乱序，就回退重来. 否则直接标记当前的 node 挂了.

  • 首先，领导者通过日志复制 RPC 的一致性检查，找到跟随者节点上，与自己相同日志项的最大索引值。
  • 也就是说，这个索引值之前的日志，领导者和跟随者是一致的，之后的日志是不一致的了。然后，领导者强制跟随者更新覆盖的不一致日志项，实现日志的一致

举个失败处理的例子:

  1. 首先 leader 通过 日志复制 RPC 消息、发送最新的日志项当 follower, 假设这个消息的 PrevLogEntry = 7 , PrevLogTerm = 4
  2. 如果跟随者在日志中、查找不到 PrevLogEntry = 7 , PrevLogTerm = 4 ， 说明不一致了 ,那么 follower 就会拒绝掉 leader 发送的新的日志项、 返回失败给 leader
  3. 这个时候、leader 会递减要复制的索引值、PrevLogEntry = 6 , PrevLogTerm = 3
  4. 如果 follower 找到了 PrevLogEntry = 6 , PrevLogTerm = 3 . 那么日志复制 RPC 成功，这样一来，领导者就知道在 PrevLogEntry = 6 , PrevLogTerm = 3 的位置、follower 的日志和自己相同
  5. leader 通过复制 RPC 、 复制并且更新覆盖该索引值之后导入日志项、实现各节点的日志的一致 .

成员变更性问题.

  • 关于成员变更，不仅是 Raft 算法中比较难理解的一部分，非常重要，也是 Raft 算法中唯一被优化和改进的部分。比如，最初实现成员变更的是联合共识（Joint Consensus），但这个方法实现起来难，后来 Raft 的作者就提出了一种改进后的方法，单节点变更（single-server changes）。

  • 配置是成员变更中一个非常重要的概念，我建议你这么理解：它就是在说集群是哪些节点组成的，是集群各节点地址信息的集合。比如节点 A、B、C 组成的集群，那么集群的配置就是[A, B, C]集合

Graph View

Backlinks