链化未来区块链技术解析系列（1）- 世界状态设计与实现
1、什么是世界状态
区块链可以理解为一个分布式的状态机：所有节点从同一个创世状态开始，依次运行达成共识的区块内的交易，驱动各个节点的状态按照相同操作序列（增加，删除，修改）不断变化，实现所有节点在执行完相同编号区块内的交易后，状态完全一致，我们把这个状态称之为世界状态。
图1 区块链状态改变
世界状态里面记录了各种信息，比如账户余额，智能合约字节码，各个智能合约自定义的数据（例如一个游戏DAPP的道具相关信息），链的配置参数等。世界状态表示的是当前状态，即记录的各状态数据的当前数值。为保证执行交易时能够快速地对世界状态进行更新，世界状态方案设计实现要考虑状态数据的快速查找以及高效更新。
2、比特币的世界状态处理
比特币的世界状态数据存储于chainstate目录，采用LevelDB进行管理，主要存储当前还没有花费的所有交易输出以及交易的元数据信息，用来验证新传入的交易和块，存储这些数据的时候会做适当的压缩。
LevelDB是一个可持久化的键值数据库，利用磁盘顺序写性能比随机写大很多的特性，采用LSM-Tree结构，将磁盘的随机写转化为顺序写，大大提高了写速度。LSM将树结构拆成一大一小两棵树，较小的一个常驻内存，较大的一个持久化到磁盘。写入操作会首先操作内存中的树，随着内存中树的不断变大，会触发与磁盘中树的归并操作，而归并操作本身仅有顺序写。
Bitcoin的LevelDB存储了多种数据，其中最主要的为Coin数据，以的方式存储，Key是CoinEntry类型，由三部分组成：1字节的大写字符“C”（DB_COIN），32字节的交易ID值以及4字节的序列号；Value为Coin对象序列化后的值。
图2 比特币LevelDB存储的Coin数据
与Coin数据操作相关类的如下图所示：CCoinsView接口类定义了对Coin的操作集合，CoinsViewDB类用来真正与LevelDB交互，此类有一个全局实例pcoinsdbview；CCoinsViewBacked类作为多个Coinview层级之间的转接层；CCoinsViewMemPool类专门用来处理Mempool相关的未花费交易；CCoinsViewErrorCatcher 类包装了对LevelDB读取的错误处理；CCoinsViewCache 类内部使用CCoinsMap存储了CoutPoint 到CCoinsCacheEntry对象的映射，此类有一个全局实例pcoinsTip。
CCoinsViewCache类是一个内存缓存实现。获取Coin时，使用传入的OutPoint 对象作为Key, 在CCoinsViewCache 内部成员hashmap 中查找；如果找不到，则在CCoinsViewCache对象初始化时传入的base view中查找, 如果在base view找到，则使用此条目填充内部hashmap。添加Coin时，也是添加到CCoinsViewCache内部成员hashmap，并设置相应的DIRTY，FRESH标记。CCoinsViewCache有Flush接口，将缓存内容通过BatchWrite写入数据库。
图3 比特币Coin操作相关类
3、以太坊的世界状态处理
比特币的世界状态是通过网络中全局的未使用交易输出（UTXO）来描述的，而以太坊则利用账户概念来描述状态信息。账户状态包含四个属性，nonce，balance，storageRoot和codeHash。以太坊用stateObject来管理账户状态，账户以Address为唯一标示，其信息在相关交易的执行中被修改。所有账户对象逐一插入Merkle-PatricaTrie(MPT)结构里，形成stateTrie。区块头数据结构中的Root字段存储了stateTrie的root数值，即世界状态的哈希值。
图4 以太坊世界状态哈希
以太坊采用StateDB来管理stateObject，它包含两种接口：Trie接口用于操作内存中的MPT，Database接口用于操作持久化存储数据库。以太坊不同版本的客户端使用的数据库不同，Go、C++以及Python客户端使用的是LevelDB，用Rust实现的Parity客户端使用的是RocksDB。RocksDB基于LevelDB开发而来，优化了LevelDB存在的一些问题。
stateTrie存储了账户的信息（余额，发起交易次数，虚拟机指令数组等等），因此每次交易执行都会导致stateTrie变化，StateDB 定义了一个函数IntermediateRoot()，用来生成实时的Root值。交易执行的入口函数StateProcessor.Process()在返回前调用了Engine.Finalize()，Finalize()在内部调用上述IntermediateRoot()函数并赋值给区块头Root字段，该值就是在该区块所有交易完成后，所有账户信息的即时状态生成的root数值。
StateDB内部利用两级缓存机制来存储和更新所有代表账户的stateObject对象，第一级缓存以map的形式存储stateObjects；第二级缓存以MPT的形式存储，最终调用CommitTo接口实现键值数据库上的持久化存储。
图5 以太坊世界状态更新
从比特币与以太坊的处理过程可以看到，两个项目均采用了内存缓存机制，配合实现持久化的键值数据库来管理世界状态，从而保证对世界状态更新的高效性。另外，两个项目无论内存缓存，还是底层持久化，均采用键值映射数据结构，以实现数据快速查找。以太坊还利用MPT结构在内存跟踪状态变化，并在每个Block的数据块头记录了其所对应的世界状态的哈希值，将各个节点的世界状态一致性也纳入到了共识校验范围。
4、链化未来世界状态处理
区块链的一个重要指标是交易处理能力TPS(Transaction Per Second)，交易处理过程会对世界状态做高速频繁读写，因此需要高性能数据库来管理世界状态。另外，交易执行对世界状态的修改，有可能因为共识协议要求进行回滚，所以需要数据库或应用层逻辑能支持数据修改回滚。比特币与以太坊所采用的键值数据库LevelDB或者RocksDB对简单Key/Value查询支持的比较好，但是对复杂查询逻辑支持需要应用层自行实现。链化未来实现的开放联盟链（以下简称开放联盟链）实现时综合考虑上述原因，选择了开源的chainbase数据库进行世界状态管理。
图6 开放联盟链世界状态处理
chainbase为内存数据库，采用内存文件映射技术，将文件映射到进程的地址空间，在物理内存空间够用的情况下，可以保证足够高的读写性能。chainbase具有undo session概念，支持对未commit的状态修改进行回滚。chainbase基于boost库的multi_index_container实现，支持多关键字索引，从而支持丰富的查询逻辑。
chainbase内存映射
进程里的内存，可分为file-backed和anonymous两种：file-backed有文件对应，且数据可修改，比如程序TEXT段，文件共享内存且数据可修改等；anonymous内存里数据没有文件对应，或者对应文件里内容不可修改，比如堆，栈，共享库，静态数据区以及未初始化的数据区。
chainbase使用memap，并设置MAP_SHARED标志，该模式是file-backed类型。系统将文件映射到进程的地址空间，直接访问内存实现对文件的读写操作。系统定期将脏数据写入磁盘，会占用CPU和IO，影响性能。chainbase大小可以超过物理内存，当访问数据时，系统通过缺页中断将数据加载到内存。虽然理论上chainbase可以无限大，但数据量超过物理内存则会导致频繁的缺页中断，使交易执行时间变大，严重影响系统TPS性能。
chainbase状态回滚支持
chainbase支持undo session概念。当创建一个undo session之后，会对chianbase的增加，删除，修改操作进行跟踪记录。如果需要回滚，则在undo的时候还原原始记录；如果不需要回滚，则在commit的时候丢弃保存的undo状态信息使修改变得不可逆。
chainbase内每张数据表都有三个独立undo stack，分别记录对该数据表所做的增加，删除，修改操作。每个Block和每个Transaction开始都会创建一个新的undo cache条目；Transaction成功，就执行undo stack融合操作，将修改并入Block的undo条目；交易失败则进行状态回滚，回退Transction对数据表的修改。
图7 chainbase undo机制
具体操作流程如上图所示，比如chainbase内原有变量a数值为3，新到的交易将其修改为4，chainbase会在修改undo statck内记录原数值3，如果交易成功，则将该修改记录与block层面的undo stack融合；如果交易失败，则执行回滚操作。Block被commit确认后，undo stack内容被丢弃。
chainbase多索引支持
chainbase采用boost库中的multi_index_container数据结构，它是boost实现的一个多关键字索引容器，可以理解为数据库中的表。在链化未来的实现中，chainbase内核心数据表一共有二十多张（参见controller.cpp中add_indices函数）。与智能合约开发数据库操作相关的有两张表 table_id_multi_index和key_value_index，table_id_multi_index保存着所有智能合约中创建的表信息，key_value_index保存着所有智能合约中创建的表的数据记录。此外还有五张表（index64_index，index128_index，index256_index，index_double_index，index_long_double_index）用来存储二级索引数据，实现数据记录的灵活查询。
5、世界状态快照生成
开放联盟链为主侧链架构，节点会随机在侧链间进行调度，链间调度引入了一个问题：节点从一条侧链调度到另外一条侧链，相当于一个新节点加入了该侧链网络，那这个节点需要有与其他节点一致的世界状态，才能加入共识参与出块流程。构建世界状态，可以利用历史区块数据，依次执行区块内保存的交易，重构出世界状态；也可以利用保存好的世界状态快照文件，直接恢复到指定块的世界状态，再继续重放后续区块。第一种方式中，链运行越久，产生的数据越多，重放需要耗费的时间越久；第二种方式中，一方面需要考虑如何能够高效地生成世界状态快照文件，另一方面要提供一种机制让节点可以验证其获取的世界状态快照文件是正确的没有经过篡改的。
如何高效地生成世界状态快照文件而不影响主线程正常处理交易，即不对TPS性能造成影响，链化未来采用了cache机制，并使用单独的世界状态快照生成线程。如下图所示，类似chainbase的undo stack机制，链化未来增加了cache模块。每次交易对chainbase数据的修改，一方面会进入undo stack用于支持状态回滚，另一方面会进入cache模块，用于给单独的世界状态快照生成线程处理。cache模块的处理逻辑与undo stack不同的地方在于，cache会保留多个block数据块的修改，并不断进行融合，每隔一定间隔（比如每生产100个区块）生成一个新的条目，如下图中901～1000，表示为编号为901到编号为1000的区块之间的数据修改cache。
图8 undo stack与worldstate cache
类似LevelDB中内存与文件系统文件融合的机制，开放联盟链的世界状态快照生成过程中会将世界状态数据存储到文件系统，利用cache机制，内存中仅占用少量空间来记录一小段时间内的数据修改。到特定区块间隔（比如每100块区块），世界状态生成线程（下图中的ws thread）会逐表将数据加载进内存（下图中的backup table db），并与cache中的修改记录进行融合，然后重新写回到文件系统。采用该机制，使得世界状态快照生成过程既不会影响主线程性能，也不会产生内存的大量占用。
图9 主线程与世界状态生成线程
文件系统每隔一定区块（可配置参数，目前链化未来主网配置为1000块）对生成的世界状态快照文件进行单独保存，并计算快照文件的哈希值。各个节点会将该哈希值上报到主链系统合约，被调度的节点启动时，会从主链获取该哈希值，从而使节点可以校验获取到的世界状态快照文件是否被人恶意篡改过。
世界状态快照生成机制，保证了节点可以快速恢复到指定区块世界状态，从而支撑链化未来主侧链机制中关键的节点随机调度功能。
6、状态爆炸及解决思路
区块链网络中的全节点在运行一段时间后，会在本地存储产生越来越多的数据。本地存储的数据包括历史数据和世界状态数据：历史数据主要以区块的形式存储，区块内包含了所有的交易信息；世界状态数据为节点处理完从创世块开始到当前块高包含的所有交易形成的当前状态数据。
无论是历史数据还是世界状态数据，都会随着系统的运行持续增长，使得运行全节点需要的存储资源越来越大。当前区块链的处理性能还比较低（比特币为7TPS，以太坊为15TPS，其他区块链一般为数千TPS），考虑到区块链处理性能获得大大提升后，存储增长问题会变得更严重，这就是状态爆炸问题。
历史数据的积累相对比较容易解决，可以采取中心化压缩存储，或者利用Checkpoint机制，全节点可以不用存储某个时间点之前历史数据。对于世界状态数据的状态爆炸问题，目前主要有状态租赁方案，状态剪枝方案，“无状态节点”方案等解决思路。
状态租赁方案
状态租赁方案要求用户为存储的数据支付租金，该租金不仅考虑数据占用空间大小，而且与其在链上存储的时间成正比。通过让用户支付状态费用，可以推动不再使用的状态信息可以随着时间的推移而被删除，从而防止数据逐步增长。关于收费模式有不同的讨论，目前没有明确的结论。
状态剪枝方案
状态剪枝方案是指全节点只存储近期的数据，比较老的历史数据将存储在其他地方，状态剪枝方案会影响那些依靠全节点索引和查询所有历史数据的DApp。状态剪枝方案不能从根本上解决问题，而且随着区块链应用越来越多，数据增加的速度也越来越快，由于存储空间不变，那么能被存储的近期数据时间也就会越来越短。
“无状态节点”方案
在无状态节点方案中，全节点不需要存储区块链的状态，而只需要对状态进行短暂的承诺（Commitment）以验证交易，这需要利用到的密码学原理包括累加器和向量承诺（Accumulators and Vector Commitments）。有研究机构构建了基于比特币和以太坊的概念验证模型，但是从概念验证到真正的落地应用，还需要做大量的工作。
针对状态爆炸问题，还有项目提出了一些新的思路，比如EOS内置交易市场，用户需要支付原生代币购买RAM进行世界状态存储；Nervos采用Cell模型，利用原生代币经济模型激励存储空间自由定价交易；Coda利用零知识证明的不断递归实现存储压缩技术等。
链化未来所采取的主侧链结构中，各个侧链的世界状态相互独立，可以理解为对世界状态的水平切分，缓解了单链结构中状态爆炸的问题。此外，链化未来也在尝试节点状态压缩技术，即节点只保存部分世界状态数据，结合交易提供的状态数据完成交易执行。同时链化未来也在积极探索“无状态节点”技术，争取早日实现该技术的工程落地。
作者：weixin_45870688
