光与影的个人博客

NEUCoder

0%

共识算法-Raft

发表于 更新于 分类于 ，

分布式共识算法-Raft

Raft是基于Paxos改进的共识算法，其最开始的设计目标即为容易理解且容易实行，所以相较于Paxos学起来更容易（确实比Paxos容易，但我还是看不懂啊）。

Raft中定义了三种角色：

  1. Leader：唯一的leader，负责与Client交互，在其他follower上备份log日志。
  2. Follower: 多个Follower，接收Leader的日志备份请求，当Leader出现问题时，选举成为新的leader。
  3. Candidate: 当Follower认为Leader失效时，Follower状态转换为Candidate，进行Leader的竞选。

Raft中只包括两种类型的RPC消息

  1. RequestVote RPC：参与选举的Candidate发送的选举消息
  2. AppendEntries RPC: Leader向Follower发送的添加日志信息

Raft的一般流程

算法主要包括两个步骤（均基于Majority Vote思想）

  1. Leader election: 选举出全局的Leader
  2. Log replication: 日志备份，每当Leader接收到Client的一个请求，Leader将日志成功的备份到多数Follower后，提交操作，向Client返回操作信息

基本流程

  1. Server集群启动，开始选举，部分Follower Server转化为Candidate状态向其他的Server发送RequestVote RPC
  2. 每个收到RequestVote RPC的Server按照”first come first serve”的原则，给对应的Candidate投票，获得过半投票的Candidate成为Leader
  3. Leader接受Client请求，写入log，并向其他Follower发送AppendEntries RPC备份log，保证所有server的state machine状态一致

Raft将时间划分为了固定的 “term”，不同服务器通过term作为逻辑时钟实现同步和一致性的保持

Leader election

要了解选举，首先要了解触发选举的条件，为了避免Leader崩溃导致的系统单点失效，Raft通过“heart beat”机制实现Leader状态的监控

  1. Leader周期性所有的Follower的发送heartbeart消息（不包含log的(AppendEntriesRPC）
  2. 每个Follower设定了一个 “election timeout” 超时时间，当Follower超过该时间为收到来自Leader的heartbeart消息时，该Follower认为Leader失效，发起选举。
  3. 服务器启动时初始化所有服务为Follower状态，并启动”election timeout”计时器

所以Leader election的触发时机为某个Follower超时，转化为Candiate状态

选举过程

Follower转化为Candidate后，开启新一轮选举，执行一下几个操作后，等待选举结果

  1. term增加1，代表进入下一个逻辑时间段
  2. 为自己投票
  3. 重置election timer
  4. 向其他Server发送RequestVote RPC，请求成为Leader

其他Server收到请求后，按照”first come first serve”原则向Candidate投票

  1. 若RequestVote RPC的term值小于当前term值，说明当前投票信息已过期，拒接投票

  2. 若未投过票，则未接收到的第一个 RV RPC投票，否则拒绝投票（”first come first serve”）

  3. election restriction：RequestVote RPC中的 more up-to-date，投票，否则拒绝

等待成为Leader的Candidate可能等到三种情况

  1. 收到了过半的投票（包括自己）-> 竞选成功，转换状态为Leader
  2. 收到了来自其他Server的term大小相同的AppendEntries RPC -> 其他Server竞选成功，转换状态为Follower
  3. 直到election timer超时也未收到上述两个情况响应 -> 进入下一轮选举

如果不断的重复出现3，也就是split votes问题

  • 多个candidate争抢，导致每个candidate均无法达到过半的票数
  • 解决方法：Raft使用随机选举超时机制（randomized election timeouts），错开不同的Follower成为Candidate的时机

一系列操作最终保证 Election Safety : 一个term内最多存在一个Leader

  • 一个term内可以不存在Leader
  • 系统同时可以存在多个leader，但每个leader一定是不同的term内选出的

Log replication

选举Leader的最终目的还是为了保证log的一致性，保证log的一致性是为了保证所有Server上state machine按照相同顺序执行相同操作以达到备份效果,Raft保证以下性质:

具体发送流程如下：

  1. Leader为每个Follower维护一个nextIndex，代表下一个AppendEntries RPC中要携带的log entry的index
  2. AppendEntries RPC中不止携带当前要添加的log entry(nextIndex指向的entry),还包括上一个log entry的term和index
  3. Follower判断当前的last entry是否与AppendEntries RPC中携带的上一个log entry的term和index（Consistent Check）
    • 一致 接受添加
    • 不一致 拒绝添加
  4. Leader 根据 Follower的响应信息，进行下一步操作
    • 若Follower拒绝，将nextIndex - 1
    • 若Follower接受，将nextIndex + 1
  5. Leader不断发送AppendEntries RPC， 直到Follower的nextIndex等于Leader的last log entry

commit时机：

  1. Leader收到超半数接受信息后即commit当前log entry

  2. Follower根据AppendEntries RPC中携带的leaderCommit号，更新自身的commitIndex，若leaderCommit > commitIndex,将commitIndex目标值

  3. 当Follower检测到 lastApplied小于commitIndex,提交lastApplied的log,并自增lastApplied

特殊情况：Raft不会提交历史主动term的日志

  • 非常难理解这么做的原因（知乎回答 + 论文中的图8 可以促进理解）
  • 我的理解：如果一个历史日志没有提交，却在当前Leader中携带，那么有两种可能的情况
    1. 历史日志未备份到多数派，其任期内的Leader就崩溃
      • 该情况下，历史任期 $Leader_{history}$和当前$Leader_{current}$中间存在空窗期，由于历史日志未备份到多数派，空窗期内可能选举出一个不含历史日志的$Leader_{mid}$,，即Leader转化流程为 $Leader_{history}-> Leader_{mid} ->Leader_{current}$
      • $Leader_{current}$ 任期内未提交日志，$Leader_{mid}$ 就有可能再次当选为leader，此时若写入新日志，就会导致历史日志被覆盖
      • 如果$Leader_{current}$ 提交了历史日志，日志覆盖就导致了提交丢失
      • 如果$Leader_{current}$ 提交了当前任期的日志，$Leader_{mid}$ 如果不携带历史日志肯定不携带当前任期日志（日志追加），不可能被选为leader，也就不会覆盖历史日志
    2. 历史日志已经备份到多数派，其任期内的leader没来得及提交就崩溃的情况
      • 该情况之后选举出的所有leader都一定含有历史日志，也就不存在覆盖问题
  • 若当前未提交log的term小于最新term，我先不能提交（图8中三个2），等当前Server成为Leader拿到最新term（term = 4），准备提交当时term的log时（图8中三个4），再提交当前log（图8中可能覆盖当前log的S5不可能被选上了，因为term = 3 小于当前 term = 4

Cluster membership changes 成员修改

Raft支持动态修改配置（例如：增加，删除Server）,为了避免在配置切换过程中出现脑裂问题，Raft通过两段式提交实现配置切换

  1. 首先由Leader创建包括新旧配置log entry的特殊 AE RPC：$C_{old_new}$, 向所有的Follower发送，超过半数同意后提交，实现 joint concensus
  2. 实现后joint concensus，Leader创建 新配置log entry：$C_{new}$，按照一般添加log entry的流程执行，成功commit后，完成配置切换

在配置切换时，可能选举出多个leader的原因来自于：

  • $C_{new}$的部分传播导致 持有$C_{new}$的server 和 持有 $C_{old}$的server 对于 投票时的majority 判断标准不同，两个server子集合在一个term内选举出了两个Leader
  • 例如下图：新配置为系统添加了两个新server(4和5)，Server1 未收到新配置，在竞选Leader时收到了 自己和Server 2的投票，即认为过半，转换为状态为Leader;Server 5使用新配置，收到了自己、Server3、Server4的投票，同样认为过半，转换状态为Leader

Raft引入了以下几个规则避免了上述问题的出现

  1. Log entry 在所有配置的Server($C_{old}$ 和$C_{old_new}$)上均进行备份（避免切换过程中，未收到$C_{old_new}$的Server遗失Log entry）
  2. 此时的Majority要满足$C_{new}$ 和 $C_{old}$两个配置中的Majority（单依靠$C_{new}$ 选不出Leader）、
  3. Server收到新配置立即生效，无论配置日志是否commit

导致的结果（要么老配置生效，要么兼容老配置和新配置生效，不会出现新配置单独生效的问题）

  1. 要么选出的leader带有$C_{old}$，根据一致性约束，将带有$C_{old_new}$的Server回退，相当于未发生配置切换
  2. 要么选出的leader只带有$C_{old_new}$，实现了joint concensus

Snapshot

当系统运行时间后，难以避免的会出现log过多，导致占用大量存储空间、Server的重启状态时间过长等问题，Raft采用快照机制实现log 压缩

  1. 每个Server单独对已commit的log entry进行快照（降低单一快照+网络传递的通信成本）
  2. Leader定期向Follower发送自己的快照，Follower根据快照情况修改本地log和快照（InstallSnapshot RPC）
    • 基本思路就是：快照里有的log entry,Follower直接删除, 直到快照和log完美衔接

既然为了避免通信开销已经让每个Server自己备份了，为什么还需要第二步骤？

  • 为了避免Follower落后Server过多，Server已经将某一个log快照以后删除，导致Follower永远收不到来自Leader的这个log

客户端

客户端连接Server部分主要有三个逻辑：

  1. 客户端如何确定Leader是谁？随机选择Server，由Server返回Leader地址
  2. 如何实现幂等？
    • Leader在Commit某操作后未返回结果直接崩溃，Client会尝试重发请求，这就需要系统支持幂等操作。
    • Raft在客户端为每个操作添加序列号，Leader维护每个Client已Commit的最新序列号，对已执行过的操作直接返回结果
  3. 对应Read-only op，如何保证返回最新结果? 换句话说就是保证Raft的强一致性（Zookeeper中会详细讲什么是强一致性-Linearizability）
    • Leader在每个term开始时，提交一个no-op entry，保证Leader得到所有的Commit Entry（由于Raft 永远不会通过计算副本数目的方式来提交之前任期内的日志条目，为了避免存在部分多数entry未提交的情况）
    • Leader每次响应只读操作前，首先通过心跳机制确定自己还是leader(以免已有另外的leader被选举，导致返回结果stale)

总结

Raft说实话理解难度是比paxos降低了，但是细节和涉及到的分布式知识太多了，我目前只能说弄懂了部分细节，整体上理解还是欠缺，即做到了深入，但以我目前的水平还做不到浅出（反正研究生不搞这个，能懂点面试吹吹nb即可）