性能赶超EOS?并发执行模型原理详解

知识
  • 区块链大本营
  • 2018-08-20 04:04

公链性能一直是行业关注的重点,如DAG的强一致性,sharding的技术可行性,超级节点的中心化问题等等。对于这些问题的解决方案都在试图通过改变区块链共识结构的方式提升性能,适用性不高,安全性也有待证明。

8月11日,星云链首席研发&星云链技术白皮书主编尚书为我们分享了一个性能提升方向的探索成果——并发执行模型,有效地在8核16G的机器上实现了2000TPS的最大并发,且还可以根据需求做横向扩展。

作为开发者或者投资者,你对公链真正了解多少?本文将带你去伪存真,从多维度认知主流公链。

以下内容为尚书现场分享实录,由区块链大本营整理发布。

正文:

我们今天的主题是关于公链性能的提升。接下来我将会讲并发执行模型。

一、如何评估公链性能

TPS(Transaction per Second),指的是每秒交易数量。一般来说,一个区块链每秒钟能打包的交易数量就是TPS,但这样评估并不完全准确。因为在区块链的结构里面,是一个区块一个区块产生的,每个区块从产生到传播到公网之间,存在网络延迟,下一个人拿到这一区块的时候,才能生成下一个区块。

所以中间除了打包这个过程外,还有一些其他的操作。打包的时间并不等同于TPS,而是比如说有1万个交易发送上链,直到最后一个交易上链,这中间有个时间窗口。用N除以这个时间窗口,得到的TPS才是准确的。

再严格一点说,我们在钱包里面做交易的时候,会出现什么场景?

这里我们首先要知道一个概念:51%攻击。它指的是有人掌握了全网50%以上算力之后,用这些算力来重新计算已经确认过的区块,使其产生分叉并且获得利益的行为。

比如说我们有一条10个区块的主链,但有另一个算力更强的人,他悄悄在世界上一个隐秘的地方挖了20个区块出来。这时,大家在公网上面看到的只有10个区块,这10个区块交易完之后,你的账户应当有10块钱,但是在它挖的20个区块的公链上面,你可能只有5块钱。又因为最长的链是主链,一旦他把20个区块释放到公网上,这条长链就变成了主链。实际上在公链上的10个区块里面,记录的所有的数据都被回滚掉了。

你在以太上面做完交易,imToken会告诉你需要等12个区块的确认。这个确认是什么意思呢?当一个区块产生了之后,并没有人可以保证这个区块会永远被写在整个区块链的主链上面,它有可能变成一条侧链。

这里存在着巨大的风险,比如说在交易所里像OTC这种业务,你给交易所10万块钱,拿到了1万个Token。但可能过一段时间,交易所之前验证的那个区块被回滚了,这个时候实际上你手上并没有那些Token。这样也就导致你原来花的10万块钱买的Token消失了,没有任何人能帮你找的回来。

因此,所有的交易所钱包都需要一个确认的过程。交易完成后,一定要等到多少个区块确认之后,交易所和钱包认为你这个交易所在的那个主链,很难被回滚了——当然只是说很难被回滚,并不是说不可能被回滚,比如说它有90%的概率不可能被回滚了,交易所也同意承担这10%的风险,通知你转账成功。这里就存在一个确认的时间。

从更严格的角度来讲,我们发了一万个交易到链上去,理论上只有这一万个交易全部确认之后,我们才说这一万个交易真正上链了,这个TPS才是我们最真实的TPS。那么,我们要怎样来衡量这个确认的概念呢?

1.PoW

2年前我们的公链有比特币,有以太坊。这两条公链所采用的共识算法叫做PoW。这就相当于大家一起来解一个智力游戏,比如说猜数字,谁最先猜出来了,谁拥有记账的权力。大家都在拼算力,随着整个网络算力的提升,题目的难度也在不断加大。

比特币设计了一个算法,保证平均每10分钟出一个区块。随着网络算力提升,它也会不断调整游戏的难度,以保证每10分钟出一个区块。通过对安全性做计算,它认为每10分钟出现一个区块,并且,当有6个区块出现时,在将近一个小时的时间窗口里面,不可能再有另外一个挖出了7个区块的大矿场,能够把这6个区块一次性全部给回滚掉。

所以说,我们所谓的确认状态,不是100%的确认,只是一个大概率确认状态。

虽然比特币说它是6个区块确认,但是可能在交易所里面你需要等到12个确认,或者20个确认,才把那个账目真正打到你的账户里面去,因为交易所也怕风险。

以太的方案在比特币之上做了一个扩展。因为比特币10分钟才有一笔交易,这对于所有的交易场景来说,基本是不可用的,除非是非常大额的交易,愿意等这10分钟。比特币的策略是上一个区块出完之后,紧跟着出来下一个区块,这是一个比拼算力的过程。

以太引入了一个新的概念。在同一个高度上,比如说上一个区块链已经出完了,接下来该出高度为11的区块了,这时可能在整个网络里面,有100个人在一个很短的时间窗口里同时挖出了第11个区块。但只有一个最终能够链到我们主链上来,所以有10个是作废的。

这10个被作废掉的区块当然是有价值的,因为它也消耗了算力。以太的方案是把这10个区块的算力,也加入到整个主链状态评估过程中,就可以在一个更短的时间内确认。因为在那个很短的时间窗口里,全网贡献的算力跟比特币在一个区块上贡献的算力差不多,通过这种方式它也能够达到跟比特币相当的一个安全指标。以太这样做的转账速度差不多在15-20秒一个区块,它需要等12个区块。

而在火币上面,大约要等到28个区块才会确认。因为火币也怕承担风险。到了12个区块也并不能说100%能够确认,它还有概率会被回滚掉。一旦回滚,火币平台就需要担负极大的资产损失责任,所以它在这个地方会等得更久。

这就是在最早一代的公链项目里,我们确认状态的现状。它是一个概率,不是100%。

2. DPoS

到了下一代,我们现在看的EOS,包括我们星云1.0所用的共识,就是DPoS。

DPoS的方案是怎样的呢?比如说我们有21个人在参与挖矿,一起编制了一条主链。在这条主链里我挖了一个矿之后,剩下的人在轮流挖矿的过程中,如果有14个不一样的人在我挖的这个区块后面出了区块,就证明他认可我这个区块,可以认为他给我投了一票。一个区块如果拿到了2/3+1的票,也就是21个人里面15个人的票,包括我自己,那么这个区块就能够得到确认。这其中有一个巨大的假设条件——整个网络里面,这21个人里面,不会超过7个人及以上是坏人,所以我们能干这个事情。

但是这个里面依旧会存在一个场景:这21个人里头,如果有7个作恶节点,他有可能在这边挖了一个区块,在另外一条隐藏的侧链上面也挖一个区块,然后再贿赂另外的8个人,也就是一共搞到15个人,在另外一条侧链上挖出一个更长的区块。等到哪天符合他的利益,比如说他在主链上已经花了1个亿,但是在侧链上那1个亿还在的时候,他们把隐藏的那条侧链公开给全网,全网在旧链上的所有数据全部被擦除掉,他们手上就重新得到了1个亿。也就是说,这少部分的15个人剥夺了所有人的利益。这样理论上来讲,也是不安全的。

当然现在大家对这个事情没有那么关注,大家还是相信那21个人,那21个人也是公开自己身份的。如果他们真的干了这个事情,可能会被人追杀,但是你也不知道他们会不会干。如果他能挣100亿美金,他也是有可能会干的,对吧?

这个就是第二阶段,大家对如何确认的一个看法。

3. PoS变种

到了第三个阶段,就是现在以太在提的Casper,然后我们提了一个Proof of Devotion。在我们这里,要保证的是做到100%确认。也就是如果公链告诉你,这个区块被确认了,那它一定是100%被确认了。这里引入了一个新的机制在于,所有要进来挖矿的人,需要先交一笔押金,你如果在这里面做了恶,你的押金会被扣。这就有一个可控的变量,你要是作恶到了极限,那就把所有人的押金全部扣完。

我们设计的方案是,即使所有人的押金全部扣完,你也没有办法把我们之前确认过的区块给回滚掉。从而保证我们一旦确认,就是100%的确认,因为在我们的体制下面,你已经没有足够的资金去回滚区块。这个就是第三代Casper和我们提的Proof of Devotion要做的事情,也就是确认的状态。这两个算法都设计出来了,但还是在验证阶段。

这就是在一个公链上面交易确认状态的三个发展方向。

二、前提条件

公链毕竟是公链,我们有一个不可能的三角,就像我们原来分布式的Cap一样,在公链里也有一个不可能的三角——安全性、去中心化、性能。在现有的条件下,三者只能选二,然后等到整个大环境,包括硬件条件、软件条件、网络环境等全部上来之后,剩下的那一个指标,才能随着大环境而提升。而安全性和去中心化,在这里面扮演的是很重要的角色。所以,在提升公链性能的时候是有一些假设、一些条件在前面的,这些条件从理论上来讲是不应该逾越的。

在这里,我们可以操作的事情有哪些呢?共识这里出现了一个新的变种DAG,它不是区块链,在它的场景里面已经没有区块的概念了,而是所有的交易在整个网络中织成一张大网来做到一致性。但这个方案现在要想做到强一致,还是存在一些问题的,所以我们现在还只是关注区块链项目,是有区块概念的。

在这个大环境下面,每一个区块在挖的过程中,必须要经历三个阶段。

第一是打包时间。一个矿工从网络中收集到了很多交易,要把这些交易打包成一个区块。打包结束之后,算好最终状态变化的情况,就可以把所有的数据广播到全网去。这里面就有一个打包的时间。

除此之外,还有一个网络延迟。它不像EOS,公网是所有的矿工网络直连的,相当于是一个小的局域网。正经的说,我们要保证去中心化场景时,我们一定是要在公网环境的,这就不可避免会存在网络延迟。

那么对方(另外一个矿工)收到区块之后,他需要去验证一下你算的所有的数据是不是对的,你如果算不对,那我在你的后面出块的话,相当于所有的数据都错了。所以收到的矿工一定还有一个验证时间。这样来看,一个区块必然有这三个时间,这三个时间里面,又很诡异的有一个现象,就是我们在一个特定的算法里面,验证时间是可以远小于计算时间的。

举个例子,比如说排序,我们现在来看,最快的排序也是O(NlogN)的,但在特定场景里面,我们要想验证一个排序实际上是很快的,只需要判断是从大到小或者从小到大一个排序的过程就可以了,这就是O(N)的时间复杂度。

在一个特定的算法里面,我们算法执行的时间,实际上远远大于算法验证的时间。这是一个很好的现象,如果真的可以做到这一点的话,我们的打包时间会远远大于验证时间。但我们是一个通用公链,并不知道用户会在我们链上写什么算法。我们不知道他们什么时候会做什么样的事情,也就不知道该怎么去验证它算的对不对。

因此,在这样一个尴尬的场景里面,我们的打包时间跟验证时间实际上是一样的,因为我们必须重走一遍它的逻辑。这样来看,我们只能尽量把这两个时间都缩小,把网络延迟时间缩小。

根据网络延迟,实际上就是要减少网络包的大小。我们可以从两个方向着手。

一个是序列化。我们能不能找到一个更好的序列化的方案,把我们的数据全部变成一个更好的序列化结构,变成二进制流发出去?这个里面我们使用了Protocol Buffer,以太用了它自己设计的一个RLP。

其实RLP的性能会比Protocol Buffer要好,但RLP算法本身的扩展性非常差,我们在设计整个区块链的过程中,不能保证未来会发生什么变化——我们未来的核心协议网络包的结构会不会产生变化,会不会添加一些新的字段,会不会改一些字段,这些都是我们不知道的,所以我们必须保留这个扩展性。从这个角度来说,Protocol Buffer比RLP要灵活的多。因此,我们选择了一个性能稍微更差一点的Protocol Buffer,但是它的扩展性更好。

第二是数据压缩。我们做完序列化之后,要打包成网络包,发到网络里面去。这里我们一定要做一个压缩,我们现在用的是Google Snappy。这个算法能够帮助我们完成50%的压缩率,对整个网络延迟的贡献度实际上是相当高的。

三、并发执行模型

接下来我们要考虑的事情就是怎么把打包时间和验证时间进行缩短。这就是我们今天要讲的重点。我们首创的并发执行模型是什么样的,为什么这样设计,它为什么可以提升公链的性能,又是如何缩短设计的并行执行模型时间的。

我们可以直观地感受到所有交易被提交到区块链上时,矿工打包的过程和它验证的过程可以理解为一个有限状态机,区块链可以理解为一个状态的集合。它有很多状态,所有交易到我们区块链公网上来之后,实际上我们状态的集合会发生迁移,它从某一个状态变到下一个状态。它就是一个有限状态机。

在传统的场景下面,这个状态机是什么样的呢?所有的交易被提交到公网上来了之后,他们对状态迁移的过程是一个交易执行的过程。一个交易执行完了之后,它迁移到下一个状态,我们再基于这个状态再接进来一个交易,再跳到下一个状态,所以,就变成了一个串行的确定有限状态机。

那么我们能不能把交易的执行过程,这个串行的状态机变成一个并行的——你提交上来10个交易,我能不能把这10个交易同时执行,最终合并到同一个状态集合里面去,这种情况能不能实现?

问题重重

我们上来就遇到了这样三个问题。

第一个问题:当我们把状态的迁移过程从串行变成并行之后,会不会每次执行的结果不一样?这一过程是否为确定有限状态机?

第二个问题:假设我们可以把所有的状态做成并行的。那么要将多个交易并行后得到的状态集合融合,这一过程中会不会产生冲突?产生冲突了怎么办?有没有办法互不冲突?

第三个问题:在传统的MySQL里有个读写锁,只要读写不冲突就好了。但在我们并行执行过程中是否存在一个更强的逻辑?我们是否需要事务隔离?如果不需要,我们能否让它变成一个更加并行的状态?

在第一个问题里,它变成并行化之后,还是不是确定的状态机呢?很不幸它不是。这个问题非常棘手,我们可以通过一个实际例子来说明。比如说我们在初始状态下,A和B有两个账户,A有1 NAS,B和C都没有NAS,那我们现在要挖一个区块,这个区块里面我们收到了2笔交易。

第一种情况是A到B转账执行完后,B到C再转账,这个时候的结果就是A和B都没有NAS了,C有一个NAS。

第二种情况是B和C可能先执行了,A和B再执行,但是B到C执行的过程中,它们之间转移一个NAS是不成功的,所以这一交易失败,A向B则会转移成功。最后的结果是A和C没有NAS,B有一个NAS。显然,我们把它并行化之后,如果这个顺序被打散了,最终的结果也就不一致了

在第二个问题里,我们能不能让两个交易并发执行,在最终做状态合并的时候互不冲突?这其实也很难做到。我们有一个很直观的感觉,比如说A到B我们收到了一个区块,里面有三个交易,A到B、B到C和D到E。

这样看来,感觉“A到B”和“B到C”是相互关联的,因为它们共享了一个地址B,而D到E似乎跟这两个交易没有太多的关系,是两波不一样的人。

那我们能不能由此把它分成两个部分,让A到B,B到C串行执行,D到E跟他们并行执行呢?这个想象很美好,但是实际上不是这样子的。比特币上可以这样干,但是所有基于以太的、通用的智能合约结构,这样都做不了。

A到B这一笔交易,它有可能不是一个普遍的转账,并不只是单纯的NAS转移。B可能是一个合约——这又是一个致命的问题:A到B转账可能会调用某一个合约,在这个合约的逻辑里,可能其中的某一条指令要从合约把一笔钱转到另一个账户上去,那个账户有可能是D,有可能是E。

我们根本不知道用户会在他的合约里面存什么样的地址,结果我们想当然地把AB、BC、DE做分割,但是可能就踩到雷了,A到B实际上是影响D到E的,这些事情在早期其实是没有办法预判的。所以说,我们想做到互不冲突也非常困难。

第三个问题,我们是否需要做事务隔离?

显然,我们不能允许1、2两个中间,互相操作相同的数据,如果操作相同数据——我举个例子,比如在2里面它先读了X=0,在2执行的过程中,1执行结束了,它把X设为了1,那2还在同一个交易里面再去读X的时候,又变成了1,实际上这个场景是不可能出现的。2在执行过程中,要么X全程都是1,要么X全都是0,不可能出现先读到0,再读到1。

所以,场景里面一定要做事务隔离。

解决思路

那么要解决这三个问题,我们能干些什么?

关于第一个问题,我们从一个确定的状态变成一个非确定的,我们需要去关注交易和交易之间的依赖关系。存在依赖关系的交易,是一定存在先后执行顺序的,比如我们常说的拓扑排序结构。所以,除了打包过程要记录它的依赖关系以外,我们在验证的时候,还要根据所记录的依赖关系做最终验证。

这里我们需要做两个事情。如果我们要记录依赖关系的话,相当于有两个交易,第一个交易做完,它所有状态修改的集合,我们是需要保存的,不然再做第二个交易的时候,都不知道它改过什么,也没办法去判断依赖关系。也就是说,我们就需要保存所有的交易执行之后的状态集合。另外,我们要提供机制,能够查询两个修改后的集合之间的精确依赖关系,这个存储其实也是要很大开销的。

第二个问题,我们能不能做到互不冲突?极难做到,因为我们完全不知道用户在他的合约里面放了什么数据,也极难追踪。我们只能尽量使两个交易互不冲突,因为我们有一个基础的预判,from和to只要互不重叠,冲突的概率就会相对小一点。

我们有一个调动模型,但最终还要有一个东西来保证它们真的互不冲突。所以两个修改后的状态集合产生了之后,我们要去看这个集合里面都修改过什么?增删查改4个操作他们都做过什么?对同一个数据做的增删查改,哪种场景下是冲突的,哪种是不冲突的?我们需要定义这个冲突模式。

与此同时,我们也需要保存所有修改后集合的状态,因为我们最终需要去判断两个集合是否相互冲突,和第一个问题一样,我们需要一大笔存储的开销。

到了第三个问题,我们要做事务隔离。比如交易1执行之前的状态是0,交易2在执行之前状态也是0,1和2可能并行执行。这一过程中,可能都会对0那个状态的数据做修改,但他们一旦修改做了重叠之后影响了其他交易的执行,这就不是事务隔离。所以我们还要保证一点:1和2在做执行的过程中,他们所依赖的前提的状态都是0,相当于把0的状态拷贝两份,给他们各自一份作为初始条件。

除了要把所有交易的修改集合保存以外,我们还要把所有的交易最开始依赖的初始条件保存,这样看的话,又是一大堆东西要存,而且这个场景是事务隔离,这个交易可能会失败,需要让它回滚。所以算法复杂度也提高了,我的存储复杂度也提高了。

解决方案

为了解决这几个问题,我们做了三个事情:

第一,我们把所有的状态统一到一起。原来的状态是分散的,我们不知道如何判断不同状态之间的冲突关系和依赖关系。所以我们在这边做了一个叫World State的工具,把所有的状态都统计、管理起来。你在增删查改任何东西之前,可以通过它来判断冲突、查看状态。

World State只是一个管理工具,那数据存在哪呢?我们还要存所有的交易修改之后的状态、和所有交易执行前的状态。而且在这个过程中,我们还得去判断它的依赖关系、冲突关系,实际上是要把每一份都拷贝一份,这个事情非常好解决。但实际上是不可行的,比如说TPS要上万,相当于是一秒钟以内要复制1万份;要上百万,就要复制上百万份…相当于是TPS越高,要的存储就越高,哪几台机器能够扛得住这么大的存储呢?

所以第二件事是,我们设计了一个结构来简化这个存储,这个名字叫做“支持嵌套事务的多版本控制并发数据库(MVCC DB)”,这个结构在我们的代码里面已经开源了,大家如果感兴趣可以看一下里面更多的细节。

第三个,我们刚刚说它变成一个非确定性状态机,要根据依赖关系来构建结构。它实际上是个拓扑图,会随着网络传播到下一个验证者那里,那个验证者会根据它的拓扑排序结构做一个调度,哪些交易可并行执行,哪些交易必须等到上一个交易执行完之后才能做,这里就要有一个拓扑图的执行引擎,来保障我们最终完成的一致性。

四、性能评测

这是我们整个模型在公链上跑出来的测试数据。我们可以看一下这样的结构给我们的性能带来了哪些变化。

我们的机器是i7,四核,纯智能合约的交易,在一秒内我们尝试打包,我们可以看到下面分别是一个核、两个核和四个核的状态,这个数据实际上是线型增长的。

所以如果我们控制了更多的核,这个数据还会不断往上涨,直到哪一天它遇到了IO瓶颈——就像右边纯转账交易测试数据看到的,我们也是一个核、两个核、四个核在做,但是它达到一个高度之后,它就遇到了IO瓶颈,我本机的IO撑不住这么多的场景了,这以后它增长的速度就开始放缓了。

我们现在本机是四核的,在线上跑的是八核的。线上8核情况下,合约交易和转账交易混合的场景下,我们最高测出了2000TPS。EOS单条链测的大约是1000-3000TPS,它的机器设备是128核的配置,网络是10GB/s直连,也就是说128核做到了1000-3000。实际上我们通过8核已经做到了,而且我们横向扩展到128核的话,性能还会提升从这个角度来说,我们的性能是会扩展得比它更好的。

当然我们现在只是一个模型结构的优化,没有对IO做任何的优化,接下来我们实际上有一套IO的优化策略要去执行,那部分做完之后,我们的性能实际上会比EOS高的多得多。

这些是我们目前已经完成的工作。

五、未来发展方向

最后,我们来看一下现在的行业内部都在如何优化他们各自供应链的性能。

算法优化

首先是一个纵向的优化。在所有的结构确定下来之后,你可以把你的算法,把IO速度做优化。我们去选取交易做并发的时候,选取策略也可以做优化,包括我们在做网络传输的过程中,每一个交易的from和to实际上是很长的。但这个交易除了广播到了我以外,也广播到了所有其他的人。也就是说,其他人手上是有它的from和to地址的,那我在网络传输过程中,是否可以优化策略,就不用传这些信息了。通过这样的方式我们可以减少网络包大小,把网络延迟拉低,也能整体延长我们的TPS。

这是在已有框架内的优化方向,那么如果你有条件改框架的话,你能做哪些事情呢?

提升CPU核数以提升性能,这实际上是一个横向扩展的机制。

所有的挖矿节点,网络直连,就像EOS做的那样,网络延迟速度几乎可以忽略不计,这样的话,TPS也高,所以它做到了0.5秒出块。

以太V神提出的sharding

这个sharding是什么概念呢?以太现在是一条单链,他想通过多链结构来提升它的性能。在多链状态里,并不是说你拥有一个钱包,你就可以在多链上自由买卖。你在A链上有100个ETH,你在B链上你没有这100个ETH,你如果要用B链的服务,你首先需要把你的钱从A链转到B链。

这样看来,多链结构并没有给大家带来任何实质便利性,所以他提的sharding,我个人认为是一个伪命题。既然是这样一个sharding模式的话,你为什么要把所有人绑在你的多链里面呢?你为什么是一个侧链的结构,而不是单独的另外一条链,通过跨链协议的方式让大家交互起来,最终就变成网络里面上千万条链,都是以太,但是这些链之间可以通过跨链协议彼此互连,数据共享。每一条线每天都能提供百万TPS,对于任何一个单独的厂商来说,是足够使用的。所以我们觉得sharding是一个伪命题,跨链才是真命题。

最近比较火的Nervos

他们提出一个方案,不要把计算放在公链的矿工节点去做计算,而是放在客户端去做计算,你算完以后给我就好了。你在算的过程中,要把所有的依赖关系和冲突都算好,我这边只做验证。这个角度上来看的话,它把我们之前并行的结构通过另外一个方案,从一个非确定状态机变成了一个确定状态机。理论上可行,但是这里面存在一个重大的问题在于,在客户端完成计算,如何在服务端进行验证?如何保证两种运算的一致?

区块链共识,这是清华的姚期智教授参与做的方案,将区块变成一个DAG。

在某一个高度上,你可能挖出了10个区块,这10个区块并不是只有一个被网络接受,而是10个都被网络接受,这10个里面包含的交易能够有一个算法达成最终一致性。

纯DAG模式

实际上,纯DAG现在还面临着众多问题,每个人在自己的节点上看到的数据都不一样,那你怎么保证最终的一致性?每个时间窗口的强一致性?这些都是存在的问题。

 


来源:区块链大本营作者:摘编编辑:gageerun

本文链接: https://www.dyqklw.com/article/20180820/398.html

声明:除非注明,本站文章均为第一区块链网原创或编译,转载时请注明文章作者和“来源:第一区块链网”,本站尊重行业规范,每篇文章都标有明确的作者和来源。文章为作者观点,不代表第一区块链网立场。

免责:阁下应知本网站的任何内容仅供参考,不能做为投资决策依据,投资有风险,入市须警慎!请谨防ICO、变相ICO!

相关文章

资讯

原创

荐读

热门标签