核心操作

bucket tree的计算过程可以分为以下四阶段：

  1. Initialize
  2. Prepare
  3. Process
  4. Commit

核心操作 - 图1

Initialize

在初始化阶段，主要进行构建树形态的构建，cache的初始化以及历史数据的恢复（从db中读取最新的根节点的哈希）

所谓树形态的构建就是利用用户配置的capacity及aggreation两个参数构建树的结构。构建函数如下：

  1. var (
  2.         curlevel  int
  3.         curSize   int = cap
  4.         levelInfo     = make(map[int]int)
  5.     )
  6.     levelInfo[curlevel] = curSize
  7.     for curSize > 1 {
  8.         parSize := curSize / aggr // 根据收敛系数计算下一层的节点个数
  9.         if curSize%aggr != 0 {
  10.             parSize++
  11.         }
  12.         curSize = parSize
  13.         curlevel++
  14.         levelInfo[curlevel] = curSize
  15.     }
  16.     conf.lowest = curlevel
  17.     for k, v := range levelInfo {
  18.         conf.levelInfo[conf.lowest-k] = v // 将每一层的节点个数信息倒置，使得根节点处于0层，哈希桶处于最高层
  19.     }

此外，bucket tree为了（1）增加读取的效率（2）防止写丢失，增加了两个cache用于缓存哈希桶和merkle节点的数据。这两个cache都是利用LRUCache实现的，每次更新时都会同步地更新cache中的内容。如此，下一次bucket tree进行哈希计算时，便可以从cache中命中热数据，尽量避免磁盘的读取。

至于防止写丢失是因为在hyperchain中，validation和commit是两个独立异步的过程，因此在进行完区块100的validation过程时，可能会立刻基于100的状态直接进行区块101的validation。而此时区块100执行过程中对账本的修改还没有被提交的数据库中，因此为了“防止写丢失”，这些内容需要从缓存中命中。

倘若此刻cache发生了容量过小未提交的内容被驱除的情况，就会导致区块101的validation的结果与其他节点不一致（通常为主节点），此时会依赖于RBFT算法进行故障处理。

其中bucketcache是用来存储哈希桶的数据，每一个哈希桶为一个cache数据项。存在的问题是，一个哈希桶本身由若干条数据项组成，随着运行时间增长，一个哈希桶的size会越来越大，导致内存占用量不断上升。

merkleNodeCache是用来存储除最高层以外的所有merkle节点数据的，merkle节点个数是固定的，每个节点的size也是有上限的，因此merkleNodeCache不存在内容占用量变大的问题。

Prepare

在准备阶段，bucket tree会接收由用户传入的修改集，并利用修改集的内容构建脏的哈希桶集。注意，返回的哈希桶中，内部的数据项是按字典序升序排列的。

  1. func newBuckets(prefix string, entries Entries) *Buckets {
  2.     buckets := &Buckets{make(map[Position]Bucket)}
  3.     for key, value := range entries {
  4.         buckets.add(prefix, key, value)
  5.     }
  6.     for _, bucket := range buckets.data {
  7.         sort.Sort(bucket)
  8.     }
  9.     return buckets
  10. }

Process

process也就是哈希重计算阶段，可以分为两部分（1）脏哈希桶的哈希重计算（2）脏merkle节点的哈希重计算。

核心操作 - 图2

脏哈希桶计算

如上图所示，在bucket tree中新插入两条数据项entry5, entry6。entry5得到的散列地址为Pos2，entry6得到的散列地址为Pos5。

哈希桶计算存在一个合并的操作，即在Pos2，需要将新插入的数据，与历史的数据进行一个合并，且按照固定的排序算法进行重排序，最终得到一个新的哈希桶，包含了所有的新旧数据，且按序排列。

每个哈希桶的哈希值为当前桶中数据的进行哈希计算得到的结果。

如图所示，Pos2与Pos5为两个脏的哈希桶，计算完成之后，将父节点中对应的孩子哈希值置为新的桶哈希值，即Merkle1-1，Merkle1-2为两个脏的merkle节点。

脏merkle节点计算

当哈希桶计算完成之后，便可以进行merkle节点的哈希计算。这步中仅对脏的merkle节点进行哈希重计算。

注意，merkle节点的哈希计算是分层进行的。

每个merkle节点维护其孩子节点的哈希值，若下一层的孩子节点哈希值发生变化，会在之前的计算中，就将最新的哈希值置到父节点中；对于没有发生变化的孩子节点，直接使用历史的哈希值即可。

每个merkle节点的哈希值，为其所有孩子节点哈希值的哈希计算得到。

Commit

计算完成之后，需要将最新的哈希桶数据、merkle节点数据进行持久化。

除此以外，所有的哈希桶数据、merkle节点数据都会被存储到缓存中，对于热数据，既可以提高数据的查找效率，也可以避免数据的写丢失情况。