An optimal backend for the IAVL about iavl

[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

[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.

[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

[alexanderbez]

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

[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.