Database

Important factors:

  • persistent key/value storage
  • reliability and efficiency (runtime performance and disk usage)
  • thread safety
  • ease of use

The considered DBs:

  • LMDB
  • LevelDB
  • RocksDB
  • sled - Rust native

To watch:

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.

LMDB

https://symas.com/lmdb/

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.

Rust bindings:

LevelDB

Log Structured Merge Tree db. Uses one global lock. Better write performance than LMDB and lower DB size.

Rust bindings:

RocksDB

A fork of LevelDB with different optimizations (supposedly for RAM and flash storage).

Used in https://github.com/simplestaking/tezedge and https://github.com/near/nearcore.

Rust bindings:

Sled

Repo: https://github.com/spacejam/sled Homepage: https://sled.rs/

Modern, zero-copy reads, lock-free and many more features.


Merkle tree data structure

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.

Patricia trie used in e.g. Ethereum and Plebeia for Tezos are designed to be more space efficient.

Sparse Merle tree as described in Optimizing sparse Merkle trees used in e.g. Plasma Cash are somewhat similar to Patricia trees, but perhaps conceptually simpler.

Considered libraries:

  • merk
  • sparse-merkle-tree
  • patricia_tree

merk

https://github.com/nomic-io/merk

Using AVL tree built on top of RocksDB. It makes it easy to setup Merkle tree storage, but:

sparse-merkle-tree

https://github.com/jjyr/sparse-merkle-tree

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

patricia_tree

https://github.com/sile/patricia_tree