结构体数组在Ethereum的世界里，数据的最终存储形式是[(8)

先来看Hex编码的实现，这里将原本[]byte形式称之为keybytes，Hex编码的基本逻辑如下图：

很简单，就是将keybytes中的1byte信息，将高4bit和低4bit分别放到两个byte里，最后在尾部加1byte标记当前属于Hex格式。这样新产生的key虽然形式还是[]byte，但是每个byte大小已经被限制在4bit以内，代码中把这种新数据的每一位称为nibble。这样经过编码之后，带有[]nibble格式的key的数据就可以顺利的进入fullNode.Children[]数组了。

Hex编码虽然解决了key是keybytes形式的数据插入MPT的问题，但代价也很大，就是数据冗余。典型的如shortNode，目前Hex格式下的Key，长度会变成是原来keybytes格式下的两倍。这一点对于节点的哈希计算，比如计算hashNode，影响很大。所以Ethereum又定义了另一种编码格式叫Compact，用来对Hex格式进行优化。

Compact编码又叫hex prefix编码，它的主要意图是将Hex格式的字符串恢复到keybytes的格式，同时要加入当前Compact格式的标记位，还要考虑在奇偶不同长度Hex格式字符串下，避免引入多余的byte。

如上图所示，Compact编码首先将Hex尾部标记byte去掉，然后将原本每2 nibble的数据合并到1byte；增添1byte在输出数据头部以放置Compact格式标记位；如果输入Hex格式字符串有效长度为奇数，还可以将Hex字符串的第一个nibble放置在标记位byte里的低4bit。

Key编码的设计细节，也体现出MPT整个数据结构设计的思路很完整。

4. 体系

到目前为止，Ethereum系统中区块数据的呈现，组织管理已经介绍了不少，我们可以开始探讨存储部分了。先来看看数据存储部分的UML关系图。

属于Ethereum代码范围内的最底层是ethdb.LDBDatabase,它通过持有一个levelDB的对象，最终为Ethereum世界里所有需要存储/读取[k,b]的需求提供服务。

留意到图中多次出现一种类似的设计模式，比如trie.Trie持有一个本地接口trie.<<Database>>，而后者的具体实现是ethdb.LDBDatabase。这种设计模式其实是golang的语法带来的。在golang中，一个结构体(类)要实现另一个接口的所有方法，不必在结构体声明时显式继承那个接口，只要完全实现那些方法。这样，当一个结构体想调用另一个包路径下结构体的多个方法时，可以声明一个本地接口，带有几个同想要调用方法完全一样的方法，就可以了，这种方式的优点是不同包之间的代码更充分的解耦合。所以在上图中，这些辅助性的本地接口全都被标为灰色，只需要关注实际调用的实现类就好了。

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

面向业务的存储模块 - StateDB

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

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-69032-8.html