背景描述

在以太坊中，以太坊的账户数据存储在一颗十六叉树中，所谓的十六叉树，是以太坊将传进去的byte数组中的每个元素拆成一个nibble数组(一个byte为2个nibble)，比如我要将一个kv对(0xaa, v)存储到十六叉书中，示意图大概如下：

在以太坊中，每个区块都包含一个stateRoot字段，它是MPT根的哈希值。这个根哈希值，是通过对根的16个子项的哈希列表进行哈希运算而获得的。这些子哈希列中的每一个，又依次是其子哈希列表的哈希，依此类推。

我们看到上面的十六叉树，深度比较浅，但是宽度却比较宽。为了计算上一个节点哈希值，需要将下面所有的节点的数据从数据库加载进来或者计算出来。也就是说，为了计算一个节点的哈希值，需要将同级的15个元素的哈希值全部加载进来，上面所示图片有2层，那么就是30个元素。

解决方式

还是以上面的的kv对 (0xaa, v) 为例存储到二叉树中，示意图大概如下：

首先，我们将key = 0xaa 映射到二叉树中，我们也跟十六叉树一样，首先将byte数组拆成nibble数组，规定当nibble的值范围是0 ~ 7时，我们往二叉树的左边走。当nibble的值范围是8 ~ f时，我们往右边走。这样，最终的key映射到了二叉树索引为6的地方，我们将v值保存到这个节点的数组。此时，如果重新计算root，那么需要读取的数据只需要二叉树索引为1，5两处。图中已经标红的两个节点。总的来说，对于深度为depth的二叉树，读取的数据为depth个。

实现

为了高效的实现这颗二叉树，我们使用数组的方式来存储这颗二叉树。所以大概说一下上面图中表示的一些含义。

图形含义

• 圆形：表示一个二叉节点，用来存储下面两个节点的计算出来的哈希值以及下面2个节点元素的个数之和。最后一层的二叉节点，则表示叶子节点元素的个数以及叶子节点的哈希值。
• 长方形：表示一个叶子节点，用来存储key-value对。
• 圆形旁边数字：二叉节点的索引值
• 长方形下面数字：叶子节点索引值
• depth：表示二叉树的层数，注意以0开始。

数据结构定义

• 二叉节点

  binaryHashNode struct {
  Hash [32]byte
  Num  uint32
  }

• 叶子节点中的一个元素

  binaryNode struct {
  Key []byte
  Val []byte
  }

• 叶子节点

  binaryLeaf []binaryNode

• 历史修改数据

type DiffLeaf struct {
    Index uint32
    Leaf  binaryLeaf
}

type Alter struct {
    PreRoot   [32]byte
    CurRoot   [32]byte
    DiffLeafs []DiffLeaf
}

• 二叉树

type BinaryTree struct {
    curDiffLeafs    []DiffLeaf       // 当前修改
    alters          []Alter          // 修改历史
    mem             mmap.MMap        // MMap
    f               *os.File         // 文件指针
    depth           int              // 二叉树深度
    unhashedIndex   []int            // 需要重新计算的叶子节点的索引
    uncommitedIndex []int            // 需要提交的叶子节点索引
    binaryHashNodes []binaryHashNode // 二叉节点
    binaryLeafs     []binaryLeaf     // 叶子节点
}

关于二叉树的一些特性

这些特性基于数组存储，二叉节点与叶子节点分别用一个数组存储。对于一颗深度为depth的二叉树。

• 元素的个数为 2^0 + 2^1 + ... + 2^depth == 2^depth - 1
• 对于索引为i的节点：左子节点索引为2i+1，右子节点索引为2i+2，父节点索引为(i-1)/2
• 对第depth层，二叉节点的索引为：[2^depth-1, 2^(depth+1) - 1)。左闭右开。
• 对于最后一层索引为i二叉节点，对应的叶子节点索引为：i - (2^depth-1)

二叉节点中的元素数目

最后一层二叉节点元素数目为叶子节点的元素数目。其他二叉节点的数目为两个子节点的数目之和

如何计算哈希值

• 二叉节点：将两个子节点的哈希值与子节点的叶子元素和的数目拼凑成一个字节数组进行计算，即Keccak256(hash1 + num1 + hash2 + num2)。对于最后一层，使用叶子节点的哈希值，同时数值为叶子节点元素的个数。
• 叶子节点：由于叶子节点存储的元素有多个，每次叶子节点插入元素的时候，都按照key值以字典序排序。叶子节点的哈希值计算方式为：Keccak256(key1 + value1) ⊕ Keccak256(key2, value2) ⊕ ... ⊕ Keccak256(keyN, valueN)
• stateRoot：以第一个二叉节点的哈希值与叶子元素和的数目拼凑成一个字节数组进行计算，即Keccak256(hash + num)

持久化到数据库中

• 二叉节点：为了加快二叉节点的读取与解码，二叉节点使用内存映射(memory map)的技术，直接将所有二叉节点数据写成一个二进制文件保存。使用mmap-go库进行读写。
• 叶子节点：key为叶子节点的哈希值。value为RLP([[key1, value1], [key2, value2], ... , [keyN, valueN])
• 历史修改数据：历史数据key为"alt" + stateRoot（加"alt"前缀是为了解决与stateRoot存储时的冲突），value为RLP(alter)。
• stateRoot: 支持数据的回滚与最近几个区块的历史数据的查询，二叉节点的第一个索引会存到levelDB中。key为stateRoot，value为第一个哈希节点的hash与叶子元素的和即RLP(hash, num)

从数据库中恢复

• 二叉节点：直接使用mmap-go库将保存的文件加载进内存即可
• 叶子节点：将最后一层的二叉节点拿到的哈希值为key，从数据库中查到对应的value，进行RLP解码，恢复叶子节点的数据。
• 历史修改数据：首先将最新的stateRoot找出来，以"alt" + stateRoot为key读出对应的value值，然后对value进行解码恢复最后的一个修改。再在最后的修改中读取出上一个stateRoot即PreRoot，以"alt" + PreRoot为key继续恢复倒数第二个修改。依次循环，将levelDB中的修改全部恢复过来。

需要测试的地方

• 每插入一千万账户，平均需要尝试的次数(即花费时间是多少)
• 一次性从leveldb中将整颗二叉树加载到内存需要花费多少时间
• 生成一颗空的树需要多少时间
  • depth = 20 大约 60ms
  • depth = 21 大约 140ms

待开发功能

• 历史数据的回滚
  • 链分叉回滚
  • 因为链挂掉或强制停止链等情况导致数据不一致的链回滚
• 历史修改数据不要重复覆盖写入
• 已写入levelDB数据的删除(以出10个区块清理一次)
  • 叶子节点数据的删除
  • 修改数据的删除
  • 合约历史数据的删除
• 内存中数据的释放
  • 合约数据的删除