🚀 High-Performance LSM-Tree Key-Value Storage Engine

A production-grade, RocksDB-inspired Log-Structured Merge-tree (LSM-tree) storage engine built entirely from scratch in C++20. This project implements a high-throughput write path, concurrent memory structures, durable crash-recovery mechanics, and optimized multi-tier read and compaction pipelines.

---

🛠️ Architecture & Core Components

1. Concurrent Skip-List MemTable

   • Lock-based thread-safe structure supporting high-concurrency multi-threaded writes.
   • Probabilistic multi-level indexing for $O(\log N)$ in-memory lookups.

2. Durability & Crash Recovery (WAL)

   • Every write is sequentially appended to a Write-Ahead Log (.log) with thread synchronization.
   • Automatic re-play on startup to fully reconstruct active memory state after unexpected crashes.

3. Asynchronous Background Flushes

   • Monitors active MemTable size thresholds (byte_size_limit_).
   • Seamlessly rolls over active MemTables into an immutable queue and signals background worker threads via condition variables (std::condition_variable) without blocking incoming client writes.

4. Optimized SSTables & Sparse Indexing

   • Flushes immutable MemTables into immutable Sorted String Tables (.sst) on disk.
   • Utilizes sparse indexes paired with binary search (std::upper_bound) to locate data chunks on disk with minimal overhead.

5. Probabilistic Bloom Filters

   • Embedded into every SSTable to execute $O(1)$ membership checks.
   • Instantly short-circuits lookups for non-existent keys, completely avoiding costly disk I/O.

6. Automated Background Compaction & MANIFEST Recovery

   • Merges multiple small SSTables into a single compacted file, purging stale key versions and reclaiming disk space.
   • Tracks active SSTable generations using a stateful .manifest file for robust multi-session recovery.

---

💻 Getting Started

Prerequisites

• A C++20 compatible compiler (g++, clang++, or MSVC).
• Standard pthread support.

Compilation & Execution

Compile the project with optimizations enabled (-O3) and thread support:

g++ -std=c++20 -O3 -pthread concurrent_skiplist.cpp -o lsm_engine
./lsm_engine


📖 Example Usage

#include "concurrent_skiplist.cpp" // or your header structure

int main() {
    // Initialize storage engine with a 100-byte MemTable flush threshold
    LSMStorageEngine<int, std::string> db("my_database", 100);

    // Insert key-value pairs
    db.Insert(1, "hello_lsm");
    db.Insert(2, "rocksdb_inspired");

    // Retrieve data
    std::string val;
    if (db.Get(1, val)) {
        std::cout << "Found: " << val << "\n";
    }

    // Non-existent keys are instantly short-circuited via Bloom filters
    bool exists = db.Get(9999, val); 
    
    return 0;
}

📊 Performance & Design Highlights
Lock-Free Read Paths: Concurrent reader-writer safety allows reads to lock-free scan active memory structures concurrently.
Zero-Loss Guarantee: Synchronous WAL writes before memory mutation ensure ACID durability properties.