预估阅读时间：30分钟
关键字：raft，分布式一致性
前言
分布式系统中为了保证服务的高可用往往需要将数据分发到不同的节点，以防止某个节点的宕机而导致服务不可用，但是数据分发总是需要一个过程，而分发过程中节点上面的数据大概率是不一致的。举个例子，一个分布式系统有ABC三个节点，并且系统有一个变量X在ABC三个节点上的初始状态都为1，client发送一个请求：将X更新为2，并且A节点首先做了更新，但是此时还并没有同步到BC节点，假如没有任何限制措施的话，client此时多次查询X很有可能得到不同的结果：1或者2（因为请求如果随机分发到不同的节点话，得到的结果是不一样的）。而Raft要做的就是保证ABC三个节点都能同步最新的数据，并且保证client查询时永远只能查询到最新的已经提交过的正确的数据。
Leslie Lamport早在90年就提出了Paxos协议，Paxos主要也是解决上面那个问题，那为什么还要研究出来一个Raft，Raft作者的意思是因为Paxos太tm难懂了，鄙人尝试看过一次Paxos的论文，得出的结论是：我觉得Raft作者说的有道理！！！其次作者另外还有一层意思是：Paxos的整体设计并没有考虑真实的使用场景，虽然理论性很强，但是很多复杂的设计是可以简化或者规避的，Raft就是基于这种考虑而设计，首要目的就是让大家都能看懂。
在介绍Raft之前，我想给数据库从业者提个问题：Raft和两阶段提交区别在哪里？或者说它们各自的使用场景是什么？在真实的使用场景中，我个人认为最大的区别是：Raft的定位主要是状态机和数据replica，而两阶段提交则是在一个更高的层面上保证整个系统的数据一致性。
上面那句话感觉跟没说一样哈，换个说法Raft主要应用在数据多副本的场景，Raft的参与节点共同持有同一份数据，并且由Raft算法来保证数据一致性，数据是share的。
而两阶段提交中处理的数据则是sharding的，往往应用在分布式事务中。因为在面临海量数据的存储时，不可能每个节点都持有所有的数据，否则无法做水平扩展，数据需要分散的保存在不同的节点上，而且业务逻辑往往需要对不同节点上面的数据同时做不同的修改，比如A节点中的X+10，B节点上Y-10（转账场景），两阶段提交就是保证分布式系统中整体数据的一致性。
Raft：往往用来实现数据多副本保证数据高可用，以及多副本内数据的一致性。
两阶段提交：往往用来保证系统整体数据是对的，各个节点的数据组合起来是符合预期的。
note：这里加上一个“往往用来”，表达是它们比较适合应用在对应的场景，而不是只能做这些。Raft协议中的集群节点变更中就用到两阶段提交来保证节点角色的正确切换，是你中有我，我中有你的关系。
了解了各自的特点才能在技术选型时做出较为合理的判断，下面我们详细介绍一下Raft的实现。
Raft实现
本文主要是对论文的补充和一些迷惑点的解释，推荐优先阅读论文，我不打算按论文的顺序翻译式的讲解，而是按自己的理解做一些解释。
首先看一个基本的client-server模型，client向server发送数据，比如修改X=1，server端收到信息后更新X并且持久化到本地后，向client返回success，这是一个server的情况。但是这种模型存在一个问题：假如server挂了，那么服务也就不可用了。解决这个问题，有一种思路是采用主备的方式，搭建一个额外的slave server，并且master server会向slave同步数据，当master不可用时，client根据配置或者proxy自动切换访问slave server来保证服务正常运行。
但是主备的方案同样存在一个问题：何时认为X数据更新成功？假设master server更新X之后就向client返回success，并且此时slave并没有来得及更新X，这时候假如master server宕机，client再次访问slave server上的X时，X并不是最新的数据，这种方案会读到旧数据（stale data）无法保证数据一致性。
假如采取另一种方案：master将数据发送给slave并且收到slave更新成功返回的消息之后，才向client汇报X更新成功，永远保证master和slave同时更新成功之后再返回success，貌似这种可以解决数据不一致的问题。但是又会引出一个新的问题：假如slave宕机迟迟没有给master返回信息，master会一直等待，client迟迟无法确认数据是否更新成功，虽然这种方案保证了数据一致性，但是无法保证可用性。
再来看一下Raft的方案，Raft规定：client维护了一个server的列表，并且当某个server失联时client的请求会自动转发到别的server。另外规定server节点至少不能少于3个（本文中server和节点的意思相同），并且每个server都需要同步client发送过来的数据。首先思考一下哪个server负责与client交互？Raft设计了一个选主算法，所有节点会根据制定好的规则选举出来一个leader，其余的节点为follower，该leader负责所有对外的通信，保证数据的出入口唯一，选举是自发的，不需要外部干预。当leader接收到client的请求时，除了修改本地的数据状态外，还会将信息发送给所有的follower，当有半数以上的follower节点向leader返回success之后，leader便会通知client数据更新成功。为什么是半数以上？因为不能保证每个节点都能正常服务，所以为了保证最大的可用性并及时响应client的请求，可以容忍小部分节点并不是最新的数据。
思考一个问题：假如leader挂了，Raft会自动选主，那client如何找到最新的leader？寻找最新的leader是因为假如leader挂了，client会自动随机选取一个server，那假如client选取的恰好是没有来得及同步数据的节点的话，该节点的数据并不是最新的，也就违背了数据一致性的原则。Raft的处理是：假如leader挂了，集群会自动发起投票，选出含有最新数据的某个节点作为leader，并且该leader通知其余所有节点，尊我为leader，并且让每个follower记录leader的ID。当client切换到了follower节点时，该节点会通知client：此时的leader是别人，你去访问它吧，这样来保证client永远访问的是最新的数据。
Raft的log
既然leader担负如此重任，那我们就有必要了解一下Raft是如何选主的。解释选举前，我们首先需要知道Raft中的数据是采用什么样的方式存储。Raft采用log的方式保存了每次client的请求，并且将log中的操作依次应用在本地的数据上，每个log都有一个下标index，index依次递增，有点类似mysql的主从复制，比如初始状态X为0，client发送一个X++的请求，那么leader会将X++的请求写入本地log，然后向各个follower节点同步X++的log，而不是同步X=1，此时X的值仍然为0。
思考一个问题：此时leader是否可以将本地的X值更新为1？答案是：不可以。因为此时leader并没有收到大部分节点log同步成功的信息，假如贸然的将X更新为1，但是大部分follower节点都更新失败的话，那意味着X++操作并没有执行成功，client再次向leader查询X值时会得到脏数据。只有当大半数节点都向leader确认已同步该log后，leader会执行commit操作，来将该log中的操作应用在具体的数据上（这里即为将X++，即X=1）。
commit这个操作很关键，leader需要获取所有follower节点已经复制的log的下标index，然后找到半数以上复制成功的最小的index。这里可能有点绕，举个例子：假如ABC三个节点，B节点通知leaderA已经复制到index为3的log，C通知已复制到2，那么超过半数的节点已经含有index为2的log，此时A会将index<=2的log依次应用在本地的数据上，leader会保存一个commitIndex（每个节点都有自己的commitIndex），用来标识此时已经提交的log index，本例中leader的commitIndex=2。而且只有log被leader commit之后才会通知client数据更新成功，这点很关键，需要注意一下，后面会讲。
下面我们来思考leader挂了该怎么选举
讲到选举，我们需要再了解几个Raft的规则：Raft中leader会定时向所有节点发送心跳，用来确认自己leader的地位，并且并且并且心跳中同时会携带log信息，用来同步数据，这样来减少网络开销。
另外每条log记录的元信息中不仅包含有index，而且还有一个term的记录，term也是依次递增，但是并不是按log的个数递增，而是按选举的次数。比如term初始值为0，第一次选举，A竞争成为了leader，将term+1，当A挂了之后，B会将term+1=2，然后重新发起选举，而且在B的任期内，它所分发的log的term恒定为2，我们可以简单认为同一个term的log即为同一个leader的一个任期的数据。term是递增的，而且Raft规定：当节点在任意一次RPC中发现返回信息中的term比自己的term大时，那么就更新自己的term等于RPC中的term，而且如果这个节点是leader时，还需要将自己降级为follower（其实这里还有一个细节，如果影响这块的理解的话，可以先忽略：论文在第六章Cluster membership changes讲到为了避免发起无意义的选举，leader在收到大于自己term的rpc时还会再判断一下是否还能接收到大部分follower的心跳，如果能的话，它不会降级）。比如这里A故障恢复的话，发现B发过来的信息中term为2，而自己本地的term为1，那么A会将自己的term更新为2。
下面我们看下Raft判断何时应该发起选举？刚才我们提到leader会定时向follower发送心跳，假如follower在规定的时间（election timeout）内没有收到leader的心跳（leader发送心跳的间隔应该小于election timeout），那么该follower就会发起申请自己为leader的选举请求，分发给集群中的所有节点）。每个节点都有权利发起选举，虽然有可能它当选不上。
注意：Raft中的节点都是通过RPC来通信，而且Raft规定RPC的返回值都都需要带上自己的term，这个目的是为了让每个节点都及时的发现集群中最大的term并且及时更新。
election timeout并不是一个固定的值，而是一个时间范围，论文推荐的经验范围：150-300ms，每个节点从这个范围内随机选择一个数值作为自己的election timeout。这样做的原因是因为：假如节点都采用同一个election timeout的话，很有可能当leader挂了时候，所有节点会同时发起选举请求，并且每个节点都选择自己作为leader，那么选举往往会失败陷入死循环。Raft论文中说到他们也曾经尝试过别的选举方案，最后确定随机timeout是他们目前测试效率最高的方案。
节点在election timeout时长内没有收到leader的心跳的话会发起选举，投自己为leader，那如何才能确保自己能够当选呢！颜值？身高？长度？财富？我们技术从业者从来都不是肤浅的人，我们是高尚的、纯粹的、脱离了低级趣味的人，绝不会庸俗的向钱看，所以我们看中的是身高+长度。身高即为term的大小，而长度即为log的长度，简单理解又长又大的server才能当选leader，好，又到了没图说个jb的环节。
上面这个图太抽象了，下面才是正确的图：
Raft规定，当节点B接收到节点A发送过来的选举请求时（每个节点都只会投自己为leader，并且分发），如果在这之前B没有投给别的节点，并且A中的log对比B中的log是up-to-date的话，那么B便投A一票。何为up-to-date？即首先A中最新的log的term要大于等于B的term，其次term相等的话，A log的长度需要大于等于B log的长度，还是两个维度（高度和长度）比大小的问题。
1. 针对同一个term，假如B在A的请求到达之前已经投了别的节点C（因为很可能有多个节点都在竞选leader，而且C和A的term相同），那么B需要拒绝A，因为B不能同时同意两个节点，不然很可能会选出来多个leader。
2. 满足第一个条件的情况下，只有申请leader的节点A与当前节点B的log对比符合up-to-date时，节点B才会投该节点A一票，投票的方式即：RPC请求返回success。
3. 节点A收到超过半数以上的success之后，变会切换成leader角色，并且携带自己的term，向所有人发送心跳，确认自己的leader地位。
Figure-6中最上面一行即为log的index，方框中的数字即为每条log对应的term，目前leader是最上面的那个节点。这里猜想一下，假如leader挂了，此时第几行有机会成为leader？按照上面的条件，第三和第五行都有机会成为leader，第三行不论是term还是index都是节点中最大的，符合条件。第五行term是最大的，但是index不是最大的，不过第五行的index要比第二和四行大，假如二、四两个节点先收到了第五个节点的选举请求时，它们会返回success，这时也满足半数以上节点同意的要求（包含该节点自己），第五个节点当选为leader。而且从图中我们也可以看出：第五个节点的最新log正好就是commit的log点，也就是说只要身高长度大于等于第五行的节点都满足当选leader的要求（因为此时index=8的数据并没有commit）。同样也说明一个问题：并不是最大最高的节点才可以当选，只要它比一大半节点要大就有机会成为leader。（虽然我不是最靓的仔，但是还要把最靓的妹）
Log Replication
leader一旦当选之后，它就负责与client进行通信，并且将数据及时的同步到follower节点。leader通过心跳来携带log entries，通过图6可以看出，假如节点5当选了leader，它向不同的节点同步数据的情况是不一样的，有的需要同步（如2、4节点），有的需要覆盖（如1，3节点）。
Raft的处理流程是：
1.首先leader为每一个follower维护一个nextIndex，可以认为是一个nextIndex数组，对应每个follower目前log复制到的index位置，并且nextIndex初始值都是当前leader的最新log的index+1。然后leader会从nextIndex-1处开始发送RPC试探：假如follower在index=nextIndex-1处的log和leader的log数据是不一致的话，返回false，leader在接收到false信息后，会将对应follower节点的nextIndex--，然后再次疯狂试探，不停的减1总能试探到一个匹配的位置，然后从该位置起将leader的log全部覆盖到follower的log（论文中对减1的操作提出了优化，可以根据log情况，每次减n来优化rpc次数，详情用户自行翻阅论文）。
图6是一个特别简单的场景，节点5为leader时，假如向节点4同步数据时，首先向将自己最新的index（7）、term（3）还有log内容（x=5）都发送给节点4，节点4发现没有这条log，然后返回false，节点5收到false后，将节点4对应的nextIndex设置为6、term为3，然后再次试探，如此反复，终于在index=2，term=1处试探成功，然后开始从该位置拷贝log。
论文中leader向follower发送的index参数名为prevLogIndex，该值为nextIndex-1，这里为了方便理解，我们假定了nextIndex即为prevLogIndex。而且follower在做判断时，会首选判断leader的term是不是大于自己的，如果leader的term小于自己，那么立马返回false，根据之前提到的规则，只要leader发现自己的term不再处于领先地位时，会自动退位。
这里follower还有一个操作：commit。leader在向follower发送RPC时，不仅包含了上面提到的信息，而且还有一个leaderCommit参数，该参数表示当前leader已经commit到的log的index。follower在接收到leaderCommit后，会根据自己log的实际情况，来更新自己的commitIndex（每个节点都维护有自己的commitIndex）。假如leaderCommit > 自身的commitIndex，那么将commitIndex设置为min(leaderCommit, 自身log的最大index)，因为有可能follower还并没有完整的log记录，此时只能选自身log的最大index作为commitIndex。
Commit的问题
上面我们顺带手说了一下follower的commit操作，但是我个人感觉这个操作对理解Raft如何保证数据一致性的问题来说意义不大，它主要做的只是将数据及时的应用在自己的状态机上，而且leader活着的时候，它是不负责对外提供数据查询的。
所以我们重点再关注一下leader的commit。
首先再次回顾一下，leader何时可以进行commit？答：当leader上面的某个log已经被大部分的follower接收之后，该log以及之前的log都可以认为是committed状态，commit所做的就是将这些log的变更应用在状态机上（log是有序复制的）。而且还有一个很关键的操作：向client返回success！这里的client是真正的对数据发起请求的客户端，因为所有请求都是从client发起的，假如client迟迟得不到server的反馈的话很有可能它还会再次发送请求，万一操作不是幂等的（X++），那数据就有问题了（很有可能++操作被执行了多次）。所以log的commit是需要把client也要考虑在内的，这才是一个闭环。
那聪明的观众就要问了：网络是不稳定的，无法保证server返回的success信息client就一定能够收到，假如返回信息丢失了，client超时没有收到返回结果，重新发起了请求，那该如何是好？
Raft给出了一个解决方案：就是每个请求request都附加上一个唯一的编号，当server收到一个请求后，它会判断一下这个request是否已经是committed（如何判断方法不一，视具体情况而定），如果发现该请求已经commited，不会再生成新的log，而是直接返回success。
好，说完了leader和follower的commit操作、leader与client的交互，论文中还提到了数据安全性的问题。下面我会提出一系列问题或结论来解释这个问题（笔者也是想了很久才明白这问题，后来发现原来是问题压根就没整明白，更别说看得懂答案了）。
达到什么样的状态就可以认为log是committed？看过论文应该都知道，每个节点都有一个commitIndex来保存当前commit点，但是这个状态是常驻内存，并不持久化到硬盘，节点重启后其实是没办法恢复这个commitIndex的。而且我认为这个commitIndex只是一个结果，个人认为只要该条log已经在大部分follower节点上同步成功时，该log就是committed。之前提到的更新状态机、向client返回success都是达到这个状态之后需要附加做的事情，这些事情哪怕没有做，该log也认为是committed状态的。
另外只有包含所有committed log的节点才有资格当选成leader。具体Raft是如何保证的，有兴趣的可以参看论文，记住这个结论就ok了。
集群会存在一种状态：某个log被leader复制到了一部分follower，但是不到半数以上，并不满足committed条件。这个时候假如leader挂了，新的leader恰好有这一部分数据，它会完成上一个leader的遗志，继续复制这些log，这时候问题就来了：新的leader能不能在复制上个leader遗留下的未commit的log到大部分节点后，直接commit上一个leader的log？
既然这样问了，往往答案是不能的，思考一下为什么不能。
如图所示，图中有abcde五个阶段，在a阶段S1是leader，并且将index为2的log复制到了S2上面，此时S1挂掉了。然后根据我们之前的理论，因为index为2的log并不是committed状态，此时其实每个节点都有资格成为leader，这里S5当选了leader并进入b阶段，更新term为3，而且顺带接收了一个request，本地写了一个新的log（不过index仍然为2），不过S5更悲剧，它只写了本地log之后就同样悲催的挂掉了，甚至都还没来得及跟外面的节点同步它的log。此时S1又神奇的活过来了，而且按Raft的规则，S1是有资格重新竞选leader的（因为S5的log并不是committed的），并且S1真的做到了当上了leader，此时处于c阶段，而且S1顺带还好心的把自己在上个任期没有完成的事情给完成了：就是把term=2、index=2的log复制到大部分节点上，如图S3接收了S1发送过来的term=2、index=2的log（Raft永远不修改log，只追加log，所以index为2的log依然保留之前的term）。
最关键的点来了，假如S1向S3发送了index为2的log并且成功了，这个时候S1能对index为2的log做commit操作吗，能返回给client说该请求已经写入成功吗？上面我们已经说了：答案是亚麻跌。
为什么不可以，因为此时假如S1叕挂掉了话，根据Raft选举规则，S5是可以再次当选为leader的，而S5呢，它在index为2的位置是含有另外一条不同于S[1-3]的log，并且S5会用自己的log覆盖掉S[1-3]已经存在的log，那就意味着S1写入的这条log写入失败了，为commit失败状态。所以Raft规定了新的leader是不可以直接提交之前的leader所残留的log的，它能做的只是帮之前的leader复制一下，然后再接收到新的请求之后，它可以commit属于自己term的log，而且Raft规定：log commit之后，该log之前的log都默认会被提交，只能用这种间接的方式来提交上个leader的log。
我们来论证一下为什么这种方法就可行：如c、d所示，S1向S3同步log之后挂掉了，并且它不能提交不属于自己term的log，此时不会向client返回该log的success，即使后来被S5覆盖，那么通知client该请求写入失败即可，符合预期。
又假如S1将index=2的log同步成功之后，又写入了新的属于自己的log（e图中的index=3的log），此时S1可以提交index=3的log，并且这个时候它才挂掉的话，根据Raft的规定，此时S5是没有资格当选leader的，这就避免了S5覆写其余节点log的问题。所以Raft针对commit操作提出了这样一个限制。
以上就是Raft算法的主要内容了，包括leader的选举，log的replication，以及commit的限制。论文后面还介绍了集群节点角色变更，log compaction，client交互过程等，并不是特别难理解，而且client交互的部分上面也提到了一点，有兴趣的读者可以自行翻阅。
总结与思考
1. Raft性能如何？Raft中leader采用心跳的方式，既维持自己的地位，并且同时在心跳中加入需要同步的log数据。看似减少了网络开销，但是我个人认为这样会不会导致哪怕是仅仅一个很小的request，也起码需要等待一个心跳周期才可以完成，响应时间是不是没有那么及时？
比如存在一个分布式数据库，插入了一条数据，数据采用Raft协议做replica，从client发起请求到写入成功，是不是至少需要等到一个心跳周期（100ms）才能返回？
如果有好的解决方案是采用批量的方式？
2. 分布式数据库中，往往会对数据进行分片，比如HBase中的数据就是按region来划分，不过HBase数据的Replica是采用HDFS来实现的。假如采用Raft做数据的Replica，每个region都是一个leader，而且每个leader都会在集群中向follower节点保持心跳，region过多的情况下，大量RPC会不会影响整个系统的性能？
3. 存在一种情况：leader已经被取代了，并且只有这个leader它自己不知道，不加任何处理的话，stale leader还是响应client的请求，尤其是读请求，返回的是过期的数据。所以Raft规定leader在收到client的读请求时，需要首先保证自己还能收到follower节点的心跳，确认自己当前还是leader，然后再返回数据，无形之中也会影响性能。
考虑到数据库是一个对性能要求极高的系统，加上第一个问题描述的心跳所存在问题，猜想Raft的性能是否能够满足分布式数据库存储的Replica的场景，如果满足，如何优化？
欢迎读者留下宝贵的建议，共同进步
欢迎读者留下宝贵的建议。共同进步
欢迎读者留下宝贵的建议。共同进步
vx：q329853099
