谈谈对分布式一致性算法Raft的理解

前言

说到分布式一致性算法,鼻祖就是Paxos,但是Paxos算法复杂难理解。而Raft则简化了算法,更容易理解,在教学和工程落地上更加贴地气。工程上应用Raft的也有很多,如TiDB,Redis Sentinel,etcd 等,作为一名工程师如果想深入了解这些底层实现,就很有必要先了解一下Raft算法。

先说下我现在对Raft的一个整体的理解,对于分布式系统副本的一致性问题,都是通过复制状态机来实现的,也就是同步的不是一个状态值,而是命令本身,我们需要一种机制让分布式系统的这些命令日志能够安全的按顺序复制并应用到本地的状态机中,Raft 通过 Leader election的机制,选出一个能购保证安全性的主节点来控制或者说处理命令,也就是发送日志到其他节点(半数以上)和应用状态机。怎么保证日志条目能够按顺序被应用且应用后不可修改就是Raft或者其他一致性算法主要解决的问题。

正文

一、核心概念概括:

系统中的角色:
  • Leader : 领导人,负责发起日志复制,以及处理客户端请求。

  • Follower:跟随者,负责投票,以及处理Leader发过来的复制请求。

  • Candidate:候选人,Follower到Leader的中间状态,只有当Leader的心跳超时后,Follower才转化为候选人进行选举。

解决的问题:
  1. Leader election : 主节点选举
  2. Log replication:日志复制,也是复制状态机的核心
  3. Safety:安全性问题,怎么保证一些事情不会发生和保证某些事情一定会发生。
复制状态机:

分布式的一致性,是在不同的节点各自维护一个状态机来实现的,状态机的机制保证只要是相同的命令顺序输入(将命令日志按顺序Append到各个节点的Log中),那么输出状态和结果肯定是一样的。

特点:
  1. 强Leader机制,日志都是由Leader同步到其他节点,对复制状态机的实现更加简单。

  2. Leader选举:采用随机计时器来发起投票,解决冲突的方式简单快捷。

主要的两种RPC通信:
  1. RequestVote Rpc: 候选人发起的选举请求

  2. AppendEntries Rpc: Leader发起的日志复制请求和心跳机制。

二、核心问题

(1)领导人选举(Leader election )

  1. 最开始所有的节点都是Follower。Follower只要能从Leader 或者 Candidate收到心跳,则永远保持Follower身份。

  2. 如果在一段时间没有收到心跳,也就是Leader超时了,那么就发起选举。

  3. 发起选举的Follower 需要将term+1 并且将自己的角色转换为Candidate,然后向集群中其他节点发起RequestVote 的RPC。

选举过程中可能存在的情况:

  • 顺利的情况下:Candidate 发启的RequestVote得到了多数派的响应,这个时候Candidate将自己转换为Leader并里面向其他服务器发起心跳来确立自己Leader的位置和组织其他Leader的产生。

  • 在投票期间,收到了AppendEntries的日志复制请求(可能是自己的Leader突然活了,也可能是新的Leader产生了),如果收到的AppendEnrties RPC 的Term 大于或等于自己的term 则承认领导人并自己转换为Follower。如果term小于自己的term则拒绝这次RPC 并且保持Candidate状态,直到Leader选出。

  • 在投票期间,有多个Candidate 或得的票数相同,无法决出胜负,那么每个Candidate会继续增加任期(term+1) 然后进行发起RequestVote RPC 直到选出为止(选举超时的时间是随机的,所以他们发起的时间是错开的,这种冲突很快就会被解决)

(2)日志复制(Log Replication):

只有Leader才能处理客户端的请求,如果是非Leader的节点收到请求后要求转发到Leader处理,客户端的每个请求包含一条待执行的复制状态机命令,Leader将这条命令作为新的日志条目附加到自己的日志中去,然后发起AppendEntries RPC 请求到其他节点,让其他节点复制当前的这条日志,如果这条日志被安全复制(半数以上节点复制成功),Leader就将这条日志应用到自己的状态机中,并响应客户端,如果有些节点没有复制成功,Leader在接下来的时间会继续尝试发起AppendEnties RPC请求复制,尽管已经回复了客户端了。

怎么判断当前的附加请求是否合法?

* 每个AppendEntries RPC请求 中会带上待复制的日志条目的上一条日志的term和Index,Follower 会检查本地的日志条目是否有相同的index和term的日志条目(好比乐观锁),如果匹配则附加到本地日志条目中,不匹配则拒绝请求。

* 集群中的节点的日志可能存在很多种可能,有可能少,也有可能存在Leader没有的日志,但是可以保证被应用到状态机中的日志肯定是Leader中有的。

(3)安全性(Safety):

说到安全性,指得是在系统要保证有些事情是不能发生,还有保证一些事情是肯定要发生的。对于Raft来说,他要保证的就是:

如果有任意节点将一个确定的日志条目应用到它的状态机中,那么其他节点不能在同一位置应用一个不同的命令。

在上面Leader election 和 Log replication的流程中,还暂时无法保证Leader的日志是最新的,所以要引入一些手段来保证。

在Leader election 中 加入一个投票成功的条件,Candidate在发起RequestVote RPC 的时候会带上以下信息

  • lastLogIndex 候选人的最后日志条目的索引值
  • lastLogTerm 候选人最后日志条目的任期号

其他服务器收到后跟自己的日志条目进行比较,判断是否Candidate的日志是否包含自己的日志,如果包含则投票给他。这样只有Candidate是拥有最新的日志,他才可能通过半数以上的投票成为Leader。

三、其他

Rpc 重试机制和幂等:

在上面的流程中AppendEntries Rpc 请求是一个并发的请求,如果中途Follower 挂了,那么Leader会不断的重试Leader会记录这台机器最后的复制的Index),而Follower处理请求的时候需要解决幂等问题。

读一致性问题:

  • 在Raft一致性读写都是通过Leader,一般情况下读请求不需要写日志,但是可能会出现脏读(Leader挂了后重新选出的Leader还不知道哪些日志被提交了,他只是有最新复制的日志。),Raft解决的办法是,Leader在选举出来后通过发送一个空的AppendEntries Rpc 到集群中来确定已经被提交的日志。这样就能保证Leader一定能读到最新状态的数据。

  • 还有一种情况就是客户端当时认为的集群的Leader 可能已经不是Leader了,所以还是可能存在脏读,Raft 的实现,在处理读请求前先跟大多数节点来次心跳的同步(Zookeeper也有类似的情况,所以zookeeper要实现强一致,每次在读的时候要调用一次sync来同步一下数据)。

参考阅读

  1. Raft 论文翻译: https://github.com/maemual/raft-zh_cn/blob/master/raft-zh_cn.md
  2. Raft 在线演示:http://thesecretlivesofdata.com/raft/