# VersionDB And MemIAVL

## Bottlenecks For Scaling

- DB size
- DB access speed

## VersionDB + Pruned IAVL Tree

# before
1.7T	application.db

# after
93G	  application.db
25G	  versiondb

## Trade Off

- [x] Consensus State Machine
- [x] Archived historical queries without merkle proofs
- [x] Histroical queries with merkle proofs for recent versions
- [ ] Histroical queries with merkle proofs for old versions

## How It Works

Store multiple version key/value pairs without a merkle tree:

key1@0001 -> value1
key1@0010 -> value2
key1@0100 -> value2
key2@0001 -> value1

## Implementations

- [Rocksdb User Defined Timestamp](https://github.com/facebook/rocksdb/wiki/User-defined-Timestamp-%28Experimental%29), supported

- [Pebble support something similar as well](https://github.com/cockroachdb/pebble/blob/master/cmd/pebble/mvcc.go), to be supported

- [A design that works on general kvdb](https://hackmd.io/39g7ncwjRyCLCccMrfBK-A), abandoned

## Migration

[Documentation](https://github.com/crypto-org-chain/cronos/wiki/VersionDB-Migration#migration)

- Extract change sets from existing IAVL tree.
- Build the versiondb from the change sets.

## MemIAVL

- On disk IAVL tree snapshot, direct accessible through mmap.
- Store the change sets of each block as write-ahead-log.

[File Format](https://github.com/crypto-org-chain/cronos/tree/main/memiavl#iavl-snapshot)

## Performance

- Query (take away: as fast as in-memory data structures)

memiavl         	 	       116.4 ns/op
memiavl-disk    	 	       168.3 ns/op
btree-degree-2  	 	       133.2 ns/op
btree-degree-32 	 	       202.8 ns/op
lru-cache       		       123.8 ns/op
go-map           	         12.52 ns/op

- Import/Export, much faster than existing impl.

## Different Solutions For Different Roles

- memiavl: consensus state machine
- versiondb: historical queries without proofs
- traditional iavl: historical queries with proofs