English Version: PREDA：the last puzzle of the parallel blockchain
TL:DR
纵观计算机的并行史；
第一个层次的并行性是指令级并行。指令级并行是20世纪最后20年体系结构提升性能的主要途径。指令级并行性可以在保持程序二进制兼容的前提下提高性能，这一点是程序员特别喜欢的。指令级并行分成两种。一种是时间并行，即指令流水线。指令流水线就像工厂生产汽车的流水线一样，汽车生产工厂不会等一辆汽车都装好以后再开始下一辆汽车的生产，而是在多道工序上同时生产多辆汽车。另一种是空间并行，即多发射，或者叫超标量。多发射就像多车道的马路，而乱序执行（Out-of-Order Execution）就是允许在多车道上超车，超标量和乱序执行常常一起使用来提高效率。在20世纪80年代RISC出现后，随后的20年指令级并行的开发达到了一个顶峰，2010年后进一步挖掘指令级并行的空间已经不大。
第二个层次的并行性是数据级并行，主要指单指令流多数据流（SIMD）的向量结构。最早的数据级并行出现在ENIAC上。20世纪六七十年代以Cray为代表的向量机十分流行，从Cray-1、Cray-2，到后来的Cray X-MP、Cray Y-MP。直到Cray-4后，SIMD沉寂了一段时间，现在又开始恢复活力，而且用得越来越多。例如X86中的AVX多媒体指令可以用256位通路做四个64位的运算或八个32位的运算。SIMD作为指令级并行的有效补充，在流媒体领域发挥了重要的作用，早期主要用在专用处理器中，现在已经成为通用处理器的标配。
第三个层次的并行性是任务级并行。任务级并行大量存在于Internet应用中。任务级并行的代表是多核处理器以及多线程处理器，是目前计算机体系结构提高性能的主要方法。任务级并行的并行粒度较大，一个线程中包含几百条或者更多的指令。
从并行计算发展的角度上来看，如今区块链所处的正是第一层次向第二层次转变的过程。主流区块链系统通常采用单链或者多链两种架构。单链，比如常见的Bitcoin和Ethereum，整个系统只有一条链，链的每个节点执行完全相同的智能合约交易，维护完全一致的链上状态。每一个区块链节点内，智能合约交易通常采用串行执行，导致整个系统的吞吐率低。
最近出现的一些高性能区块链系统，虽然采用了单链架构，但同时也支持智能合约交易的并行执行。布朗大学和耶鲁大学的Thomas Dickerson和Maurice Herlihy等人在其PODC’17的论文中首先提出了基于STM（Software Transactional Memory）方法的并行执行模型，该方法通过optimistic parallelism（乐观并行）的方式将多条交易并行执行，如果交易在并行执行过程中遇到了状态访问冲突的问题，则通过STM去完成状态的回滚，然后再串行执行这些有状态冲突的交易。这类方法被应用到了多个高性能区块链项目当中，包括Aptos，Sei，Monad等等。与之对应，另一种并行执行模型基于pessimistic concurrency（悲观并行）的方式，即交易被并行执行之前，需要检测交易访问的状态是否存在冲突，只有不存在冲突的交易才能够被并行执行。这类方法通常采用预先计算（pre-compute）的方式，利用程序分析工具对智能合约代码做静态分析并构建状态依赖关系，比如有向无环图（DAG）。当并发交易提交到系统以后，系统根据交易需要访问的状态以及状态之间的依赖关系来判断交易是否可以并行执行。只有相互之间没有状态依赖关系的交易才会被并行执行。该类方法被应用到了Zilliqa（CoSplit版本），Sui等高性能区块链项目当中。上述的并行执行模型，都可以显著提升系统的吞吐率。这两种方案对应的是上文提到的指令级别并行。但是，这些工作存在两个问题，1）可扩展性问题和2）并行语义表达问题，我们将在下文详细阐述。