Architecture

​

Overview

┌─────────────────────────────────────┐
│     Database / Transaction API      │  ← User-facing interface
├─────────────────────────────────────┤
│    MVCC Transaction Manager         │  ← Snapshot isolation
├─────────────────────────────────────┤
│   B-tree Storage Engine (CoW)       │  ← Document indexing
├─────────────────────────────────────┤
│  Pager (LRU Cache + Page Alloc)    │  ← Page management
├─────────────────────────────────────┤
│   Write-Ahead Log (WAL)             │  ← Durability & recovery
├─────────────────────────────────────┤
│        File System                  │  ← Physical storage
└─────────────────────────────────────┘

​

Core components

​

Database

pub struct Database {
    pager: Arc<Pager>,
    wal: Arc<WAL>,
    metadata: Arc<RwLock<Metadata>>,
    tx_manager: Arc<TransactionManager>,
    version_chains: Arc<RwLock<HashMap<...>>>,
    // ... configuration and metrics
}

• Initialize and coordinate all subsystems
• Manage collection metadata (schemas, indexes, roots)
• Provide transaction lifecycle management
• Execute automatic checkpointing
• Track database-wide metrics

​

Pager

pub struct Pager {
    file: Arc<Mutex<File>>,
    cache: LRUCache,              // ~100MB default
    num_pages: Arc<RwLock<u64>>,
    metadata_page: Arc<RwLock<u64>>,
    free_list: Arc<RwLock<Vec<PageNum>>>,
    // ...
}

• 4KB pages - Standard page size for efficient I/O
• LRU caching - 25,000 page default (~100MB)
• Free list management - Reuses deleted pages
• Corruption detection - Validates header on open (src/core/pager.rs:222)

​

Write-Ahead Log (WAL)

pub struct WALFrame {
    pub tx_id: u64,
    pub page_num: u64,
    pub page_data: Vec<u8>,    // 4KB
    pub checksum: u32,         // CRC32 integrity check
    pub salt1: u32,            // Replay protection
    pub salt2: u32,
}

1. Before commit: Write modified pages to WAL with checksums
2. fsync WAL: Guarantee durability to disk
3. Update database: Write pages to main file
4. Checkpoint: Merge WAL into main file, truncate WAL

• Crashes during commit (replay from WAL on recovery)
• Torn writes (checksums detect corruption)
• Incomplete transactions (salt values prevent stale frame replay)

​

B-tree Storage Engine

pub struct BTree {
    pager: Arc<Pager>,
    inner: Arc<RwLock<BTreeInner>>,  // CoW state tracking
}

struct BTreeInner {
    root_page: u64,
    cow_pages: HashMap<u64, u64>,    // old → new page mapping
    new_pages: HashMap<u64, bool>,   // track allocated pages
}

• When a transaction modifies a page, it allocates a new page instead of overwriting
• Old pages remain untouched for concurrent readers
• On commit, the new root is atomically swapped
• Supports O(log n) document lookup, insert, and deletion

​

Data flow: Insert operation

let mut tx = db.begin()?;
let mut users = tx.collection("users");
users.insert(json!({"name": "Alice"}))?;
tx.commit()?;

1. Begin transaction (src/core/transaction.rs:56)
   • Allocate MVCC transaction ID (xmin)
   • Capture snapshot ID (latest committed tx)
   • Take snapshot of all collection B-tree roots
2. Insert document (src/core/tx_collection.rs)
   • Allocate new page for document
   • Write versioned document with xmin = current tx
   • Insert into CoW B-tree (may trigger splits)
   • Track document write in transaction
3. Commit transaction (src/core/transaction.rs:445)
   • Conflict detection: Check if other transactions modified same documents
   • Acquire commit lock: Serialize commits
   • Write to WAL: Log all page changes with checksums
   • Write to pager: Update pages in cache
   • Sync WAL: fsync() for durability
   • Update metadata: New B-tree roots
   • Mark committed: Update MVCC manager

​

Concurrency model

• Multiple readers: Share the same snapshot, never block each other
• Multiple writers: Build independent tree versions, serialize at commit
• Read + Write: Readers use old snapshot, writers create new version

• Check if documents modified by this transaction were also changed by a committed transaction
• If conflict detected → rollback and retry (automatic with run_transaction())
• If no conflict → commit succeeds

​

File layout

mydb.db          # Main database file
mydb.db-wal      # Write-ahead log
mydb.db.lock     # Lock file (exclusive write mode)

┌──────────────────────┐
│  Page 0: Header      │  ← Magic, version, num_pages, metadata_page
├──────────────────────┤
│  Page 1...N: Data    │  ← B-tree nodes, documents, indexes
├──────────────────────┤
│  Page M: Metadata    │  ← Collections, schemas, index definitions
└──────────────────────┘

• Magic number validation (JSIN)
• Version and page size
• Total page count
• Metadata page pointer
• Free page list
• Next transaction ID

​

Performance characteristics

• Write throughput: ~19,150 docs/sec (1000 docs per transaction)
• Read latency: 0.009ms @ 16 threads (MVCC snapshot isolation)
• Query speed: Sub-millisecond even on 2500+ documents
• Concurrent writes: Linear scaling up to core count

1. LRU page cache - 100MB default reduces disk I/O
2. Batch commits - Groups up to 32 transactions into single fsync
3. Sequential WAL writes - Append-only for minimal seek overhead
4. Batched checkpoints - Writes consecutive pages in single syscall
5. Per-database buffer pools - Reduces allocations for B-tree operations

​

Thread safety

• Arc<RwLock<T>> for read-heavy state (metadata, MVCC info)
• Arc<Mutex<T>> for exclusive access (file I/O, commit serialization)
• Lock-free atomics for counters (transaction IDs, metrics)

​

Next steps