在以太坊中，所有和账户相关的状态信息都是通过 StateDB 来存储和获取的。StateDB 作为表层和其他逻辑模块交互，在 StateDB 之后使用 Merkle Patricia Trie (MPT) 结构来构建编码后的 state 关系，用于快速索引以及回滚等操作。MPT 中的所有节点最后都会以 key - value 的形式存入磁盘数据库。

Annchain.OG为了支持可能的回滚需求，在数据存储方面，StateDB目前已经支持Trie树的存储，支持state历史记录的回滚。我们尤其针对智能合约的使用需求做了StateDB的适配改进。

拆解 StateDB 和 Trie 在以太坊中的实现以及两者在账户状态存储流程中所扮演的角色。

作者介绍

Uni，Annchain核心开发成员。英国计算机专业海归硕士，曾担任金融机构区块链技术研究员，发表多篇技术文章。对区块链共识，P2P网络，底层存储处理等有较深入研究。现annchain核心开发人员,主要负责交易核心处理逻辑及数据存储模块。

Merkle Patricia Trie

MPT 是结合了 Merkle Tree 和 Patricia Tree 的特点后创建的树形数据结构。其包含了如下的一些特点：

· 能存储任意长度的键值对数据。

· 支持 Merkle Proof，用于节点的快速校验。
· 能快速的查询 key 所对应的 value 数据。

在以太坊中，MPT被定义为四种不同类型的节点：fullNode, shortNode, valueNode, hashNode：

valueNode 存储具体的 value 数据，它的 key 是从 root 到此节点的路径上所有 key 的总和。
hashNode 存储一个数据库中其他节点的哈希用作索引。
shortNode 是 MPT 的枝干节点之一。"Key" 字段存储当前 shortNode 之后所有 node 共同的一段前缀 key。"Val" 字段存储一个后续的节点。如果从根节点到当前节点所组成的 key 前缀已经键值对结构中的"键"完全吻合，且没有其它符合此前缀的键值对存在，则后续节点为一个 valueNode。如果满足此前缀 key 的键值对组合多于一个，则后续存储一个 fullNode。
fullNode 是 MPT 的枝干节点之一。和 shortNode 不同的是，fullNode 没有 Key 字段，只有一个 node 数组 "Children"。fullNode 主要作用是存储有共同前缀 key 但是在后续key值产生分歧的所有键值对。Children 数组中的每一个元素都表示一个前缀符号（具体可以参考下面的例子），用不同的前缀符号来分隔不同的键值对。以太坊中 Children 数组的长度为 17，因为涉及具体的编码方式，所以不在这里展开讲为什么这么设置。可以简单将 17 理解为 16 + 1，16 进制加上本身的 value 值。

具体例子

光看字面比较抽象，我们看看具体的例子。假设现在我们有 6 个键值对：

 

他们在 MPT 中就会以如下的方式存储：

可以看到，因为存在前缀分歧，所以 Root 节点是 fullNode。后续节点分成两派，key 以 c 为前缀和以 d 为前缀。我们关注以 d 为前缀的三个键值对，它们的 key 分别是 "dog"、"doge" 和 "doggie"。除了开头的 d 以外，它们还有个共同的前缀og。因此 Root 节点往下引申一个 ShortNode 2。ShortNode 2 的 key 就是 "og", 又因为除了og 其它部分都存在分歧，所以 ShortNode 2 的 Val 字段存储的是一个FullNode（参考上面对 shortNode 的解释）。

上面提到过，fullNode 存在17个元素，可以简单理解为 16 进制加上本身 value 值构成 17 个元素。在我们的例子中，此处的 FullNode 2 已经构成了 dog 这个前缀 key（根节点的 d 加上后续 shortNode 的 og），已经完全吻合 dog - value4 这个键值对中的 key，所以 FullNode 2 的末尾便是一个 ValueNode，ValueNode 的值是 value4。

FullNode 2 的前缀 key 再加上其内部的 e 能够构成前缀 key "doge"，所以 e 位置下面直接引申一个 ValueNode，其值便是 doge - value5 这键值对内的 value5。

FullNode 2 的前缀 key 加上其内部的 g 组成 key 前缀 dogg。剩下的符合dogg 前缀的只有doggie - value6。所以 g 下面引申一个 ShortNode 5，其节点的Key字段为 ie，Val 字段为一个值为 value6 的 ValueNode。另外三个前缀为 c 的键值对则同理可以得到图中的结构。

MPT 的编码

上面的例子中所有的数据都是没有经过编码的，这会造成什么问题呢？之前提过 FullNode 的每个 Children 元素都代表一个前缀符号，如果不对key进行编码则很难将这个前缀符号规范化，使得前缀的种类过多无法确定 Children 数组的长度。

为了解决这个问题，以太坊使用 Hex 编码对所有键值对的key进行编码。编码后所有的key就都由 [0,1,2,3,4,5,6,7,8,9,a,b,c,d,e,f] 这 16 个十六进制符号组成。编码后，FullNode 的 Children 就可以分割成 16 份，每份对应各自的前缀符号，这也是为什么以太坊 FullNode 的 Children 数组长度是 17 ( 16 个子节点 + 本身节点 )。

举个例子：假设键值对doggie - value6经过编码后变为 0x646f67676965 - value6，那么在 Root 节点中这个键值对就会被分到 6 这个子节点下面，也就是 Children 数组的第七个元素中。

StateDB

StateDB 作为账户状态的更新以及查询入口，基于具体逻辑的方法调用。比如账户余额的更新，nonce 的查询等。同时，它还肩负着所有合约数据的存储查询。为了支持数据的快速查询以及区块的回滚操作，StateDB 使用 MPT 结构作为其下层的存储方式。

先来看看 StateDB 的数据结构：

db - 用于连接下层 trie 数据库的字段。本身不存储数据，为了调取 TrieDB 存在。
trie - 当前所有账户信息构建的 MPT 结构。
stateObjects - 存储缓存的账户 state 信息。
stateObjectsDirty - 标记被更改的state对象，用于后续的 commit 操作。
StateDB通过操作和查询stateObjects中缓存的state对象来完成业务逻辑的执行。如果stateObjects中找不到需要操作的对象，则通过createObject(addr common.Address) 方法从trie字段的MPT中读取对应的state对象并放入缓存中。

stateObject

stateObject 是以太坊中用于存储每个账户信息的数据结构：

 

data 字段保存账户的余额，Nonce等信息。同时，在后续落盘 MPT 的过程中，主要存储的内容就是经过编码序列化后的 data 字段。

这里值得特别提一点的是 stateObject 的 trie 字段和 data 中的 Root 字段。和 StateDB 中的 trie 不同，此处的 trie 是用来存储此 state 地址下的合约数据的。每个地址账户都会有属于自己的一棵 trie 用来做合约存储。data 中的 Root 则是这个 trie 的根节点的哈希。在将 state 数据存入 StateDB 的 trie 的过程中会带上这个 Root，这么做的好处主要是能将合约数据和世界状态数据绑定在一起，增加关联性和安全性，同时，在后续的回滚操作中能通过世界状态 trie 的 Root 还原出包括合约数据的所有状态。

 

由于篇幅有限，上篇就先只介绍 MPT 和 StateDB 本身。在下篇，我们将重点结合上图讲解 StateDB 和 MPT 两者的工作结构，以及不同类型 Transaction 执行过程中 StateDB 和 MPT 的逻辑流程。

 

整体结构

在以太坊中，数据的最上层就是上图中的StateDB。StateDB负责将数据做最初步的记录。往下一层是Trie层，Trie负责将所有数据结构化，方便后续的存储查询回滚等操作。Trie分两种，State Trie和Storage Trie。前者是世界状态树，记录了所有账号的余额nonce等基本信息。后者用于记录各种合约数据。世界状态树只有一棵，合约状态树有很多棵，因为每个合约都有棵属于自己的合约状态树。

Trie再往后就是TrieDB，TrieDB将Trie中的节点序列化后存储在内存中。TrieDB的主要作用是做为最终插入硬盘数据之前的缓存层。整个结构中最后一环就是最终硬盘上的数据库。

 

以太坊中，StateDB的主要数据结构是StateObject。每个StateObject代表一个地址的状态。在StateObject中主要有两个结构，data 和 dirtyStorage。data 用于存储账号的基本信息如余额nonce等，dirtyStorage用于存储该账号地址下的合约的数据。具体实现可以参考以太坊 core/state/ 目录下的 state_object.go文件。

状态更更新流程

 

1. 当收到一个区块时，以太坊会根据区块内body的内容逐条执行里面的交易。在执行过程中，会确认此交易是否调用合约。
2. 如果是合约相关的交易，则创建一个新的EVM对象并根据交易中的Data字段的执行码执行合约。
3. 执行期间所有的合约状态更改都会记录到合约的StateObject 的 dirtyStorage 中。
4. 执行完成后更新 From，To 俩地址的StateObject 的 data 字段。主要更新 Balance 和 Nonce。

到第四步执行完，所有此交易相关的状态更改就都记录到 StateDB 中了。之后在所有的区块交易都执行完后，StateDB就保存了了此区块造成的所有状态更新。

执行完所有区块交易后，程序会调用StateDB.Commit() 方法，将StateDB中的脏状态更更新到Trie上：

 

需要注意的是，trie 更新并不会从0开始重新构建一个新的trie。因为trie的数据结构特点只需要将更改路径上的节点更新即可。如下图所示：

左边是原来的trie，右边是更新后的trie。假设新的数据不涉及节点2和节点4，那么只需要在更节点中将其中一个叶子节点设置成节点2即可。同时原来的trie中不被继续使用的节点不会被删掉，而是继续存在db中，方便后续回滚操作。

通过调用 trie.Commit() 将新产生的映射到 TrieDB 的过程中，首先会将新的节点转化成cachedNode。
在我们的例子中，就是节点 1，3，5，6，7。cachedNode 存储了节点的本体以及它的叶子节点
hash，用于最终落盘时的序列化。此处具体可以参考以太坊 trie 目录下的 database.go 文件。
StateDB.Commit() 完成后，程序会执行最后的落盘步骤，将 TrieDB 中的脏节点写入磁盘数据库中：

 

这一步就是调用 TrieDB.Commit() ，将所有的脏节点（1，3，5，6，7）序列列化成 []byte 结构，然后用hash作为 key，[]byte 结构做为 value，存储到最终的磁盘数据中。

到这一步落盘步骤完成后，整个状态数据的更新就算完成了。

回滚

我们前面提到过，更新trie结构时，旧trie中不需要的节点并不会被从db中删除。所以在回滚时，我们只需要知道要回滚到的状态树的根节点，然后从磁盘数据库中以此根节点为源头，重新加载出这个根节点对应的整棵树就可以还原出当时的状态了。在以太坊中，这个根节点的hash都会存在每个区块的header中，所以假设我们要回滚到区块高度为 n 的状态，那么只需要读取出区块 n 的 header 中的root hash，然后用这个hash为源头从数据库还原整棵树就 ok 了。

上一篇：
Schnorr签名的前世今生：为什么说比特币的隐私性是不可避免的？ 下一篇：
撞库攻击：一场用户与平台同舟共济的保卫战BitOL|比特在线-关注区块链技术动态的区块链导航博客BitOL|比特在线-关注区块链技术动态的区块链导航博客本文转自《区块网》/BitOL|比特在线-关注区块链技术动态的区块链导航博客