介绍Raft算法是一种分布式共识算法。它比paxos更容易理解和设计。我们已将算法完整实现并应用在自主研发的高可靠消息中间件CMQ中，同时沉淀Raft算法库供外部使用。本文主要介绍了Raft算法的原理、工程中遇到的问题及解决方法，以及提高性能的措施。一、背景介绍分布式系统是指一组通过网络协同工作的独立计算机。客户端看起来像一台机器在工作。随着互联网时代数据规模的爆发式增长，传统的单机系统在性能和可用性上已经无法胜任。分布式系统具有扩展性强、可用性高、成本低、效率高等优点，得到广泛应用。但是，与单机系统相比，分布式系统的实现要复杂得多。CAP理论是分布式系统的理论基石。它提出了以下三个要素：一致性（强一致性）：任何客户端都可以读取到其他客户端的最新更新。可用性（availability）：系统始终处于可服务状态。Partition-tolenrance（分区容错）：单机故障或网络分区时，系统仍能保证强一致性和可用性。分布式系统最多只能满足其中两个要素。对于分布式系统来说，P显然是必不可少的，所以只能在AP和CP之间权衡。AP系统牺牲了强一致性，这在一些业务场景（比如金融）中是不能接受的。CP系统可以满足这样的要求。问题的关键是会牺牲多少可用性。传统的主备强同步模式虽然可以保证一致性，但是一旦机器出现故障或者网络分区，系统就会变得不可用。paxos、raft等共识算法的提出弥补了这一缺陷。在保证CP的前提下，他们只要求大部分节点可以正常连接，系统可以一直处于可用状态，可用性显着提高。paxos的理论性很强，开发者需要自己处理很多细节，这也是它有很多变种的原因。相对来说，raft更容易理解和工程化，一经提出便火了起来。在我们关注的消息中间件领域，金融支付业务往往对数据的强一致性和高可靠性有严格的要求。强一致性：A转100元给B，系统返回A转账成功。之后B查看余额时，应该可以显示100元到账了。如果发现没有接收到或者过了一段时间没有接收到，那么这样的系统就不是强一致性的；高可靠性：如果一个请求成功返回给客户，那么就需要保证请求结果不会丢失。调研了主流的消息中间件，发现它们在处理这种场景时都存在一定的不足：RabbitMQ：一个请求需要在所有节点上处理两次才能保证一致性，性能不高。Kafka：Kafka主要用在日志和大数据方面。少量的数据丢失是可以容忍的，但不适合对数据可靠性要求高的系统。RocketMQ：没有使用一致性算法。如果配置为异步模式，数据可能会丢失。在同步模式下，节点故障或网络分区都会影响可用性。SQS：只提供最终一致性，不保证强一致性。针对以上分析，我们设计开发了CMQ，一个基于Raft的强一致、高可靠的消息中间件。接下来我们将详细介绍raft算法的原理，如何应用到CMQ中来保证消息可靠不丢失，以及我们在实现过程中所做的性能优化。2Raft算法核心原理2.1概述Raft算法最早由DiegoOngaro博士在2014年USENIX的论文《In Search of an Understandable Consensus Algorithm》中提出。该算法主要包括选举和日志同步两部分：最后阶段的选举：从集群中选出一个合适的节点作为Leader。第二阶段日志同步：选出的Leader接收客户端请求，并转化为raft日志。Leader将日志同步到其他节点。当大多数节点写入成功时，日志变为Committed。一旦Committed，日志将不会被篡改。当Leader失败时，切换到***阶段重新选举。以下是贯穿整个Raft算法的重要术语：Term：节点的当前周期可视为一个文明时代。votedFor：当前Term的投票信息，每个节点只能对给定的Term投票一次。entry：raft日志中的基本单元，包括index、term和user_data。索引在日志文件中按顺序分配，term是创建entry的leaderterm，user_data是业务数据。State：节点角色（Leader、Candidate、Follower之一）。CommitIndex：已经提交的日志Index。StateMachine：状态机。业务模块与Raft交互。ApplyIndex：已经应用到的日志Index。ElectionTime：选举超时。节点使用RPC通信完成选举和日志同步。发送方在发送RPC时会携带自己的Term，接收方在处理RPC时有如下两个通用规则：RPC中的RTerm大于自己当前的Term，更新自己的Term=RTerm，votedFor=null，转换为Follower。RPC中的RTerm小于自己当前的Term，请求被拒绝，响应包携带自己的Term。2.2选举Raft算法属于强领导模式。只有领导者才能处理客户的请求。Leader通过心跳来维护自己的状态。除非领导者出现故障或网络异常，否则领导者将保持不变。选举阶段的目的是从集群中选出一个合适的Leader节点。选举过程：1、节点初始状态为Follower，Follower只是被动接收请求。如果在ElectionTime超时时没有收到Leader的AppendEntryRPC，Follower认为当前没有Leader，转向Candidate。2.Candidate在集群中广播RequestVoteRPC，试图竞选Leader。其他节点收到后首先判断是否同意本次选举，并将结果返回给Candidate。如果Candidate收到大多数节点的同意响应，它将成为Leader。3.Leader收到客户端请求，将其转化为一个Entry追加到日志文件中，同时通过AppendEntryRPC将日志Entry同步到其他节点。下面通过一个案例详细说明选举过程。1）初始状态：由3个节点组成的集群，初始状态均为Follower状态，图中方块代表节点的raft日志。2）发起选举：节点1的选举定时器先超时，转为Candidate，Term自动递增，更新voteFor=1（为自己投票），然后广播RequestVoteRPC给节点中的其他节点集群，RequestVoteRPC会携带节点的日志信息。3）响应选举：节点2和节点3收到RequestVoteRPC后，根据RPC规则更新term和voteFor(term:6,voteFor:null)；然后判断是否同意本次选举，如果已经投给别人，则拒绝投票第二次选举（这里voteFor:null未投），如果登录RequestVoteRPC不完整，则拒绝，否则同意（日志节点1比这里的2和3更完整）；***通过voteReplyRPC响应投票结果。4）选举完成：由于节点2和节点3都同意本次选举，所以节点1在收到任何一个voteReplyRPC（多数同意）后，就会成为leader。选举超时值：在选举过程中，两个节点的选举定时器可能同时超时发起选举。每个节点获得一半的选票，选举失败。选举失败意味着系统没有Leader，无法服务。如果选举计时器是常数，很可能两者会再次同时到期。为了减少冲突的概率，选举超时值采用随机值。另外，如果选举超时值过大导致Leader失效，需要很长时间才能重新选举。选举超时值通常取300ms到600ms之间的随机值。2.3日志同步选举阶段完成后，Leader节点开始接收客户端请求，将请求封装成一个Entry，追加到raft日志文件的末尾，然后将Entry同步到其他Follower节点。当大部分节点写入成功后，Entry被标记为committed，raft算法保证committed的Entry永远不会被修改。日志同步的具体过程：1）Leader为每个节点维护NextIndex和MatchIndex。NextIndex表示要发送给节点的Entry索引，MatchIndex表示该节点匹配的Entry索引，每个节点维护CommitIndex表示当前提交的Entry索引。成为Leader后，所有节点的NextIndex会被设置为上一条日志索引+1，MatchIndex会被设置为0，自身的CommitIndex会被设置为0。2）Leader节点会不断的将user_data转化为Entry并将其附加到日志文件的末尾。Entry包括index、term、user_data，其中index在日志文件中从1开始依次赋值，term为Leader当前任期。3）Leader通过AppendEntryRPC将Entry同步给Follower，Follower收到后验证Entry之前的日志是否匹配。如果匹配，则直接写入Entry，返回成功；否则，将删除不匹配的日志并返回失败。验证是通过在AppendEntryRPC中携带之前的entry信息写入到Entry中来完成的。4）当Follower返回成功后，更新对应节点的NextIndex和MatchIndex，继续发送后续的Entry。如果MatchIndex更新后大部分节点的MatchIndex大于CommitIndex，则更新CommitIndex。当Follower返回失败时，返回NextIndex并继续发送，直到Follower返回成功。5）Leader会在每次AppendEntryRPC中携带当前的***LeaderCommitIndex，Follower写入成功后，Follower会更新自己的CommitIndex为Min(LastLogIndex,LeaderCommitIndex)。在同步过程中，每次写入日志都需要flush，保证宕机时数据不会丢失。下面举例介绍日志同步的基本过程：1）初始状态下，所有节点的Term=2，CommitIndex=2，此时Leader收到一个y←9的请求，转换为Entry写入到日志末尾，Entry的索引为3term=1。2）Leader通过AppendEntryRPC将Entry同步给2个Follower。RPC中包含了之前的Entry信息（index=2term=1），Follower收到之前的Entry后首先检查是否和自己匹配（这里是匹配成功），然后写入Entry，返回Leader成功。3)Leader收到Follower的回复包后更新对应节点的NextIndex和MatchIndex。此时大部分节点的MatchIndex大于CommitIndex，所以Leader更新CommitIndex=3。4）Leader继续向Follower发送AppendEntry。此时因为没有NewEntry，所以RPC中的entry信息为空，LeaderCommitIndex为3，Follower收到后更新CommitIndex=3(Min(3,3))。日志冲突：在日志同步过程中，可能会出现节点间日志不一致的情况。比如follower写日志太慢的场景，或者leader切换导致oldleader上有未提交的脏数据。在Raft算法中，当日志发生冲突时，以Leader的日志为准，Follower删除不匹配的部分。如下图所示，Follower节点和Leader节点的日志存在不一致。其中，(a)、(b)节点日志不完整，(c)、(d)、(e)、(f)节点日志冲突。Leader先从index=11（最后一个entryindex+1）开始发送AppendEntryRPC，Followers都返回不匹配，Leader收到后不断回滚。(a)、(b)找到第一个匹配的日志后会正常同步，(c)、(d)、(e)、(f)会在这个过程中逐步删除不一致的日志，最后所有节点的日志都一致与领袖。成为Leader节点后，现有的日志不会被修改或删除，只会追加新的日志。2.4算法证明了Raft算法的两个核心性质：1）提交的日志不会被修改；（可靠性）2）所有节点上的数据是一致的。(Consistency)具体证明如下：1)LeaderCompleteness：在给定Term上提交的日志必须存在于后续更高Term的Leader上。(Thelogisnotlost)TheelectedLeadermustcontainallthecurrentlysubmittedlogs:thesubmittedlogsexistonmostnodes,andthepremiseofagreeingtotheelectionisthatthecandidate'slogmustbecompleteorupdated.没有提交日志的节点肯定得不到大多数节点的投票（这些节点都提交了日志，不满足日志足够完整的前提），无法成为Leader。Leader节点不会修改或删除现有日志（算法的约束）。综上所述，无论是选举还是日志同步，都不会破坏提交的日志，事实证明。2）状态机安全：所有节点的数据最终是一致的。根据LeaderCompleteness可以看出提交的日志不会再被修改，业务的状态机将Entry中的user_data应用一一取出，最终所有节点的数据一致。2.5集群管理Raft算法在工程上充分考虑了集群管理问题，支持向集群动态添加节点，淘汰故障节点。下面详细介绍增加和删除节点的过程。添加节点如下图所示。集群包含ABC，A是Leader，现在添加节点D。1）清除D节点上的所有数据，避免脏数据。2）Leader通过AppendEntryRPC将库存日志同步到D，使D的数据跟上其他节点。3）D的日志追上后，LeaderA创建一个ConfigEntry，其中集群信息包括ABCD。4）LeaderA将ConfigEntry同步给BCD，Follower收到后应用。之后所有节点的集群信息变成ABCD，添加完成。注意：在第2步的过程中，Leader还在接收客户端请求生成Entry，所以只要D和A的log相差不大，就认为D赶上了。删除节点如下图所示。集群原本包含ABCD，A是leader，现在节点D被移除。1）LeaderA创建一个ConfigEntry，其中集群信息为ABC。2）A通过AppendEntryRPC将日志同步到节点BC。3）ABC应用日志后，集群信息变为ABC，A不再向D发送AppendEntry，D从集群中移除。4）此时D的簇信息还是ABCD。选举超时后，发起选举。为了防止D的干扰，引入了一个额外的机制：当所有节点正常收到Leader的AppendEntry后，拒绝其他节点发送的选举请求。5）清除D的数据，下线。2.5Raft应用我们使用StateMatchine统一表示业务模块，通过ApplyIndex维护应用的日志索引。下面是Raft与状态机的交互过程：1）客户端请求发送到Leader节点。2）Leader节点的Raft模块将请求转化为Entry，同步给Followers。3）Raft模块在大部分节点写入成功后更新CommitIndex。4）各节点StateMachine依次读取ApplyIndex+1和CimmitIndex之间的Entry，取出user_data并应用，完成后更新ApplyIndex。5）Leader上的StateMachine通知客户端操作成功。6）如此循环。2.6快照管理节点重启时，由于无法获知StateMatchine当前的ApplyIndex（除非每次应用log都持久化ApplyIndex，保证原子操作，成本高），StateMatchine的数据必须清除并将ApplyIndex设置为0，从头开始应用日志，代价太大，这个问题可以通过定期创建快照来解决。如下图所示：1）应用Entry5后，将当前StateMatchine数据连同Entry信息写入快照文件。2）如果节点重启，首先从快照文件中恢复StateMatchine，相当于应用了直到Entry5的所有entry，但是效率明显提升。3）设置ApplyIndex为5，然后继续从Entry6开始应用日志，数据与重启前一致。快照的优点：减少重启时间：通过快照+ raft日志恢复，无需从第一个入口开始。节省空间：快照完成后，可以删除快照点之前的Raft日志。2.7异常场景及处理Raft具有很强的容错能力。只要大部分节点连接正常，就可以保证系统的一致性和可用性。下面是一些常见的异常情况及其影响和处理：可以看到异常情况对系统的影响很小，即使Leader挂了，也可以在很短的时间内恢复。不管怎样，系统保持强一致性，为此牺牲了一些可用性（当大部分节点失效时，概率极低）。但是当leader失效时，新的leader可能会包含老leader没有提交或者已经提交但是没有通知客户端的日志。由于算法规定日志成为leader后不允许删除，所以这部分日志会被新的leader同步提交。但是，由于连接信息丢失，客户端无法得知情况。当发起重试时，会出现重复数据，需要幂等性保证。另外，raft的核心算法是基于leader的，网络分区时可能会出现falseleader问题，这也需要特别考虑。下面是网络分区时生成伪Leader的过程：上面的例子中，Leader和两个Follower之间的网络不正常，但是两个Follower之间的通信是正常的。由于收不到Leader的心跳，其中一个Follower发起选举成为Leader。领导者成为伪领导者。接下来我们分析这种场景是否会影响系统的一致性：写一致性：发送给新leader的写请求可以提交，但是发送给伪leader的请求不能提交。Write请求中只有一个leader被正常处理，因此写入一致性不受影响。读一致性：如果读请求没有经过Raft同步，当客户端的写请求发送给新的leader并执行成功后，读请求发送给fakeleader并得到结果，会造成数据不一致。这个问题有两种解决方案：读请求也通过Raft同步，这样不会出现不一致，但是会增加系统负载。Leader节点收到读请求后，等待大部分节点再次响应心跳RPC，然后返回结果。因为大多数节点响应心跳，这意味着当前肯定没有另一个Leader（大多数节点仍然与当前Leader保持租约，新的Leader需要获得多数票）。2.8小结Raft算法具有强一致性、高可靠性、高可用性的优点，具体体现在：Leader节点是最完整的，所有的请求都由Leader发出。处理，所以从客户端的角度来看是强一致的。高可靠：Raft算法保证committedlog不会被修改，StateMatchine只应用committedlog，所以当client收到请求成功，就意味着数据不会改变。Committed日志在大部分节点上冗余存储，只有不到一半的磁盘故障数据不会丢失。高可用：从Raft算法的原理可以看出，选举和日志同步都只需要大部分节点的正常互联即可，因此少量节点故障或网络异常不会影响系统的可用性。即使leader失效，在选举超时后，集群会自动选举出新的leader，无需人工干预，不可用时间极短。但是当Leader失效时，会出现数据重复问题，需要业务去重或者幂等性保证。高性能：相对于必须向所有节点写入数据才能返回客户端成功的算法，Raft算法只需要大部分节点成功，少数节点处理缓慢，不会延迟整体的运行系统。原文链接：https://cloud.tencent.com/community/article/678192【本文为专栏作者《腾讯云技术社区》原创稿件，转载请联系原作者获得授权】点此查看更多关于作者的好文
