首先用一个问题引入分布式一致性的概念如何用多台计算机维持同一份数据在分析这个问题之前可能首先还要回答两个更直观的问题为什么要用多台计算机保持同一份数据从多台计算机读这一份数据的时候数据是一样的吗对于第一个问题简单分析一下就明白了。因为分布式系统中的节点都有一定的概率发生故障虽然单个节点的故障概率比较小但当系统规模不断上升故障的概率就变大了许多也即虽然一台设备很少发生故障但是当设备规模变大故障就成了日常。节点的故障会对系统的可用性、可靠性产生影响。当数据在系统中只有一份存储时如果发生断电、主机crash、网络故障那么导致的是数据的暂时不可用如果发生磁盘损坏则会导致数据丢失也就是系统不可靠。因此数据冗余复制集、副本集即同一分数据在系统中不同节点保存多份可以有效提高系统的可用性和数据的可靠性。第二个问题是分布式系统中最复杂的问题之一 副本的一致性问题即从系统外部读取系统内部各个副本间的数据在一定的约束条件下是一致的。为了解决第二个问题人们提出了很多不同的副本控制协议即在分布式系统中按照特定的流程规范来读写副本数据使得副本满足一定的可用性和一致性的要求。副本控制协议有很多也有不同的分类标准比如同步与异步、强一致性与弱一致性、中心化与去中心化等。中心化副本控制协议所谓的中心化就是对于副本集的更新操作有一个中心节点来协调管理将分布式的并发操作转化为单点的并发操作从而保证副本集内各节点的一致性。其优点在于逻辑简单将复杂的问题分布式并发转换成一个有成熟解决方案的问题单点并发。但缺点在于副本集的可用性依赖于中心节点如果中心节点故障即使有中心节点自动切换机制也会出现数10秒的不可用。大多数的分布式存储都会采用中心化副本控制协议比如GFS、TFS、MongoDB。而去中心化则是说副本集中没有中心节点所有节点的地位是平等的大家都可以接受更新请求相互通过协商达成数据的一致。去中心化副本控制协议的最大好处在于可用性比较强只要有大多数节点存活就能提供服务。但缺点是协议流程复杂尤其是需要强一致性保证的时候。在业界中Dynamocassandra就是基于去中心化协议。下面主要讨论中心化副本控制协议从以下方面进行讨论。写节点怎么将变更的数据同步到其他节点同步还是异步非写节点能否提供读数据如果能够允许会不会读取到过时的数据。主节点是怎么产生的当主节点宕机的时候怎么选择出新的主节点。是有统一的复制集管理中心记录谁主谁次各自的状态还是复制集自己选举出一个主节点主从节点数据更新流程第一个问题复制集之间数据的同步是同步模式还是异步模式在中心化副本控制协议中主节点primary提供写入操作数据会同步到其他节点。注意上面语句中第一个同步是指复制集中节点间数据趋于一致的过程。所谓同步Synchronous replication就是说对于客户端请求系统阻塞到复制集中所有节点都更新完成才能向客户端返回即write all。而异步Asynchronous replication模式只要一个或者部分节点更新则算写入操作成功通常是write one。上图来源于Distributed systems for fun and profit下同即为同步模式客户端的请求被发送到s1这个副本集s1将请求转发给s2、s3等s2、s3都操作完成之后再向客户端返回结果。在同步模式下系统的可靠性非常好只要有一个节点正常就能保证数据不丢失。但是系统的更新可用性非常差只要有一个节点异常就无法完成更新而且响应延迟比较大取决于副本集中网络延时最大、处理速度最慢的节点。上图则是异步模式客户端的写请求只要在一个节点上完成就立即向客户端返回结果。在上图中数据被写入到s1即认为写入成功向客户端返回系统在后台由s1向s2、s3节点同步数据。异步模式下系统的吞吐量会比较好但是存在数据丢失的风险比如上图中如果在数据同步到s2和s3之前s1挂掉那么刚才客户端的更新就丢失了关键在于客户端认为已经写入成功了。另外异步模式下客户端在写入成功之后立刻从系统读取数据有可能读不到最新的数据比如上图中如果客户端写入s1之后立刻从s2 读取读取的数据是过期数据。在数据同步的时候选择同步模式还是异步模式呢这个取决于系统对一致性、可用性、响应延迟的要求。比如在分布式文件系统GFS中需要保证复制集内副本的强一致性而单次读写的响应延迟并没有那么重要因此选择了同步模式即primary需要等到所有的secondary都写入成功才会向客户端返回。而在分布式数据库MongoDB中决定权交给了用户用户可以决定使用同步模式还是异步模式。第二个问题数据的流向流向有两种链式与主从模式。链式就是指从一个节点推送到最近的节点比如GFS“最近” 可以用IP地址或者节点间心跳TTL来衡量如图所示图片来源于清华阿里-大数据课程的PPT链式写入不难看出写入过程中每个节点的带宽利用都比较均衡可以充分利用网络资源也不会有单点压力但是需要经过多个节点写入延迟会比较大。而主从模式则是指数据同时从primary节点到secondary节点如图所示来源默认情况下MongoDB也是采用的链式模式但是可以通过设置settings.chainingAllowed false 来采用主从模式。在主从模式下Secondary会从Primary拉取OPLOG并应用到本地。显然在这种模式下Primary节点的带宽压力比较大但是写入延迟会小一些。第三个问题主从节点数据读取复制集中不同的系统在数据读取方面有两个问题。第一secondary节点是否提供读服务第二如果可以从Secondary读取那么这个接口是否开放给用户。第一个问题如果secondary节点提供数据读取服务那么是否会读取到过期的数据即不是最新成功写入的数据比如在异步写入的时候客户端得到成功写入的返回之后立即去secondary上读取那么有可能读到过时的数据这对于强一致性的情况是不能允许的。我们知道元数据的管理一般也是复制集而元数据需要保证强一致性因此元数据的写入一般都是同步的。比如GFS中master由一个active也就是primary节点、多个standby也就是secondary节点组成在元数据写入到active的时候要保证本地和远程机器都写入成功才能返回而且只有active提供读取服务。第二个问题如果复制集中的节点都能提供读取服务那么接口是否提供给最终用户呢在haystack中多个在不同机器上的物理卷组成一个逻辑卷一个逻辑卷就是一个复制集。当读取请求到达的时候是由haystack的元数据服务器directory根据负载均衡的原则选出提供服务的物理卷即用户是不知道读取请求是落地到哪个物理节点的。而对于mongodb用户可以在查询语句里面指定是从Primary读取还是从Secondary读取或者让系统来选择Nearest。主节点选举在中心化副本控制协议中这个中心primary是怎么选出来的呢是上级指定还是民主选举呢GFS系统中Primary节点是由masterGFS中的元数据服务器通过lease机制选择的简单说来GFS给某个节点颁发Lease该节点就成为了Primary节点Primary节点也可以在过期之前重新申请Lease而且Lease的颁发、申请信息都是在chunkserver与master的心跳中因此也不会带来过多额外的开销。使用Lease机制能很好的避免在复制集中出现双主同时有两个节点认为自己是Primary现象。而在Zookeeper、TFS、MongoDB中都是通过去中心化的协议选举出Primary节点选举出Primary节点之后就变成了中心化的副本控制协议当Primary出现故障之后会重新选举过程。对于民主选举两个因素非常重要第一是强一致性只能选举出一个Primary第二个是可用性选举过程要越快越好。为了达到强一致性需要使用分布式一致性协议目前较为常见的协议有Paxos协议该协议可以实现所有备份均可以提供对外服务并且保证强一致性通过理论和实践检验可以达到分布式的要求。Raft协议则是Paxos的一种特化在这个协议的实现中备份间需要区分主从角色只有主节点可以提供对外服务协议实现简单高效能很容易的同各种分布式数据一致性同步场景相结合是工程实现最好的选择。raft是工程上使用较为广泛的强一致性、去中心化、高可用的分布式协议。在这里强调了是在工程上因为在学术理论界最耀眼的还是大名鼎鼎的Paxos。但Paxos是少数真正理解的人觉得简单尚未理解的人觉得很难大多数人都是一知半解。raft的论文中两位研究者也提到他们也花了很长的时间来理解Paxos但是也觉得很难理解认真理解了一年之后研究出了raft算法。raft是一个共识算法consensus algorithm所谓共识就是多个节点对某个事情达成一致的看法即使是在部分节点故障、网络延时、网络分割的情况下也能完成。去中心化的加密货币区块链也需要共识算法。和区块链需要考虑恶意节点的情况不同在分布式系统中共识算法更多用于提高系统的容错性比如分布式存储中的复制集replicationraft协议是一种leader-based的共识算法。raft算法概览Raft算法的头号目标就是容易理解这从论文的标题(Raft.Understandable Distributed Consensus)就可以看出来。当然Raft增强了可理解性在性能、可靠性、可用性方面是不输于Paxos的。Raft more understandable than Paxos and also provides a better foundation for building practical systems为了达到易于理解的目标raft做了很多努力其中最主要是两件事情问题分解状态简化问题分解是将复制集中节点一致性这个复杂的问题划分为数个可以被独立解释、理解、解决的子问题。在raft子问题包括leader electionlog replicationsafetymembership changes。而状态简化更好理解就是对算法做出一些限制减少需要考虑的状态数使得算法更加清晰更少的不确定性比如保证新选举出来的leader会包含所有commited log entryRaft implements consensus by first electing a distinguished leader, then giving the leader complete responsibility for managing the replicated log. The leader accepts log entries from clients, replicates them on other servers, and tells servers when it is safe to apply log entries to their state machines. A leader can fail or become disconnected from the other servers, in which case a new leader is elected.上面的引文对raft协议的工作原理进行了高度的概括raft会先选举出leaderleader完全负责replicated log的管理。leader负责接受所有客户端更新请求然后复制到follower节点并在“安全”的时候执行这些请求。如果leader故障followers会重新选举出新的leader。这就涉及到raft最新的两个子问题 leader election和log replicationleader electionraft协议中一个节点任一时刻处于以下三个状态之一leaderfollowercandidate给出状态转移图能很直观的直到这三个状态的区别可以看出所有节点启动时都是follower状态在一段时间内如果没有收到来自leader的心跳从follower切换到candidate发起选举如果收到majority的造成票含自己的一票则切换到leader状态如果发现其他节点比自己更新则主动切换到follower。总之系统中最多只有一个leader如果在一段时间里发现没有leader则大家通过选举-投票选出leader。leader会不停的给follower发心跳消息表明自己的存活状态。如果leader故障那么follower会转换成candidate重新选出leader。term从上面可以看出哪个节点做leader是大家投票选举出来的每个leader工作一段时间然后选出新的leader继续负责。这根民主社会的选举很像每一届新的履职期称之为一届任期在raft协议中也是这样的对应的术语叫term。term任期以选举election开始然后就是一段或长或短的稳定工作期normal Operation。从上图可以看到任期是递增的这就充当了逻辑时钟的作用另外term 3展示了一种情况就是说没有选举出leader就结束了然后会发起新的选举后面会解释这种split vote的情况。选举过程详解上面已经说过如果follower在election timeout内没有收到来自leader的心跳也许此时还没有选出leader大家都在等也许leader挂了也许只是leader与该follower之间网络故障则会主动发起选举。步骤如下增加节点本地的current term切换到candidate状态投自己一票并行给其他节点发送RequestVote RPCs等待其他节点的回复在这个过程中根据来自其他节点的消息可能出现三种结果收到majority的投票含自己的一票则赢得选举成为leader被告知别人已当选那么自行切换到follower一段时间内没有收到majority投票则保持candidate状态重新发出选举第一种情况赢得了选举之后新的leader会立刻给所有节点发消息广而告之避免其余节点触发新的选举。在这里先回到投票者的视角投票者如何决定是否给一个选举请求投票呢有以下约束在任一任期内单个节点最多只能投一票候选人知道的信息不能比自己的少这一部分后面介绍log replication和safety的时候会详细介绍first-come-first-served 先来先得第二种情况比如有三个节点A B C。A B同时发起选举而A的选举消息先到达CC给A投了一票当B的消息到达C时已经不能满足上面提到的第一个约束即C不会给B投票而A和B显然都不会给对方投票。A胜出之后会给B,C发心跳消息节点B发现节点A的term不低于自己的term知道有已经有Leader了于是转换成follower。第三种情况没有任何节点获得majority投票比如下图这种情况总共有四个节点Node C、Node D同时成为了candidate进入了term 4但Node A投了NodeD一票NodeB投了Node C一票这就出现了平票 split vote的情况。这个时候大家都在等啊等直到超时后重新发起选举。如果出现平票的情况那么就延长了系统不可用的时间没有leader是不能处理客户端写请求的因此raft引入了randomized election timeouts来尽量避免平票情况。同时leader-based 共识算法中节点的数目都是奇数个尽量保证majority的出现。log replication当有了leader系统应该进入对外工作期了。客户端的一切请求来发送到leaderleader来调度这些并发请求的顺序并且保证leader与followers状态的一致性。raft中的做法是将这些请求以及执行顺序告知followers。leader和followers以相同的顺序来执行这些请求保证状态一致。Replicated state machines共识算法的实现一般是基于复制状态机Replicated state machines何为复制状态机If two identical,deterministicprocesses begin in the same state and get the same inputs in the same order, they will produce the same output and end in the same state.简单来说相同的初识状态 相同的输入 相同的结束状态。引文中有一个很重要的词deterministic就是说不同节点要以相同且确定性的函数来处理输入而不要引入一下不确定的值比如本地时间等。如何保证所有节点get the same inputs in the same order使用replicated log是一个很不错的注意log具有持久化、保序的特点是大多数分布式系统的基石。因此可以这么说在raft中leader将客户端请求command封装到一个个log entry将这些log entries复制replicate到所有follower节点然后大家按相同顺序应用applylog entry中的command则状态肯定是一致的。下图形象展示了这种log-based replicated state machine​​​​​​​请求完整流程当系统leader收到一个来自客户端的写请求到返回给客户端整个过程从leader的视角来看会经历以下步骤leader append log entryleader issue AppendEntries RPC in parallelleader wait for majority responseleader apply entry to state machineleader reply to clientleader notify follower apply log可以看到日志的提交过程有点类似两阶段提交(2PC)不过与2PC的区别在于leader只需要大多数majority节点的回复即可这样只要超过一半节点处于工作状态则系统就是可用的。那么日志在每个节点上是什么样子的呢不难看到logs由顺序编号的log entry组成 每个log entry除了包含command还包含产生该log entry时的leader term。从上图可以看到五个节点的日志并不完全一致raft算法为了保证高可用并不是强一致性而是最终一致性leader会不断尝试给follower发log entries直到所有节点的log entries都相同。在上面的流程中leader只需要日志被复制到大多数节点即可向客户端返回一旦向客户端返回成功消息那么系统就必须保证log其实是log所包含的command在任何异常的情况下都不会发生回滚。这里有两个词commitcommittedapply(applied)前者是指日志被复制到了大多数节点后日志的状态而后者则是节点将日志应用到状态机真正影响到节点状态。The leader decides when it is safe to apply a log entry to the state machines; such an entry is called committed. Raft guarantees that committed entries are durable and will eventually be executed by all of the available state machines. A log entry is committed once the leader that created the entry has replicated it on a majority of the serverssafety在上面提到只要日志被复制到majority节点就能保证不会被回滚即使在各种异常情况下这根leader election提到的选举约束有关。在这一部分主要讨论raft协议在各种各样的异常情况下如何工作的。衡量一个分布式算法有许多属性如safetynothing bad happens,liveness something good eventually happens.在任何系统模型下都需要满足safety属性即在任何情况下系统都不能出现不可逆的错误也不能向客户端返回错误的内容。比如raft保证被复制到大多数节点的日志不会被回滚那么就是safety属性。而raft最终会让所有节点状态一致这属于liveness属性。raft协议会保证以下属性Election safety选举安全性即任一任期内最多一个leader被选出。这一点非常重要在一个复制集中任何时刻只能有一个leader。系统中同时有多余一个leader被称之为分裂 split这是非常严重的问题会导致数据的覆盖丢失。在raft中两点保证了这个属性一个节点某一任期内最多只能投一票只有获得majority投票的节点才会成为leader。因此某一任期内一定只有一个leader。log matching很有意思log匹配特性 就是说如果两个节点上的某个log entry的log index相同且term相同那么在该index之前的所有log entry应该都是相同的。如何做到的依赖于以下两点If two entries in different logs have the same index and term, then they store the same command.If two entries in different logs have the same index and term, then the logs are identical in all preceding entries.首先leader在某一term的任一位置只会创建一个log entry且log entry是append-only。其次consistency check。leader在AppendEntries中包含最新log entry之前的一个log 的term和index如果follower在对应的term index找不到日志那么就会告知leader不一致。在没有异常的情况下log matching是很容易满足的但如果出现了node crash情况就会变得复杂。比如下图注意上图的a-f不是6个follower而是某个follower可能存在的六个状态leader、follower都可能crash那么follower维护的日志与leader相比可能出现以下情况比leader日志少如上图中的ab比leader日志多如上图中的cd某些位置比leader多某些日志比leader少如ef多少是针对某一任期而言为什么会出现上面这些不同呢对于比leader日志少的情况比较容易理解可能是出于网络故障节点没有收到leader发出的appendEntry的消息对于比leader多的情况可能是由于该节点曾经当选过leader但是它还没有来得及把自己收到的命令发布出去就已经挂了所以只有它自己保存了这些消息对于ef的情况可能是在term 2和term 3中节点曾经当选并收到一些命令但是还没有来得及发出appendEntry的消息它就down了然后一直down到term 8才重新加入。但是term 8中leader的数据还是受到了大部分节点的支持的。当出现了leader与follower不一致的情况leader强制follower复制自己的logTo bring a follower’s log into consistency with its own, the leader must find the latest log entry where the two logs agree, delete any entries in the follower’s log after that point, and send the follower all of the leader’s entries after that point.leader会维护一个nextIndex[]数组记录了leader可以发送每一个follower的log index初始化为eader最后一个log index加1 前面也提到leader选举成功之后会立即给所有follower发送AppendEntries RPC不包含任何log entry 也充当心跳消息,那么流程总结为step 1 leader 初始化nextIndex[x]为 leader最后一个log index 1step 2 AppendEntries里prevLogTerm prevLogIndex来自 logs[nextIndex[x] - 1]step3 如果follower判断prevLogIndex位置的log term不等于prevLogTerm那么返回 False否则返回Truestep 4 leader收到follower的回复如果返回值是False则nextIndex[x] - 1, 跳转到step2. 否则step 5 同步nextIndex[x]后的所有log entriesleader completeness vs elcetion restrictionleader完整性如果一个log entry在某个任期被提交committed那么这条日志一定会出现在所有更高term的leader的日志里面。这个跟leader election、log replication都有关。一个日志被复制到majority节点才算committed一个节点得到majority的投票才能成为leader而节点A给节点B投票的其中一个前提是B的日志不能比A的日志旧。下面的引文指处了如何判断日志的新旧voter denies its vote if its own log is more up-to-date than that of the candidate.If the logs have last entries with different terms, then the log with the later term is more up-to-date. If the logs end with the same term, then whichever log is longer is more up-to-date.上面两点都提到了majoritycommit majority and vote majority根据Quorum这两个majority一定是有重合的因此被选举出的leader一定包含了最新的committed的日志。raft与其他协议Viewstamped Replication、mongodb不同raft始终保证leader包含最新的已提交的日志因此leader不会从follower catchup日志这也大大简化了系统的复杂度。corner casestale leaderraft保证Election safety即一个任期内最多只有一个leader但在网络分割network partition的情况下可能会出现两个leader但两个leader所处的任期是不同的。如下图所示系统有5个节点ABCDE组成在term1Node B是leader但Node A、B和Node C、D、E之间出现了网络分割因此Node C、D、E无法收到来自leaderNode B的消息在election time之后Node C、D、E会分期选举由于满足majority条件Node E成为了term 2的leader。因此在系统中貌似出现了两个leaderterm 1的Node B term 2的Node E, Node B的term更旧但由于无法与Majority节点通信NodeB仍然会认为自己是leader。在这样的情况下我们来考虑读写。首先如果客户端将请求发送到了Node BNode B无法将log entry 复制到majority节点因此不会告诉客户端写入成功这就不会有问题。对于读请求stale leader可能返回stale data比如在read-after-write的一致性要求下客户端写入到了term 2任期的leader Node E但读请求发送到了Node B。如果要保证不返回stale dataleader需要check自己是否过时了办法就是与大多数节点通信一次这个可能会出现效率问题。另一种方式是使用lease但这就会依赖物理时钟。从raft的论文中可以看到leader转换成follower的条件是收到来自更高term的消息如果网络分割一直持续那么stale leader就会一直存在。而在raft的一些实现或者raft-like协议中leader如果收不到majority节点的消息那么可以自己step down自行转换到follower状态。State Machine Safety前面在介绍safety的时候有一条属性没有详细介绍那就是State Machine SafetyState Machine Safety: if a server has applied a log entry at a given index to its state machine, no other server will ever apply a different log entry for the same index.如果节点将某一位置的log entry应用到了状态机那么其他节点在同一位置不能应用不同的日志。简单点来说所有节点在同一位置index in log entries应该应用同样的日志。但是似乎有某些情况会违背这个原则上图是一个较为复杂的情况。在时刻(a), s1是leader在term2提交的日志只复制到了s1 s2两个节点就crash了。在时刻b), s5成为了term 3的leader日志只复制到了s5然后crash。然后在(c)时刻s1又成为了term 4的leader开始复制日志于是把term 2的日志复制到了s3此刻可以看出term 2对应的日志已经被复制到了majority因此是committed可以被状态机应用。不幸的是接下来d时刻s1又crash了s5重新当选然后将term 3的日志复制到所有节点这就出现了一种奇怪的现象被复制到大多数节点或者说可能已经应用的日志被回滚。究其根本是因为term 4时的leader s1在C时刻提交了之前term 2任期的日志。如何理解呢如果S1不是只提交2而是连同最新的日志4一起提交了这样的话有三个节点的日志到达了term 4那么接下来S5就不会当选也不会出现日志回滚的情况。因此为了杜绝这种情况的发生Raft never commits log entries from previous terms by counting replicas.Only log entries from the leader’s current term are committed by counting replicas; once an entry from the current term has been committed in this way, then all prior entries are committed indirectly because of the Log Matching Property.也就是说某个leader选举成功之后不会直接提交前任leader时期的日志而是通过提交当前任期的日志的时候“顺手”把之前的日志也提交了。那么问题来了如果leader被选举后没有收到客户端的请求呢论文中有提到在任期开始的时候发立即尝试复制提交一条空的logRaft handles this by having each leader commit a blank no-op entry into the log at the start of its term.因此在上图中不会出现C时刻的情况即term4任期的leader s1不会复制term2的日志到s3。而是如同(e)描述的情况通过复制-提交 term4的日志顺便提交term2的日志。如果term 4的日志提交成功那么term 2的日志也一定提交成功此时即使s1 crashs5也不会当选。leader crashfollower的crash处理方式相对简单leader只要不停的给follower发消息即可。当leader crash的时候事情就会变得复杂。在这篇文章中作者就给出了一个更新请求的流程图。我们可以分析leader在任意时刻crash的情况有助于理解raft算法的容错性。总结raft将共识问题分解成两个相对独立的问题leader electionlog replication。流程是先选举出leader然后leader负责复制、提交loglog中包含command为了在任何异常情况下系统不出错即满足safety属性对leader electionlog replication两个子问题有诸多约束leader election约束同一任期内最多只能投一票先来先得选举人必须比自己知道的更多比较termlog indexlog replication约束一个log被复制到大多数节点就是committed保证不会回滚leader一定包含最新的committed log因此leader只会追加日志不会删除覆盖日志不同节点某个位置上日志相同那么这个位置之前的所有日志一定是相同的Raft never commits log entries from previous terms by counting replicas.