Crate donadb_x 

DonaDbX — Lock-Free Storage Engine for Blockchain Validator State

DonaDbX is a high-performance, append-only key-value store built for blockchain validator state. It combines a lock-free write path, atomic N-shard double-buffering, parallel BLAKE3 Merkle folding, and crash-safe segment rotation into a single coherent API surface.

Architecture

The engine is composed of five cooperating subsystems:

┌──────────────────────────────────────────────────────────────┐
│                        DonaDbX API                           │
└───────────┬──────────────────────────────────┬───────────────┘
            │                                  │
  ┌─────────▼──────────┐            ┌──────────▼──────────┐
  │  1. ExecutionFrame │            │  3. DualBufferEngine │
  │  Isolated write    │            │  N-shard ArcSwap;    │
  │  arena; rollback   │            │  atomic buffer swap  │
  └─────────┬──────────┘            └──────┬───────────────┘
            │                             │
            │                  ┌──────────┼──────────────┐
            │                  │          │              │
  ┌─────────▼──────────┐  ┌────▼───────┐  ┌▼────────────┐
  │  2. CommutativeLog │  │ 4. Rayon   │  │ 5. Segment  │
  │  Lock-free mmap    │  │    fold    │  │    Manager  │
  │  fetch_add +       │  │  Parallel  │  │  Rotation,  │
  │  memcpy append     │  │  BLAKE3 +  │  │  manifest,  │
  │  posix_fallocate   │  │  XOR root  │  │  recovery   │
  └────────────────────┘  └────────────┘  └─────────────┘

#	Subsystem	Role
1	ExecutionFrame	Isolated write arena with zero-copy rollback. Writes are visible via DonaDbX::get immediately; visible via the index after ExecutionFrame::commit.
2	commutative::CommutativeLog	Memory-mapped append log. One fetch_add reserves space; one memcpy fills it. posix_fallocate pre-allocates physical blocks so disk-full surfaces at segment creation, not mid-write.
3	DualBufferEngine	N shards (one per logical CPU), each with monotonically-growing logs. DonaDbX::commit snapshots all shards and launches parallel fold without blocking writers.
4	Rayon fold pool	After each commit, runs parallel BLAKE3(value) hashing across all shards simultaneously. Maintains a commutative XOR accumulator key XOR BLAKE3(value) for the state root.
5	SegmentManager	Rotates the active log to a sealed segment at the fill threshold. Writes a crash-safe JSON manifest via atomic write-tmp → rename. Replays on reopen.

Key design decisions

Lock-free writes. DonaDbX::put performs a single fetch_add on the shard’s write_offset atomic to reserve a slot, then copies the payload in with memcpy. No mutex is acquired on the hot write path.

Parallel fold. DonaDbX::commit snapshots all shard write frontiers and dispatches them to a Rayon thread pool for parallel processing. Each shard is folded independently, maximizing CPU utilization.

Commutative Merkle root. The state root is maintained as an XOR accumulator over key XOR BLAKE3(value) for every key. Incremental updates are O(1): XOR out the old contribution, XOR in the new one. The final root is BLAKE3(accumulator).

Immediate read visibility. DonaDbX::get checks three sources in order: (1) the shard index (O(1), covers folded writes), (2) an active-log scan over the current unflushed batch (covers writes since the last fold), (3) sealed segments (covers rotated history). In-batch reads are visible immediately without waiting for the next commit().

Crash recovery. The first 8 bytes of seg_active.log store committed_offset as a little-endian u64. On reopen, the engine scans only the range [8, committed_offset), rebuilding the index and XOR accumulator from scratch. Partial writes above committed_offset are silently discarded. No separate write-ahead log is needed.

Disk-full protection. posix_fallocate(2) is called at segment creation time. If the filesystem cannot allocate the required space, DbError::Io(ENOSPC) is returned immediately — never as a SIGBUS mid-write inside a validation loop.

Quick start

use donadb_x::{DonaDbX, Config};

let db = DonaDbX::open("./state", Config::default()).unwrap();

let key = [1u8; 32];
db.put(key, b"hello").unwrap();

// commit() swaps the active buffer and launches an async fold.
let ack = db.commit(1).unwrap();

// wait() blocks until the fold completes and returns the 32-byte state root.
let root = ack.wait();

assert_eq!(db.get(&key).unwrap(), b"hello");
println!("state root: {}", hex::encode(root));

Multi-threaded writes with BlockWriter

For high-throughput ingestion, acquire one BlockWriter per thread per block. Each writer holds a direct Arc<CommutativeLog>, so writers on different shards contend only on their own shard’s write_offset atomic — never on each other.

use donadb_x::{DonaDbX, Config};
use std::sync::Arc;

let db = Arc::new(DonaDbX::open("./state", Config::default()).unwrap());

let handles: Vec<_> = (0..4).map(|shard_id| {
    let db = Arc::clone(&db);
    std::thread::spawn(move || {
        let writer = db.writer(shard_id);
        for i in 0u8..64 {
            let mut key = [0u8; 32];
            key[0] = shard_id as u8;
            key[1] = i;
            writer.put(key, &[i; 8]).unwrap();
        }
    })
}).collect();

for h in handles { h.join().unwrap(); }
let root = db.commit(2).unwrap().wait();
println!("block 2 state root: {}", hex::encode(root));

Complexity summary

Operation	Complexity	Notes
put()	O(1)	One fetch_add + one memcpy; no locks
get()	O(1) + O(u)	O(1) index hit; O(u) unflushed scan on miss, where u = records in current batch
get_at()	O(v)	MVCC chain walk over v versions of the key
commit()	O(1) enqueue	Swap is instantaneous; fold is async
state_root()	O(1)	Reads the pre-maintained XOR accumulator
Segment rotation	O(n) amortised	Runs once at fill threshold per segment
Crash recovery	O(r)	Replays r committed records from the active log

Re-exports

pub use commutative::MmapRef;

pub use string_index::StringIndex;

Modules

commutative

Public commutative-log API: lock-free, memory-mapped append log. CommutativeLog — lock-free mmap append log with parallel rayon fold at commit.

index

Public index API: sharded hash-map for key → log-offset lookups. ShardIndex — 256-shard in-memory key→offset lookup table.

string_index

String prefix index — secondary BTreeMap for lexicographic prefix scans. String prefix index — secondary BTreeMap for lexicographic prefix scans.

Structs

BlockWriter

Re-export so callers can use BlockWriter without importing dual_buffer. A write handle scoped to one thread and one block.

CommitAck

Handle returned by DonaDbX::commit().

Config

Runtime configuration for a DonaDbX instance.

DonaDbX

The top-level storage engine handle.

ExecutionFrame

An isolated write arena scoped to a single block.

Enums

DbError

The unified error type for all DonaDbX operations.

Type Aliases

DbResult

Convenience alias for Result<T, DbError>.