谭浩的博客

Simple is beauty.

分布式系统 —— Raft详解

基本介绍

Raft 协议是一个分布式共识协议,其用来使多台机器想一台机器一样对外提供服务,同时能够忍受少部分机器崩溃问题。通过在多台机器上维护复制日志的一致性来实现复制状态机,从而解决分布式系统的若错性。

Raft 协议通过对问题进行分解和解耦,将一致性协议分解为三个独立的子问题:

  • Leader Election: 当现存的领导者宕机之后,一个新的领导者将被选举出来。
  • Log Replication: 领导者从客户端接受日志条目,在集群中复制日志,并强制其他节点的日志和其保持一致。
  • Safety:任何服务节点在状态机中应用了某个日志,则其他节点不能再同样的日志索引下应用不用的日志。通过增加选举机制保障该属性。

    Raft 核心

Raft 基础

Raft 将节点分为三种状态,分别为LeaderCandidateFollower。其中 Follower只能被动响应LeaderCandidate 的请求。其状态之间的转化如下图所示。

Raft 将时间分为不同的任期,每一次任期有一次新的选举产生,如果出现投票被分裂的情况,则将产生新的一轮选举。Raft 节点直接通过RPC进行通讯,核心的协议实现需要两种RPC,分别为投票请求RPC和追加日志RPC。

Leader 选举

每一个 Raft 节点启动时都为Follower,并且只要收到了Candidate或者Leader 的有效信息就一致保持该状态。Leader通过给其他所有节点定期发送心跳检测来维持其统治地位。如果一个Follower节点在一段时间内未收到任何消息,则其转变为Candidate并发起一轮新的选举。

Follower 发起新的选举的步骤:

  • 增加当前的任期
  • 转变为Candidate状态
  • 为自己投票,并并行的请求集群中其他节点的投票

对于一个Candidate需要获得集群中的大多数节点的投票才能赢得选举,一旦赢得选举则转变为Leader并给其他所有节点发送心跳检测用于维持权威,并组织新的选举。

注意:有可能存在多个节点平分了投票数,从而导致没有任何节点能够获得大多数节点的选票,则在一段随机时间的等待之后开启一轮新的选举。

日志复制

领导者被选举出来之后,则其负责客户端的请求,并将日志追加给Follower,当一个日志被安全地复制之后,则其在状态机中应用该日志并返回给客户端。Leader会不断地给Follower发送追加日志的请求直到其他节点最终存储了所有的日志。

节点日志按下图组织,当Leader发现日志能够安全地被状态机应用,则日志状态为commited。当日志被复制到集群中的大部分机器上时,则其是可提交的,如下图的条目7。

Raft 协议关于日志维持以下属性:

  • 如果两个日志条目拥有相同的任期号以及日志索引则其存储命令也相同
  • 如果两个日志条目具有相同的任期号和索引则其前面的日志相同

Leader通过强制其他节点复制自己的日志保证一致性。Leader节点通过nextIndex维持其需要发给其他节点的日志索引。

安全性

保证任何被选举的Leader包含前面任期被提交的日志。Raft 通过投票阻止Candidate赢得选举,除非其具有所有已经提交的日志。Raft 通过比较日志列表中最后一个条目的任期和索引来判断是否是更新的日志。如果两个条目具有不同的任期,则任期大的更新;如果条目任期相同的,日志列表长的更新。