分布式一致性协议笔记

本文将阐述如何在分布式系统上实现一致性,以及一些分布式共识算法。

非分布式系统上的一致性

事务

ACID准则

对于关系型数据库,存在ACID原则维护事务的正确可靠性。

  1. 原子性
    原子性(atomicity)表现为事务中的所有操作要么全部完成,要么全部不完成(回滚),不会出现中间状态。以转账为例,假设A向B转账200元,那么原子性要求事务不存在A的钱扣了,但是B的钱没到账。
  2. 一致性
    一致性(consistency)表现为在事务开始前和结束后完整性约束(不变量)不被破坏。
  3. 隔离性
    隔离性(isolation)表现为数据库支持多个并发事务同时进行增删改。以转账为例,假设A和B同时向C转账200元,那么结束后C应当收到400元,而不存在只收到200块的情况。
  4. 持久性
    持久性(durability)表现为事务结束后对数据的修改是持久化的。例如系统发生宕机后,数据不应当消失。

前像与后像

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

事务更新的两条规则

提交规则

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

先记后写规则

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

事务的隔离等级

  1. Read Uncommitted
    读取未提交的数据,即脏读。
  2. Read Committed
    读取提交的数据,会产生不可重复读(Nonrepeatable Read),因为一个事务在处理的过程中可能有多个其他事务进行Commit。
  3. Repeatable Read
    MySQL的默认隔离级别,同一事务的多个实例在并发读取数据时,会看到同样的数据行。会产生幻读现象,也就是一个事务的两次查询中数据笔数不一致。
  4. Serializable
    等同于在每个读的数据行上加S锁

为了保证一致性,我们需要悲观锁、乐观锁或者多版本并发控制(Multi-Version Concurrency Control, MVCC)这样的机制。

MVCC

MVCC可以算作一种乐观锁,因为它在读取数据时不加锁,更新数据时对副本进行操作,直到合并前才加锁,这有点类似于CAS。

2PL

我们知道死锁有四个条件:互斥、占有且申请、不可抢占和循环等待。而为了解决死锁问题,一个方案就是一次性获得所有的锁,这样实际上破坏了占有且申请的条件。不过这样一次性锁协议牺牲了并发性。为此我们引入了2PL,2PL将加解锁过程分为两个阶段,在第一阶段只能加锁或者操作数据,不能解锁;在第二阶段只能解锁或者操作数据,不能加锁。相比于1PL并发度提高了,但是存在死锁问题了。

意向锁

意向锁的产生是为了提高执行效率,它要求如果我们对一个下层节点加锁,那么我们会对上层节点加意向锁。我们考虑一个数据表中有一些行正在被锁定,而我们现在试图加一个表级锁,这显然是要被阻塞的,但阻塞前我们需要遍历数据表的每一行才知道我们表中有些行被锁定了。为此意向锁要求在锁定行时对数据表也维护一个状态,表示当前数据表中有些行时被锁定的,因此你意向是获得表锁,那么请原地阻塞,别往下找了,现在是不可能的。
以意向共享锁IS为例,如果我们想对一行加S锁,那么我们先要对表加IS锁,表示我们对表中的某一行有加共享锁的意向。此外,如果把上下层节点组合起来看,能组合成四种锁的类型即SIS、SIX、XIS、XIX。以共享意向排他锁SIX为例,对数据表加S锁,说明要读取整个表,对数据表加IX锁,表示要更新数据表中的一些行。除了SIX,其他的锁并没有提高强度,可以退化为一个表级锁或者行级锁。以SIS为例,我们要读取整个表,对表加S锁,然后要读取其中一行,对表加IS锁,实际上可以简化为一个对表加S锁的操作。

分布式系统中的一致性

数据库系统与高可用性

对于逐步增长的用户规模和并发量,最初我们的做法是在单服务器单数据库的架构上修修补补。对于高并发的请求,我们使用服务器集群+负载均衡,对于数据库的压力,我们在服务器和数据库之间加上一层缓存。随着数据库压力的进一步增大,我们升级架构为主从架构,我们写请求始终在主库,并不断向从库同步,读请求则始终在从库。主从架构实际上是一个HA解决方案,能实现读写分离,并且主从数据库可以互为热备份,但会带来一些一致性的问题。对于更大并发的要求,我们还可以实行垂直拆分/水平拆分,将数据表按列/行拆分为多个。
基于共识算法的分布式集群相比主从架构提供了更好的冗余方式,集群可以管理超过两个节点,并且所有节点都是对等的,称为replica,这些replica可以(并且应当)在空间位置上广泛分布,并且具有负载均衡的能力。

CAP理论

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

一致性

分布式系统中对一致性(consistency)的定义是all nodes see the same data at the same time。这个要求是比较高的,通常称为强一致性(Strong consistency)、线性一致性(Linearizability)、外部一致性(External consistency),有的时候系统保证在更新操作后的一段时间后,系统能够达到一致性状态,这称为弱一致性。弱一致性可以分为最终一致性、因果一致性、单调读一致性、单调写一致性等。
具体地讲,一致性需要满足下面三个条件

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

分布式一致性与事务一致性

从概念上分布式中的一致性(CAP中的C)和事务一致性(ACID中的C)是完全不一样的,CAP中的一致性要求多副本的系统的行为表现得像单系统一样,并且对这个系统的修改是原子的。而事务一致性强调事务前后不变量不能改变。

分布式一致性与分布式共识

分布式一致性(Consistency)和共识(Consensus)是完全不同的两个概念,但是后者是实现前者的一个工具。

可用性

可用性即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)问题,而是去正确地处理它,这就引入了下面的一些协议。

分布式事务

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

Cassandra之类的系统允许用户配置成功写操作的最小节点数W、成功读操作的最小节点数R和副本节点的数量N。我们可以根据读写请求的数量来动态调整可用性和一致性之间的trade-off。

分布式共识

2PC和分布式共识算法

前面我们讨论了实现分布式事务的一些方法,我们看到在2PC的算法中如果协调者宕机会导致集群整体阻塞的情况,因此我们需要保证诸如协调者节点的高可用性(HA)。而为了保证HA,我们可以使用Paxos或者Raft等来维护一个复制状态机,这样即使有协调者这样的节点挂掉,我们能够选举出新的协调者。为了能实现这样的选举,我们就需要诸如Paxos之类的共识协议来保证在出现单点故障等情况之后,剩余的节点之间能够最终达成正确共识(参考一致性的三个要求)。
因此从设计上讲2PC和Paxos之流就奔着不同的目标而去。例如2PC要求保证全体一致,而Raft孩子要求多数一致,这样2PC实际上牺牲了可用性。但是当我们考虑的不是各Replication而是各Partition之间的一致性时,这个全体一致就是必要的。

全序广播(Total order broadcast)

复制状态机

复制状态机(Replicated State Machine)源自Paxos算法。通过同步日志,使得多个节点从相同的初始状态开始,按顺序执行相同的命令,转移到相同的状态,复制状态机中向所有节点同步的是操作本身。
与复制状态机相对应的是primary backup system,它向所有节点同步的是操作的结果。

拜占庭将军问题

拜占庭将军问题指在一个有n个节点的集群内部,有t个节点可能发生任意错误的情况下,如果n <= 3t,一个正确的共识不可能达成。我们回顾先前的一致性要求,现在我们需要所有的正确节点最终一定会(termination)决定一个相同(agreement)值,并且这个值是由正确的节点提出来的(validity)。

Raft

Raft协议的设计者们认为Paxos协议非常难于理解,并且需要作出很多修改才能够应用到工程中,因此设计了偏重于实现的Raft协议,这甚至体现在他们的论文标题《In Search of an Understandable Consensus Algorithm(Extended Version)》上,此外作者也提供了一个C++版本的实现liblogcabin。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]区间里的日志条目依次apply到复制状态机上。我们这里仍然要特别注意提交(commit)与应用(apply)区别。一个是针对日志,一个是针对RSM。

Leader专用状态

  1. nextIndex[]:对于每一个服务器,Leader下一个需要发送给它的日志条目的索引值。初始值(当某个节点成为Leader后进行这项初始化)为Leader的logs.size()。在一些实现中会使用commitIndex + 1
  2. matchIndex[]:对于每一个服务器,已经复制给他的日志的最大索引值。初始值为-1,这个值是非常保守的。
    这两个值是Leader用来同步各Follower的日志的,但是当一个节点成为Leader时,它实际上并不知道其他节点上的日志情况,所以它给出的值都是需要调整的。这个调整的过程非常巧妙,它是和日志复制一同进行的。我们将在Log replication部分详细说明。

任期

Raft中的Leader具有任期term机制,每个term只会对应一个Leader,所以可以通过term唯一标识这个Leader。每个节点维护有自己已知最新的currentTerm,出于网络分区等原因,它不一定是全局最新的。服务器之间通信时会交换各自的任期号,根据论文5.1节,如果一个节点检查到自己的currentTerm小于对方在RPC(包括Request和Response)中附带的term,则更新到较大的任期值;相对应地,如果检测到自己的大于对方的,则忽略对方的请求。当一个Leader发现自己具有过期的任期时,它会立刻切换成Follower。
注意,一个有较大任期号的RequestVote请求并不意味着发送该请求的节点是Leader。但是一个较大任期号的AppendEntries请求一定是来自Leader的,因为只有Leader会发送AppendEntries。

一个有趣的问题(一个离题的讨论)

在Raft编程实践中,当节点收到一个Candidate的RequestVote请求时更新term的做法,在我们判断选举结束时会有一些麻烦。一般地,假如我们观测Candidate节点,当它收到足够的票数时我们能够知道新Leader被决议出来,并且就是自己。但假如我们观测Follower节点,那么当它第一次收到新Leader合法的AppendEntries心跳时我们知道新Leader被决议出来,并且是发送方。但我们发现第一次和第二次并不是那么好区分,因为无论是第几次,我们观测的节点始终是Follower,而term也始终没有变(不然说明Leader又换了)。所以我们会使用另外的状态leader_name来维护Leader的名字,并在第一次收到心跳时设置其值为发送方,在丢失Leader或发现选举开始时将其值清空。这样我们就可以通过值是否为空来判断是否是第一次收到心跳了,于是我们能够准确找出选举结束的时刻。

日志与日志约束

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

  1. 领导人只附加原则(Leader Append-Only)(论文节5.3详细论述)
    Leader绝对不会删除或者覆盖自己的日志,只会增加。从上文中我们已经知道在Log replication部分会介绍一个Leader优雅的逐步同步Follower的日志,以求达到和自己一致的方法。而这换句话说也就意味着当Leader和Follower不一致时,永远是Follower顺应Leader,此时Follower的日志可能会被Leader覆盖。
  2. 日志匹配原则(Log Matching)(论文节5.3详细论述)
    这个原则包含以下两个小点:
    1. 如果不同节点上的日志中的两个条目具有相同的index和term,那么这两个条目的内容是一致的。
      这个特性为下面的领导人完全性提供了必要保证
      我们知道一个日志条目必然是由某个Leader在某个index创建的,根据领导人只附加原则,每个领导人在index创建的日志条目必然是unique的,因为日志的删除和覆盖不被允许。而在论述任期机制时我们又知道term是能唯一标识Leader的。综上,我们可以仅根据index和term唯一标识一个日志条目。
    2. 如果不同节点上的日志中的两个条目具有相同的index和term,那么这两个日志index前的部分也相同。
      这是由AppendEntriesRPC这个RPC中prevLogIndexprevLogTerm两个字段保证的。当一个AppendEntriesRPC命令到达时,Follower会比较自己是否具有prevLogIndexprevLogTerm所标记的条目,如果没有(这意味着诸如Leader宕机等情况导致的诸如没有能够全部复制到所有节点的情况)则拒绝这次添加(此时AppendEntriesRPC失败了),并且会削减掉自己已知的不符合Leader日志的部分(可以查看后文有关AppendEntriesRPC的部分)。因此每一次的AppendEntriesRPC都会附带一次check,从而保证了这条性质,有点类似于归纳法(induction)。
      根据日志匹配原则,我们在实现时可断言logs.size() == logs.back().index() + 1 == last_log_index() + 1。除非出现了Log compact的情况,这也是我们在实现时应当小心使用log.size()logs[]的原因。
  3. 领导人完全性(Leader Completeness)
    这个特性是Raft的一个核心特性。如果某个日志条目在某个term中已经被提交,那么这个条目必然出现在所有具有更大的term的Leader中,在这里已提交是必须的,我们将在Log replication中进行详细说明。这个规定实际上保证了选出的Leader拥有所有已经提交的日志条目,容易看出,我们先前的领导人只附加原则实际上为这个特性提供了条件。
    Raft的论文提到除了Leader-based的共识算法,其他的共识算法并不保证这个特性,例如Viewstamped Replication算法。
  4. 状态机安全特性(State Machine Safety)
    如果一个Leader已经apply了位于index的日志条目,那么没有任何服务器可以在这个index上apply一个不同的日志条目。
    状态机安全特性实际上保证了所有的服务器都会按照相同的顺序提交相同的日志给RSM(论文5.4.3节旁注)。事实上根据领导人完全性可以证明状态机安全性,首先一个被apply的日志必须是已提交并与Leader相同的。如果某个较早term上的日志条目被apply的话,日志匹配原则能够保证所有之后term对应的Leader都拥有相同的日志条目,因此他们稍后也会apply相同的日志条目。
    Raft协议保证一旦条目被提交,那么它是持久化的(durable)(不会被丢失或更改),并且一定会被所有可用的复制状态机执行(论文5.3节)。

RPC

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

AppendEntriesRPC

AppendEntriesRPC具有心跳包和推送日志的作用。此外,通过AppendEntriesRPC我们还可以发现选举产生的新Leader,可以参考先前讨论任期时提到的有趣的问题。这个RPC包含以下部分

  1. term
    表示领导人的当前任期号。为了表示区别,下面写作rpc_term_id
  2. leaderId
    表示当前领导人的id,这样来自客户端的请求能被Follower转发给Leader。
  3. prevLogIndexprevLogTerm
    表示新日志条目之前的index和其对应的term,这个是为了保障先前提到的日志匹配原则。Leader在构造这两个字段时实际上是根据自己维护的nextIndex[]matchIndex[]来计算的。

  4. entries
    entries就是我们要维护的日志条目。

  5. leaderCommit
    表示Leader已经提交的日志的序号,这样其他的服务器才能知道Leader当前的提交位置,并跟随提交。

AppendEntriesRPC Response

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

  1. term表示当前的任期号
  2. success
    表示这次添加是否成功,它的判定规则如下:

    1. rpc_term_id < term时返回false,显然我们不接受一个较老的Leader。
    2. 当我们不存在满足prevLogIndex的条目时返回false。
    3. 即使存在prevLogIndex的条目,但这个条目的term不同于prevLogTerm时,删除从prevLogIndex开始的所有项目。
      这里的“不同于”是非常重要的,如果Follower拥有Leader发来的所有的Entries,他也是不能删除自己后面的Entry的。当Follower收到RPC时,prevLogIndex肯定是可能大于等于Follower的log大小的,例如Leader收到了Client的新Log。但prevLogIndex也是可能小于的,最普遍的一种情况是Leader刚选举出来,还在试探Log。还有一种情况是Follower拥有了先前某个Leader复制的一些Log,而当前的Leader没有。还有一些情况是我们收到了经历了时延的RPC
    4. 添加所有我们log中没有的条目。
    5. 同步leaderCommit

      特别地,对于心跳包,我们同样应当进行这样的检测

      RequestVoteRPC

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

RequestVoteRPC Response

投票者在接受到该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相同,那么日志比较长的那个就新。如果一个候选人的日志和大多数的节点一样新,那么它一定持有了所有已经提交的日志条目。
具体原因我们在稍后讨论,我们现在要看的是这个断言描述了给VoteFor某个RequestVoteRPC的条件:

  1. 远端的term(也就是在RequestVoteRPC传递的)不能小于自己的term
  2. 远端的lastLogTerm不能小于自己的lastLogTerm
  3. 如果远端和自己的lastLogTerm相等,那么远端的lastLogIndex不能小于自己的lastLogIndex

场景

注意,有时候一个刚竞选成功的Leader会收到同term的Candidate的Vote请求,而它会给一个Candidate投票。参考下面的log:https://paste.ubuntu.com/p/zrz29bgFPk/。这应该是一个错误的实现导致的,当Leader竞选成功时,我们不需要重置其`vote_for`。

Log replication

一旦由当前Leader创建的某日志条目被成功复制到过半数的服务器上时,这个Leader可以提交该条目及自己日志中该条目之前的所有条目(论文5.4.2节会提到一些细节证明)。这里要求至少过半数实际上为前面的选举投票顺利进行提供了保障,剩余的节点(可能因为宕机或者脑裂没收到)可以在后面慢慢AppendEntries。不需要全部成功复制的原因会在Safety中进行论证。有意思的是即使先前的条目可能是由其他Leader创建的,但这也不影响提交,事实上在下面的讨论中我们可以看到,这种方式实际上是唯一的可以提交较旧的term的日志条目的方法。
AppendEntriesRPC中,Leader还通过leaderCommit字段来告知所有的Follower自己当前的提交位置,每个服务器会试图在本地提交直到commitIndex的日志。注意到有的服务器可能在本地并没有这个commitIndex的日志,因此它只能提交到自己最新日志条目的index位置。在更新完后,每个节点会更新lastApplied,从而将新的commitIndex后面的日志条目应用到复制状态机上。在apply之后,Leader便可以向客户返回结果。

提交来自较旧任期的日志条目

我们将论文中的5.4.2节放到这里来讨论。
下面的一张图展示了当前Leader对具有较旧的term的日志条目进行提交时的一种情况,其中一个已经被存储到大多数节点中的较旧的日志条目(c阶段中的term 2 index 2)也会被未来的Leader(d term 3 index 2)覆盖掉。这也是在提到领导人完全性原则时我们强调了已提交三个字的原因。

我们首先查看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,这时候按照我们错误的可以提交较旧的条目的假设,S1已经可以提交黄色块了,但是它又挂了,因此没能成功提交。此时到了d阶段,S5恢复了,此时它的term最大,因此通过S2、S3、S4当选,这时候它稳定了,于是覆盖了所有的黄色和红色log。为了解决这个问题,Raft禁止提交一个较旧的term的条目,即使它已被复制到大部分节点。

对日志不一致问题的处理

下面我们关注Leader的复制请求的结果。其实通过前文已经知道,在正常情况下,Leader的日志始终是和Follower的一致的,所以来自Leader的AppendEntriesRPC始终会是成功的,但一旦Leader或者Follower出现崩溃或者网络发生脑裂,日志就会处于不一致状态,例如有些Follower会比Leader少条目或多条目,这时候就违背了日志匹配原则,导致失败,我们稍后看到这个失败实际上会被用来进行恢复一致性的工作。多条目看起来不可思议,但如下图所示,f就是一种情况,多出来的三个term为2的条目,这是可能是由于它是term为2时的Leader,并且添加了一些日志,但是在提交前崩溃了。

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

有关强制复制日志的细节

由于实现细节的问题,可能会导致MIT 6.824 Lab2的TestFigure8Unreliable2C过不了,可以查看代码的on_append_entries_request函数的847-881行

Safety

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

有关领导人完全性的论述(论文5.4.3节)

现在我们利用反证法证明领导人完全性。首先我们提出反命题,即存在一个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也应当包含这个日志条目。

有关非Leader节点故障的讨论(论文5.5节)

有关可用性的讨论(论文5.6节)

有关脑裂(网络分区)的讨论

由于某些节点的失效,部分节点的网络连接会断开,并形成一个与原集群一样名字的集群,这种情况称为集群脑裂(split-brain)现象。这个问题非常危险,因为两个新形成的集群会同时索引和修改集群的数据。Raft协议能够解决由于网络分区导致的脑裂,我们从脑裂过程中和脑裂恢复后两个阶段来讨论。

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

Membership changes

相比整体下线集群在重新启动的方法,Raft提供另一个方案。为了保障安全性,我们需要在新旧配置的过渡期间确保四个基本原则的基石之一,Leader与term一一对应不会被打破。论文指出直接做切换时不现实的,如下图所示,当集群规模从3变为5时,存在时间点使得集群分划为两个部分,其中绿色部分使用旧配置$C_{old}$进行选举,蓝色部分使用新配置$C_{new}$进行选举。因此Raft使用两个阶段实现配置转换。

两阶段的转换有很多种方法,例如可以在第一阶段禁用旧配置,然后在新阶段启用新配置,这样在两个阶段之间系统不能响应客户请求。Raft的解决方案是第一阶段切换到一个过渡的称为joint consensus的配置上,当joint consensus被提交之后,系统再转换到新配置上,这样就不会存在新老配置共存的问题。joint consensus阶段要求如下:

  1. 日志条目应当被复制到对应到新旧两种配置的所有机器上。
  2. 两种配置中的任意服务器都可以作为Leader。
  3. 选举和提交日志的共识必须同时经由两种配置的多数同意。也就是说要得到两种配置下各自的过半票数

在图中,虚线部分表示已创建未提交的日志配置条目,实现部分表示被提交的配置条目。可以看到配置转换过程被分为三个阶段:

  1. 从Leader收到配置变更请求到在$C_{old, new}$被提交前
    此时单独根据$C_{old}$决议。
    首先,Leader在收到配置变更请求后,生成一个表示$C_{old, new}$这个配置的日志条目,并按照通常的方式AppendEntry。一旦这个日志提交成功,集群进入joint consensus状态。特别地,节点只要收到新配置的AppendEntry就会切换到新配置,无论这个AppendEntry有没有被提交。因此提交成功只是说明进入了joint consensus状态,此时很多节点已经切换到了配置$C_{old, new}$。
    当Leader提交了配置$C_{old, new}$对应的日志条目时,它一定是使用的这个配置进行的决议。当Leader在这一阶段崩溃时,新选举的Leader可能是$C_{old, new}$,也可能是$C_{old}$。
  2. 在$C_{new}$被提交后到配置变更完成
    此时单独根据$C_{new}$决议。
    特别地,如果Leader使用$C_{new}$配置的话,这个时间节点可以提前到$C_{new}$被创建。
  3. 在1和2的中间阶段,即joint consensus状态
    在这一阶段配置$C_{old, new}$已被提交,此时$C_{old}$退出舞台。由于Leader已被提交,所以领导人完全性原则保证了没有$C_{old, new}$的Candidate注定选举失败。此时Leader节点可以安全地去AppendEntry配置$C_{new}$的条目了。

三个Issue

  1. 刚加入的新节点没有日志
    这里指的是我们计算多数的时候不考虑他们的投票权。此时他们仅接受日志的复制,不参与包括commit、vote之类的投票,这一阶段的结束
  2. 新配置需要移除Leader
  3. 删除节点

实现

liblogcabin的实现方案是列出一个Configuration类,这个类包含以下几个关键信息

  1. Configuration::State state
    这是个enum类型,包含四种可能值BLANKSTABLESTAGINGTRANSITIONAL。分别对应于集群初始化、正常运行、Issue1的解决方案和joint consensus状态。
  2. quorumAll()
    是否获得当前配置下的多数票,这里需要根据TRANSITIONAL分类讨论。

Log compaction

Raft采用了Snapshot的方法来实现日志持久化,这种方法是独立于Raft的Strong Leader的原则的,这是由于每个节点的Snapshot的状态对Leader来说是透明的。论文中指出这样做是合乎情理的,这是由于我们Snapshot的东西都是经过一致性检验的,所以不会存在冲突,Snapshot只是Follower去reorganize自己数据的行为。此外,由Leader创建日志而非Follower创建日志有以下的弊端:

  1. 网络开销。这是因为Leader要将Snapshot复制到每个Follower,而这是冗余的,因为Follower实际上有全部信息。
  2. 实现复杂。

InstallSnapshot

当Leader发现Follower[i]的next_index已经严重落后,落到了自己的snapshot里面(next_index[i] <= get_base_index()),就应当发送InstallSnapshot RPC催促其补上。这个RPC应当包含Leader自己持久化的log,这部分应该是已经提交了的。
当Follower收到这个RPC时首先进行例行判断,例如term是否大于等于自己的current_term并更新,否则拒绝。如果自己是Candidate要切换回Follower,重新超时等等。接着直接dump下来Leader的snapshot。
一个Snapshot表示state machine到last_included_index为止的状态,因此last_included_index必须位于已apply(而不是commit)的日志。在创建snapshot之后,我们可以将直到last_included_index的所有日志压缩成一个日志。

持久化

我们需要区分持久化persist和快照snapshot技术。persist指持久化论文Figure2列出的vote_forcurrent_termlogs三个状态。特别注意诸如commit_index是volatile的。

Paxos

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