An optimal backend for the IAVL

[zmanian]

So I've been thinking a bit about the properties of an optimal backend for the IAVL tree.

We currently use a general purpose backend for the IAVL tree like leveldb.

This isn't optimal because general purpose back end because general purpose backends where not designed to store immutable data structures and locality properties of common data access.

Here are things we observe.

1. Some leaves are mutated frequently. Some subtrees are accessed every block. Others are infrequently red. We want to have a cache oblivious data structure that is optimized for this access pattern. Frequently mutated and red data should be stored together.

2. Ideally we would have copy on write semantics for the immutable data structure and we should be pulling lessons from purely functional data structures. Ideally we should never copy a leaves and nodes from a new version of the merkle tree. Instead we should track references to those nodes in unpruned versions and only delete the value when all the versions which reference a leaf/node have been pruned.

[mattkanwisher]

One of the first issues, is the underlying persistence area is quite dumb and has little knowledge of what its storing, so you can't even optimize the storage much cause it just uses a https://github.com/tendermint/tendermint/blob/master/libs/db/types.go#L4 tendermint/db interface. It would be nice to know about the tree and info when doing persistence. Maybe nodedb should be pluggable or something even more higher level

See https://github.com/tendermint/iavl/blob/master/nodedb.go#L37

[zmanian]

According to Jae, IAVL tree already has Copy on Write semantics

[davebryson]

I wonder if it'd be worthwhile to explore an approach for iavl similar to what they're doing on the handshake project - creating a flat file database designed around the tree:

We devise an authenticated data structure, which unlike the Ethereum Trie or
Sparse Merkle Tree, is intended for storage in flat files. This removes the
overhead of database lookups entirely by making the data structure its own
database implementation.

By storing a merkelized data structure in a series of append-only files, we are
able to provide traditional database features such as snapshotting, atomicity,
and crash consistency. Given our requirements, a trie is the obvious choice as
a backing data structure.

Flat File Merkle Tree

Urkel Implementation

[alexanderbez]

Assuming Urkle supports snapshotting, range queries/proofs and prefix iteration, can't it be used as a drop-in replacement for IAVL?

[davebryson]

Snapshotting - yes
Simple small proofs - yes
Range queries/proofs - would need to be implemented

Additionally, you'll also need compaction. Essentially you're creating a custom database for the tree. Not a trivial thing to get right. But I bet the Tendermint team has the "chops" to do it 😃

I don't know about a drop-in replacement if Tendermint prefers AVL. There's primarily 2 versions of the Urkel tree: simple base 2, and radix like.

[tac0turtle]

#144 has a few ideas related to this, when this work is picked up please check that pr

[yihuang]

Had a quick glance over Urkle implementation, it seems the storage format is similar to our new node key format, index the nodes by order, we can also do a similar flat file storage like this.