本文整理自APMCon 2016中国应用性能管理大会 数据库性能优化专场 京东资深架构师 张成远 题为《深入理解Raft及在NewSQL中的使用》的演讲，现场解读Raft核心内容，剖析etcd Raft库的设计实现，针对此类复杂分布式系统算法的测试方法，并介绍业界主流NewSQL的详细设计，Raft在其中发挥的重要作用，以及如何使用等。

张成远：我是京东资深架构师张成远，目前主要是做分布式数据库相关的一些架构研发等工作。今天主要讲一下Raft在NewSQL的使用，因为内容涉及到Raft和NewSQL，我会先讲一下什么是NewSQL，什么是事务以及一致性等，还有NewSQL大概是怎么做的，然后再讲一下Raft是什么以及Raft是怎么样工作的。

一、What is NewSQL

从SQL到NoSQL再到NewSQL，一路走来大概经历过这样一个发展过程，一开始最早的时候是SQL类产品，后来慢慢有了NoSQL的东西，最近这一两年开始有NewSQL这个概念。SQL理论，也就是关系型数据库理论大概是上世纪70年代左右就是已经提出来了，这个理论下产生了很多的产品，像MySQL、Oracle、PostgreSQL、SQL Server等很多很多。

后来随着分布式系统的发展衍生了NoSQL这个概念，出现了很多的分布式存储系统像Redis、mongoDB、cassandra等，这些NoSQL类的产品特点是不支持SQL，主要以KV形式存储，在扩容方面非常容易，可以较为轻松的进行一些集群的伸缩等操作。NoSQL出来以后一直喊着要把SQL颠覆，后来在实际生产环境中我们发现这两者是一种长期并存的趋势，每类产品都有一定的适用场景。

等到后来，大家可能希望出现一种东西可以结合SQL跟NoSQL的优点，既支持SQL支持事务又可以比较容易的进行集群的伸缩扩容等操作，让海量数据方面的处理可以更加的容易，所以就出现了NewSQL的概念。NewSQL这个概念之下，国内外都有一些优秀的开源的项目在做像TiDB、CockroachDB等，但目前开源领域可能还没有在生产环境当中真正大规模使用的。如果要说真正落地使用的话可能当属google的F1/spanner了，但他们家没有开源只有论文流出。

二、What is transaction

然后，接下来讲一下NewSQL最大的特点，就是支持SQL同时支持事务，支持SQL比较好理解，相当于可以用SQL的方式来增删改查这个系统，至于支持事务那我们就要回到非常老的一个问题，到底什么是事务？支持事务，那事务到底是什么定义？事务有ACID属性，也就是原子性、一致性、隔离性还有持久性。

原子性是指整个事务要么成功，要么失败(跟没有发生过一样)，不要有任何的中间状态。

一致性其实在一定程度上来说主要是数据库层面的完整性，打个比方A的帐户里面100块钱，B的帐户里面50块钱，然后，A给B 25块钱，首先是从A上减去25块钱，然后将这25块钱加到B上，最终都是75块钱。不能出现A减25块钱然后B的25块钱没有加上去，这样全局数据库完整性就不一致了，这个属性需要应用程序自己做更多的考虑，另外数据库层面保证了原子性、隔离性以及持久性的时候，外加应用程序自身的逻辑是正常的，那这个一致性就是可以保证的。

什么是隔离性呢，一般是指并发事务操作彼此之间不可见，简单的说就是A做操作的时候不要让B事务看到。

持久性，简单的理解就是事务commit了以后要保证这个事务是一直不会丢失的。比如你把A减了100块钱或者A加了100块钱，这个事情如果告诉用户已经成功了就是成功了，不能出现因为机器挂掉之类导致这种修改丢失。

还有一个概念也要提一下，这个也是一个比较老的概念，就是CAP。

很多时候会把CAP一致性和ACID的一致性混在一起，CAP一致性跟ACID的一致性其实是两回事情。CAP的一致性是针对很多个节点，要求各个节点之间的数据是完全一致的，也就是要求实际存储的数据是完全一致的一致性，也就是纯粹的多副本方式。

CAP里的A其实就是高可用，简单的理解就是随时去访问都可以访问到，CAP里的P是说在发生一些网络异常状况的时候是否可以容忍。在绝大多数的系统当中，理论上来说CAP是不能同时满足的，但在实际生产环境中往往选择弱化的P，也就是当发生网络异常时直接将一部分异常节点舍弃保证剩余节点的服务都是正常的从而保证了整体的服务，所以从这个角度上来说CAP是可以全部满足的，或者说满足生产需求已经足够。

上图是我们在做分布式数据库的时候一般的一些做法，很多的时候直接基于一些现有的SQL类产品，比如MySQL，外加一层数据库中间件的方式比如引入Proxy的方式来解决这个分布式数据库问题，SQL发过来以后由Proxy接收然后解析拆解，再把相应的SQL发到相应的SQL产品上，支持简单的事务。为什么叫做简单的事务呢，因为如果只涉及到一个分片是可以的，但是多个就是支持不了的，确切的说是因为不能保证严格的分布式事务的语义，后面会详细讲一下。

三、NewSQL 

那么NewSQL是怎么样的？NewSQL有很多种可能的实现方式，这里列举NewSQL其中的一种架构模式，如上图，上层兼容SQL协议的一个协调者，然后通过RPC之类的通信方式和底层存储通信，存储节点可能会选择Rocksdb之类的K/V存储系统。为什么说上图这个是一个协调者，但看到的效果看起来也像一个代理像一个Proxy？他的区别在于可以做很多的事情，可以对这个事务进行一些记录，记录到日志里面，还可以提供全局的事务ID之类，保证同一个大事务里的各个节点上的子事务ID可以和全局事务ID是一样，后面会详细讲一下。

一般来说，NewSQL要支持SQL同时有NoSQL的优点，这个从实现上面来说给用户的感觉就是SQL产品，SQL过来以后协调者会把它拆成各种各样的KV操作，丢到各个节点上去，相当于丢到多个分片上，但同一个分片上有很多个节点，这些节点之间要保证数据是一致的，这样可以做到这个分片上万一有节点挂了，还有另外的节点可以对外提供服务。

1、隔离性

那怎么保证同一个分片内多个节点之间的数据是一致的呢？Raft就是用来保证各个节点是一致的。为什么上图Rocksdb这层要引入Range的概念呢？因为作为一个节点可能数据量会非常大，后期要支持扩容怎么扩？如果这个节点不拆分是没有办法扩的，所以要引入Range这个逻辑概念。需要扩容的时候就可以把Range进行拆分成多个，每一个Rocksdb上面放很多的Range，然后把这些Range迁移到其他的Rocksdb上面去，相当于通过拆分加迁移方式同时达到扩容整个集群容量的目的，每一个Range相当于一个分片里的节点，多个Range通过Raft构成一个分片，同一个分片里的Range的数据是一样的。

现在我们再回过头去讲一下，为什么基于现有的SQL类产品开发一个Proxy的方式其实是没有办法保证严格的分布式事务的，有一种场景很容易理解：假设以MySQL为例，如果一个事务里有多条SQL，这些SQL如果涉及到不同的MySQL实例，可能会出现一个分片的MySQL上提交成功了，另一个分片的MySQL挂了，那就会出现事务只提交一半的情况，这种情况就保证不了原子性。

如果有一个分片的MySQL挂了，事务的原子性无法保证这种场景是比较好理解的，但是其实就算所有的分片上的MySQL都是正常的也是无法严格保证事务的，为什么呢？因为前面讲过ACID里有一个隔离性属性，并发事务之间要求是不可见的，而基于MySQL中间件的方式是保证不了隔离性的。

如上图，假设有4个事务是同时发生的，对于理解就是并发过去的到Proxy节点的时候实际上肯定是有一个顺序的，这个顺序我们假设是T1、T2、T3、T4个顺序，如果4个事务涉及到4个分片，4个事务同时落到四个片的MySQL上但实际上在每个MySQL上这四个事务的执行顺序可能是不一样的，每个MySQL上会有自己的一个执行序列，也就是这些事务在每个MySQL上会组成一个可串行化调度的序列，所谓可串行化调度就是并发的事务操作会按照一定的顺序执行，执行以后的效果等价于这些事务按照某个顺序串行执行的效果，那么这个调度序列就是可串行化调度的，而这些等价的串行顺序可能是一样的也可能是不一样的。比如这四个事务T1、T2、T3、T4在分片一上的执行顺序可能是T1、T3、T2、T4，分片二上的执行顺序却是T4、T2、T1、T3，分片三的执行顺序是T1、T2、T3、T4，而分片四上的执行顺序是T1、T4、T2、T3。

在这种情况下，分片2上就会出现事务T1会看到T4和T2的修改，而在分片1、3和4上，事务T1事务是先执行的，所以并不会看到T4和T2的修改，这就相当于在全局范围内，事务T4和T2的部分修改被T1读到了，而另一部分却没有被T1读取到，出现了T1和T2及T4之间的隔离是有问题的，所以在全局范围内是无法保证严格事务之间的隔离性的。

再举个例子如图所示，假设变量a和b都是5，此时有事务T1和T2且全局执行顺序是T1和T2，假设每个分片上都是按照T1和T2的方式执行，结果最终结果a和b都是14，此时是符合事务的可串行化调度的。

但是可能出现一种情况，在分片1上的执行顺序是T2、T1，分片2上的执行顺序是T1、T2，此时分片1上a就变成了15，而分片2上就变成了14， 这就不符合可串行化的条件了，因为从全局来说T1和T2是混在一起的，即不等价于T1T2的执行顺序也不等价于T2T1的执行顺序。怎么解决这个问题呢，这时一般会采用引入一个全局的事务ID，在实际执行的时候可能会采用时间戳的方式，具体细节这块今天先不展开讨论了。

2、原子性

前面讲了隔离性问题，现在我们再讲一下原子性，在保证分布式事务的时候要支持分布式事务语义，那ACID 4个属性都要满足，前面介绍了隔离性，那原子性这个怎么解决呢？在实际实现的时候往往采用类似两阶段提交的方式，我这里画的是两阶段提交的理论上的定义，全局会有一个协调者，事务要提交的时候协调者会发送请求到各个参与节点，参与节点确认可以提交了就会回复给协调者表示通过，如果参与节点表示这个事务因为一些原因不能提交就会给协调者反馈说这个事务需要回滚，那么协调者就会根据这些反馈信息来综合决定事务是否需要提交。只有所有的参与节点都表示可以提交，协调者才会在自己先写日志提交这个事务，然后发送commit命令到所有的参与节点，如果出现任何一个参与节点表示需要回滚，那么协调者就会在先写日志表示abort这个事务，然后把abort信息发送给每个节点。图上的每一个圈都是一个系统的状态，是一个典型的状态机，其中两层圆圈表示的终止状态，整个状态机最终会到达终止状态上，状态机的东西在后面我也会再提一下。

3、持久性

讲完NewSQL里怎么支持原子性和隔离性，我们再讲一下持久性。同时也要提一下CAP里的一致性，刚才已经说了CAP的一致性和ACID里的一致性不是一个概念，CAP里的一致性是解决多个节点副本之间数据一致性的问题，好比MySQL的主从数据完全一样，那就符合CAP里的一致性，从这个层面上来说CAP里的一致性其实对应事务里的持久性。

为什么这么说呢，大家想一个例子，还是以MySQL的主从为例来说明。主从主要可以解决高可用的问题也可以解决数据备份的问题，如果主从之间假设没有数据的复制，那么在主挂了或者出异常以后，从接替主开始对外服务相当于保证了CAP里的A，但是之前所有已经提交的事务都丢失了，因为主从之间没有进行数据复制，相当于丢失了ACID里的持久性。

假设主从之间有数据复制但是有延后，那么当发生主从切换的时候，依然会存在事务丢失的情况，因为可能会出现有几个事务在主上已经提交了，但是还没有复制到从上，此时主挂了从开始担任主对外提供服务依然保证了CAP里的A，但是依然会存在已经提交的事务丢失的情况。所以从这个角度来说CAP里的多个节点之间的一致性本质上是对应ACID属性里的持久性，如果不追求事务的持久性，那也就不用关心各个节点之间的数据是否一致了。

既然已经明确了CAP里的一致性本质上对应了持久性这个属性，那接下来的问题就是这个一致性也就是ACID里的持久性怎么做呢，对MySQL来说可能有半同步的复制方式，但是半同步在实际使用当中，如果真的出现一些问题比如网络问题或者机器性能问题等最终可能会变成异步复制，并不能保证严格的一致性。

所以在NewSQL中一般会考虑采用Raft来保证一致性。如上所示各个Node里有很多的Range，各个Range之间通过Raft来保证彼此之间的一致性，多个Range组成的Raft组合相当于是一个分片，Raft保证了这些Range之间的一致性从而保证了事务在同一个节点的多副本上的持久性。

四、What is raft

在真正开始介绍Raft之前，我想先引入一个状态机的介绍，因为前面的部分以及后面的部分都会涉及到状态机，那什么是状态机呢，需要简单介绍一下。

1、State machine

其实状态机可以简单的理解就是一个五元组，状态机可以记录为M={Q, ?,δ, q0, F}，其中Q是状态集合；?是输入符号，在实际工程中也可以理解为具体的事件；δ是转移函数，表示在某个状态下接收了某个符号会进入到什么状态；q0是整个状态机的可能的起始状态；F是整个状态机的终止状态，在实际表示的时候一般会用上层的圆圈表示，终止状态的理解更恰当的说是指相对稳定的状态，所以并不是说到了终止状态以后整个状态机就不工作了，比如图上这个状态机的效果就是接收了1*0+(0|1)*的字符串。之所以在这里提一下状态机到底是一个什么东西是因为前面的两阶段提交就是一个状态机，后面的Raft也是到处都是状态机。

现在接下去讲一下什么是Raft，Raft简单的说就是相比传统的Paxos算法来说是一个更简单且比较容易理解，在工程上也比较容易实现的一种一致性算法，通过选举leader以及日志复制的方式完成工作，具体的实现会有一些措施来确保整个算法是可以安全工作的，比如如何保证操作复制到多数节点才生效，再比如出现异常时少数节点上有的日志在大多数节点上可能是没有的这种情况，如何通过算法将这些日志清除掉。

上图是Raft工作的示意图，Client发送请求到Leader上，consensus部分可以理解为Raft的主要工作部分，请求先发送到consensus模块，consensus部分会把操作先记录到本地日志中，然后同时将这个操作复制到大多数其他节点上去，等确认大多数节点已经接收到了这个操作，然后会把这个操作apply到上层的状态机，在实际实现的时候可以理解为把这个操作真正的应用到K/V存储上去，比如Rocksdb。

2、Server State

一个Raft组合相当于有很多节点，里面除了leader的角色还会有其他的角色，上图是一个角色转换图，一个新加入的节点首先是一个follower的角色，如果follower加入的时候发现没有leader就会变成Candidate的角色，发起选举准备竞选leader，如果这个candidate节点收到了大多数节点的投票，那么它就可以顺利的成为leader开始对外提供服务。但是如果此时没有选举成功且整组里还是没有leader，那么这个candidate会继续进行选举。如果这个candidate发起选举的时候发现已经有其他的节点成为了leader，那么它就会回到follower角色，这是一个典型的一个状态机，其中follower是起始状态，而follower和leader可以理解为终止状态，candidate是普通中间状态，也就是每一个节点的稳定状态最终一定会在停留在这两个状态中的一个，终止状态不代表一旦进入就要永远停留在这个状态，确切的说应该理解为一种相对稳定的状态。

3、Term & log index

在介绍日志复制之前，需要介绍两个概念，Term和Log index，Term相当于一个抽象的逻辑时间单位，每个Term里只有一个leader，如果在这个Term里没有发生网络抖动或者leader出异常的情况也就是没有发生新的选举的情况，那么这个Term一直保持不变，leader也一直保持不变。Log index是指每条操作命令在记录到日志的时候所在日志的位置，可以将log理解为一个很大的数组，log index就像是这个大数组的下标，往Log里每添加一条操作，log index就加1。在添加操作的时候要同时记录该操作对应的index以及Term，所以会出现不同操作命令对应的Term是一样的情况，比如图上x=1这个操作Term是1，log index是1，y=1这个操作Term是2，log index是2，假如在此时发生了一次选举，后面的操作的记录情况可能出现如图上所示的情况，x=7这个操作Term=2，log index是3，y=5这个操作Term=2, log index是4，x=2这个操作Term=2，log index是5，假设此时又发生了选举，每次选举的时候Term都会往上增加，此时Term变成了3但是因为一些原因这个Term内选举没有成功，当这次选举失败以后发现还没有leader就继续将Term增大到4继续进行选举，所以后面的y=3的操作记录的时候对应的Term就是4，log index=6，紧接着之后y=6的操作Term=4，log index=7，后续其他操作的记录方式跟这个类似。

4、Log replication

下面我们再以日志复制的具体例子来分析一下日志是怎么在Raft的各个节点之间进行复制的。假设有3个节点，leader上有这些日志，从图上可以看到已经记录了有12条操作，方框里的数字是Term，从图上可以看到这个系统已经发生过几次选举，但是这个leader后来重新选举的时候又继续成为了leader，方框上面的数字代表的是log index，可以看到log index是依次递增的。这些所有的操作会被复制到所有的follower上，在leader这端相当于会维护一个信息记录每个follower都复制到哪里了，比如这个图上所示follower1已经复制到log index为6的位置了，而follow2已经复制到log index为9的位置了，因为leader自己已经到了log index为12的位置，那么在全局来说log index为9以及9之前的操作都已经复制到了大多数节点上，所以9这个位置及之前的操作都可以安全的apply到上层的状态机，在实际实现的时候可以理解为可以把这个操作安全的应用到Rocksdb上，而9这个位置也就是commit index, commit index代表的是这个log index所在位置及以前的操作在全局范围内已经复制到了大多数节点上是不会丢失的，本质是满足持久化条件的，所以可以安全的将这些操作真正的生效。

日志复制里还有两条非常关键的特性，在同一个Raft组里不同节点日志上的操作如果log index和Term是一样的，那么对应的操作一定是一样的；另一个是如果不同节点日志上的某个位置拥有相同的log index和Term，那么表示在这个位置之前的所有的操作都是一样的。

具体讲一下这个是怎么做到的，这里简单举个例子，上图示意的是一个leader和其中一个follower的情况，假设这个follower是follower1，从图上可以看出来Term为1的时候leader是leader，Term为2和3的时候，follower1成为了leader，不过从Term=4之后原来的leader又重新成为了leader，并且后来可能因为网络抖动等原因又发生了一次选举，leader节点依然被选为了leader，所以会看到Term=5的时候leader这个角色保持不变。

此时出现了一种什么情况呢，在follower1上我们可以看到Term=2和Term=3的时候对应的log index依次为4、5、6，而这三条操作在leader的日志里没有。这是一种什么样的情况呢，有可能的一种情况是在Term=2和Term3的时候，follower1成为了leader，把这三个操作记录到了自己的日志中，但是还没来得及复制到其他节点上结果因为网络抖动或者自身异常等一些原因，原来的leader重新发起选举又成为了leader。这个时候原来leader对外正常提供了服务，且日志里记录了Term=4及以后的操作，那这个follower1在接收leader日志的时候有一部分日志和leader的日志就是不一样的，这部分日志我们之前也已经提过需要剔除掉的。

那怎么剔除掉这部分日志呢？在这个follower重新连上leader的时候，leader会把当前自身的<serverid, currentITerm, preLogTerm, preLogIndex> 信息传给follower1,  preLogTerm和preLogIndex分别是leader当前日志里的最后一条日志的信息，在这个图中假设暂时没有新的发生选举，那么此时leader传给follower1的currentITerm、preLogTerm、preLogIndex分别是5,5,12。Follower1收到消息以后会检查自己日志的信息，一看自己当前的preLogTerm和preLogIndex分别是3和6，明显是不对应的，所以follower会告知leader自己当前的lastLogIndex，也就是自己当前日志的index位置，图中的情况follower1告诉leader自己的last log index是7，此时leader会直接到自己log index为7的位置准备把信息发给follower1，同时会把7位置之前的6位置的Term和log index信息发送给follower1，在leader上6位置的Term=4，而在follower1上6位置的Term=3，说明此时还是没有匹配上，于是leader会继续把该复制给follower1的日志的起始位置继续往日志起始的方向挪动，一直到log index=3的时候Term=3刚好对应上，那说明此时leader和follower1在log index=3之前的位置记录都是一样的，可以从log index=4的位置开始将操作记录一条一条的复制给follower1，从而做到即使因为一些极端的情况某些日志不一致了也可以将没有被复制到的大多数节点上的日志是安全清除。

最后小结一下，今天主要是讲了一下NewSQL怎么支持分布式事务，根据事务ACID的属性分析了一下，原子性主要是采用两阶段提交的方式来保证，一致性的话其实和传统的数据库的一致性一样，主要是数据库整体的完整性，隔离性的话可以考虑采用全局时间戳这类的方式实现，持久性的话采用的Raft的方式也就是对应CAP里的一致性。最后还讲了Raft师怎么工作的，最主要的就是两部分，一个是leader选举，一个是日志复制。

关于APMCon：

2016中国应用性能管理大会（简称APMCon 2016）于8月18日至19日在北京新云南皇冠假日酒店隆重召开。APMCon由听云、极客邦和InfoQ联合主办的作为国内APM领域最具影响力的技术大会，首次举办的APMCon以“驱动应用架构优化与创新”为主题，聚焦当前最为热门的移动端、Web端和Server端的性能监控和管理技术，整个会议设置包含了：性能可视化、服务端监控实践、运维自动化、数据库性能优化、APM云服务架构和HTML5调优最佳实践等话题，致力于推动APM在国内的成长与发展。