区块链-以太坊MPT存储

最近研究以太坊MPT的数据存储性能，仔细地确认了一下MPT树的数据存储方式。众所周知，以太坊中的世界状态是通过MPT树实现的。MPT树是在内存中的连接关系，为了持久化存储，MPT树的连接关系转化为一系列的K-V对。以太坊将这些K-V对存储在levelDB中。有关MPT树的基本知识，可以查看

以太源代码 - MPT原理以及实现

。

1）MPT树的内存结构

MPT树的内存结构，如下图。一颗MPT树由4种节点连接组成：fullnode是分支节点，shortnode代表扩展节点或者叶子节点（取决于value是hashNode还是valueNode）。

需要指出的是：MPT的叶子节点（账户信息）是按照账户的地址（Address）的字典排序形成。也就是说，MPT树上的一个叶子节点路径上的所有的key组成的是账户地址。

2）MPT树物理存储

在内存中，节点和节点的连接关系可以通过“指针”完成。为了将连接关系持久化，需要将节点内容生成对应的，唯一的“地址”。其他引用节点内容的节点，只需要记录引用节点的地址即可，示意如下图中的蓝色部分。

以太坊中，节点内容的地址就是节点内容的hash。比如一个由“key”以及一个“hashNode”组成的节点，节点内容是rlp（key，hashNode），对应的地址是内容的hash。在存储中，存储的是hash到rlp的KV对。其他引用节点的“连接”用hash值代替，从而隐性的实现“连接”。

再举fullnode的例子，在存储中，fullnode的内容是rlp（hashNode，hashNode ... hashNode, valueNode)组成。

3）账户修改

从上述可见，一个叶子节点的改变，导致节点内容的改变，节点的“地址”也会发生变化。也就是说，父亲节点和该节点的“连接”地址发生变化。因为父亲节点的内容包括“连接”地址，所以父亲节点的内容也发生变化，父亲节点的“地址”也随着变化。随即，父亲的父亲也发生变化，一直变化到MPT的树根。

总的来说，一个账户的改变，导致MPT树，从叶子到树根，整条路径上的所有节点的KV对都发生变化，需要更新到存储中。

以太坊中的节点间的“连接”关系用hash来代替，主要原因，hash结果唯一。还有个原因，有关账户中的Storage数据的MPT树。在Storage的数据构建的MPT树，节点排序是通过Storage数据内容的hash，这样保证MPT树的最大高度，避免攻击者通过构造Storage创建深度很高的MPT树。

MPT树中的分支节点的分支个数设置为16，而不是更大的原因，可能是怕分支节点内容变的太大，在节点内容大小和树高之间的一个平衡。