分布式系统从理论到实战
首页 死磕 Java 优质系列 Java 技术总览 Java 面试宝典 关于我

分布式基础（五）——分布式理论之分布式一致性：Raft算法原理

转
 2023-08-12  阅读(2)
©版权
原文作者：Ressmix 原文地址：https://www.tpvlog.com/article/63

上一章，我已经带大家了解了Paxos算法，Paxos算法过于晦涩，在工业应用中比较少，比较有名的是Google Chubby。但是Paxos算法的思想非常重要，本章我要介绍的Raft算法就是基于Multi-Paxos 思想实现的。

Raft算法在理解和实现上都要比Paxos容易得多，也是现在分布式系统开发首选的共识算法，掌握Raft算法，可以得心应手地处理绝大部分场景的容错和一致性需求，比如分布式配置系统、分布式 NoSQL 存储等等。

在讲解Raft算法之前，我建议读者先看看下面这个教程，然后再来看我的文章，这是我认为对Raft算法讲解最生动的教程：Raft: Understandable Distributed Consensus，也便于你理解我接下来要讲的内容。

一、角色

Raft 算法是通过”一切以领导者为准“的方式，实现一系列值的共识和各节点日志的一致。 Raft算法的核心就是通过 选举 来达成一致性，该算法一共涉及三种角色（状态）、两大过程（Leader Election、Log Replication）。

我们先来看下Raft算法涉及的角色，在Raft算法中，所有节点都有三种状态，状态之间可以互相转换。

202308122212591971.png

节点的状态流转见下图：

202308122213000392.png

1.1 Follower（跟随者）

Raft协议刚开始时，所有节点都是Follower，默默地接收和处理来自Leader的消息，当等待Leader心跳信息超时的时候，就主动站出来，推荐自己当Candidate。

1.2 Candidate（候选人）

Candidate将向其他节点发送投票请求（RequestVote），通知其他节点来投票，如果赢得了大多数（N/2+1）选票，就晋升Leader。

1.3 Leader（领导者）

Leader主要负责处理客户端请求，进行日志复制等操作，每一轮选举的目标就是选出一个Leader；Leader会不断地发送心跳信息，通知其他节点“我是领导者，我还活着，你们现在不要发起新的选举，找个新领导者来替代我。”

二、Leader Election（领导者选举）

2.1 选举流程

1.首先，在初始状态下，集群中所有的节点都是 Follower 状态，并被设定一个随机 election timeout （150ms-300ms）：

202308122213008353.png

2.如果超时时间到期后没有收到来自Leader的心跳，节点就发起选举：将自己的状态切换为 Candidate ，增加自己的任期编号，然后向集群中的其它 Follower 节点发送请求，询问其是否选举自己成为 Leader：

202308122213016844.png

3.其他节点接收到候选人 A 的请求投票消息后，如果在编号为 1 的这届任期内还没有进行过投票，那么它将把选票投给节点 A，并增加自己的任期编号：

202308122213025535.png

4.当收到来自集群中过半数节点的接受投票后，节点即成为本届任期内 Leader，他将周期性地发送心跳消息，通知其他节点我是Leader，阻止Follower发起新的选举：

202308122213031866.png

如果在指定时间内（一个随机时间，每个节点都不同），Follower没有接收到来自Leader的心跳消息，那么它就认为当前没有Leader，推举自己为Candidate，发起新一轮选举。

2.2 通信方式

在 Raft 算法中，节点之间的通信采用的是RPC方式，在Leader选举中，需要用到两类RPC：

  1. 请求投票（RequestVote）RPC：由Candidate在选举期间发起，通知各Follower进行投票；
  2. 日志复制（AppendEntries）RPC：由Leader发起，用来进行日志复制和心跳。

2.3 任期

在选举流程中，我提到Leader节点是有任期的，每个任期由单调递增的数字标识，比如节点 A 的任期编号是 1。任期编号是随着选举的举行而变化的：

  1. Follower在等待Leader的心跳信息超时后，会推举自己为Candidate，此时会增加自己的任期编号；
  2. 如果一个节点发现自己的任期编号比其他节点小，那么它会更新自己的编号为较大的编号值。比如节点 B 的任期编号是 0，当收到来自节点 A 的请求投票消息时，因为消息中包含了节点 A 的任期编号，且编号为 1，那么节点 B 将把自己的任期编号更新为 1。
  3. 当任期编号相同时，日志完整性高的Follower（也就是最后一条日志项对应的任期编号值更大，索引号更大），拒绝投票给日志完整性低的Candidate。

三、Log Replication（日志复制）

在 Raft 算法中，副本数据是以日志的形式存在的，Leader接收到来自客户端写请求后，处理写请求的过程就是一个日志复制的过程。

3.1 日志项

日志是由 日志项 组成的，那么日志项究竟是什么样子呢？

日志项是一种数据格式，它主要包含客户端的指令（Command），还有索引值（Log index）、任期编号（Term）等信息：

202308122213037467.png

从上图可以看到，一届领导者的任期中，往往有多条日志项，而且日志项的索引值是连续的，

3.2 复制流程

  1. 首先，当Leader节点接收到客户端的写请求后，会创建一个新日志项，并附加到本地日志中；
  2. Leader通过日志复制（AppendEntries）RPC 消息，将日志项复制到集群其它Follower节点上；
  3. 如果Leader接收到大多数的“复制成功”响应后，它将日志项应用到自己的状态机，并返回成功给客户端。如果Leader没有接收到大多数的“复制成功”响应，那么就返回错误给客户端；
  4. 当Follower接收到心跳信息，或者新的AppendEntries消息后，如果发现Leader已经提交了某条日志项，而自己还没应用，那么Follower就会将这条日志项应用到本地的状态机中。

202308122213051698.png

从上面这个过程可以看出，当Follower节点接受Leader的心跳消息或者AppendEntries消息后，会将日志项应用到自己的状态机。这个优化，降低了处理客户端请求的延迟，将二阶段提交优化为了一段提交，降低了一半的消息延迟。

3.3 一致性检查

在 Raft 算法中，Leader通过强制Follower直接复制自己的日志项，处理不一致日志。具体有 2 个步骤：

  1. 首先，Leader通过AppendEntries消息，找到Follower节点上与自己相同日志项的最大索引值。也就是说，这个索引值之前的日志，Leader和Follower是一致的，之后的日志是不一致的了。
  2. 然后，Leader强制Follower更新不一致日志项，实现日志的一致。

举个例子来理解下， 为了方便演示，我们引入 2 个新变量 ：

  • PrevLogEntry： 表示当前要复制的日志项的前一条日志项的索引值。比如下图中，如果Leader将索引值为8的日志项发送给Follower，那么此时 PrevLogEntry 值为 7；
  • PrevLogTerm： 表示当前要复制的日志项的前一条日志项的任期编号。比如下图中，如果Leader将索引值为8的日志项发送给Follower，那么此时 PrevLogTerm 值为 4。

202308122213058339.png

  1. 首先，Leader通过AppendEntries消息，发送当前最新的日志项到Follower，这个日志项的 PrevLogEntry 值为 7，PrevLogTerm 值为 4；
  2. 如果Follower在它的日志中，找不到PrevLogEntry 值为 7、PrevLogTerm 值为 4 的日志项，也就是说它的日志和Leader的不一致了，那么Follower就会拒绝接收新的日志项，并返回失败信息给Leader；
  3. 此时Leader会递减要复制的日志项的索引值，并发送新的日志项到Follower，这个消息的 PrevLogEntry 值为 6，PrevLogTerm 值为 3；
  4. 如果Follower在它的日志中，找到了 PrevLogEntry 值为 6、PrevLogTerm 值为 3 的日志项，那么AppendEntries消息返回成功，这样一来，Leader就知道在 PrevLogEntry 值为 6、PrevLogTerm 值为 3 的位置，Follower的日志项与自己相同；
  5. 最后， Leader通过AppendEntries消息，复制并更新覆盖该索引值之后的日志项（也就是不一致的日志项），最终实现了集群各节点日志的一致。

四、总结

本章，我对Raft算法的原理进行了详细讲解，Raft算法是Multi-Paxos 思想的落地，其核心就是领导者选举和日志复制。Raft 算法能很好地处理绝大部分场景的一致性问题，推荐大家在设计分布式系统时，优先考虑 Raft 算法，当 Raft 算法不能满足现有场景需求时，再去调研其他共识算法。

目前开源界对Raft算法的实现有很多，在生产环境落地较多并接受过大量检验的是 Hashicorp Raft ， 感兴趣的读者可以自行参考官方文档进行学习。

Java 面试宝典是大明哥全力打造的 Java 精品面试题，它是一份靠谱、强大、详细、经典的 Java 后端面试宝典。它不仅仅只是一道道面试题，而是一套完整的 Java 知识体系，一套你 Java 知识点的扫盲贴。

它的内容包括：

  • 大厂真题：Java 面试宝典里面的题目都是最近几年的高频的大厂面试真题。
  • 原创内容：Java 面试宝典内容全部都是大明哥原创，内容全面且通俗易懂，回答部分可以直接作为面试回答内容。
  • 持续更新：一次购买，永久有效。大明哥会持续更新 3+ 年，累计更新 1000+，宝典会不断迭代更新，保证最新、最全面。
  • 覆盖全面：本宝典累计更新 1000+，从 Java 入门到 Java 架构的高频面试题，实现 360° 全覆盖。
  • 不止面试：内容包含面试题解析、内容详解、知识扩展，它不仅仅只是一份面试题，更是一套完整的 Java 知识体系。
  • 宝典详情：https://www.yuque.com/chenssy/sike-java/xvlo920axlp7sf4k
  • 宝典总览：https://www.yuque.com/chenssy/sike-java/yogsehzntzgp4ly1
  • 宝典进展：https://www.yuque.com/chenssy/sike-java/en9ned7loo47z5aw

目前 Java 面试宝典累计更新 400+ 道，总字数 42w+。大明哥还在持续更新中，下图是大明哥在 2024-12 月份的更新情况：

想了解详情的小伙伴，扫描下面二维码加大明哥微信【daming091】咨询

同时，大明哥也整理一套目前市面最常见的热点面试题。微信搜[大明哥聊 Java]或扫描下方二维码关注大明哥的原创公众号[大明哥聊 Java] ，回复【面试题】 即可免费领取。

阅读全文
文章标签： 分布式架构设计