以太坊MPT的存储和源码分析

以太坊源码分析－Trie树源码实现

在上一篇文章中，在理论层面上给出了以太坊MPT数据结构的背景数据结构，本篇主要从源码角度分析Trie树在以太坊中的实现和目的思路。

本篇主要包含：

1. trie树相关的代码目录展示2. 以太坊改进的MPT数据结构在内存和持久化存储的过程3. 以太坊Trie树的源码实现相关代码分析

(后续预告：以太坊P2P网络源码实现分析， 以太坊交易和区块源码实现分析，以太坊交易和区块的存储源码分析。)

跟trie树相关的代码在 go-ethereum/trie目录内，包含的代码文件有：

➜ go-ethereum git:(master) tree trie

trie

├── database.go

├── encoding.go

├── encoding_test.go

├── errors.go

├── hasher.go

├── iterator.go

├── iterator_test.go

├── node.go

├── node_test.go

├── proof.go

├── proof_test.go

├── secure_trie.go

├── securetrietest.go

├── sync.go

├── sync_test.go

├── trie.go

└── trie_test.go

源码实现

—————————

MPT存储流程图

MPT的存储涉及3种编码方式：

KeyBytes编码Hex编码Compact编码

在完成Compact编码后，会通过折叠操作把子结点替换成子结点的hash值，然后以键值对的形式将所有结点存储到数据库中.

源代码文件：

trie/encoding.go

KeyBytes编码：

即原始关键字，比如图中的0x811344、0x879337等。每个字节中包含2个nibble（半字节，4 bits），每个nibble的数值范围时0x0~0

Hex编码：

由于我们需要以nibble为单位进行编码并插入MPT，因此需要把一个字节拆分成两个，转换为Hex编码。

编码转换是在Trie.TryUpdate()中触发的，具体转换代码

Compact编码

a. 当我们需要把内存中MPT存储到数据库中时，还需要再把两个字节合并为一个字节进行存储，这时候会碰到2个问题：

b. 关键字长度为奇数，有一个字节无法合并

需要区分结点是扩展结点还是叶子结点 为了解决这个问题，以太坊设计了一种Compact编码方式，具体规则如下：

编码转换是在Trie.Commit()时触发的，具体调用在hasher.hashChildren()函数中, 代码见：

Trie的数据结构：

node的结构，可以看到node分为4种类型， fullNode对应了黄皮书里面的分支节点，shortNode对应了黄皮书里面的扩展节点和叶子节点(通过shortNode.Val的类型来对应到底是叶子节点(valueNode)还是分支节点(fullNode))

trie的结构， root包含了当前的root节点， db是后端的KV存储，trie的结构最终都是需要通过KV的形式存储到数据库里面去，然后启动的时候是需要从数据库里面加载的。

originalRoot 启动加载的时候的hash值，通过这个hash值可以在数据库里面恢复出整颗的trie树。cachegen字段指示了当前Trie树的cache时代，每次调用Commit操作的时候，会增加Trie树的cache时代。

Trie树的插入，查找和删除 Trie树等数据结构相关的代码，均在trie目录内，详细代码不再粘贴。

New函数：初始化调用New函数，函数接受一个hash值和一个Database参数，如果hash值不是空值的化，就说明是从数据库加载一个已经存在的Trie树， 就调用trei.resolveHash方法来加载整颗Trie树，这个方法后续会介绍。 如果root是空，那么就新建一颗Trie树返回。

Trie树的插入，这是一个递归调用的方法，从根节点开始，一直往下找，直到找到可以插入的点，进行插入操作。参数node是当前插入的节点， prefix是当前已经处理完的部分key， key是还没有处理玩的部分key, 完整的key = prefix + key。 value是需要插入的值。 返回值bool是操作是否改变了Trie树(dirty)，node是插入完成后的子树的根节点， error是错误信息

Trie树的Get方法，基本上就是很简单的遍历Trie树，来获取Key的信息。

更多的Trie树的使用方法， 在trie_test.go里面有比较详细的参考。

Trie树的序列化和反序列化

序列化主要是指把内存表示的数据存放到数据库里面， 反序列化是指把数据库里面的Trie数据加载成内存表示的数据。 序列化的目的主要是方便存储，减少存储大小等。 反序列化的目的是把存储的数据加载到内存，方便Trie树的插入，查询，修改等需求。

Trie的序列化主要才作用了前面介绍的Compat Encoding和 RLP编码格式。 序列化的结构在黄皮书里面有详细的介绍。

Trie树的cache管理

Trie树的cache管理。 还记得Trie树的结构里面有两个参数， 一个是cachegen,一个是cachelimit。这两个参数就是cache控制的参数。 Trie树每一次调用Commit方法，会导致当前的cachegen增加1。

然后在Trie树插入的时候，会把当前的cachegen存放到节点中。

Trie树的默克尔证明

源码文件： trie/proof.go

主要提供两个方法，Prove方法获取指定Key的proof证明， proof证明是从根节点到叶子节点的所有节点的hash值列表。 VerifyProof方法，接受一个roothash值和proof证明和key来验证key是否存在。

Prove方法，从根节点开始。把经过的节点的hash值一个一个存入到list中。然后返回。

VerifyProof方法，接收一个rootHash参数，key参数，和proof数组， 来一个一个验证是否能够和数据库里面的能够对应上。

加密的Trie

源码文件：trie/security_trie.go

为了避免刻意使用很长的key导致访问时间的增加， security_trie包装了一下trie树， 所有的key都转换成keccak256算法计算的hash值。同时在数据库里面存储hash值对应的原始的key。

———————

本篇关于Trie的源码分析结束。

后续还有以太坊P2P网络源码实现分析， 以太坊交易和区块源码实现分析，以太坊交易和区块的存储源码分析。