以太坊源码分析 数据存储

本文分析以太坊数据存储相关的流程。

首先介绍一下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快速定位交易回执所在的位置,加速交易回执的查找。

下一章:以太坊源码分析 Ethash算法

Ethash是以太坊目前使用的共识算法,其前身是Dagger-Hashimoto算法,但是进行了很大的改动。1. Dagger-HashimotoDagger-Hashimoto算法想要达到以下几个目标:抵 ...