Eureka
0%

basic raft protocol

发表于 更新于 分类于

01 Basic Raft协议

本文目标：分享笔者自己对Basic Raft的流程和设计目的。为了降低复杂度，本次不涉及任何性能优化和成员变更，只关注正确性（也称safety）

引言

多副本机制是提高系统容灾能力的手段之一。使用多副本机制引入一个新的问题——如何让不同副本的数据保持一样。客观上，副本之间有快有慢，数据会存在不一样的时刻（苛求数据同时写入所有副本本身就是不可能的）。通过共识协议解决副本之间的数据一致性问题：我们可以通过共识算法对用户屏蔽副本之间的差异，最理想的情况就是用户使用起来和单副本没区别，感知不到副本的存在。

不少项目如etcd、TiDB等均采用Raft作为他们的共识协议。本文基于Ongaro的博士论文中的第三章，首先介绍basic Raft（后文均简称Raft）的流程；然后结合笔者自己的理解，讨论协议的设计思路；最后简单讨论协议的正确性。

Basic Raft

Raft使用复制状态机（replicated state machine）来对副本进行抽象。关于复制状态机的定义我们这里就不展开介绍，如果感兴趣推荐阅读Leslie Lamport的Time, Clocks and the Ordering of Events in a Distributed System

这里我们以KV数据库为例，每个副本都是一个独立的KV数据库，这个数据库用状态机来表示。每个状态机有一个输入序列（后文也会称replicated log），序列中的每一个动作是一个对数据库的变更，比如set(x) = 10。所有状态机从一个统一的初态开始，读取输入序列中的动作依次执行。

假设不同状态机的输入序列中是完全一样，可以预见的是：每个状态机执行到相同位置的动作时，不同节点的数据库是一摸一样的。

那么如何保证输入序列中是完全一样呢？由Raft来保证为所有复制状态机提供一个完全一致的replicated log，从而间接实现所有副本的数据是一致的。

那么我们怎么评价一个共识是正确的呢？与算法的正确性类似，算法存在一个不变式，在运行过程中要一直保持该不变式不被打破，可以认为该算法是正确的。这样的不变式在分布式协议中通常被叫做Safety属性。这里我们可以给出State Machine Safety来定义复制状态机的一致性，在Raft运行过程中，要保证时刻满足State Machine Safety，否则都会让副本出现不一致的状态。

State Machine Safety

If a server has applied a log entry at a given index to its state machine, no other server will ever apply a different log entry for the same index.

Overview

一个Raft共识组内有n个副本（n一般为3或5）。Raft协议首先通过选举算法选出一个leader，由leader负责日志同步——leader接受client的写请求封装为日志，然后将该日志发送到所有副本；当leader感知到超过一半的节点都成功写入该日志后，向client返回ack确认。这个ack向client保证该日志被保存在大多数个副本上的replicated log中相同的位置上。每个节点会异步将日志提交到状态机。

leader节点的存在可以简化复制流程：leader全权决定在每个日志的位置。如果出现follower的日志和leader不一样的情形时，follower会丢弃自己的日志，重新从leader同步；整个数据流也会很简单——leader单向流动到其他非leader节点。

可以预见的是，如果leader出现异常，整个复制流程都会停滞，系统会进入不可用状态。选举算法不仅要保证选出一个新的leader来恢复写入外，还需要保证“无损”，即保证State Machine Safety不被打破。

定义

副本状态

Raft协议将副本分为3个状态：leader、follower和candidate，副本在任意时刻只会处于其中一个状态。状态跃迁图如下所示。

  • follower：节点启动/进入一个新term后的状态。follower不会向外发送消息，只会被动接受leader的日志同步或者candidate的投票请求
  • candidate：节点开启选举的状态。在该状态，candidate会向所有节点广播投票请求
  • leader：节点当选leader的状态。leader会定期向所有节点广播心跳消息，和处理client的读写请求

逻辑时钟

Raft协议将时间划分为无限多个term，每个term的时间不固定，可长可短，但是每个term内至多有一个leader节点（也可以没有leader）。每个节点各自维护term，发往其他节点的消息都会附带自己当前的term。接受者会拒绝小于自己term的消息，如果收到一个包含更大term的消息，会将自己的term更新为更大的值，同时将副本状态设置为follower。

可以将term看作节点之间的逻辑时钟。

日志

Raft将日志定义为一个三元组<term, index, command>，每个节点都维护自己的 replicated logs，有下面几个约束：

  1. 日志连续无空洞 => index值连续
  2. 任意两个日志可比: a < b => a.term < b.term || a.index < b.index
    1. a < b，理解为a在b前面/更早追加到队列中或者a比b旧。

日志复制协议

本节我们介绍Raft协议日志复制的详细流程，不妨先假设我们存在一个完美的leader选举算法，确保我们任何在任意一个term内至多只存在一个leader，且任意一个leader都不会打破State Machine Safety。

在Raft中，leader节点始终只会追加数据，不会对已有的数据有任何修改。而follower节点无条件接受leader的数据，当出现相同index的日志存在冲突时，也以leader数据为主。整个复制流程如下：

  1. leader节点收到客户端的请求/command后，将其追加到自己的replicated log中，这时候可以确定该command的index
  2. 然后并行向所有节点同步这条日志
  3. 当leader节点收到过半节点（包括leader）的ack后，就可以向客户端返回ack确认。

当client收到写请求的ack，意味着这条日制被leader判定为committed——这个日志可以安全地提交到状态机上，即满足State Machine Safety属性。那么leader如何判断一个日志committed呢？一共有两个规则，任意一个满足即可：

  1. 如果该日志是leader当前term内发起同步的，那么leader收到该日志过半节点的ack（这里留一个小疑问，为什么要强调当前term？我们后面的章节再回答这个问题）
  2. （传递性）该日志后面的任意一个日志被判定为committed。

每个节点都会记录最后一条committed日志的index，记为commitIndex。leader根据上面的判定条件更新commitIndex，而follower从leader同步commitIndex。只有在commitIndex之前的消息才可以被状态机执行。每个副本会异步执行commitIndex之前的日志，每个节点会记录最后一条被执行完的日志的index，记为lastApplied。任何时刻都有lastApplied <= commitIndex成立。

响应读请求

在Raft中，由Leader处理client的读请求（可以做follower read优化）：当client发出一个读请求时，leader会从状态机中完成读请求，然后将结果返回给client。我们仍以一个KV数据库为例，写请求可以表示为set(key) = val的操作，读请求表示为read(key)。写请求会被leader通过复制协议追加到所有副本的replicated log中，而读请求则会从leader的KV数据库中读取对应key的值。

但是当一个写请求（例如set(x) = 10）收到leader的ack，并不意味着这时候发出一个读请求（例如 read(x)）就能马上得到10。因为Raft是将请求写入日志和日志被状态机执行分开，日志被状态机执行并不在写请求的处理路径上。

但是当用户在t1时刻写入一个值，很希望在t1之后就能够读到这个值，不会再读到t1之前的值。线性一致性可以满足这个需求（关于一致性的讨论推荐阅读Replication（上）常见复制模型&分布式系统挑战）。

这里给一个Raft实现线性一致性的方案：leader在收到读请求时，如果发现lastApplied < commitIndex，说明状态机还有已经commit的日志没有执行，那么会先执行这些日志，然后再处理读请求。

容易得到：在同一个leader内，线性一致性读这个约束很容易保证：读写请求都由leader处理。但是如果发生leader切换，为了保证线性一致性，就要求new leader.lastApplied >= old leader.lastApplied。

这里的介绍非常浅显&不严谨，实际上线性一致性读在Raft工程实践有很多优化，受限于篇幅在此不展开讨论，如果感兴趣可以阅读论文6.4和https://cn.pingcap.com/blog/lease-read。

选举算法

本节我们介绍Raft的选举算法。通过上文的日志复制，我们可以发现leader在Raft中扮演非常重要的角色。在介绍日志复制时，我们假设存在一个完美的选举算法选出一个正确的leader——任意一个term内至多只存在一个leader，且任意一个leader都不会打破State Machine Safety。我们通过下面两个反例，来看这两个条件被打破后对safety的挑战：

  1. 同一个term内如果有多个leader节点同时存在。会发生同一个index被不同的leader写入成功，然后给client返回ack，但是数据被另一个leader覆盖，副本之间的replicated log不一致；

  1. 新leader打破State Machine Safety，意味着新leader没有历史leader committed的日志。如下图示例，S1和S2在1的位置已经已经commit&执行日志<1,1>，但是新leader S3没有<1,1>，它重新提交<2,1>，那么S3的副本状态机在第1条日志执行的是<2,1>，而S1、S2在第1条日志执行的是<1,1>，不满足State Machine Safety。

对应的，这里给出两个选举算法的safety属性：Election Safety和Leader Completeness。Election Safety避免同一个term内多leader的现象，从而保证在一个term内所有committed的日志在所有副本都是一致的；Leader Completeness则保证新leader拥有所有历史leader commit的日志。

Election Safety: At most one leader can be elected in a given term.

Leader Completeness: If a log entry is committed in a given term, then that entry will be present in the logs of the leaders for all higher-numbered terms.

现在我们可以提出各种各样的选举算法，只需要保证：当选举算法结束选出一个leader在开始处理请求前，一定满足这两个safety属性。

下面我们介绍Raft的leader选举算法。Raft选举算法最核心的策略：让有足够新日志的节点当选leader。

leader节点会定期给所有节点发送心跳消息，心跳消息附带term信息，向其他节点表明自己是该term的leader。如果任意一个follower节点持续一段时间内都没有接收到合法的leader心跳信息，那么这个follower就会开始选举流程，尝试竞选新term的leader。一个完整的选举流程如下：

  1. 自增当前的term，记为term’，设置选举倒计时；

  2. 将节点状态变更为candidate，向所有节点发出requestVote（请求中附带自己最后一条日志的term和index），尝试获取该节点的投票（默认自己给自己一票赞成票）；

  3. 如果收到过半的赞成票，将节点状态变更为leader，该节点当选term’的leader，整个选举流程结束；

  4. 否则，直到倒计时结束都没有完成流程或者收到一个不低于term‘的leader心跳/日志复制，该节点都会退回follower状态，结束这一轮term’的选举。

只有follower状态的节点才会响应candidate的请求投票，如果candidate拥有的日志比自己的新，follower会回复candidate赞成票，否则无视。每个follower在一个term至多投出一个赞成票，如果有多个candidate，那么follower只会给第一个满足规则的candidate投票。

在一轮选举中，可能会出现多个candidate或者candidate的日志太过落后，导致没有candidate能够赢得选举的情况，那这一轮term不会存在合法的leader，所有candidate会退回follower，然后等待下一次超时重新触发选举。

当一个candidate完成流程3，即收到过半的赞成票后，这时候就可以处理client的写请求了。那读请求呢？如果不需要线性一致性时，这时候新leader也可以开始响应读请求；如果需要线性一致性读，那么新leader此时不能处理读请求，因为无法确认自己的lastApplied是否超过old leader的lastApplied。但是新leader能够得到的信息是：自己一定有所有commit的日志。

简单证明 新leader一定有所有commit的日志

不妨假设：

一共有3个节点n1、n2、n3

0～10index的消息都已经被历史leader提交；

n3没有第10th的commit log，但是当选leader 。

10th log commit => 至少有2个节点同步了该日志，所以只能是n1、n2；

n3当选leader => 除了n3的赞成票外，n1或者n2至少有一个节点投赞成票，不妨假设是n1

=> n1（最后一条日志index是10）认为n3的日志（最后一条日志是9）比自己新，矛盾

那么新leader怎么找到一个安全的commitIndex呢？至少需要保证下面不等式成立。

(old leader.lastApplied <= old leader.commitIndex) < new leader.lastApplied <= new leader.commitIndex)

前文论述了新leader有历史所有leader commit的日志，那最安全的是把自己所有的日志都变为提交状态即可。要达到这个目的可以有两个思路：

  1. new leader将所有不确定提交的日志重新走复制流程。这里需要对committed的判断条件中的第一个条件放宽：如果该日志是leader当前term内发起同步的，那么leader收到该日志过半节点的ack即可认为该日志可以commit。

  2. 完成一个当前term下新日志的同步，通过提交规则中的传递性来确保之前所有的日志可以commit。

我们先描述第2个方法后者，在实践中这个日志一般是新leader主动追加一个特殊的日志no-op，日志的内容为空。当这个日志满足commit条件时——过半节点同步到该日志，那么该日志之前的所有日志也一定被同步，此时新leader能推导出，no-op的index一定大于old leader的commitIndex。

这里我们通过一个反例来论述第一个方法是不可行的：

  1. 在a中，S1当选term2的leader，正在同步日志<2,2>
  2. 在b中，S1刚完成<2,2>同步到S2后就宕机，此时S5能够获得S3、S4和S5的赞成票，当选term3的leader
  3. 在c中，S5成功当选term4的leader，它看到<2,2>但不确定是否commit，所以仍用<2,2>（注意这里不是<4,2>因为leader不能修改历史数据）来重新同步，收到3个ack后判断<2,2>可以commit，之后新写<4,2>
  4. 两个不同的时间线
    1. 在d1中，S1刚完成<2,2>的提交但没来得及同步<4,3>就宕机，这时S5恢复，并且成功当选term5的leader（因为S3最后一条日志的term是3，大于S2、S3、S4，能够获得足够的赞成票），开始重新同步<3,2>并且收到足够的ack，已经提交的<2,2>被覆盖，State Machine Safety被打破
    2. 在d2中，S1正常完成<2,2>和<4,3>的同步和提交。此时S5不可能当选leader

通过上面的反例，我们可以发现：对于历史term的日志，通过判断日志保存的副本数过半后就认为可提交是不安全的，所以在「日志复制协议」中的提交规则会加入在当前term的限制。

容灾

可以容忍不过半个节点故障/慢。Raft通过日志复制流程来解决follower节点故障的场景，通过leader选举来解决leader节点故障的场景。

https://raft.github.io/ 该网站可以可视化raft的运行，可以指定任意节点宕机、重启等

正确性/证明

如上文描述，State Machine Safety是我们的最终目标，State Machine Safety达成后就有线性一致性的基础，后续面临的挑战就是怎么对client屏蔽不同副本执行进度不一样。在前文介绍复制状态机时，我们看到如果不同状态机有相同的replicated log时，那么State Machine Safety是很容易满足的，相同的replicated log可以描述为Log Matching，即在不同节点，相同的位置及之前的日志都是一样的。

显然，Log Matching和日志复制相关，在日志复制流程中我们可以看到，在同一个term内，当Election Safety成立时，即只有一个leader，log Matching显然成立，因为leader只会追加数据。如果不发生leader切换，那就是一个完美的结局。。

一旦发生leader切换，为了保证Log Matching不被打破，我们很自然地要求新leader拥有旧leader commit的日志，即Leader Completeness。

所以在论证Raft正确性时，Election Safety和Leader Completeness是两个需要证明的关键点，上文也对Leader Completeness有一个简单描述，这里就不详细展开了，感兴趣的同学可以阅读论文3.6.3节和论文B.3附录中的lemma2和lemma 8的证明。（反证法，利用复制的majority和leader选举的majority一定有交集制造矛盾点，老套路了）

Election Safety: At most one leader can be elected in a given term.

Log Matching: If two logs contain an entry with the same index and term, then the logs are identical in all entries up through the given index.

Leader Completeness: If a log entry is committed in a given term, then that entry will be present in the logs of the leaders for all higher-numbered terms.

State Machine Safety: If a server has applied a log entry at a given index to its state machine, no other server will ever apply a different log entry for the same index.

后续TODO

basic raft加了许多限制来让协议简单，但是离实践可用还需要很多优化，如preVote、线性一致性读等。预计在2023年底来尝试总结下实践raft遇到的问题及对应优化思路。