文章阅读页通栏

Annchain深度之以太坊系列:StateDB和Trie

来源: Annchain 作者:
在以太坊中,所有和账户相关的状态信息都是通过 StateDB 来存储和获取的。StateDB 作为表层和其他逻辑模块交互,在 StateDB 之后使用 Merkle Patricia Trie (MPT) 结......
在以太坊中,所有和账户相关的状态信息都是通过 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 了。

关键词: Annchain  以太坊  
0/300