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

2019-03-15 18:11 栏目:经验之谈 来源:网络整理 查看()
在以太坊中,所有与帐户相关的状态信息都通过StateDB存储和检索。 StateDB与其他逻辑模块交互作为表面层。在StateDB之后,Merkle Patricia Trie(MPT)结构用于构造快速索引​​和回滚操作的编码状态关系。 MPT中的所有节点最终都作为键值存储在磁盘数据库中。

为了支持可能的回滚要求,Annchain.OG目前支持Trie树存储以进行数据存储,并支持回滚状态历史记录。我们已经对StateDB进行了适应性改进,特别是对于智能合约的使用。

反汇编Ethereum中StateDB和Trie的实现以及它们在帐户状态存储过程中所扮演的角色。

作者介绍

Uni,Annchain核心开发成员。他拥有英国计算机科学硕士学位,并曾担任金融机构区块链技术研究员。他发表了几篇技术文章。对区块链共识,P2P网络和底层存储处理进行了更深入的研究。现在,annchain的核心开发人员主要负责交易核心处理逻辑和数据存储模块。

Merkle Patricia Trie

MPT是通过结合Merkle Tree和Patricia Tree的特征而创建的树数据结构。它包含以下功能:

·能够存储任意长度的键值对数据。
·支持Merkle Proof以快速验证节点。

·可以快速查询与密钥对应的值数据。

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

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

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

valueNode存储特定值数据,其键是从根到此节点的路径上所有键的总和。
hashNode存储数据库中其他节点的哈希值以用作索引。
shortNode是MTP的分支节点之一。 “Key”字段存储当前shortNode之后所有节点共有的前缀前缀密钥。 'Val'字段存储后续节点。如果由当前节点的根节点组成的密钥前缀与结构中的“密钥”完全匹配,并且没有与该前缀匹配的其他键值对,则后续节点是valueNode。如果对于该前缀密钥满足多于一个键值对,则随后存储fullNode。
fullNode是MTP的分支节点之一。与shortNode不同,fullNode没有Key字段,只有一个节点数组'Children'。 fullNode的主要功能是存储所有具有公共前缀密钥但在后续密钥值中存在差异的键值对。 Children数组中的每个元素表示前缀符号(请参阅下面的示例),使用不同的前缀符号分隔不同的键值对。以太坊中的Children数组的长度为17.因为它涉及特定的编码方法,所以不在此扩展它的设置原因。你可以简单地将17视为16 + 1,十六进制加上它自己的值。

具体例子

看一下字面抽象,让我们看看具体的例子。假设现在我们有6个键值对:

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


它们以下列方式存储在MPT中:

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

如您所见,根节点是fullNode,因为存在前缀分歧。后续节点分为两方,密钥以c为前缀,前缀为d。我们关注以d为前缀的三个键值对,其键为'dog','doge'和'doggie'。除了开头的d之外,它们还有一个共同的前缀og。因此,根节点向下扩展了ShortNode 2。 ShortNode 2的关键是'og',并且由于og的其他部分存在差异,因此ShortNode 2的Val字段存储FullNode(请参阅上面的shortNode说明)。

如上所述,fullNode中有17个元素,可以很容易地理解为十六进制加上它自己的值来形成17个元素。在我们的例子中,FullNode 2在这里形成了狗前缀键(根节点的d加上后续shortNode的og),这正是狗的键值对中的键 - 值4,所以结束FullNode 2的值是ValueNode,ValueNode的值是value4。

FullNode 2的前缀键加上其内部e可以形成前缀键'doge',因此值直接从e位置导出,值是doge - value5键值对的value5。

FullNode 2的前缀键加上其内部g形成键前缀dogg。匹配dogg前缀的唯一一个是doggie - value6。因此,g遵循ShortNode 5的扩展,其Key字段为ie,而Val字段是ValueNode,其值为value6。前缀为c的其他三个键值对可以类似地构造。

MPT编码

上例中的所有数据都是未编码的。是什么导致这个问题? FullNode之前提到的每个Children元素代表一个前缀符号。如果密钥未编码,则很难对前缀符号进行规范化,因此太多类型的前缀无法确定Children数组的长度。

为了解决这个问题,以太坊使用十六进制编码来编码所有键值对的键。编码后的所有密钥由16个十六进制符号[0,1,2,3,4,5,6,7,8,9,a,b,c,d,e,f]组成。在编码之后,FullNode的Children可以被分成16个副本,每个副本对应于它自己的前缀符号,这就是为什么以太坊FullNode的Children数组长度是17(16个子节点+自己的节点)。

例如:假设键值对doggie - value6被编码为0x646f67676965 - value6,则Root节点中的键值对将被分为6个子节点,这是Children数组的第七个元素。 。

StateDB

StateDB用作帐户状态和查询条目的更新,基于具体的逻辑方法调用。如更新帐户余额,查询nonce等。同时,它还具有所有合同数据的存储查询。为了支持快速数据查询和阻止回滚操作,StateDB使用MPT结构作为其底层存储。

我们来看看StateDB的数据结构:

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

Db - 用于连接底层trie数据库的字段。数据不是自己存储的,以便检索TrieDB。
Trie - 所有帐户信息的当前MPT结构。
stateObjects - 存储缓存的帐户状态信息。
stateObjectsDirty - 为随后的提交操作标记已更改的状态对象。
StateDB通过操作和查询stateObjects中缓存的状态对象来执行业务逻辑执行。如果在stateObjects中找不到需要操作的对象,则通过createObject(addr common.Address)方法从trie字段的MPT读取相应的状态对象并将其放置在缓存中。

stateObject

stateObject用于存储以太坊中每个帐户的信息的数据结构:

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


数据字段包含帐户余额,Nonce等信息。同时,在后续MPT的过程中,主存储内容是编码数据字段。

这里值得一提的是stateObject的trie字段和数据中的Root字段。与StateDB中的trie不同,此处的trie用于在此状态地址下存储合同数据。每个地址帐户都有自己的合同存储trie。数据中的根是此trie根的哈希值。此Root将包含在stateDB的trie中存储状态数据的过程中。这样做的主要优点是它可以绑定合同数据和世界状态数据,增加相关性和安全性,同时,在随后的滚动操作中,包括合同数据在内的所有状态都可以通过世界国家的根源。

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


由于空间有限,第一部分只介绍MPT和StateDB本身。在下一节中,我们将重点介绍StateDB和MPT的工作结构,以及StateDB和MPT在实现不同类型的Transaction时的逻辑流程。


整体结构

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

在以太坊中,最高级别的数据是上图中的StateDB。 StateDB负责制作最初步的数据记录。下一层是Trie层,Trie负责构造所有数据以便于后续存储查询回滚操作。 Trie,State Trie和Storage Trie有两种类型。前者是一个世界状态树,记录基本信息,例如所有账户的随机数。后者用于记录各种合同数据。世界上只有一个状态树,合同状态树中有很多树,因为每个合同都有自己的合同状态树。

Trie继续使用TrieDB,TrieDB将Trie中的节点序列化并将它们存储在内存中。 TrieDB的主要作用是在最终插入硬盘数据之前充当缓存层。整个结构中的最后一个循环是最终硬盘上的数据库。

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


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

状态更新过程

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


1.当收到一个块时,以太坊将根据块中正文的内容逐个执行事务。在执行期间,确认交易是否调用合同。
2.如果它是与合同相关的事务,则创建一个新的EVM对象,并根据事务中数据字段的执行代码执行合同。
3.执行期间的所有合同状态更改都将记录到合同的StateObject的dirtyStorage中。
4.执行完成后,更新From,To的StateObject的Data字段。主要更新Balance和Nonce。

到第四步结束时,与此事务相关的所有状态更改都将记录到StateDB。执行完所有块事务后,StateDB会保存此块导致的所有状态更新。

执行所有块事务后,程序将调用StateDB.Commit()方法将StateDB中的脏状态更新为Trie:

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


应该注意的是,trie更新不会从0重建新的trie。因为trie的数据结构特征只需要更新更改路径上的节点。如下图所示:

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

左侧是原始的trie,右侧是更新的trie。假设新数据不涉及节点2和节点4,则在更多节点中只需要将一个叶节点设置为节点2。同时,原始trie中未使用的节点将不会被删除,但将继续存在于db中以方便后续的回滚操作。

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

通过调用trie.Commit()将新生成的进程映射到TrieDB,新节点首先转换为cachedNode。
在我们的例子中,它是节点1,3,5,6,7。 cachedNode存储节点及其叶节点的本体
哈希,用于最终放置时的序列化。在这里,您可以参考Ethereum trie目录中的database.go文件。
在StateDB.Commit()完成之后,程序执行最后的排序步骤,将TrieDB中的脏节点写入磁盘数据库:

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


这一步是调用TrieDB.Commit(),将所有脏节点(1,3,5,6,7)序列转换为[]字节结构,然后使用hash作为键,[] byte结构作为值,存储到最终的磁盘数据。

完成此步骤后,将完成整个状态数据的更新。

回滚

正如我们前面提到的,在更新trie结构时,旧trie中不需要的节点不会从db中删除。因此在回滚中,我们只需要知道要回滚的状态树的根节点,然后使用根节点作为磁盘数据库的源,并重新加载对应于根节点的整个树以恢复当前国家不见了。在以太坊中,这个根节点的散列将存在于每个块的头部中,因此如果我们想要回滚到块高度为n的状态,那么我们只需要读取块n的头部中的根散列。然后使用此哈希作为源从数据库中还原整个树。

微信二维码
售前客服二维码

文章均源于网络收集编辑侵删

提示:币友交流QQ/WX群请联系客服加入!

郑重申明:资讯文章为网络收集整理,官方公告以外的资讯内容与本站无关!
虚拟币开发,虚拟币交易平台开发,山寨币交易平台开发 Keywords: 虚拟币开发 虚拟币交易平台开发 山寨币交易平台开发