背景介绍
分布式系统是指一组独立的计算机，通过网络协同工作的系统，客户端看来就如同单台机器在工作。随着互联网时代数据规模的爆发式增长，传统的单机系统在性能和可用性上已经无法胜任，分布式系统具有扩展性强、可用性高、廉价高效等优点得以广泛应用。
但与单机系统相比，分布式系统在实现上要复杂很多。cap理论是分布式系统的理论基石，它提出以下3个要素：
lconsistency（强一致性）：任何客户端都可以访问到同一份最新的数据副本。
lavailability（可用性）：系统一直处于可服务状态，每次请求都能获得非错的响应。
lpartition-tolenrance（分区可容忍性）：单机故障或网络分区，系统仍然可以保证强一致性和可用性。
一个分布式系统最多只能满足其中2个要素。对于分布式系统而言，p显然是必不可少的，那么只能在ap和cp之间权衡。ap系统牺牲强一致性，这在某些业务场景下（如金融类）是不可接受的，cp系统可以满足这类需求，问题的关键在于会牺牲多少可用性。传统的主备强同步模式虽然可以保证一致性，但一旦机器故障或网络分区系统将变得不可用。paxos和raft等一致性算法的提出，弥补了这一缺陷。它们在保证cp的前提下，只要求大多数节点可以正常互联，系统便可以一直处于可用状态，可用性上显著提高。paxos的理论性偏强，开发者需要自己处理很多细节，这也是它有很多变种的原因，相对而言raft更易理解和工程化，一经提出便广受欢迎。
在我们关注的消息中间件领域，金融支付类业务往往对数据的强一致性和高可靠性有严格要求。
在对主流的消息中间件进行调研后，发现它们在应对这种场景时都存在一定的不足：
lrabbitmq：一个请求需要在所有节点上处理2次才能保证一致性，性能不高。
lkafka：主要应用在日志、大数据等方向，少量丢失数据业务可以忍受，但不适合要求数据高可靠性的系统。
lrocketmq：未采用一致性算法，如果配置成异步模式可能丢失数据，同步模式下节点故障或网络分区都会影响可用性。
lsqs：只提供最终一致性，不保证强一致性。
鉴于以上分析，我们设计开发了基于raft的强一致高可靠消息中间件cmq。接下来会介绍raft算法原理细节、如何应用在cmq中在保证消息可靠不丢失，以及实现过程中在性能方面所作的优化。
二raft算法介绍
2.1概述
raft算法是diegoongaro博士在论文《insearchofanunderstandableconsensusalgorithm》,2014usenix中首次提出，算法主要包括选举和日志同步两部分:
以下是贯穿raft算法的重要术语：
节点之间通过rpc通信来完成选举和日志同步，发送方在发送rpc时会携带自身的term，接收方在处理rpc时有以下两条通用规则：
1)rpc中的rterm大于自身当前term，更新自身term=rterm、votedfor=null，转为follower。
2)rpc中的rterm小于自身当前term，拒绝请求，响应包中携带自身的term。
2.2选举算法
raft算法属于强leader模式，只有leader可以处理客户端的请求，leader通过心跳维持自身地位，除非leader故障或网络异常，否则leader保持不变。选举阶段的目的就是为了从集群中选出合适的leader节点。
选举流程如下：
节点初始状态均为follower，follower只被动接收请求，如果electiontime到期时仍未收到leader的appendentryrpc，follower认为当前没有leader，转为candidate。
candidate在集群中广播requestvoterpc，尝试竞选leader，其他节点收到后首先判断是否同意本次选举，并将结果返回给candidate。如果candidate收到大多数节点的同意响应，转为leader。
leader接收客户端请求，将其转为entry追加到日志文件，同时通过appendentryrpc同步日志entry给其他节点。
选举超时值：
在选举时可能会出现两个节点的选举定时器同时到期并发起选举，各自得到一半选票导致选举失败，选举失败意味着系统没有leader，不可服务。如果选举定时器是定值，很可能两者再次同时到期。为了降低冲突的概率，选举超时值采用随机值的方式。此外，选举超时值如果过大会导致leader故障会很久才会再次选举。选举超时值通常取300ms~600ms之间的随机值。
2.3日志同步
选举阶段完成后，leader节点开始接收客户端请求，将请求封装成entry追加到raft日志文件末尾，之后同步entry到其他follower节点。当大多数节点写入成功后，该entry被标记为committed，raft算法保证了committed的entry一定不会再被修改。
日志同步具体流程：
1）leader上为每个节点维护nextindex、matchindex，nextindex表示待发往该节点的entryindex，matchindex表示该节点已匹配的entryindex，同时每个节点维护commitindex表示当前已提交的entryindex。转为leader后会将所有节点的nextindex置为自己最后一条日志index+1，matchindex全置0，同时将自身commitindex置0。
2）leader节点不断将user_data转为entry追加到日志文件末尾，entry包含index、term和user_data，其中index在日志文件中从1开始顺序分配，term为leader当前的term。
3）leader通过appendentryrpc将entry同步到followers，follower收到后校验该entry之前的日志是否已匹配。如匹配则直接写入entry，返回成功；否则删除不匹配的日志，返回失败。校验是通过在appendentryrpc中携带待写入entry的前一条entry信息完成。
4）当follower返回成功时，更新对应节点的nextindex和matchindex，继续发送后续的entry。如果matchindex更新后，大多数节点的matchindex已大于commitindex，则更新commitindex。follower返回失败时回退nextindex继续发送，直到follower返回成功。
5）leader每次appendentryrpc中会携带当前最新的leadercommitindex，follower写入成功时会将自身commitindex更新为min(lastlogindex,leadercommitindex)。
同步过程中每次日志的写入均需刷盘以保证宕机时数据不丢失。
日志冲突：
在日志同步的过程中，可能会出现节点之间日志不一致的问题。例如follower写日志过慢、leader切换导致旧leader上未提交的脏数据等场景下都会发生。在raft算法中，日志冲突时以leader的日志为准，follower删除不匹配部分。
如下图所示，follower节点与leader节点的日志都存在不一致问题，其中(a)、(b)节点日志不全，(c)、(d)、(e)、(f)有冲突日志。leader首先从index=11(最后一条entryindex+1)开始发送appendentryrpc,follower均返回不匹配，leader收到后不断回退。(a)、(b)在找到第一条匹配的日志后正常同步，(c)、(d)、(e)、(f)在这个过程中会逐步删除不一致的日志，最终所有节点的日志都与leader一致。成为leader节点后不会修改和删除已存在的日志，只会追加新的日志。
2.4集群管理
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日志相差不大即认为d已追上。
删除节点：
如下图所示，集群中原来包含abcd，a为leader，现在剔除节点d。
1)leadera创建一条configentry，其中集群信息为abc。
2)a将日志通过appendentryrpc同步给节点bc。
3)abc在应用该日志后集群信息变为abc，a不再发送appendentry给d，d从集群中移除。
4)此时d的集群信息依旧为abcd，在选举超时到期后，发起选举，为了防止d的干扰，引入额外机制：所有节点在正常接收leader的appendentry时，拒绝其他节点发来的选举请求。
5)将d的数据清空并下线。
2.5快照管理
在节点重启时，由于无法得知statematchine当前applyindex(除非每次应用完日志都持久化applyindex，还要保证是原子操作，代价较大)，所以必须清空statematchine的数据，将applyindex置为0,，从头开始应用日志，代价太大，可以通过定期创建快照的方式解决该问题。如下图所示：
1）在应用完entry5后，将当前statematchine的数据连同entry信息写入快照文件。
2）如果节点重启，首先从快照文件中恢复statematchine，等价于应用了截止到entry5为止的所有entry，但效率明显提高。
3）将applyindex置为5，之后从entry6继续应用日志，数据和重启前一致。
2.6异常场景及处理
raft具有很强的容错性，只要大多数节点正常互联，即可保证系统的一致性和可用性，下面是一些常见的异常情况，以及他们的影响及处理：
可以看到异常情况对系统的影响很小，即使是leader故障也可以在极短的时间内恢复，任何情况下系统都一直保持强一致性，为此牺牲了部分可用性（大多数节点故障时，概率极低）。不过，leader故障时新的leader可能会包含旧leader未提交或已提交但尚未通知客户端的日志。由于算法规定成为leader后不允许删除日志，所以这部分日志会被新leader同步并提交，但由于连接信息丢失，客户端无法得知该情况。当发起重试后会出现重复数据，需要有幂等性保证。此外，raft的核心算法都是围绕leader展开，网络分区时可能出现伪leader问题，也需要特殊考虑。
三raft在cmq中的应用和性能优化
3.1raft算法在cmq中的应用
我们用statematchine统一表示业务模块，其通过applyindex维护已应用的日志index。以下为raft与状态机交互的流程：
1）客户端请求发往leader节点。
2）leader节点的raft模块将请求转为entry并同步到followers。
3）大多数节点写入成功后raft模块更新commitindex。
4）各节点的statemachine顺序读取applyindex+1到cimmitindex之间的entry，取出其中的user_data并应用，完成后更新applyindex。
5）leader上的statemachine通知客户端操作成功。
6）如此循环。
下面介绍cmq详细的生产消费流程：
生产流程：
1）生产者将生产消息的请求发往leader的raft模块。
2）raft模块完成entry的创建和同步。
3）大多数节点上持久化并返回成功后entry标记为committed。
4）所有节点的statemachine应用该日志，取出实际的生产请求，将消息内容写入磁盘，更新applyindex。该步骤不需要刷盘。
5）leader回复客户端confirm，通知生产成功。
6）如果此后机器重启，通过raft日志恢复生产消息，保证了已confirm的消息不丢失。
消费流程：
1）消费者从leader节点拉取消息。
2）leader收到后从磁盘加载未删除的消息投递给客户端。
3）客户端处理完成后ack消息，通知服务器删除消息。
4）ack请求经raft同步后标记为committed。
5）各节点状态机应用该日志，将消息对应的bit置位，将其设置为已删除并更新applyindex。
6）通知客户端删除成功。
7）如果机器重启，通过raft日志恢复ack请求，保证了已删除的消息不会再投递。
快照管理：
快照管理与业务紧密相关，不同系统快照制作的成本差异很大，cmq中快照的内容十分轻量，一次快照的耗时在毫秒级，平均5min创建一次，各节点独立完成。实现上内存中维护了一份动态的快照，制作快照时首先拷贝出动态快照的副本，之后处理流继续更新动态快照，用拷贝出的副本创建快照文件，不影响实际的处理流。快照具体内容包括：
1）term：快照对应entry的term（参照算法）
2）index：快照对应entry的index（参照算法）
3）node_info：entry时的集群配置信息。
4）topicinfo：每个队列一项。cmq中同一队列生产的消息顺序写入，分片存储，因此只需记录最后一个分片的状态（分片文件名，文件偏移量）。
5）queueinfo：每个队列一项。cmq中采用bitmap记录消息的删除情况，在内存中维护，在制作快照时dump到快照文件。
3.2raft算法性能优化
raft算法的性能瓶颈主要有两方面：
1）每次日志写入后都需要刷盘才能返回成功，而刷盘是一个比较耗时的操作。
2）由于算法限制，所有的请求都由leader处理，不能做到所有节点皆可提供服务。
针对以上两个问题，我们做了以下优化：
batchprocessing：在请求量较大时，并不是每一条日志写入都刷盘，还是累积一定量的日志后集中刷盘，从而减少刷盘次数。对应的，在同步到follower时也采用批量同步的方式，follower接收后将日志批量写盘。
multi-raft：进程中同时运行多个raft实例，机器之间组建多raft组，客户端请求路由到不同的group上，从而实现多主读写，提高并发性能。通过将leader分布在不同机器上，提高了系统的整体利用率。
async-rpc：在日志同步过程中采用同步rpc方式，在一端处理时另一端只能等待，性能较差。我们采用异步的方式使得leader端发送和follower端处理并发进行。发送过程中leader端维持一个�...