以太坊数据结构与存储分析

一．概述在以太坊中，数据的存储大致分为三个部分，分别是：状态数据、区块链和底层数据。

其中，底层数据存放以太坊中全部数据，存储形式是[k,v]键值对，目前使用数据库是LevelDB；所有与交易，操作相关的数据，都存储在链上；StateDB 是用来管理账户的，每个账户都是一个 stateObject。

二．区块部分区块结构：

区块链是以太坊的核心之一，所有交易以及结构都存于一个个区块中，接下来我们看看以太坊中的区块结构是怎样的。

以太坊中所有结构定义基本都可以在 core/types 中找到，区块结构定义在 block.go

中：

受比特币区块链数据结构的影响，我以为 block 可以简单地分为 head 和 body 两部分。但读了以太坊源码后，我发现 Ethereum 不是这样设计的。在 block.go 中，定义了以太坊区块链的区块结构为：

可以看到 body+head!=block。除此之外，block.go 文件中还定义了许多结构，比如用于

协议的 extblock，用于存储的 storageblock 等。

可以看到，header 结构用的非常频繁，接下来看看 header 结构是如何定义的：

Header 成员变量的解释如下:

• ParentHash：指向父区块(parentBlock)的指针。除了创世块(Genesis Block)外，每个区块有且只有一个父区块。
• Coinbase：挖掘出这个区块的矿工地址。用于发放奖励。
• UncleHash：Block 结构体的成员 uncles 的哈希值。注意这个字段是一个 Header 数
• 组。
• Root：StateDB 中的“state Trie”的根节点的哈希值。Block 中，每个账户以 stateObject 对象表示，账户以 Address 为唯一标示，其信息在相关交易(Transaction)的执行中被修改。所有账户对象可以逐个插入一个 Merkle-PatricaTrie(MPT)结构里，形成“state
• Trie”。
• TxHash: Block 中 “tx Trie”的根节点的哈希值。Block 的成员变量 transactions 中所有的
• tx 对象，被逐个插入一个 MPT 结构，形成“tx Trie”。
• ReceiptHash：Block 中的 “Receipt Trie”的根节点的哈希值。Block 的所有 Transaction 执行完后会生成一个 Receipt 数组，这个数组中的所有 Receipt 被逐个插入一个 MPT 结构中，形成”Receipt Trie”。（比特币区块中有一颗用于存放交易的梅克尔树，而以太坊中有不同功能的三棵 M-P 树）
• Bloom：Bloom 过滤器(Filter)，用来快速判断一个参数 Log 对象是否存在于一组已知的 Log 集合中。
• Difficulty：区块的难度。Block 的 Difficulty 由共识算法基于 parentBlock 的 Time 和Difficulty 计算得出，它会应用在区块的‘挖掘’阶段。
• Number：区块的序号。Block 的 Number 等于其父区块 Number +1。
• Time：区块“应该”被创建的时间。由共识算法确定，一般来说，要么等于parentBlock.Time + 10s，要么等于当前系统时间。
• GasLimit：区块内所有 Gas 消耗的理论上限。该数值在区块创建时设置，与父区块有关。具体来说，根据父区块的 GasUsed 同 GasLimit * 2/3 的大小关系来计算得出。
• GasUsed：区块内所有 Transaction 执行时所实际消耗的 Gas 总和。
• Nonce：一个 64bit 的哈希数，用于“挖矿”。

区块存储：

区块的数据最终都是以[k,v]的形式存储在数据库中，数据库在主机中的存储位置为：

datadir/geth/chaindata。具体代码在 core/database_util.go 中。区块在储存是，head 和

body 是分开存储的。

以 writeHeader 为例：

在存储 header 时，内容部分的 key 为：前缀+num(uint64 big endian)+hash；value 是区块

头的 rlp 编码。其余的模块存储方式类似：

各种前缀也都定义在 database_util.go 文件中，值得注意的是，在此文件中还有用于只存储区块头的一套函数，应该是为提高以太坊的灵活性。

三．交易部分交易部分的内容比较多，已写在专门的一个文档,请查看上一篇内容。

四．Merkle-PatriciaTrieMerkle-PatriciaTrie 简介：

Ethereum 使用的 Merkle-PatriciaTrie(MPT)结构，源自于 Trie 结构，又分别继承了

PatriciaTrie 和 MerkleTree 的优点，并基于内部数据的特性，设计了全新的节点体系和插入载入机制。

Trie ，又称为字典树或者前缀树(prefix tree)，属于查找树的一种。它与平衡二叉树的主要不同点包括：每个节点数据所携带的 key 不会存储在 Trie 的节点中，而是通过该节点在整个树形结构里位置来体现；同一个父节点的子节点，共享该父节点的 key 作为它们各自 key 的前缀，因此根节点 key 为空；待存储的数据只存于叶子节点中，非叶子节点帮助形成叶子节点 key 的前缀。下图来自 wiki-Trie，展示了一个简单的 Trie 结构。

PatriciaTrie ，又被称为 RadixTree 或紧凑前缀树(compact prefix tree)，是一种空间使用率经过优化的 Trie。与 Trie 不同的是，PatriciaTrie 里如果存在一个父节点只有一个子节点， 那么这个父节点将与其子节点合并。这样可以缩短 Trie 中不必要的深度，大大加快搜索节点速度。

MerkleTree ，也叫哈希树(hash tree)，是密码学的一个概念，注意理论上它不一定是 Trie。在哈希树中，叶子节点的标签是它所关联数据块的哈希值，而非叶子节点的标签是它的所有子节点的标签拼接而成字符串的哈希值。哈希树的优势在于，它能够对大量的数据内容迅速作出高效且安全的验证。假设一个 hash tree 中有 n 个叶子节点，如果想要验证其中一个叶子节点是否正确-即该节点数据属于源数据集合并且数据本身完整，所需哈希计算的时间复杂度是是 O（log(n)），相比之下 hash list 大约需要时间复杂度 O(n)的哈希计算，hash

tree 的表现无疑是优秀的。

上图来自 wiki-MerkleTree，展示了一个简单的二叉哈希树。四个有效数据块 L1-L4， 分别被关联到一个叶子节点上。Hash0-0 和 Hash0-1 分别等于数据块 L1 和 L2 的哈希值， 而 Hash0 则等于 Hash0-0 和 Hash0-1 二者拼接成的新字符串的哈希值，依次类推，根节点的标签 topHash 等于 Hash0 和 Hash1 二者拼接成的新字符串的哈希值。比特币在存储交易时就用的此种数据结构。

实现部分

MPT 的相关代码在 tire 文件夹中。

Node.go 中定义了四种类型的节点，分别是：

其中，nodeFlag 是用于在创建/修改节点是存放缓存数据的。

fullNode 是一个可以携带多个子节点的父(枝)节点。它有一个容量为 17 的 node 数组成员变量 Children，数组中前 16 个空位分别对应 16 进制(hex)下的 0-9a-f，这样对于每个子节点，根据其 key 值 16 进制形式下的第一位的值，就可挂载到 Children 数组的某个位置，fullNode 本身不再需要额外 key 变量；Children 数组的第 17 位，留给该 fullNode 的数据部分。fullNode 明显继承了原生 trie 的特点，而每个父节点最多拥有 16 个分支也包含了基于总体效率的考量。

shortNode 是一个仅有一个子节点的父(枝)节点。它的成员变量 Val 指向一个子节点，而成员 Key 是一个任意长度的字符串(字节数组[]byte)。显然 shortNode 的设计体现了PatriciaTrie 的特点，通过合并只有一个子节点的父节点和其子节点来缩短 trie 的深度，结果就是有些节点会有长度更长的 key。

valueNode 充当 MPT 的叶子节点。它其实是字节数组[]byte 的一个别名，不带子节点。在使用中，valueNode 就是所携带数据部分的 RLP 哈希值，长度 32byte，数据的 RLP 编码值作为 valueNode 的匹配项存储在数据库里。

这三种类型覆盖了一个普通 Trie(也许是 PatriciaTrie)的所有节点需求。任何一个[k,v]类型数据被插入一个 MPT 时，会以 k 字符串为路径沿着 root 向下延伸，在此次插入结束时首先成为一个 valueNode，k 会以自顶点 root 起到到该节点止的 key path 形式存在。但之后随着其他节点的不断插入和删除，根据 MPT 结构的要求，原有节点可能会变化成其他node 实现类型，同时 MPT 中也会不断裂变或者合并出新的(父)节点。比如：

假设一个 shortNode S 已经有一个子节点 A，现在要新插入一个子节点 B，那么会有两种可能，要么新节点 B 沿着 A 的路径继续向下，这样 S 的子节点会被更新；要么 S 的Key 分裂成两段，前一段分配给 S 作为新的 Key，同时裂变出一个新的 fullNode 作为 S 的子节点，以同时容纳 B，以及需要更新的 A。

如果一个 fullNode 原本只有两个子节点，现在要删除其中一个子节点，那么这个fullNode 就会退化为 shortNode，同时保留的子节点如果是 shortNode，还可以跟它再合并。

如果一个 shortNode 的子节点是叶子节点同时又被删除了，那么这个 shortNode 就会退化成一个 valueNode，成为一个叶子节点。诸如此类的情形还有很多，提前设想过这些案例，才能正确实现 MPT 的插入/删除/查找等操作。当然，所有查找树(search tree)结构的操作，免不了用到递归。

hashNode 跟 valueNode 一样，也是字符数组[]byte 的一个别名，同样存放 32byte 的哈希值，也没有子节点。不同的是，hashNode 是 fullNode 或者 shortNode 对象的 RLP 哈希值，所以它跟 valueNode 在使用上有着莫大的不同。

在 MPT 中，hashNode 几乎不会单独存在(有时遍历遇到一个 hashNode 往往因为原本的 node 被折叠了)，而是以 nodeFlag 结构体的成员(nodeFlag.hash)的形式，被 fullNode 和shortNode 间接持有。一旦 fullNode 或 shortNode 的成员变量(包括子结构)发生任何变化，它们的 hashNode 就一定需要更新。所以在 trie.Trie 结构体的 insert()，delete()等函数实现中，可以看到除了新创建的 fullNode、shortNode，那些子结构有所改变的 fullNode、shortNode 的 nodeFlag 成员也会被重设，hashNode 会被清空。在下次 trie.Hash()调用时，整个 MPT 自底向上的遍历过程中，所有清空的 hashNode 会被重新赋值。这样trie.Hash()结束后，我们可以得到一个根节点 root 的 hashNode，它就是此时此刻这个 MPT结构的哈希值。

Header 中的成员变量 Root、TxHash、ReceiptHash 的生成，正是源于此。明显的，hashNode 体现了 MerkleTree 的特点：每个父节点的哈希值来源于所有子节点哈希值的组合，一个顶点的哈希值能够代表一整个树形结构。hashNode 加上之前的fullNode，shortNode，valueNode，构成了一个完整的 Merkle-PatriciaTrie 结构，很好的融合了各种原型结构的优点，非常值得研究。

节点增删查改用到的函数都定义于 trie.go。在 MPT 的查找，插入，删除过程中，如果在遍历时遇到一个 hashNode，首先需要从数据库里以这个哈希值为 k，读取出相匹配的v，然后再将 v 解码恢复成 fullNode 或 shortNode。在代码中这个过程叫 resolve。

五．StateDB在系统设计中，底层数据库模块和业务模型之间，往往需要设置本地存储模块，它面向业务模型，可以根据业务需求灵活的设计各种存储格式和单元，同时又连接底层数据库，如果底层数据库(或者第三方 API)有变动，可以大大减少对业务模块的影响。在以太坊中，StateDB 就担任这个角色，它通过大量的 stateObject 对象集合，管理所有“账户”信息。

StateDB 有一个 trie.Trie 类型成员 trie，它又被称为 storage trie 或 stte trie，这个 MPT 结构中存储的都是 stateObject 对象，每个 stateObject 对象以其地址(20 bytes)作为插入节点的 Key；每次在一个区块的交易开始执行前，trie 由一个哈希值(hashNode)恢复出来。另外还有一个 map 结构，也是存放 stateObject，每个 stateObject 的地址作为 map 的 key。那么问题来了，这些数据结构之间是怎样的关系呢？

如上图所示，每当一个 stateObject 有改动，亦即“账户”信息有变动时，这个stateObject 对象会更新，并且这个 stateObject 会标为 dirty，此时所有的数据改动还仅仅存储在 map 里。当 IntermediateRoot()调用时，所有标为 dirty 的 stateObject 才会被一起写入 trie。而整个 trie 中的内容只有在 CommitTo()调用时被一起提交到底层数据库。可见，这个 map 被用作本地的一级缓存，trie 是二级缓存，底层数据库是第三级，各级数据结构的界限非常清晰，这样逐级缓存数据，每一级数据向上一级提交的时机也根据业务需求做了合理的选择。

StateDB 还可以管理账户状态的版本。这个功能用到了几个结构体：journal，revision，先来看看 UML 关系图：

其中 journal 对象是 journalEntry 的散列，长度不固定，可任意添加元素，接口journalEntry 存在若干种实现体，描述了从单个账户操作(账户余额，发起合约次数等)，到account trie 变化(创建新账户对象，账户消亡)等各种最小事件。revision 结构体，用来描述一个‘版本’，它的两个整型成员 jd 和 journalIndex，都是基于 journal 散列进行操作的。

上图简述了 StateDB 中账户状态的版本是如何管理的。首先 journal 散列会随着系统运行不断的增长，记录所有发生过的单位事件；当某个时刻需要产生一个账户状态版本时， 代码中相应的是 Snapshop()调用，会产生一个新 revision 对象，记录下当前 journal 散列的长度，和一个自增 1 的版本号。

基于以上的设计，当发生回退要求时，只要根据相应的 revision 中的 journalIndex，在journal 散列上，根据所记录的所有 journalEntry，即可使所有账户回退到那个状态。每个 stateObject 对象管理着以太坊中的一个“账户”。stateObject 有一个成员变量data，类型是 Accunt 结构体，里面存有账户 Ether 余额，合约发起次数，最新发起合约指令集的哈希值，以及一个 MPT 结构的顶点哈希值。

stateObject 内部也有一个 Trie 类型的成员 trie，被称为 storage trie，它里面存放的是一种被称为 State 的数据。State 跟每个账户相关，格式是[Hash, Hash]键值对。有意思的是，stateObject 内部也有类似 StateDB 一样的二级数据缓存机制，用来缓存和更新这些State。

stateObject 定义了一种类型名为 storage 的 map 结构，用来存放[Hash,Hash]类型的数据对，也就是 State 数据。当 SetState()调用发生时，storage 内部 State 数据被更新，相应标示为”dirty”。之后，待有需要时(比如 updateRoot()调用)，那些标为”dirty”的 State 数据被一起写入 storage trie，而 storage trie 中的所有内容在 CommitTo()调用时再一起提交到底层数据库。