leaf separation or versiondb integration

[yihuang]

The key observation here is leaf nodes contains all the key/value pairs, if we store the leaf nodes separately in the same way as versiondb, we can query or iterate the key/value pairs directly without traversing the branch nodes.
Put it another way, it avoids the duplications between iavl and versiondb, or has fully integrated versiondb inside the iavl, and we won't need the fast node index anymore.

We assumeI the db has fully migrated to new node key format here, so we can get the version from the node key. It probably don't work with the lazy migration, aka. the mixed mode.

func getLeaf(key []byte, version int64) Node {
  // leaf nodes are stored in similar way as versiondb
  value := versiondb.Get(key, version)
  // compute the node hash on the fly
  return MakeLeafNode(version, key, value)
}

func getNode(nodeKey NodeKey) Node {
  // load the branch node with the new node key format
}

func getRightChild(n *Node) Node {
  if n.flag & RightLeaf > 0 {
    return getLeaf(n.key, n.rightChildKey.version)
  } else {
    return getNode(n.rightChildKey)
  }
}

func getLeftChild(n *Node) Node {
  if n.flag & LeftLeaf > 0 {
    // `leftKey` is a new field which stores the key of it's left child, only need for the `height==1` nodes.
    return getLeaf(n.leftKey, n.leftChildKey.version)
  } else {
    return getNode(n.leftChildKey)
  }
}

Highlights

• Nodes whose height==1 need to add a new field leftKey to store the key of it's left child (the original key field is the key of right child).
• Need to do an explicit deletion operation when deleting a key/value pair, previously just implicitly orphan the old leaf.
• Don't store the leaf node hash on disk at all, since it's trivial to recompute on the fly, we can cache the hash in the cached node though.
• Support a new pruning mode that only prune the branch nodes, but leave the archived leaf nodes, which can still supports archived historical state queries.
• Don't need the fast node index anymore, it'll be as fast as that for queries at all versions.
• VersionDB only supports rocksdb and pebbledb as backends.

[kocubinski]

When optimizing for reads and space on disk it definitely makes sense to consider a SS backend without inner nodes, with the (big) caveat that we'll need to support historical proofs in some other way.