FlashDB

FlashDB is a high-performance, embedded Log-Structured Merge (LSM) tree key-value store written from scratch in modern C++20. It was built not just to use a database, but to deeply understand the low-level mechanics of storage engines—how data is persisted safely, how memory buffers transition to immutable on-disk structures, and how read amplification is controlled. The design philosophy strictly prioritizes educational clarity and algorithmic correctness over premature micro-optimizations, ensuring every layer (WAL, MemTable, SSTable, Bloom Filter) is explicitly decoupled and understandable.

Architecture

sequenceDiagram
    autonumber
    actor Client
    participant API as KVStore API
    participant WAL as Write-Ahead Log (Disk)
    participant MemTable as MemTable (RAM)
    participant SSTBuilder as SSTableBuilder
    participant Disk as SSTable (Disk)

    Client->>API: put("user_123", "data")
    
    %% Phase 1: In-Memory Write
    rect rgba(0, 150, 255, 0.1)
        Note right of API: Phase 1: Fast In-Memory Write
        API->>WAL: Append: [0x00][user_123][data]
        WAL-->>API: (fsync complete)
        API->>MemTable: Insert: user_123 -> data
        API-->>Client: Success (Returns instantly)
    end

    %% Phase 2: Asynchronous Flush
    opt MemTable Threshold Reached (>10,000 items)
        rect rgba(255, 150, 0, 0.1)
            Note right of API: Phase 2: Flush to Disk
            API->>SSTBuilder: Create new Builder
            
            loop For each sorted key in MemTable
                SSTBuilder->>SSTBuilder: Hash key into Bloom Filter
                SSTBuilder->>Disk: Write [flag][key][value] block
            end
            
            SSTBuilder->>Disk: Serialize & Write Bloom Filter
            SSTBuilder->>Disk: Serialize & Write Sparse Index
            SSTBuilder->>Disk: Write Footer (Offsets & Magic Byte)
            
            API->>MemTable: Clear MemTable
            API->>WAL: Delete old WAL & create new one
        end
    end

Loading

Benchmarks & Performance

FlashDB includes two separate benchmarking suites to empirically prove its performance characteristics:

1. Local Macro-Benchmark: An end-to-end Python-driven time-series benchmark that simulates a massive, continuous database workload over time and plots visual graphs.
2. Google Micro-Benchmark: A C++ micro-benchmarking tool (google_bench_kvstore.exe) that isolates and tests single operations in a tight loop to measure nanosecond-level performance.

1. Compaction & Read Amplification (Macro-Benchmark)

As SSTables accumulate, read latency degrades (Read Amplification). When compaction is triggered (red star), multiple SSTables are merged into one, instantly restoring optimal read speeds.

2. Write Throughput (Macro-Benchmark)

Because all writes in an LSM tree hit the in-memory MemTable and append-only WAL, random writes are just as fast as sequential writes.

(Note: Random writes sometimes benchmark slightly higher than sequential writes here. In a traditional B-Tree, random writes are exponentially slower due to random disk seeks. In our LSM tree, all writes are transformed into sequential WAL appends, completely eliminating disk seeks. The slight edge for random writes is a statistical artifact of std::map (Red-Black tree) requiring slightly fewer rebalancing rotations for random insertions compared to perfectly sequential insertions).

3. Read Performance: The Bloom Filter Effect (Macro-Benchmark)

A Bloom Filter drastically reduces disk I/O when querying non-existent keys. Without it, the engine scans the disk index of every SSTable. With it enabled, read performance for non-existent keys jumps by 85x-90x.

4. Google Benchmark Results (Micro-Benchmark)

We use the industry-standard google/benchmark suite to measure the pure C++ performance of individual operations.

Benchmark	Time per operation	CPU time	Iterations
BM_WriteSequential	25.8 us	21.9 us	40,727
BM_WriteRandom	23.3 us	19.1 us	49,778
BM_ReadThroughput	385 us	338 us	2,358
BM_ReadWithoutBloomFilter	575 us	558 us	1,120
BM_ReadWithBloomFilter	8.45 us	8.49 us	86,510

Notice the enormous ~68x speedup on reads for non-existent keys when the Bloom Filter is enabled (8.45 us vs 575 us).

Key Design Decisions

(See DESIGN.md for detailed explanations)

• Size-Tiered Compaction (vs Leveled): Prioritizes write-amplification over read-amplification, making it easier to reason about file merges in a simpler architecture.
• Concurrency via std::shared_mutex: Uses coarse-grained reader-writer locks to ensure absolute safety while allowing concurrent reads.
• Strict Sync Policy: The WAL fsyncs every write before returning to the client to guarantee 100% durability at the cost of extreme throughput.
• std::map over std::unordered_map: A Red-Black tree keeps keys perfectly sorted in memory, which allows us to stream them sequentially to disk during a flush.

Deliberately Out of Scope

To ensure the project remained focused, robust, and mature within its boundaries, the following were explicitly scoped out:

• Network Layer / HTTP API: This is strictly an embedded storage engine (like RocksDB or SQLite). Building a client-server architecture would distract from the core disk storage mechanics.
• Leveled Compaction: Implementing full leveled compaction (L0 -> L1 -> L2) introduces immense complexity in overlapping file ranges and background scheduling. Size-tiered is sufficient to demonstrate the concept.
• Lock-Free Concurrency: While lock-free skip lists are theoretically faster for MemTables, they introduce notoriously subtle memory ordering bugs. A reader-writer lock provides 80% of the performance with 100% of the provable safety.

Build & Run Instructions

# Clone the repository
git clone https://github.com/yourusername/key-value-store.git
cd key-value-store

# Create build directory
mkdir build && cd build

# Configure and compile
cmake ..
cmake --build .

# Run Unit Tests
ctest --output-on-failure

# Run the automated Macro-Benchmarking Suite (outputs to benchmarks/results/)
cd ..
.\run_benchmarks.bat

# Run the Google Micro-Benchmarks
.\build\benchmarks\google_bench_kvstore.exe