以太坊 存储流程
首先介绍一下 MPT 的存储流程，然后依次分析 StateDB、Transactions、Receipts 的存储，这 3 棵树的 Merkle Root 最终会存储到区块 Header 中的 Root、TxHash、ReceiptHash 字段。
1.MPT 存储流程
从图中可以看出，MPT 的存储涉及 3 种编码方式：
- KeyBytes 编码
- Hex 编码
- Compact 编码
在完成 Compact 编码后，会通过折叠操作把子结点替换成子结点的 hash 值，然后以键值对的形式将所有结点存储到数据库中。下面详细介绍上面 3 中编码方式。
1.1 KeyBytes 编码
即原始关键字，比如图中的 0x811344、0x879337 等。每个字节中包含 2 个 nibble（半字节，4 bits），每个 nibble 的数值范围时 0x0~0xF。
1.2 Hex 编码
由于我们需要以 nibble 为单位进行编码并插入 MPT，因此需要把一个字节拆分成两个，转换为 Hex 编码。编码转换是在 Trie.TryUpdate()中触发的，具体转换代码参见
trie/encoding.go：
func keybytesToHex(str []byte) []byte {
l := len(str)*2 + 1
var nibbles = make([]byte, l)
for i, b := range str {
nibbles[i*2] = b / 16
nibbles[i*2+1] = b % 16
}
nibbles[l-1] = 16
return nibbles
}
1.3 Compact 编码
当我们需要把内存中 MPT 存储到数据库中时，还需要再把两个字节合并为一个字节进行存储，这时候会碰到 2 个问题：
- 关键字长度为奇数，有一个字节无法合并
- 需要区分结点是扩展结点还是叶子结点
为了解决这个问题，以太坊设计了一种 Compact 编码方式，具体规则如下： - 扩展结点，关键字长度为偶数，前面加 00 前缀
- 扩展结点，关键字长度为奇数，前面加 1 前缀（前缀和第 1 个字节合并为一个字节）
- 叶子结点，关键字长度为偶数，前面加 20 前缀（因为是 Big Endian）
- 叶子结点，关键字长度为奇数，前面加 3 前缀（前缀和第 1 个字节合并为一个字节）
编码转换是在 Trie.Commit()时触发的，具体调用在 hasher.hashChildren()函数中，转换代码参见
trie/encoding.go：
func hexToCompact(hex []byte) []byte {
terminator := byte(0)
if hasTerm(hex) {
terminator = 1
hex = hex[:len(hex)-1]
}
buf := make([]byte, len(hex)/2+1)
buf[0] = terminator << 5 // the flag byte
if len(hex)&1 == 1 {
buf[0] |= 1 << 4 // odd flag
buf[0] |= hex[0] // first nibble is contained in the first byte
hex = hex[1:]
}
decodeNibbles(hex, buf[1:])
return buf
}
2. StateDB 的存储
StateDB 中存储了很多 stateObject，而每一个 stateObject 则代表了一个以太坊账户，包含了账户的地址、余额、nonce、合约代码 hash 等状态信息。所有账户的当前状态在以太坊中被称为“世界状态”，在每次挖出或者接收到新区块时需要更新世界状态。
为了能够快速检索和更新账户状态，StateDB 采用了两级缓存机制，参见下图：
- 第一级缓存以 map 的形式存储 stateObject
- 第二级缓存以 MPT 的形式存储
- 第三级就是 LevelDB 上的持久化存储
当上一级缓存中没有所需的数据时，会从下一级缓存或者数据库中进行加载。
我们可以看一下 StateDB 具体实现的 UML 图：
可以看到，一共封装了 3 个包：state，trie，ethdb。如果按接口类型来分，主要分为 Trie 和 Database 两种接口。Trie 接口主要用于操作内存中的 MPT，而 Database 接口主要用于操作 LevelDB，做持久化存储。StateDB 中同时包含了这两种接口。
查看 StateDB 和 stateObject 的定义可以发现，这两种类型内部各有一个 Trie，那么这两个 Trie 里存储的什么内容呢？请看下图：
StateDB 里的 Trie 以账户地址为 key，存储经过 RLP 编码后的 stateObject。stateObject 里的 Trie 也被称为 storage trie，存储的是智能合约执行后修改的变量值，细节可以参见之前的一篇文章：以太坊 stateObject 中 Storage 存储内容的探究
这两个 Trie 是怎么关联起来的呢？实际上 stateObject 内部有一个 Account 类型的字段，我们看一下它的类型定义：
type Account struct {
Nonce uint64
Balance *big.Int
Root common.Hash // merkle root of the storage trie
CodeHash []byte
}
看到了吧，Account 类型内部有一个 Root 字段，记录的正是对应的 storage trie 的 merkle root。
3. Transactions 的存储
从图中可以看出，MPT 中是以交易在区块中的索引的 RLP 编码作为 key，存储交易数据的 RLP 编码。
事实上交易在 LeveDB 中并不是单独存储的，而是存储在区块的 Body 中。在往 LeveDB 中存储不同类型的键值对时，会在关键字中添加不同的前缀予以区分，这些前缀的定义在 core/rawdb/schema.go 中：
// Data item prefixes (use single byte to avoid mixing data types, avoid `i`, used for indexes).
headerPrefix = []byte("h") // headerPrefix + num (uint64 big endian) + hash -> header
headerTDSuffix = []byte("t") // headerPrefix + num (uint64 big endian) + hash + headerTDSuffix -> td
headerHashSuffix = []byte("n") // headerPrefix + num (uint64 big endian) + headerHashSuffix -> hash
headerNumberPrefix = []byte("H") // headerNumberPrefix + hash -> num (uint64 big endian)
blockBodyPrefix = []byte("b") // blockBodyPrefix + num (uint64 big endian) + hash -> block body
blockReceiptsPrefix = []byte("r") // blockReceiptsPrefix + num (uint64 big endian) + hash -> block receipts
txLookupPrefix = []byte("l") // txLookupPrefix + hash -> transaction/receipt lookup metadata
bloomBitsPrefix = []byte("B") // bloomBitsPrefix + bit (uint16 big endian) + section (uint64 big endian) + hash -> bloom bits
preimagePrefix = []byte("secure-key-") // preimagePrefix + hash -> preimage
configPrefix = []byte("ethereum-config-") // config prefix for the db
因此，以 b + block index + block hash 作为关键字就可以唯一确定某个区块的 Body 所在的位置。
另外，为了能够快速查询某笔交易的数据，在数据库中还存储了每笔交易的索引信息，称为 TxLookupEntry。TxLookupEntry 中包含了 block index 和 block hash 用于定位区块 Body，同时还包含了该笔交易在区块 Body 中的索引位置。
4. Receipts 的存储
交易回执的存储和交易类似，区别是交易回执是单独存储到 LevelDB 中的，以 r 为前缀。
另外，由于交易回执和交易是一一对应的，因此也可以通过 TxLookupEntry 快速定位交易回执所在的位置，加速交易回执的查找。