Raft

一致性协议

保证即使在部分副本宕机的情况下,也能正常对外提供服务,通常基于状态机复制,即所有节点从同一个state触发,经过同样的操作序列log,到达同样的state

Replicated State Machines

  • 状态机: 当我们说一致性的时候,实际就是在说要保证这个状态机的一致性。状态机会从log里面取出所有的命令,然后执行一遍,得到的结果就是我们对外提供的保证了一致性的数据
  • Log: 保存了所有修改记录
  • 一致性模块: 一致性模块算法就是用来保证写入的log的命令的一致性,这也是raft算法核心内容

Replicated State Machines

Raft协议

一个动态过程

Leader Election

  • Leader:请求的处理者,接受client的更新请求,本地处理后再同步至其他副本
  • Follower:请求的被动更新者,从Leader接受更新请求,写入本地日志文件
  • Candidate:如果Follower副本在一段时间内没有收到Leader的心跳,则重新选主,所有副本变成Candidate,直到选主结束

Leader Election

时间被分成连续随机长度的term,每个term初进行选主:

  1. Follower将自己的cur_term_id+1,并将自己转换为Candidate
  2. 发送VoteRPC给其他Server,进行投票
  3. 选主结束后,主的状态切为Leader,并定期给其他server发送心跳,告诉对方自己是cur_term的leader。(每个term最多只有1个leader)。
  4. 其他server如果收到了来自Leader的AppendEntriesRPC,rpc_term_id >= cur_term_id的RPC时,将自己切为Follower,并更新cur_term_id
  5. 如果没有任何一个Leader产生并发送心跳,则超时的Candidates将cur_term_id+1,发起新一轮投票
  6. 第一个超时的Candidate带着最大的term_id发送VoteRPC,自己成为Leader

Log Replication

Log Replication

Log Replication

  • Leader将命令作为一个log entry添加到日志中,然后给其他server发AppendEntriesRPC请求,当Leader确定一个log entry已经被大多数副本写入日志,就将这条log entry应用到状态机中,并返回给客户端。如果某个Follower挂了,会一直给这个Follower发AppendEntriesRPC直到日志一致。
  • Raft保证一条被应用于状态机的log entry已经持久化了,并且会被所有的节点执行。 Log Replication

  • 当一个新的Leader出现时,需要保证一致性:
    • 以新Leader的log为准,其他Follower可能多或少数据,需要达成一致
    • Leader给所有Follower推送该Follower的next_index表示发送的下一条log entry在该Follower中的位置。
    • 如果Follower找不到对应term_id & next_index-1的对应log entry,则拒绝Leader
    • Leader将它的next_index-1再发送,直到AppendEntriesRPC请求被接收。

Safety

  • 只有保存了最新日志的节点才能选举成为Leader
    • 在Vote时,Candidate带上自己的term_id和index,其他server收到消息时,如果发现:
      • 本地的term_id > rpc_term_id
      • 本地的term_id = rpc_term_id,但是本地的index > rpc_index
    • 则认为自己的日志比RPC中的更新,拒绝投票
  • Committed log entry:
    • Leader确认这条log entry被大多数(过半)写盘了,则这条log entry被committed。
    • Leader不能直接commit当前term的log entry

Log Compaction

Snapshot

快照(英语:snapshot)是整个系统在某个时间点上的状态。这个名词是由摄影中借用而来。它储存了系统映象(System image),让电脑系统在出现问题时,可以快速恢复到未出问题前的状况。

Raft:每个副本独立对自己的系统状态进行Snapshot,并且只对已经提交的log entry进行Snapshot。

注意点

  • 太频繁会消耗带宽
  • 太不频繁,会导致节点重启需要回放大量日志,影响可用性
  • 耗时过长:copy-on-write

集群拓扑变化 old->new

集群拓扑变化

  1. Leader生成的log entry,内容为Cold U Cnew(并集)代表新旧拓扑共存,待大多数Follower确认这条并集log entry后,提交这条log entry
  2. Leader生成新的log entry,内容为Cnew,推送给Follower,待大多数Follower确认这条并集log entry后,提交这条log entry
  3. server在收到log entry时,以其配置覆盖本地配置

Q&A

  • Q:为什么用了两阶段协议,不直接从Cold切到Cnew?
  • A:在这个阶段下选主,需要同时得到Cold和Cnew的多数投票,而直接切换成Cnew,可能某个Candidate A没有收到,认为自己仍处于Cold,收到Cold的大多数投票就认为自己是Leader,而实际Leader是Cold&Cnew均有多数投票的Candidate B。因此为了避免出现多个Leader采用该策略。

Raft in Consul

Raft in Consul

  • Client:无状态
  • Server:有状态(Raft,可以尽量避免太多的节点个数) 在开始的时候,单个Consul Server进入bootstrap模式,把自己选为Leader,当一个RPC请求到达一台非Leader Server上时,这个请求会被转发到Leader上,Leader判断它是只读还是可写,只读的话直接查询并且执行,可写的话才生成一条log entry,并用Raft的方法处理它。
  • Datacenter:私有网络环境,数据通过DC做分割,Leader只对自己这个数据中心内的数据负责。当一个请求到达一个数据中心,这个请求会被转发到正确的Leader那里。

    一致性模式

  • Default
  • Consistent
  • Stale

Reference

Raft论文

Consul官方文档

Table of Contents