AeroDB High-Level Architecture Design¶

Design document for Phase 0 — Minimum Viable Infrastructure

Single-node, schema-mandatory, WAL-backed, deterministic database engine.

1. System Overview¶

aerodb is a single-node document database engine with mandatory schemas, deterministic behavior, and WAL-backed durability. It prioritizes correctness, predictability, and operational clarity over performance, flexibility, or feature breadth.

graph TB
    subgraph "Client Interface"
        API[API Layer]
    end

    subgraph "Query Processing"
        Parser[Query Parser]
        Validator[Schema Validator]
        Planner[Deterministic Query Planner]
        Executor[Query Executor]
    end

    subgraph "Storage Engine"
        WAL[Write-Ahead Log]
        Index[B-Tree Index Manager]
        Storage[Document Storage]
        Checksum[Checksum Validator]
    end

    subgraph "Recovery"
        Recovery[Recovery Manager]
    end

    API --> Parser
    Parser --> Validator
    Validator --> Planner
    Planner --> Executor
    Executor --> WAL
    Executor --> Index
    WAL --> Storage
    Index --> Storage
    Storage --> Checksum
    Recovery --> WAL
    Recovery --> Storage

2. Major Components and Responsibilities¶

2.1 API Layer¶

Responsibility: Accept client requests, route to query processing, return results or explicit errors.

Invariants Upheld: - F1 (Fail Loudly): All errors are explicit and returned to client - F2 (No Partial Success): Request either fully succeeds or fully fails - O3 (Observable System State): All operations are logged

2.2 Query Parser¶

Responsibility: Parse query syntax into an internal representation. No interpretation, no guessing.

Invariants Upheld: - Q3 (Execution Never Guesses): Ambiguous queries are rejected - F3 (Errors Are Deterministic): Same malformed query → same error

2.3 Schema Validator¶

Responsibility: Enforce that all documents conform to their declared schema before any write.

Invariants Upheld: - S1 (Schema Presence Is Mandatory): No schemaless writes - S2 (Schema Validity Is Enforced on Write): Invalid data never enters storage - S3 (Schema Versions Are Explicit): Documents reference explicit schema version - S4 (Schema Violations Are Fatal): Validation failure = write rejection

2.4 Deterministic Query Planner¶

Responsibility: Generate a query execution plan that is deterministic, bounded, and explainable.

Determinism Mechanism: 1. Index selection is rule-based (not statistics-driven heuristics) 2. Rules are versioned and explicit 3. Same (query, schema, indexes) → same plan

Invariants Upheld: - T1 (Deterministic Planning): Same inputs → same plan - T3 (Planner Changes Are Explicit): Any rule change is versioned/opt-in - Q1 (Queries Must Be Bounded): Unbounded queries rejected - Q2 (No Implicit Full Scans): Scans require explicit declaration

2.5 Query Executor¶

Responsibility: Execute the plan produced by the planner. No rewriting, no optimization.

Invariants Upheld: - T2 (Deterministic Execution): No timing/thread-dependent behavior - Q3 (Execution Never Guesses): Execute plan as specified

2.6 Write-Ahead Log (WAL)¶

Responsibility: Ensure all acknowledged writes are durable before acknowledgment.

Invariants Upheld: - D1 (No Acknowledged Write Is Ever Lost): WAL sync before ack - R1 (WAL Precedes Acknowledgement): Mandatory - R2 (Recovery Is Deterministic): WAL enables deterministic replay

2.7 Document Storage¶

Responsibility: Store documents on disk in a structured format with integrity validation.

Invariants Upheld: - D2 (Data Corruption Is Never Ignored): Checksums enable detection - D3 (Reads Never Observe Invalid State): Only schema-valid data stored

2.8 B-Tree Index Manager¶

Responsibility: Maintain B-tree indexes for efficient, bounded lookups.

Invariants Upheld: - Q1 (Queries Must Be Bounded): Indexes enable bounded execution - T1 (Deterministic Planning): Index availability is explicit

2.9 Checksum Validator¶

Responsibility: Validate integrity of all data read from storage.

Invariants Upheld: - D2 (Data Corruption Is Never Ignored): Detection is mandatory - K1 (Corruption Detection Is Mandatory): Checksums on all records - K2 (Corruption Is Never Silently Repaired): Halt, don't repair

2.10 Recovery Manager¶

Responsibility: Restore database to consistent state after crash.

Invariants Upheld: - R2 (Recovery Is Deterministic): Same WAL → same state - R3 (Recovery Completeness Is Verifiable): Explicit status report

2.11 Execution Concurrency Model¶

Responsibility: Enforce deterministic, single-threaded execution.

Phase 0 Model: Single global execution lock.

Enforcement: - API Layer acquires global lock on request entry - Lock released only after: - Write: WAL fsync and acknowledgment - Read: Result returned to client - If lock is held, subsequent requests block

Invariants Upheld: - T2 (Deterministic Execution): No concurrent execution eliminates timing dependencies

2.12 Configuration Manager¶

Responsibility: Validate and enforce configuration constraints.

Phase 0 Configuration Surface:

Forbidden Configurations: - Any mode that disables WAL fsync - Any mode that weakens schema validation - Any mode that bypasses checksums - Any mode that allows partial success

Invariants Upheld: - O2 (Config Cannot Violate Safety): Unsafe configurations rejected at startup

3. Write Atomicity Model¶

3.1 Atomicity Boundary¶

Single-Document Atomicity: Each write operation (insert, update, delete) modifies exactly one document atomically.

Atomicity Guarantee: - A write operation is atomic at the document level - Partial document updates are never observable - All secondary state (indexes) is updated as part of the same atomic operation

Index State Model: Indexes are derived, rebuildable state.

Write Operation Atomicity Stages:

1. Append to WAL (with checksum)
2. Fsync WAL to disk
3. Apply to Document Storage (with checksum)
4. Update B-Tree Indexes (in-memory, derived from storage)
5. Acknowledgment to client

Critical Rule: Steps 1-3 are the durability boundary. Index updates (step 4) occur after durability is guaranteed but before acknowledgment. If a crash occurs after step 3 but before step 4, recovery rebuilds indexes from storage.

Invariants Upheld: - D1 (No Acknowledged Write Lost): WAL fsync guarantees durability - F2 (No Partial Success): Document + index update completes or entire operation fails - C1 (Single-Document Atomicity): Only one document modified per operation

4. Write Path¶

sequenceDiagram
    participant Client
    participant API
    participant Parser
    participant SchemaValidator
    participant Planner
    participant WAL
    participant Storage
    participant Index

    Client->>API: Write Request (insert/update/delete)
    API->>API: Acquire global execution lock
    API->>Parser: Parse Operation
    Parser->>SchemaValidator: Validate Document Against Schema

    alt Schema Invalid
        SchemaValidator-->>API: Reject (Schema Violation Error)
        API->>API: Release lock
        API-->>Client: Error Response
    end

    SchemaValidator->>Planner: Plan Write Operation
    Planner->>Planner: Verify write is bounded (update/delete)

    alt Unbounded Write
        Planner-->>API: Reject (Unbounded Operation Error)
        API->>API: Release lock
        API-->>Client: Error Response
    end

    Planner->>WAL: Append Log Entry (with checksum)
    WAL->>WAL: fsync to disk
    WAL->>Storage: Apply to document storage
    Storage->>Index: Update B-tree index (derived state)
    Storage-->>API: Acknowledgment
    API->>API: Release lock
    API-->>Client: Success Response

Write Path Steps¶

1. Client Request: Client sends write operation (insert, update, delete)
2. Acquire Lock: API layer acquires global execution lock (§2.11)
3. Parse: API layer parses request into internal representation
4. Schema Validation:
5. Document validated against declared schema version
6. Invalid documents rejected immediately (S2, S4)
7. Plan Bounded Check:
8. For updates/deletes: verify operation targets bounded set (§4.1)
9. Unbounded updates/deletes rejected
10. WAL Append:
11. Document operation written to WAL with checksum
12. This step must complete before acknowledgment (R1)
13. WAL Sync:
14. Explicit fsync to guarantee durability (D1)
15. Durability boundary: write is now recoverable
16. Apply to Storage:
17. Document persisted to storage with checksum
18. Update Index:
19. B-tree indexes updated (derived state, rebuildable from storage)
20. Acknowledgment:
    • Success returned to client only after all steps complete
21. Release Lock: Global execution lock released

Critical Guarantee: No write is acknowledged until WAL is synced to disk. This ensures D1 (No Acknowledged Write Is Ever Lost).

4.1 Bounded Update/Delete Rules¶

Definition: A write operation is bounded if the set of affected documents can be determined with a provable upper bound before execution.

Allowed Predicates for Updates and Deletes:

Enforcement Rules:

1. Primary Key Operations: Always bounded (exactly one document)
2. Indexed Equality: Bounded by index lookup
3. Indexed Range: Bounded only if explicit $limit is provided
4. Non-Indexed Fields: Always rejected (unbounded)
5. Bulk Operations: Allowed only if predicate is bounded and limit is explicit

Rejection Behavior: - Unbounded updates/deletes are rejected at planning stage - Error code: UNBOUNDED_OPERATION - Error message includes specific reason (e.g., "non-indexed field", "missing limit")

Invariants Upheld: - Q1 (Queries Must Be Bounded): All operations have provable bounds - Q3 (Execution Never Guesses): System does not guess how many documents will be affected

5. Read Path¶

sequenceDiagram
    participant Client
    participant API
    participant Parser
    participant Planner
    participant Executor
    participant Index
    participant Storage
    participant Checksum

    Client->>API: Query Request
    API->>API: Acquire global execution lock
    API->>Parser: Parse Query
    Parser->>Planner: Request Execution Plan

    Planner->>Planner: Determine index to use
    Planner->>Planner: Estimate cost (scan, time, memory)

    alt Unbounded Cost
        Planner-->>API: Reject (Unbounded Query Error)
        API->>API: Release lock
        API-->>Client: Error Response
    end

    Planner-->>Executor: Execution Plan
    Executor->>Index: B-tree lookup (if indexed)
    Index->>Storage: Retrieve documents
    Storage->>Checksum: Validate checksums

    alt Checksum Invalid
        Checksum-->>API: Reject (Corruption Detected)
        API->>API: Release lock
        API-->>Client: Error Response
    end

    Checksum-->>Executor: Valid documents
    Executor->>Executor: Apply filter, sort, limit
    Executor-->>API: Result set
    API->>API: Release lock
    API-->>Client: Success Response with data

Read Path Steps¶

1. Client Request: Client sends query (find, filter, sort, limit)
2. Acquire Lock: API layer acquires global execution lock (§2.11)
3. Parse: API layer parses query into AST
4. Plan Generation:
5. Planner selects index based on deterministic rules (T1)
6. Planner estimates cost upper bound
7. Unbounded queries rejected (Q1, Q2)
8. Plan Returned: Human-readable plan available for explain
9. Execution:
10. Executor follows plan exactly (T2)
11. Index lookup for bounded data access
12. Documents retrieved from storage
13. Schema Version Filtering: Documents filtered by schema version (§5.1)
14. Checksum Validation:
15. Every document checksummed on read
16. Corrupted documents cause operation failure (D2, K2)
17. Filter/Sort/Limit:
18. Applied in deterministic order
19. Sort only on indexed fields (as per SCOPE.md)
20. Result Return:
    • Ordered, deterministic result set returned
    • Ordering guaranteed by index or primary key (T2)
21. Release Lock: Global execution lock released

Critical Guarantee: Execution is deterministic—same query on same data always produces same results in same order.

5.1 Schema Version Semantics for Reads¶

Phase 0 Rule: Queries operate on documents of a single, explicitly specified schema version.

Query Syntax Requirement:

find({...predicates...}, {schema_version: "v1"})

Read Semantics:

1. Explicit Version Match: Only documents with schema_version == "v1" are read
2. Incompatible Versions: Documents with other schema versions are transparently skipped
3. No Cross-Version Operations: Cannot query across multiple schema versions in Phase 0

Example:

Error Cases:

Invariants Upheld: - S3 (Schema Versions Are Explicit): Queries must specify version - D3 (Reads Never Observe Invalid State): Only schema-valid data for specified version

6. Determinism Enforcement¶

6.1 Query Planning Determinism¶

Mechanism: Rule-based index selection with explicit versioning.

Invariants: T1, T3

6.2 Query Execution Determinism¶

Mechanism: Explicit result ordering and no runtime variance.

Invariants: T2

6.3 Crash Recovery Determinism¶

Mechanism: Sequential WAL replay with deterministic application.

Invariants: R2, R3

7. Crash Recovery¶

7.1 Recovery Conceptual Flow¶

stateDiagram-v2
    [*] --> DetectUncleanShutdown
    DetectUncleanShutdown --> ScanWAL: No clean shutdown marker
    DetectUncleanShutdown --> NormalStartup: Clean shutdown marker

    ScanWAL --> ValidateEntries: Read WAL from beginning
    ValidateEntries --> ReplayEntries: All checksums valid
    ValidateEntries --> HaltWithError: Any checksum failure

    ReplayEntries --> ApplyToStorage: Apply each entry sequentially
    ApplyToStorage --> RebuildIndexes: All WAL entries applied

    RebuildIndexes --> VerifyConsistency: Indexes rebuilt from storage
    VerifyConsistency --> ReportSuccess: Storage consistent
    VerifyConsistency --> HaltWithError: Consistency failure

    ReportSuccess --> NormalStartup
    HaltWithError --> [*]
    NormalStartup --> [*]

7.2 Recovery Steps¶

1. Detect Unclean Shutdown: Check for clean shutdown marker
2. Scan WAL from Beginning: Phase 0 has no checkpointing; WAL replay starts at entry 0
3. Validate Entries: Verify checksum of each WAL entry
4. Any corrupted entry: halt and report (§7.3)
5. Replay Entries: Apply entries to storage in strict append order
6. Same WAL → same resulting state (R2)
7. Rebuild Indexes: Reconstruct all B-tree indexes from document storage
8. Verify Consistency: Confirm storage matches replayed state
9. Report Status: Explicit success/failure with details (R3)
10. Success: database ready
11. Failure: database does not start, operator intervention required

7.3 WAL Corruption Policy (Phase 0)¶

Policy: Any WAL corruption halts startup. No partial replay.

No Partial Replay: If any WAL entry is corrupted, the database refuses to start.

Rationale: - Partial replay is non-deterministic (depends on corruption location) - Cannot distinguish between "never written" and "corrupted after write" - Predictable failure is safer than unpredictable recovery

Operational Response: - Operator must restore from backup - WAL corruption is treated as catastrophic failure - System logs specific WAL entry number and checksum failure details

Invariants Upheld: - K2 (Corruption Is Never Silently Repaired): Halt, don't repair - R2 (Recovery Is Deterministic): No heuristic partial replay - R3 (Recovery Completeness Is Verifiable): Explicit halt with reason

7.4 Checkpointing Strategy (Phase 0)¶

Phase 0 Rule: Checkpointing does NOT exist.

Implications:

• Every recovery replays the entire WAL from the beginning
• WAL grows unbounded during a single session
• Clean shutdown writes shutdown marker but does not truncate WAL
• Restart after clean shutdown still replays full WAL

Deferred Work (post-Phase 0): - Periodic checkpointing - WAL truncation after checkpoint - Incremental recovery from last checkpoint

Invariants Upheld: - R2 (Recovery Is Deterministic): Full replay eliminates ambiguity

7.5 Recovery Guarantees¶

Invariants Upheld: D1, R1, R2, R3, K1, K2

8. Configuration Constraints¶

8.1 Configuration Surface (Phase 0)¶

Principle: Minimal configuration surface with safe-only defaults.

8.2 Forbidden Configurations¶

The following configurations are rejected at startup:

8.3 Configuration Validation¶

Startup Behavior:

1. Parse configuration file
2. Validate all parameters against allowed values
3. Reject any unsafe configuration with explicit error
4. Log all configuration values at startup

Error Example:

FATAL: Invalid configuration
  Parameter: wal_sync_mode
  Value: "none"
  Reason: WAL fsync cannot be disabled (violates durability guarantee D1)
  Allowed values: ["fsync"]

Invariants Upheld: - O2 (Config Cannot Violate Safety): Unsafe configurations rejected

9. Invariant-to-Component Mapping¶

10. Trade-offs and Non-Goals¶

10.1 Deliberate Trade-offs¶

10.2 What Is Deliberately NOT Optimized¶

Per SCOPE.md and VISION.md, the following are explicitly not goals for Phase 0:

10.3 Explicit Non-Features (Phase 0)¶

• Joins
• Aggregations
• Multi-document transactions
• Replication
• Sharding
• Auto-indexing
• Full-text search
• Adaptive query rewriting
• Checkpointing
• WAL truncation
• Multi-version schema reads

11. Summary¶

This architecture defines a strict, deterministic, single-node document database with:

• Mandatory schemas enforced at write time with explicit version references
• WAL-backed durability with explicit fsync before acknowledgment
• Deterministic query planning using rule-based index selection (no heuristics)
• Deterministic execution via single global execution lock (no concurrency)
• Deterministic crash recovery via full WAL replay from beginning (no checkpointing in Phase 0)
• Fail-loud semantics for all error conditions
• Checksum-based corruption detection with halt-on-corruption policy (no silent repair)
• Single-document atomicity with indexes as derived, recoverable state
• Bounded operations with formal rules for update/delete predicates
• Single schema version per query (no cross-version reads in Phase 0)
• Minimal, safe-only configuration with explicit rejection of unsafe settings

Every component is designed to uphold one or more invariants from INVARIANTS.md. Trade-offs are explicit and align with VISION.md priorities: correctness over performance, predictability over cleverness, explicitness over magic.