专栏首页分布式架构一致性算法 - Raft协议总述
原创

一致性算法 - Raft协议总述

​- 起源 -

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)
    • 如果节点将某一位置的日志应用到了状态机,那么其他节点在同一位置不能应用不同的日志。

Raft协议只能顺序一致性,因此业界在使用时做了很多优化。比如TiKV中使用了Raft,但做了非常多的优化,提高了Raft性能。阿里的另PolarDB,也是使用了改进版的Parallel-Raft,使Raft实现了并行提交的能力。 ​

​- 作者介绍 -

林淮川

毕业于西安交通大学;奈学教育《百万架构师训练营》讲师、企业级源码内源负责人,前大树金融高级架构师、技术委员会开创者、技术总监;前天阳宏业交易事业部技术主管;多年互联网金融行业(ToB)经验。

​​

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 一致性算法-Gossip协议实践(Memberlist)

    咱们上文简单说了Gossip协议的原始方案,在真实场景有几百种变种,比较常见的Gossip 协议实现框架有:

    林淮川
  • 一致性算法-Gossip协议详解

    Gossip protocol 也叫 Epidemic Protocol (流行病协议),是基于流行病传播方式的节点或者进程之间信息交换的协议。。Gossip ...

    林淮川
  • 一致性算法 - Distro协议在Nacos的实践

    本系列文章前面几篇已经总体介绍了一致性、AP的Gossip、CP的Raft。接下去咱们了解一个简单的AP协议:Distro协议。Distro是阿里巴巴的私有协议...

    林淮川
  • Hyperledger Fabric学习笔记02-网络节点的架构

    节点是区块链的通信主体,是一个逻辑概念。多个不同类型的节点可以运行在同一物理服务器上。有多种类型的节点:客户端、Peer节点、排序服务节点和CA节点。下图为网络...

    汐楓
  • 讨论帖:如果只有两个数据中心,使用 Raft 协议还有意义吗?

    对 Raft 有所了解的同学都知道,Raft 一般会使用奇数个节点,比如 3、5、7 等等。这是因为 Raft 是 一种基于多节点投票选举机制的共识算法,通俗地...

    PingCAP
  • redis 主从复制

    在分布式系统中,为了解决单点问题,通常会把数据复制多个副本部署到其他节点,以便满足故障恢复和负载均衡等需求。redis也是如此,它为我们提供了复制功能,实现了相...

    小手冰凉
  • 关于BUS通信系统的一些思考(三)

    好久没写总结啦,最近一段时间比较忙,抽出的空闲时间都在不断完善之前提到的一个进程间通信lib的想法和实现(libatbus)。

    owent
  • Java数据结构和算法(十)——二叉树

      接下来我们将会介绍另外一种数据结构——树。二叉树是树这种数据结构的一员,后面我们还会介绍红黑树,2-3-4树等数据结构。那么为什么要使用树?它有什么优点? ...

    IT可乐
  • 分布式进阶__详解zookeeper的配置文件

    initLimit=10  follower节点启动后与leader节点完成数据同步的时间

    矿泉水
  • 寻找红黑树的操作手册

    二叉树知识点回忆以及整理这篇文章中我们说过“二叉树是一个简单的二分查找,但其性能取决于二叉树的层数”。

    静默加载

扫码关注云+社区

领取腾讯云代金券