Proposal

The only pure Rust alternative is redb but it still does not support to be opened by different processes. Hence, we can forget it.

IMO, rocksdb is recommended, it is blazing fast comparing to rusqlite. rocksdb has the column family design, which is quite fit to our project (one column family for DA blobs and the other for blocks). The column family feature just like we can create tables in SQL. RocksDB by using memory map and cache, makes both read and write performance very fast. There are some blockchains already using rocksdb in production, so we may can give it a try? But, rocksdb also ordered by key, we still need to think a way to support range query for our blocks data (indexing or use the block height as the key).

Requirements

• Must have:
  • Can be opened by multiple processes, no dir lock.
• Nice to have:
  • Not ordering by key, but in respect of the insertion order.

Key-value Database

Three kinds of main architecture:

• B+ Tree
  • Pros:
    • Efficient Reads: B+ Trees are excellent for read-heavy operations due to their ability to perform binary searches, leading to fast data retrieval.
    • Range Queries: Supports efficient range queries as data is sorted.
  • Cons:
    • Write Overhead: Writing data can be more expensive due to the need for rebalancing the tree after insertions or deletions.
    • Fragmentation: Over time, the database can become fragmented, requiring periodic maintenance.
• Log-structed Merge Tree (LSM)
  • Pros:
    • High Write Throughput: LSM excels in environments with high write volumes because it minimizes disk I/O by batching writes.
    • Efficient Space Utilization: Compaction processes optimize storage space and maintain data in a compact format.
    • Scalability: Well-suited for distributed systems where write scalability is crucial.
  • Cons:
    • Read Latency: Read operations can be slower, especially if the data is not in the in-memory structure, due to the need to search multiple levels.
    • Compaction Overhead: The compaction process can consume significant system resources and impact performance.
• Bitcask
  • Pros:
    • Fast Writes: Appending data to the end of a file ensures that writes are consistently fast.
    • Low Latency Reads: Having all keys in memory with direct pointers to the data on disk results in low latency reads.
    • Simplicity: The architecture is straightforward, leading to easy implementation and maintenance.
  • Cons:
    • Memory Usage: Requires that all keys fit in memory, which can limit scalability for databases with a vast number of keys.
    • Data Compaction: Over time, the log file can become fragmented with dead data (due to updates and deletions), requiring periodic compaction.

Toughts:

In our case, read performance is more important than write performance, but we also need to try our best to utility disk usage. If we will finally persistent data to a standalone database, then Bitcask is better. If not LSM is better.

(However, Rust does not have bitcask key-value database, and the only LSM based key-value database is rocksdb, a C++ binding crate).

Available options for Rust

• redb:
  • Transaction: multiple readers, single writer.
  • Underlying: B+ Tree
  • Pros:
    • Pure Rust, actively maintained.
  • Cons:
    • Too young, not see any blockchain is using.
• rocksdb:
  • Transaction: multiple readers, multiple writers.
  • Underlying: Log-structed Merge Tree
  • Pros:
    • Developed by Facebook, well maintained and promised, already be used in Solana's ledger.
  • Cons:
    • It is a C++ binding, not pure Rust.
• parity-db:
  • Transaction: multiple readers, single writer
  • Underlying: Unknown
  • Pros:
    • The data can be partitioned into columns, may be useful for our DA.
  • Cons:
    • Only used in parity's blockchain, less example.