以太坊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网络源码实现分析, 以太坊交易和区块源码实现分析,以太坊交易和区块的存储源码分析。

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20180612G0SVIK00?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 yunjia_community@tencent.com 删除。

扫码关注云+社区

领取腾讯云代金券