分布式一致性协议笔记

在本文中将讨论CAP理论、2PC和3PC协议、RWN协议、Raft协议、Paxos协议。

分布式系统中的CAP理论

CAP理论

CAP理论提出之后一直广受质疑,但并不影响其成为一套经典理论。
CAP理论认为一致性(consistency)、可用性(availability)和分区容错性(partition tolerance)是不可能同时被满足的。

一致性

一致性即all nodes see the same data at the same time。这个要求是比较高的,通常称为强一致性,有的时候系统保证在更新操作后的一段时间后,系统能够达到一致性状态,这称为弱一致性。最终一致性是一种弱一致性模型,还可以分为因果一致性、单调读一致性、单调写一致性等。
具体地讲,一致性需要满足下面三个条件

  1. agreement
    决议需要得到所有节点的认同,通常是首先批准一个多数票的决议,然后进行同步。
  2. validity
    决议的值需要满足合法性要求
  3. termination(liveness)
    决议过程能够在有限步内结束,并产生结果。

可用性

可用性即reads and writes always succeed。这个要求系统能够始终在正常时间内对用户的请求进行响应。当然由于可能出现的一致性问题,这个响应不一定是正确的。

分区容错性

分区容错性即the system continues to operate despite arbitrary message loss or failure of part of the system。由于分布式集群中常出现网络分区情况,即集群中的一部分机器与另一部分机器中断连接,这可能是由于网络故障,产生网络分区;也可能是由于某些节点宕机。我们除非设计出一个永远不会出故障的网络,否则我们必须要容忍P。于是C和A便成为了trade-off。由于网络分区的概率比较小,并且是易于探测的,所以C和A大多数情况是能够比较好地满足的,所以说我们要做的不是根除网络分区及其导致的部分失效(partial failure)问题,而是去正确地处理它,这就引入了下面的一些协议。

分布式共识

关系型数据库中的事务

ACID准则

对于关系型数据库,存在ACID原则维护事务的正确可靠性。原子性(atomicity)表现为事务中的所有操作要么全部完成,要么全部不完成(回滚),不会出现中间状态。一致性(consistency)表现为在事务开始前和结束后完整性约束不被破坏。隔离性(isolation)表现为数据库支持多个并发事务同时进行增删改。持久性(durability)表现为事务结束后对数据的修改是持久化的。

前像与后像

在关系数据库中常使用Write ahead log(WAL)算法,WAL要求在数据实际写入之前先写日志,这样能够保证在故障发生后能通过日志进行恢复。
事务有只有两种完成方式,提交即全做事务中的操作,和回滚即全不做事务中的操作。在事务的中间过程中可能对数据块的值进行修改,但最终这些修改必须要通过提交和回滚来实现持久化。
AI(后像,After Image),指的是每次更新时数据块的新值。对于一个已提交的事务,当故障发生时应当REDO它的后像。注意一旦事务提交,就不能UNDO它的前像,会破坏完整性约束;但是事务提交前任意的删改都可以通过UNDO来撤销。事务提交和往数据库写值(执行事务)是两个不同概念。
BI(前像,Before Image),指的是每次更新时数据块的旧值。对于一个未提交的事务或提交进行到一半,当故障发生时应当UNDO它的前像。
UNDO和REDO操作具有幂等性,即对前像UNDO或对后像REDO任意多次,结果都是相同的。

事务更新的两条规则

提交规则

后像必须在提交前写入非易失存储器(数据库或运行记录)中。
当后像只写入日志而没写入数据库中也可以提交事务,因为出现故障之后可以使用后像REDO进行恢复。

先记后写规则

数据库中有先记后写原则,如果在事务提交前将后像写入数据库,则必须首先把前像记入日志。这样做的好处是在事务提交完成前如果出现故障,可以通过日志文件中的该前像进行UNDO,此时即使数据库没有被修改,也只是进行一次多余的UNDO操作。

分布式共识面临的问题

分布式事务

由于分布式系统中存在多个副本,所以维护这些副本的一致性成为核心问题之一。分布式事务相对于仅涉及单个数据库事务的难点在于其提交或回滚不仅决定于自身,还决定于其他节点上事务执行的状态。从理想考虑,只要有一台节点失效,其他节点就要进行rollback。为了实现这一点,需要一个协调者(Coordinator)来根据所有参与者(Cohorts)的情况判断是否完成提交或终止提交。同时协调者的故障称为单点故障,也就是这个故障能够直接导致集群无法运行,需要特别考虑。

拜占庭将军问题

复制状态机

复制状态机(RSM)源自Paxos算法。通过同步日志,使得多个节点从相同的初始状态开始,按顺序执行相同的命令,转移到相同的状态。

2PC和3PC

两阶段提交协议

第一阶段(投票阶段)

首先协调者向所有的参与者发出提交请求VOTE_REQUEST,参与者按照事务的标准流程写UNDO和REDO等日志,并在本地执行事务。如果事务执行顺利,则不提交(尽管事务中的全部操作已经正确完成),返回一个VOTE_COMMIT给协调者,表示自己成功执行了事务。如果事务执行出现错误,则返回一个VOTE_ABORT。

第二阶段(执行提交阶段)

假设协调者没有宕机,相应会出现两种状态:

  1. 成功,发生在所有的参与者节点都返回VOTE_COMMIT
    此时协调者向所有参与者发送GLOBAL_COMMIT,参与者收到之后正式提交事务并释放资源,然后返回ACK确认
  2. 失败,发生在任意参与者节点返回VOTE_ABORT,或者有的参与者timeout
    此时协调者向所有参与者发送GLOBAL_ROLLBACK,参与者收到之后UNDO回前像状态,然后返回ACK确认

协调者宕机情况对一致性的影响

OK,刚才协调者没有宕机,看起来很美好,可是如果协调者宕机了呢?首先如果有一台参与者收到来自协调者的信息GLOBAL_COMMIT,那么就能通过某种选举协议作为新的协调者重新掌控大局。可是如果这台参与者也宕机了呢?这就需要分类讨论

  1. 假设参与者全部宕机
    这时候整个集群“死绝了”,变成平凡情况,由于没人(有能力)commit,所以不一致性不会受到破坏。
  2. 假设参与者部分宕机
    这时候不一致性是一定遭到破坏的了。虽然未宕机的参与者中可能存在有收到来自协调者消息的,可以选一个新协调者出来,但是宕机的参与者究竟是否提交成功是个量子力学问题了,所以新协调者即使知道原协调者发出了commit指令,也不能断然决定去commit。

二阶段提交协议的不足

阻塞

2PC协议中,参与者一直是事务阻塞的,因此在事务进行的过程中,系统不能响应第三方节点的访问。这是偏于保守的,牺牲了一部分的可用性。
阻塞带来的另一个问题来自于协调者可能的故障。如果协调者挂掉,连接中断,可以重新选一个协调者。但如果协调者宕机,那么所有的参与者会跟着阻塞下去。这和参与者宕机形成比较,协调者对于参与者有timeout机制,但是参与者对协调者没有timeout机制。

不一致

我们知道2PC协议通过分出投票阶段能够根据所有节点上事务的执行情况判断执行提交或者回滚。但它在第二阶段依然会出现不一致问题。

  1. 第二阶段出现网络分区
    假设协调者发出了GLOBAL_COMMIT请求时发生了网络分区,此时有一部分节点收到消息正常commit,但另一部分节点未收到,还处于阻塞状态。
    此时协调者仍可以通过最终返回的ACK进行补救。

  2. 第二阶段协调者宕机
    假设协调者宕机了,并且部分接受到GLOBAL_COMMIT请求的参与者也宕机/分区了,此时不论一致性,单宕机的参与者的事务是否提交都已经是不确定的了

三阶段提交协议

三阶段提交协议针对以上2PC的两点不足采取了一些措施:对参与者也引入超时措施,将执行提交阶段拆为两步。

CanCommit阶段

这个类似于2PC的投票阶段,协调者发出询问是否可以提交,Yes为可以提交,No相反。

PreCommit阶段

需要分为三种情况讨论:

  1. 如果上阶段全部为Yes
    协调者发送PreCommit请求并进入Prepared状态
    参与者接受到PreCommit后确保事务操作全部执行并记录UNDO与REDO,返回ACK

  2. 如果上阶段有No
    协调者发送abort请求
    参与者接受到abort后,REDO,中断事务,发送ACK

  3. 例外情况:参与者未收到协调者的消息
    这可以认为是协调者的timeout,此时中断事务
    注意到这里参与者是可以处理协调者的timeout的

DoCommit阶段

这是真正的事务提交阶段,同样分为三种情况

  1. 协调者收全上阶段ACK
    协调者发送DoCommit请求
    参与者接受到DoCommit后提交事务,返回ACK

  2. 协调者未收到上阶段ACK
    这发生在协调者没有收到一些参与者的ACK(网络分区或该参与者abort)
    协调者发送abort请求
    参与者接受到abort,使用同上阶段的方式中断事务

  3. 例外情况:参与者未收到协调者的消息
    这又是一个协调者的timeout,此时提交事务
    为什么选择提交事务而不是中断事务?因为此时提交事务成功的可能性非常非常大了,但仍有例外,例如:
    进入PreCommit后,协调者发出的是abort请求,如果只有一个Cohort收到并进行了abort操作,而其他对于系统状态未知的Cohort会根据3PC选择继续Commit,这仍然会导致不一致,不过这个概率就显然非常小了

三阶段提交协议的不足

相对于2PC,3PC避免了协调者宕机之后可能出现的参与者们陷入状态停滞,群龙无首的情况。但仍然有较小的概率会导致不一致。

RWN

Raft

Raft协议的设计者们认为Paxos协议非常难于理解,并且需要作出很多修改才能够应用到工程中,因此设计了偏重于实现的Raft协议,这甚至体现在他们的论文标题《In Search of an Understandable Consensus Algorithm(Extended Version)》上。Raft协议主要分为三个模块,Leader election、Log replication和Safety。
Raft将服务器节点分为Leader、Candidate和Follower三种,协调者被称为领袖/主(Leader),参与者被称为群众(Follower)。相对于其他的协议,Raft中的Leader更强,这体现在

  1. Leader是唯一的
  2. Log entries只能从Leader发送给其他服务器,事实上Follower不主动发送,而只响应来自Leader和Candidate的请求
  3. 客户端只能和Leader交互,如果客户端首先连上了Follower,那么会被Follower转发给Leader
  4. Raft的独特之处还在于其在Leader election的过程中Raft使用了随机计时器进行超时。此外,Raft还提供了一个joint consensus的算法处理Membership changes的问题。

Raft基础概念

状态

Raft协议要求在每个节点上维护以下的状态:

共有状态

  1. currentTerm
    这个在后面的讨论中非常常用,表示了当前服务器已知的最新任期。
  2. votedFor
    顾名思义。
  3. log[]
    这个是日志,是我们需要维护一致性的对象。
  4. commitIndex
    已知的最大的已经被提交的日志条目的index。对Follower来说,这个是根据来自Leader的AppendEntriesRPC中的leaderCommit字段来更新
  5. lastApplied
    一旦commitIndex > lastApplied,那么就将[lastApplied + 1, commitIndex]区间里的日志条目依次应用到复制状态机上

Leader专用状态

  1. nextIndex[]:对于每一个服务器,Leader下一个需要发送给它的日志条目的索引值,初始化为Leader最后索引值加1
  2. matchIndex[]:对于每一个服务器,已经复制给他的日志的最大索引值

这两个值是Leader用来同步各Follower的日志的,其功能可以查看Log replication部分。

任期

Raft中的Leader具有任期机制,每个节点维护有自己节点上最新的currentTerm,出于网络分区等原因,它不一定是在全局最新的。服务器之间通信时会交换各自的任期号,如果一个节点检查到自己的currentTerm小于对方在RPC中附带的term,则更新到较大的任期值;相对应地,如果检测到自己的大于对方的,则忽略对方的请求。当一个Leader发现自己具有过期的任期时,它会立刻切换成Follower。

日志与日志约束

来自客户端的请求被表示成一系列将被应用到复制状态机上的指令,这些指令在Raft集群的所有节点上被记录为日志条目(Log Entries)。在每个日志条目中记录了对应的term以及是否该条目已经被提交。Raft协议下要求日志满足以下的约束,这些约束贯穿Raft整个算法,并且是相互密不可分的。

  1. 领导人只附加原则(Leader Append-Only)
    Leader绝对不会删除或者覆盖自己的日志,只会增加。在后面的讨论中我们可以看到在Leader的生命周期中会通过一个优雅的办法逐步同步Follower的日志,以求达到和自己一致。换句话说,当Leader和Follower不一致时,永远是Follower顺应Leader,此时Follower的日志可能会被Leader覆盖。
  2. 日志匹配原则(Log Matching)
    如果不同节点上的日志中的两个条目具有相同的index和term,那么这两个条目的内容是一致的。这个特性是由于条目始终是由Leader创建的,而一个unique的条目必然是有某个Leader(因为每个term对应一个领导人,因此可以通过term唯一标识)在某个index创建的,这使得我们可以仅根据index和term唯一标识一个日志条目。这个特性实际上是下面一个特性的必要保证
    如果不同节点上的日志中的两个条目具有相同的index和term,那么这两个日志index前的部分也相同。这是由AppendEntriesRPC这个RPC中prevLogIndexprevLogTerm两个字段保证的。当一个AppendEntriesRPC命令到达时,Follower会比较自己是否具有prevLogIndexprevLogTerm所标记的条目,如果没有则拒绝这次添加。因此这个特性得以始终被维护。
  3. 领导人完全性(Leader Completeness)
    如果某个日志条目在某个term中已经被提交,那么这个条目必然出现在所有具有更大的term的Leader中,在这里已提交是必须的,我们将在Log replication中进行详细说明。这个规定实际上保证了选出的Leader拥有所有已经提交的日志条目,容易看出,我们先前的领导人只附加原则实际上为这个特性提供了条件。Raft的论文提到除了Leader-based的共识算法,其他的共识算法并不保证这个特性,例如Viewstamped Replication算法。
  4. 状态机安全特性(State Machine Safety)
    如果一个Leader已经提交了给定的index的日志条目,那么任何其他的服务器在这个index不会提交一个不同的日志。
    一旦条目被提交,那么它是持久化的(durable)而不会被丢失或更改,并且一定会被所有可用的复制状态机执行。

RPC

Raft中定义了两种主要的RPC包,AppendEntriesRPCRequestVoteRPC

AppendEntriesRPC

AppendEntriesRPC具有心跳包和推送日志的作用,包含以下部分

  1. term
    表示领导人的当前任期号。为了表示区别,下面写作rpc_term_id
  2. leaderId
    表示当前领导人的id,这样来自客户端的请求能被Follower转发给Leader。
  3. prevLogIndexprevLogTerm
    表示新日志条目之前的索引值和其对应的任期号,这个是为了实现我们日志匹配原则中的一个特性。
  4. entries
    entries是一个数组,记录了若干日志条目。这些日志条目被Leader发送给所有的Follower。
  5. leaderCommit
    表示Leader已经提交的日志的序号,这样其他的服务器才能知道Leader当前的提交位置,并跟随提交。

Follower在接受到该RPC后会发送回执

  1. term
    表示当前的任期号
  2. success
    表示是否有效,包括检查prevLogIndexprevLogTerm这两个条目是否能够满足日志匹配原则,检查如果term < currentTerm则返回false。

RequestVoteRPC

  1. term
    表示候选人的任期号
  2. candidateId
    表示候选人的id
  3. lastLogIndexlastLogTerm
    表示Candidate的最后日志条目的index和term,每个投票者会比较对方是否新于自己的,从而进行投票。

投票者在接受到该RPC后会基于term和投票规则进行判定,并发送回执

  1. term
  2. voteGranted表明是否同意

Leader election

投票过程

在2PC中我们看到,参与者必须对协调者有timeout机制,否则整个系统会阻塞,Raft同样有这样的功能。Leader存活时会不停的往所有的节点发送RPC心跳包,考虑一个节点在election timeout时间(随机150ms-300ms,每个节点不同)中没有接到心跳包的情况。站在全局的角度来看,这可能是老Leader挂了,所以得选举出一个新的Leader出来;这也可能是网络延迟/分区的原因,因此可能在选举途中或者结束后老Leader又回来了。但站在这个节点的角度来看,它只能认为Leader已经挂了,因此成为Candidates参加Leader选举。此时它执行下面两个操作:

  1. 递增自己的currentTerm
  2. 发送RequestVoteRPC消息给所有节点,这时候节点们根据一定规则进行投票

成为Leader需要获得整个集群共$N$个节点中过半数($\ge N/2+1$)的票,才能成为新的Leader,这是为了保证最多只会有一个候选人赢得选举。投票可能产生三种结果:

  1. 自己成为Leader
    获得过半数票的节点自动成为Leader,并开始发送心跳包,也就是entries字段为空的AppendEntriesRPC。这样其余的节点发现rpc_term_id比自己的currentTerm大时就可以知道已经选出一个新主了,此时选举结束,Candidate重新变为Follower,并同步自己的currentTerm与新主一致。
    假设先前是老Leader发生网络分区从而导致选举的产生,在新Leader产生后网络又恢复了。此时他收到了来自新Leader的心跳包。显然这个心跳包中的rpc_term_id比老Leader自己的currentTerm要大,根据任期的约束,老Leader知道了新Leader的存在,切回Follower状态并更新任期。如果老Leader在发现新Leader依然履行了一次职责,发送了一个AppendEntriesRPC。首先它会被Candidate和已经发现新Leader的节点拒绝,因为它们的任期号肯定比老Leader的要大。
  2. 别人成为Leader
    对应于第一种情况,此时自己发现了一个任期号更大的Leader传来的心跳,于是自己退出选举。
  3. 没有Leader产生
    这发生在没有节点获得过半数的票的情境下,例如有很多Follower的timeout时间比较接近,在选举开始时都timeout变成了Candidate,这时候每个Candidate都会投给自己,所以没有Candidate能获得大多数。此时认为currentTerm + 1届的任期以没有Leader告终,节点们开始下一轮的election timeout。由于每个节点election timeout时间都是随机的,所以下一次出现timeout时间接近的可能性并不高。

投票原则

在上一节中我们提到收到RequestVoteRPC请求的节点会根据一定规则进行投票,事实上这是非常重要的,因为我们需要维护领导人完全性的原则。在Raft原论文中,这一部分是放到Safety章节来说明的,因此有必要在阅读此部分时首先查看Log replication章节。
首先,我们已经知道在投票的时候一个Candidate必须得到过半数的节点的支持,这是因为每一个已经提交的日志条目必然存在在至少一个这样的节点上。我们上面断言的正确性来自在下面Log replication部分的一个规则:当Leader创建的某日志条目被成功复制到过半数的服务器上时,Leader可以提交该条目。
下面我们进行另一个断言:如果两份日志最后的条目的term不同,那么term大的日志新。如果两份日志最后的条目term相同,那么日志比较长的那个就新。如果一个候选人的日志和大多数的节点一样新,那么它一定持有了所有已经提交的日志条目。

Log replication

一旦由当前Leader创建的某日志条目被成功复制到过半数的服务器上时,这个Leader可以提交该条目及自己日志中该条目之前的所有条目,此后Leader会告知客户执行的结果。这里至少要过半数的原因是为前面的投票成功进行提供了保障,而不需要全部成功复制的原因会在Safety中进行论证。有意思的是即使先前的条目可能是由其他Leader创建的,但这也不影响提交,事实上在下面的讨论中我们可以看到,这种方式实际上是唯一的可以提交较旧的term的日志条目的方法。

下面的一张图展示了当前Leader对具有较旧的term的日志条目进行提交时的一种情况,其中一个已经被存储到大多数节点中的较旧的日志条目(c)也会被未来的Leader(d)覆盖掉,从而说明这样做是行不通的。这也是在提到领导人完全性原则时我们强调了已提交三个字的原因。

我们首先查看a阶段,此时S1是Leader,生成一个黄色块的条目并复制给S2,此时由于未超过半数,所以S1不能进行提交。紧随后在本阶段我们看到S1未能继续复制黄色条目而崩溃了,此时S5透过S3、S4和S5的选票成为Leader(此时S1已挂,而S2的lastLogIndexlastLogTerm会让它反对S5)。S5紧接着创建了一个蓝色块条目放到了索引2处,此时如果S5继续复制它的蓝色方块,那么S1和S2的黄色方块肯定会被覆盖掉,不过在这个例子中S5都没来得及复制就挂掉了,这时候S1恢复了,这时候它的term最大,因此成功竞选。现在到了c阶段,这时候S1继续它复制黄色log的未竞伟业,同时创建了一个红色块。S1将黄色log继续复制给S3,这时候按照我们先前的可以提交较旧的条目的假设,它已经可以提交黄色块了,但是它又挂了,因此没能成功提交。此时到了d阶段,S5恢复了,此时它的term最大,因此通过S2、S3、S4当选,这时候它稳定了,于是覆盖了所有的黄色和红色log。为了解决这个问题,Raft禁止提交一个较旧的term的条目,即使它已被复制到大部分节点。

AppendEntriesRPC中,Leader还通过leaderCommit字段来告知所有的Follower自己当前的提交位置,每个服务器会试图在本地提交直到commitIndex的日志。注意到有的服务器可能在本地并没有这个commitIndex的日志,因此它只能提交到自己最新日志条目的index位置。在更新完后,每个节点会试图将新的commitIndex后面的日志条目应用到复制状态机上,并更新lastApplied
下面我们关注Leader的复制请求的结果。在正常情况下,Leader的日志始终是和Follower的一致的,所以来自Leader的AppendEntriesRPC始终会是成功的,但一旦Leader或者Follower出现崩溃或者网络发生脑裂,日志就会处于不一致状态,例如有些Follower会比Leader少条目或多条目,这时候就违背了日志匹配原则,导致失败,我们稍后看到这个失败实际上会被用来进行恢复一致性的工作。
多条目看起来不可思议,但如下图所示,f就是一种情况,多出来的三个term为2的条目,这是可能是由于它是term为2时的Leader,并且添加了一些日志,但是在提交前崩溃了。

对于这种不一致的状态,Raft有简单粗暴的方法来处理,就是强制Follower直接复制自己的日志,这同时也是领导人只附加原则的要求。根据领导人完全性原则,我们的Leader在选举时是具有完全的日志的。
在这个同步过程中,nextIndex[]matchIndex[]就派上了用场。nextIndex[]维护了Leader下一个需要发送给Follower的日志序号,当Leader刚选举成功时,它是不知道各个Follower的日志相对于自己的情况的,因此默认nextIndex[]都为自己最后一条日志加一。但这样发出去的日志可能不会被接受,原因是根据之前提到过的日志匹配原则,如果Follower没有Leader的最后一条日志,那么它必然不能匹配Leader发送的AppendEntriesRPC中的prevLogIndexprevLogTerm所标记,因此它会返回给Leader一个拒绝,此时Leader就会减小对应的nextIndex并重试。我们需要特别注意的是在这个过程中Follower的日志是有可能被Leader覆盖的。容易看到这里其实是可以进行优化的,但是Raft论文指出这个优化并不是很必要的,因为现实中失败很少发生,而且也不大可能会造成很多的日志不一致的问题。
容易看出,这种算法是非常优雅的,因为它把恢复一致性的过程和正常增加日志的过程统一起来了,我们不需要对恢复一致性过程额外进行设计,可想而知这个额外设计是相当麻烦的,因为我们还要考虑在回复一致性过程中出现失败的情况。

Safety

这一部分的论述对应了原论文安全性论证部分,证明了上面的Leader election和Log replication的算法是可靠的。

有关领导人完全性的论述

现在我们利用反证法证明领导人完全性。首先我们提出反命题,即存在一个term为T的Leader提交的日志条目没有被其后的term为U的Leader所拥有。因此我们进行下面的推导

  1. 根据领导人只附加原则,这个记录在U竞选时就就不存在。
  2. 考虑到这个日志条目已经被提交,所以Leader T一定已经把它复制到过半数的集群上了;同时考虑到Leader U当选,所以它也收到了过半数的票。因此至少有一个节点它既拥有Leader T的日志条目又投票给了Leader U。我们考虑这个投票者。
  3. 这个投票者必然在投票给Leader U前接受了来自这个Leader T的日志。如果它在投票后才接受到来自Leader T的AppendEntriesRPC,那么它肯定会拒绝这条RPC,因为当收到来自Leader U的RequestVoteRPC时,这个投票者就已经更新自己的currentTerm了,因此现在它的currentTerm肯定大于RPC中的rpc_term_id
  4. 这个投票者在投票时也保留了这个来自Leader T的日志。这是由于经过所有中间term的Leader都保有这个日志条目(我们假设中U是第一个没有这个日志条目的任期)。而Follower只有在日志和Leader冲突时才会丢日志。
  5. 既然这个投票者给Leader U投票,那么Leader U的日志必然不会比投票者的日志要旧。我们接下来从index更大和term更新两种情况来讨论。
  6. 首先假如投票者和Leader U当前的term是相同的,那么Leader U就会拥有更大的index,也就是日志更长。既然如此Leader U应当具有投票者当前所有的日志。
  7. 其次,另一种情况下,Leader U的最后一条日志的term要比投票者的最后一条日志大,并且要大于T。这是因为投票者的最后一条日志的term至少是T,毕竟投票者拥有一条在Leader T任期内提交的日志。而根据我们的假设,Leader U之前的Leader也拥有这样的一条日志。那么根据日志匹配原则的要求,Leader U也应当包含这个日志条目。

脑裂(网络分区)的处理

由于某些节点的失效,部分节点的网络连接会断开,并形成一个与原集群一样名字的集群,这种情况称为集群脑裂(split-brain)现象。这个问题非常危险,因为两个新形成的集群会同时索引和修改集群的数据。
Raft协议能够解决由于网络分区导致的脑裂。我们知道每一届的Leader都有一个term,

特别地,当网络分区多于两块的时候,会不会存在有两个分区中都选出了新的term相同的Leader呢?我认为应该是不可能的,因为成为Leader必须达到全局的多数$N/2+1$张票,最多只能有一个。所以当分区较多的时候,很可能无法选出新Leader。另外某节点也不容易去“获得当前分区的多数票”,因为它也无法界定当前分区的范围。

Paxos

Paxos将网络中的节点分为proposer、acceptor和learner三种类。其中proposer即提案的提出者,acceptor对提案经投票,投票的最终结果交给learner进行同步。