浅谈分布式一致性算法 Raft

  • 五分钟学SRE

    2022-03-25 09:15:00
  • 数据库开发技术
  • 原创

文章目录

1，什么是一致性算法

2，raft简介

3，服务器角色

4，term

5，RPC

6，Leader选举

7，日志复制

    A，日志的前提条件与格式

    B，日志请求流程

    C，State Machine Safety


什么是一致性算法

    在只使用单个服务器时容易由于发生错误导致数据丢失等事情发生，解决数据单点问题就是备份，将操作重复到多个机器上就不怕单个机器出错了。但随之而来的就是，数据不一致、乱序等问题，一致性算法想要做到的是即使有结点出错，对外仍是一个完整的可以正常工作的整体。

    Raft 是一个非拜占庭的一致性算法，即所有通信是正确的而非伪造的。N 个结点的情况下（N为奇数）可以最多容忍 (N−1)/2(N−1)/2 个结点故障。



    Raft 正常工作时的流程如上图，也就是正常情况下日志复制的流程。Raft 中使用 日志 来记录所有操作，所有结点都有自己的日志列表来记录所有请求。算法将机器分成三种角色：Leader、Follower 和 Candidate。正常情况下只存在一个 Leader，其他均为 Follower，所有客户端都与 Leader 进行交互。

    所有操作采用类似两阶段提交的方式，Leader 在收到来自客户端的请求后并不会执行，只是将其写入自己的日志列表中，然后将该操作发送给所有的 Follower。Follower 在收到请求后也只是写入自己的日志列表中然后回复 Leader，当有超过半数的结点写入后 Leader 才会提交该操作并返回给客户端，同时通知所有其他结点提交该操作。

    通过这一流程保证了只要提交过后的操作一定在多数结点上留有记录（在日志列表中），从而保证了该数据不会丢失。

Raft简介

    Raft 是一种为了管理日志复制的分布式一致性算法,Raft 可以解决分布式 CAP 理论中的 CP，即 一致性（C：Consistency） 和 分区容忍性（P：Partition Tolerance），并不能解决 可用性（A：Availability） 的问题。

Raft将一致性分解为多个子问题：

Leader election:

  • 选择一台机器作为leader

  • 检测crash, 选择新leader

Log复制 (Log replication)

  • Leader 接受client发来的请求, 追加到自己的log

  • Leader 将log复制到其他机器 (overwrites inconsistencies)

安全性（Safety）

  • 保持log一致

  • 只有持有最新log的服务器能成为leader

日志压缩（Log compaction）

成员变更（Membership change）

Raft implements consensus by first electing a distin- guished leader, then giving the leader complete responsi- bility for managing the replicated log. The leader accepts log entries from clients, replicates them on other servers, and tells servers when it is safe to apply log entries to their state machines. Having a leader simplifies the man- agement of the replicated log. For example, the leader can decide where to place new entries in the log without con- sulting other servers, and data flows in a simple fashion from the leader to other servers. A leader can fail or be- come disconnected from the other servers, in which case a new leader is elected


服务器角色

Raft将系统中的角色分为领导者（Leader）、跟从者（Follower）和候选人（Candidate）：

  • Leader：接受客户端请求，并向Follower同步请求日志，当日志同步到大多数节点上后告诉Follower提交日志。

  • Follower：接受并持久化Leader同步的日志，在Leader告之日志可以提交之后，提交日志。

  • Candidate：Leader选举过程中的临时角色。

Raft要求系统在任意时刻最多只有一个Leader，正常工作期间只有Leader和Followers。

Raft算法角色状态转换如下：

Server states. Followers only respond to requests from other servers. If a follower receives no communication, it becomes a candidate and initiates an election. A candidate that receives votes from a majority of the full cluster becomes the new leader. Leaders typically operate until they fail.

图来自https://web.stanford.edu/~ouster/cgi-bin/papers/raft-atc14

Term

    Raft算法将时间分为一个个的任期（term），每一个term的开始都是Leader选举。在成功选举Leader之后，Leader会在整个term内管理整个集群。如果Leader选举失败，该term就会因为没有Leader而结束。

    

    Time is divided into terms, and each term begins with an election. After a successful election, a single leader manages the cluster until the end of the term. Some elections fail, in which case the term ends without choosing a leader. The transitions between terms may be observed at different times on different servers.

    每一段任期从一次选举开始。Raft 保证了在一个给定的任期内，最多只有一个领导者。

    如果选举成功，Leader 会管理整个集群直到任期结束。如果选举失败，那么这个任期就会因为没有 Leader 而结束。

RPC

    Raft 算法中服务器节点之间的通信使用 远程过程调用（RPC）。基本的一致性算法只需要两种 RPC：

RequestVote RPC - 请求投票 RPC，由 Candidate 在选举期间发起。AppendEntries RPC - 附加条目 RPC，由 Leader 发起，用来复制日志和提供一种心跳机制。



Leader选举

    Raft 使用心跳（heartbeat）触发Leader选举。当服务器启动时，初始化为Follower。

    每个 Follower 都设置了一个随机的竞选超时时间，一般为 150ms ~ 300ms

    Leader向所有Followers周期性发送heartbeat。如果Follower在选举超时时间内没有收到Leader的heartbeat，就会等待竞选时间超时后发起一次Leader选举。


    Follower将其当前term加一然后转换为Candidate。它首先给自己投票并且给集群中的其他服务器发送 RequestVote RPC （RPC细节参见八、Raft算法总结）。结果有以下三种情况：

赢得了多数的选票，成功选举为Leader；收到了Leader的消息，表示有其它服务器已经抢先当选了Leader；没有服务器赢得多数的选票，Leader选举失败，等待选举时间超时后发起下一次选举。

日志复制

日志的前提条件与格式

    选举出leader后，系统进入对外工作期。客户端的一切请求来发送到leader，leader来调度这些并发请求的顺序，并且保证leader与followers状态的一致性。raft中的做法是，将这些请求以及执行顺序告知followers。leader和followers以相同的顺序来执行这些请求，保证状态一致。

    日志由含日志索引（log index）的日志条目（log entry）组成。每个日志条目包含它被创建时的 Term 号，和一个复制状态机需要执行的指令。如果一个日志条目被复制到半数以上的服务器上，就被认为可以提交（Commit）了。

    日志条目中的 Term 号被用来检查是否出现不一致的情况。

    日志条目中的日志索引（一个整数值）用来表明它在日志中的位置。

    Raft 保证了如下几点：

Leader 绝不会覆盖或删除自己的日志，只会追加 （Leader Append-Only）如果两个日志的 index 和 term 相同，那么这两个日志相同 （Log Matching）如果两个日志相同，那么他们之前的日志均相同


第一点主要是因为选举时的限制，根据 Leader Completeness，成为 Leader 的结点里的日志一定拥有所有已被多数节点拥有的日志条目，所以先前的日志条目很可能已经被提交，因此不可以删除之前的日志。

第二点主要是因为一个任期内只可能出现一个 Leader，而 Leader 只会为一个 index 创建一个日志条目，而且一旦写入就不会修改，因此保证了日志的唯一性。

第三点是因为在写入日志时会检查前一个日志是否一致。换言之就是，如果写入了一条日志，那么前一个日志条目也一定一致，从而递归的保证了前面的所有日志都一致。从而也保证了当一个日志被提交之后，所有结点在该 index 上提交的内容是一样的（State Machine Safety）。


日志请求流程

  从leader的视角来看会经历以下步骤：

leader append log entryleader issue AppendEntries RPC in parallelleader wait for majority responseleader apply entry to state machineleader reply to clientleader notify follower apply log


  日志的提交过程有点类似两阶段提交(2PC)，不过与2PC的区别在于，leader只需要大多数（majority）节点的回复即可，这样只要超过一半节点处于工作状态则系统就是可用的。

    如果 Follower 崩溃或者运行缓慢，再或者网络丢包，Leader 会不断的重复尝试发送 AppendEntries RPC 请求 （尽管已经回复了客户端），直到所有的跟随者都最终复制了所有的日志条目。


State Machine Safety

  如果节点将某一位置的log entry应用到了状态机，那么其他节点在同一位置不能应用不同的日志。简单点来说，所有节点在同一位置（index in log entries）应该应用同样的日志。但是似乎有某些情况会违背这个原则：

上图是一个较为复杂的情况。

    在时刻(a), s1是leader，在term2提交的日志只赋值到了s1 s2两个节点就crash了。

    在时刻（b), s5成为了term 3的leader，日志只赋值到了s5，然后crash。

    然后在(c)时刻，s1又成为了term 4的leader，开始赋值日志，于是把term2的日志复制到了s3，此刻，可以看出term2对应的日志已经被复制到了majority，因此是committed，可以被状态机应用。

    不幸的是，接下来（d）时刻，s1又crash了，s5重新当选，然后将term3的日志复制到所有节点，这就出现了一种奇怪的现象：被复制到大多数节点（或者说可能已经应用）的日志被回滚。

  究其根本，是因为term4时的leader s1在（C）时刻提交了之前term2任期的日志。为了杜绝这种情况的发生：

引用论文的原话

Raft never commits log entries from previous terms by counting replicas.Only log entries from the leader’s current term are committed by counting replicas;once an entry from the current term has been committed in this way, then all prior entries are committed indirectly because of the Log Matching Property.

  也就是说，某个leader选举成功之后，不会直接提交前任leader时期的日志，而是通过提交当前任期的日志的时候“顺手”把之前的日志也提交了，具体怎么实现了，在log matching部分有详细介绍。那么问题来了，如果leader被选举后没有收到客户端的请求呢，论文中有提到，在任期开始的时候发立即尝试复制、提交一条空的log

  因此，在上图中，不会出现（C）时刻的情况，即term4任期的leader s1不会复制term2的日志到s3。而是如同(e)描述的情况，通过复制-提交 term4的日志顺便提交term2的日志。如果term4的日志提交成功，那么term2的日志也一定提交成功，此时即使s1crash，s5也不会重新当选。

参考文章

https://github.com/maemual/raft-zh_cn/blob/master/raft-zh_cn.md

https://www.cnblogs.com/xybaby/p/10124083.html

https://cloud.tencent.com/developer/article/1814820?from=article.detail.1780034

请使用浏览器的分享功能分享到微信等