深入理解Raft及在NewSQL中的使用

如需转载请联系听云College团队成员小尹 邮箱:yinhy#tingyun.com

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

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

一、What is NewSQL

1.jpg

从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

2.jpg

然后,接下来讲一下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。

3.jpg

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

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

4.jpg

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

三、NewSQL 

5.jpg

那么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中间件的方式是保证不了隔离性的。

6.jpg

如上图,假设有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之间的隔离是有问题的,所以在全局范围内是无法保证严格事务之间的隔离性的。

7.jpg

再举个例子如图所示,假设变量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、原子性

8.jpg

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

3、持久性

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

9.jpg

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

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

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

10.jpg

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

四、What is raft

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

1、State machine

11.jpg

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

12.jpg

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

13.jpg

上图是Raft工作的示意图,Client发送请求到Leader上,consensus部分可以理解为Raft