- persistent key/value storage
- reliability and efficiency (runtime performance and disk usage)
- thread safety
- ease of use
The considered DBs:
- sled - Rust native
- sanakirja - too new to be considered for now, but has some promising initial results - TLDR. it can fork tables efficiently, it beats LMDB in benchmarks and usability
The current preference is for RocksDB as it's tried and tested. Eventually, we might want to benchmark against other backends for our specific use case.
A compact and efficient, persistent in-memory (i.e. mmap-based) B+trees database. Reportedly has a great read performance, but not as good at writing.
- https://github.com/vhbit/lmdb-rs - some comparison notes with danburkert/lmdb-rs
Log Structured Merge Tree db. Uses one global lock. Better write performance than LMDB and lower DB size.
A fork of LevelDB with different optimizations (supposedly for RAM and flash storage).
Modern, zero-copy reads, lock-free and many more features.
Some popular choices for merkle tree in the industry are AVL(+) tree, Patricia Trie and Sparse Merkle Tree, each with different trade-offs.
AVL(+) tree is used in e.g. Cosmos. The advantage of this structure is that key don't need to be hashed prior to insertion/look-up.
- Compact Sparse Merkle Trees https://eprint.iacr.org/2018/955.pdf
- Efficient Sparse Merkle Trees (caching) https://eprint.iacr.org/2016/683.pdf
Using AVL tree built on top of RocksDB. It makes it easy to setup Merkle tree storage, but:
- is not yet fully implemented as described (e.g. concurrent ops)
- benchmarks seem to differ from results in README
- doesn't have past states of the tree, instead relies on RocksDB snapshot/checkpoint features, which means that it's strongly coupled
- uses a custom encoding lib which is zero-copy, but big-endian everywhere
- there are a
unsafeusages that are not well described/justified
- uses some experimental dep such as https://github.com/rust-lang-nursery/failure (now deprecated)
A nice abstraction, albeit not yet declared stable. It allows to plug-in a custom hasher function (which is important for circuit friendliness) and storage backend. Has minimal dependencies and support Rust