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

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

学习课程时，还可以获得为期一个月的BaaS平台试用机会，免费使用高性能区块链服务（点击链接免费领取）。 课程学习结合实操，让你快速成为区块链高手！

数据结构

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

MPT数据结构演化过程

在介绍MPT之前，我们先简单介绍一下其他树的特点：

树

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

字母表Trie中三个字符串的存储

Trie 树的优点是尽量减少不必要的字符串比较，在查询具有公共前缀键的数据时非常高效； 缺点是内存消耗大，尤其是前缀不重复的情况下，直接查询的效率没有哈希表高。

帕特里夏特里

PatriciaTrie 被称为压缩前缀树，是一种更节省空间的 Trie。 对于每个节点，如果该节点是唯一的子节点，则将其与父节点合并。

Patricia Trie 演示的字符串存储

默克尔树

Merkle Tree在上一篇文章中介绍过，这里就不过多介绍了。

默克尔帕特里夏特里

Merkle Patricia Trie 是一种改进的数据结构，结合了 Merkle 树和前缀树的优点。 在以太坊中，MPT 树中加入了几种不同类型的树节点（空节点、分支节点、叶节点和扩展节点），以最小化整体树高并降低操作的复杂度：

Null Node：初始化节点；

Branch Node：用于表示一个非叶子节点，有多个子节点。 顾名思义，这个节点可以引出多个分支；

Leaf Node：用于表示唯一的kv数据；

Extension Node：与叶节点结构相同，但用于表示多个key中重复的部分，value指向下一个节点，而不是真正的数据。 添加这个节点的目的主要是为了压缩节点，减少存储空间；

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

1）在密钥前添加一个4位的标志前缀。 最低位用于编码原始密钥长度的奇偶校验信息。 如果密钥长度为奇数，则该位为1； 低 2 位编码一个特殊的终止标记。 如果该节点是叶节点，则该位为1；

2）如果原key的长度为偶数，则在key前加一个值为0x0的4位前缀，因为一个byte在16进制编码中由两个字符表示，所以字符总长度必须为偶数number，这一步是填充操作；

扩展节点和叶节点的几个前缀

改进融合的Merkle Patricia Trie也形成了自己的特点：

一种。 所有的key经过16进制编码转换后存储在MPT树中；

b. 每个节点都由散列引用，它代表数据库中索引的另一个节点。 当整棵树存储在leveldb中时，也可以维护关系；

C。 根据节点哈希读取节点数据，无需加载整棵树的数据，避免不必要的IO开销；

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

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

上图是刚才使用MPT结构组织处理后的4个kv数据的示意图。 从这张图中可以看出分支节点、扩展节点和叶节点的结构。 分支节点之所以有十六个数组加一个值字段是因为以太坊中所有的键值都是十六进制的，所以键值中的数字都在0-f范围内； 叶子节点和扩展节点结构完全一样，都是根据前缀来区分的。 前缀的值按照Hex-Prefix进行编码。 叶子节点的值是真正要存储的数据。 扩展节点的key存放子节点共享的key，value指向下一个节点。 当数据在内存中时，按照上图组织，但是当数据要存储在磁盘中时，需要将节点之间的关联关系改为哈希引用。 从内存结构到存储到磁盘的kv过程如下两图所示：

节点由哈希引用

MPT树中的节点被编码成kv数据

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

区块和交易

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

以太坊框图

Transaction Root：区块中包含的所有交易的哈希值；

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

Receipt Root：所有交易执行结果（包括合约创建和执行结果）的哈希值；

以上三个HashRoots分别对应三个MPT结构，而这些MPT结构都与区块密切相关。 MPT组织数据的过程已经举例说明，这里不再赘述。 不同的是数据源不同，键值不同。 图中还有一个存储Trie，也对应一个MPT结构。 这棵树属于每个账户，后面会详细介绍。 区块中的Data字段包含了区块中打包的所有交易，交易数量会受到Header中GasLimit的限制。

交易根计算过程

上图展示了Transaction Root的计算过程。 一个区块中的所有交易都是通过MPT组织起来的，根节点的哈希就是需要的数据。 这里可以看到写入MPT的kv数据，key值为单个Transaction在整个交易列表中的序号的(0,1,2,…)rlp编码值，value为rlp编码交易的价值。 rlp编码是以太坊结构序列化的主要编码方式。 其内部实现细节这里不做详细介绍，可以参考相关文档。

块被序列化为 kv 数据

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

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

1) 'H'+Block Hash -> Block Number block hash to block height index

2）'h'+区块号+'n'->区块哈希区块高度到区块哈希索引

3)'r'+Block Number+Block Hash-> Block Receipts Block Receipts索引信息

当然，以太坊中的指数信息远不止上面列举的这些内容。 正是因为有这些索引信息的存在，才能在业务层的使用过程中，高效的查询到所需的数据信息，包括在区块浏览器中进行各个维度的查询。

帐户状态

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

账户结构图

Account中有四个属性值：Nonce、Balance、Storage Root、Code Hash。 Nonce是一个递增的整数值，用于标记每个账户发起交易时的交易编号。 如果发起交易成功，则该值加1； balance记录账户的资产余额； Storage Root 和 Code Hash 用于合约账户。 Storage Root是合约代码在evm中执行后根节点的hash，所有成员变量都是通过MPT组织的，Code Hash是合约账户对应的合约代码的hash。

在以太坊中，每个账户（Address）对应一个StateObject，一个StateObject包含一个Account，每个区块对应一整套StateObjects，包含所有地址的状态信息，可以称为一个账户状态。 区块对应的账户状态以MPT格式存储，即上面提到的State Trie，区块中记录了State Trie根节点的哈希值。 使用MPT存储账户的好处是每个区块对应的State Trie只能存储和计算发生变化的节点，没有发生变化的节点可以直接使用hash引用前一个区块存储的节点，节省资源空间和提高存储效率。

更改两个 State Tries 的实例

假设StateRoot A在block 1，StateRoot B在block 2，两个block的balance因为一个账户0x2565bb发生了变化以太坊数据同步与存储改进，如图13所示，我们来分析一下这两个State Tries的变化。 由于账户状态变化只影响根节点的一个分支，其他分支不受影响，所以从0x2565bb账户数据所在的叶子节点向上遍历到根节点的节点都受到影响，哈希值这些节点中的所有都需要重新计算和恢复，而没有变化的节点则不需要重新计算和恢复。 上图中，根节点编号为1的分支仍然引用前一个区块中存储的分支节点哈希，编号为2的分支引用的哈希值需要更新，这样一个新的StateRoot B将得到。 此时State Trie B只需要分别存储图中虚线的叶子节点和根节点，需要存储的数据非常少。

从上面的例子可以看出，以太坊巧妙地使用了MPT来存储数据。 不仅关联了每个区块中所有账户的状态，而且不会占用过多的存储空间，查询效率也非常高。

合约执行

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

首先，当我们发起一笔交易时，to地址为空，交易中的data字段携带编译好的合约代码。 当 evm 执行交易时，它将被视为合约创建交易。 接下来evm会自动创建一个合约地址，执行合约代码并初始化代码中的变量以太坊数据同步与存储改进，创建一个新的Account并绑定合约地址，存储合约代码和数据。 前面说过，以太坊中的所有数据都是以kv的形式存储的。 合约代码以其散列作为键存储，代码本身作为值存储。 同时将合约代码哈希设置为账户中的代码哈希； 合约代码初始化后 成员变量也按照一定的规则序列化成kv，使用MPT（即前面提到的Storage Trie）组织存储，计算根节点的hash并设置到Storage Root中帐户; 如果交易中包含资产，则这些资产将被设置到Account中的Balance字段并转移到合约账户中。

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

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

概括

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

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