《迅雷链精品课》第七课：以太坊数据存储分析

 上一节课我们学习了比特币的区块链数据存储，接着前一篇的内容，我们继续了解以太坊的相关内容。业界一直把以太坊认为是区块链发展进程中 2.0 的代表，因为它在比特币的基础上增加了图灵完备的智能合约，扩展了区块链的使用场景，同时还时刻保存着一份账户状态，方便查询账户信息。下面我们将在正文分析以太坊是如何实现这些特性。

在学习课程的时候，你也可以领取 BaaS 平台为期一个月的试用机会，免费使用高性能区块链服务（点击链接即可免费领取https://blockchain.xunlei.com/baas/try.html）。课程学习结合实践操作，让你迅速成为区块链大牛！

数据结构

MPT 全称 Merkle Patricia Trie，是以太坊用来组织管理账户数据、生成交易集合哈希的重要数据结构, 它融合了 Trie、Patricia Trie、Merkle Tree 这 3 种数据结构的优点，如下图所示：

MPT 数据结构演变过程

在介绍 MPT 之前，我们首先简要地介绍一下其它几种树的特点：

Trie

Trie 树，又称前缀树或字典树，是一种用于快速检索的多叉树结构，其中的键通常是字符串，如英文字母的字典树是一个 26 叉树，数字的字典树是一个 10 叉树。与二叉查找树不同，键不是直接保存在节点中，而是由节点在树中的位置决定。一个节点的所有子孙都有相同的前缀，也就是这个节点对应的字符串，根节点对应空字符串。实际上 trie 每个节点是一个确定长度的数组，数组中每个节点的值是一个指向子节点的指针，最后有个标志域，标识这个位置为止是否是一个完整的字符串。

三个字符串在字母 Trie 中的存储情况

Trie 树的优点是最大限度地减少无谓的字符串比较，查询拥有共同前缀 key 的数据时十分高效；缺点是内存消耗大，尤其是前缀不重复的情况下，其次直接查询效率没有哈希表高。

Patricia Trie

Patricia Trie 称为压缩前缀树，是一种更节省空间的 Trie。对于每个节点，如果该节点是唯一的儿子的话，就和父节点合并。

Patricia Trie 展示的字符串存储情况

Merkle Tree

Merkle Tree 在前面一篇文章有介绍，这里不再过多介绍。

Merkle Patricia Trie

Merkle Patricia Trie 是一种经过改良、融合了默克尔树和前缀树两种树结构优点的数据结构。在以太坊中，为 MPT 树新增了几种不同类型的树节点(空节点、分支节点、叶子节点、扩展节点)，以尽量压缩整体的树高、降低操作的复杂度：

空节点(Null Node)：初始化的节点；

分支节点(Branch Node)：用来表示拥有超过一个孩子节点以上的非叶子节点，从其名称上可以看出来，这个节点可以引出多个分支；

叶子节点(Leaf Node)：用来表示唯一的一个 kv 数据；

扩展节点(Extension Node)：和叶子节点结构相同，但用它来表示多个 key 中的重复部分，value 指向下一个节点而不是真实数据。增加这个节点的目的主要是压缩节点，减少存储空间；

既然叶子节点和扩展节点的结构是相同的，那么怎么区分这两个节点呢？这就要先说一下 MPT 中对这两种节点用到的 key 值编码方式：Hex-Prefix 编码（十六进制前缀编码）。Hex-Prefix 编码的规则如下：

1) 在 key 之前增加一个 4bit 的 flag 前缀，其中最低位用来编码原本 key 长度的奇偶信息，key 长度为奇数，则该位为 1；低 2 位中编码一个特殊的终止标记符，若该节点为叶子节点，则该位为 1；

2) 若原本 key 的长度为偶数，则在 key 之前再增加一个值为 0x0 的 4bit 前缀，因为在十六进制编码中一个字节用两个字符表示，所以总的字符长度必须是偶数，这一步属于补位操作；

扩展节点和叶子节点几种 Prefix

经过改良和融合之后的 Merkle Patricia Trie 也形成了自身的特性：

a. 所有的 key 都经过十六进展编码转换之后，再存入 MPT 树中；

b. 每个节点按 hash 引用，该 hash 代表着另外一个节点在数据库中索引，当整棵树存储到 leveldb 中也能保持关联关系；

c. 根据节点 hash 读取节点数据，不用加载整棵树的数据，避免了不需要的 IO 开销；

下面我们用四个 kv 数据，使用一棵 MPT 树结构来展示数据从处理、组织到存储的整个流程，从这个过程中也就可以看出以太坊是如何组织交易，账户状态等数据的。

四个 kv 数据十六进制编码转换

上图所示就是刚才处理之后的四个 kv 数据使用 MPT 结构组织的示意图，从这个图中可以看到分支节点、扩展节点和叶子节点的结构。分支节点之所以十六个数组再加一个 value 字段，是因为在以太坊中所有的 key 值都是十六进制的，所以 key 值里面的数字全部在 0-f 范围内；叶子节点和扩展节点结构完全一样，根据 prefix 来进行区分，prefix 的值是按照 Hex-Prefix 编码得得到的，叶子节点的 value 是真实要存储的数据，扩展节点的 key 存储的是子节点共有的 key，value 指向下一个节点。当数据在内存中时按照上图组织，但当这些数据要存储到磁盘时，节点之间的关联关系就需要变成 hash 引用。从内存结构演变成存储到磁盘的 kv 过程如下两图所示：

节点之间通过 hash 引用

MPT 树中节点编码成 kv 数据

从上面两张图可以看到节点之间由 hash 建立关联关系，并把每个节点编码成 kv 数据存储格式的过程。根节点的 hash 就是整棵树的 HashRoot，每个节点按照 kv 方式存储到磁盘，在需要的时候可以根据 HashRoot 把整棵树在内存中还原，也可以单独根据节点的 hash 访问单个节点。

区块和交易

以太坊区块结构和比特币相似，由 Header 和 Data 组成，且它们都是采用的 POW 共识算法，所以 POW 相关的字段都有，区别在于以太坊的 Header 中多了两个关键的 State Root 和 Receipt Root 字段，下图所示为以太坊区块示意图：

以太坊区块示意图

Transaction Root：区块中包含的所有交易的 hash；

State Root：所有账户(包括合约账户)状态的 hash；

Receipt Root：所有交易执行结果(包括合约创建和执行结果)的 hash；

上述三种 HashRoot 分别对应着三个 MPT 结构，而这些 MPT 结构都与区块息息相关。MPT 组织数据的过程，在前面我们已经举例说明了，这里不再详述，区别就是数据源不一样，key 值不相同。图中还有一个 storage Trie，这也对应着一个 MPT 结构，这个树属于每个账户，后面详细介绍。在区块中的数据 Data 字段，包含了区块打包的所有交易，交易的数量会受到 Header 中 GasLimit 的限制。

Transaction Root 计算过程

上图所示就是 Transaction Root 的计算过程，把一个区块中所有的交易用 MPT 组织，根节点的 hash 就是需要的数据。这里可以看到写入 MPT 的 kv 数据，key 值是单个 Transaction 在整个交易列表中序号的(0,1,2,…)rlp 编码值，value 是 Transaction 的 rlp 编码值。rlp 编码是以太坊结构体序列化的主要编码方式，它的内部实现细节这里不详细介绍，可以查阅相关文档。

区块序列化成 kv 数据

在以太坊中所有数据都存储在 leveldb 数据库，即所有要存储的数据都以 kv 方式存储，这和比特币用文件存储区块数据不太一样。上图所示为一个区块序列化成 kv 数据的过程，单个区块序列化成两个 kv，一个存储 header 信息，key 为标识符小写字母 h+区块号+区块 Hash， value 为 Header 数据的 rlp 编码；一个存储 Data 信息，key 为标识符小写字母 b+区块号+区块 Hash， value 为 Data 数据的 rlp 编码。

除了区块序列化之外，以太坊为了高效的查询建立了很多索引，这些索引信息也以 kv 方式存储在 leveldb 数据库，例如上图中的交易信息索引。交易信息索引信息 key 为小写字母 l+交易 hash，value 为结构体（TxLookupEntry）的 rlp 编码值。再列举几个：

1) ‘H’+Block Hash  -> Block Number    区块 hash 到区块高度索引

2) ‘h’+Block Number+’n’ -> Block hash   区块高度到区块 hash 索引

3) ‘r’+Block Number+Block Hash-> Block Receipts  区块 Receipts 索引信息

当然以太坊中的索引信息不止上面列举的这些内容，正是由于这些索引信息的存在，在业务层使用过程中才会高效的查询到需要的数据信息，包括区块浏览器从各个维度查询。

账户状态

区块链中的账户和银行系统的账户类似，就是记录资产的一个地址。在以太坊中有两种账户——普通账户和合约账户：用于个人数字资产记录的账户称为普通账户，这类账户由私人密钥控制，拥有者可以查询余额，可以创建和签名一笔交易发起转账或者支付；区块链为成功部署于其上的合约代码和数据生成的帐号称为合约账户，它是代码(它的功能)和数据(它的状态)的集合。这两类账户的数据使用相同结构来记录，即 Account：

Account 结构图

在 Account 中有 Nonce、Balance、Storage Root、Code Hash 四个属性值。Nonce 是一个递增的整数值，用来标记每个账户发起交易时的交易序号，成功发起一笔交易该值就加 1；Balance 记录账户的资产余额；Storage Root 和 Code Hash 是针对合约账户的，Storage Root 是合约代码在 evm 中执行完成后，所有成员变量以 MPT 组织之后的根节点的 hash，而 Code Hash 就是合约账户对应的合约代码的 hash。

在以太坊中，每个账户(Address)对应着一个 StateObject，StateObject 包含一个 Account，每个 block 对应一个完整的包含所有 address 的状态信息即 StateObject 的集合，可以称为账户状态。和 block 对应的账户状态使用 MPT 格式存储，即前面提到的 State Trie，block 中记录 State Trie 根节点的 hash。使用 MPT 来存储账户的好处是每个 block 对应的 State Trie 可以只存储和计算有变化的节点，未变化的节点可以直接使用 hash 引用前面一个区块存储的节点，节省资源空间，提高存储效率。

两个 State Trie 的变化实例

假设 StateRoot A 在区块 1，StateRoot B 在区块 2，两个区块因为一个账户 0x2565bb 的余额发生了变化如图 13 所示，我们来分析一下两个 State Trie 的变化。由于一个账户的状态变化仅仅影响根节点的一个分支，其它分支是不受影响的，所以从 0x2565bb 账户数据所在的叶子节点向上遍历到根节点经过的节点都受到了影响，这些节点的 hash 值都需要重新计算，并且重新存储，而没有任何改变的节点不需要重新计算和存储。在上图中根节点序号为 1 的分支还是引用上个区块存储的分支节点 hash，而序号为 2 的分支引用的 hash 值需要更新，从而会得到一个新的 StateRoot B。此时 State Trie B 只需要单独存储图中虚线的叶子节点和根节点，需要存储的数据很少。

从上面的例子可以看出以太坊使用 MPT 存储数据的巧妙之处，既在每个区块关联了所有账户的状态，但又没有使用太多的存储空间，查询效率也非常高。

合约执行

合约代码其实就是用一种编程语言编写的一段代码，该代码编译成二进制数据之后可以在以太坊虚拟机 evm 中被加载和执行。一个合约账户只对应一份合约代码数据，但同一份合约代码可以对应多个合约账户。既然合约是代码，那么合约是如何被执行的，执行结果怎么存储的，我们一步步分析。

首先，当我们发起一笔交易，to 地址为空，交易中数据字段带上编译之后的合约代码，在 evm 执行这笔交易时，就会认为是创建合约的交易。接下来 evm 就会自动创建一个合约地址、执行合约代码并初始化代码中的变量、新建一个 Account 与合约地址绑定、存储合约代码和数据。前面讲过，以太坊中所有数据都是以 kv 方式存储的，合约代码就以其 hash 为 key，代码本身为 value 进行存储，同时合约代码 hash 会设置到 Account 中的 Code Hash；合约代码初始化之后的成员变量也按照一定规则序列化成 kv，使用 MPT(即前面提过的 Storage Trie)组织并存储，计算出根节点的 hash 设置到 Account 中的 Storage Root；如果交易中带了资产，这些资产会设置到 Account 中的 Balance 字段，转移给合约账户。

其次，当新来一笔 to 地址为合约地址，调用合约中某个方法的合约交易时， evm 就会找到合约地址对应的 Account，然后根据 Code Hash 加载合约代码，并在执行代码过程中加载成员变量的值进行逻辑运算。在合约执行完成之后，修改过的变量会再进行存储，然后重新计算 Storage Root 修改账户状态信息。

当然，合约交易的执行并不仅仅是修改成员变量的值，还可以通过逻辑代码进行资产的自动化转移改变其他账户的状态，这是普通交易做不到的。

小 结

本文从区块结构、交易结构和存储方式介绍了比特币实现方式和存储的相关内容，展示了区块链在去中心化、数据防篡改等方面的优势。下一篇继续介绍以太坊区块链相关方面的内容。

*恭喜完成第七课的学习，第八课我们将继续了解迅雷链多链结构的课程，欢迎关注~