LSM-Tree Storage Engine (lsmdb)

A high-performance, embedded NoSQL key-value storage engine implemented in Go.

This project is built from scratch using the Log-Structured Merge-Tree (LSM-Tree) architecture. It is designed for applications that require massive write throughput, efficient range scans, and strict durability. It features an append-only Write-Ahead Log (WAL), an in-memory SkipList-based MemTable, and on-disk SSTables with sparse indexing and Bloom Filters.

✨ Key Features

• High-Throughput Writes: All write operations (Put, Delete) are performed in-memory (MemTable) and sequentially appended to the WAL, avoiding random disk I/O.
• Strong Durability: Includes a Write-Ahead Log (WAL) with CRC32 checksums to ensure data integrity and automatic recovery in case of an unexpected crash.
• Fast & Efficient Reads: Utilizes Bloom Filters to prevent unnecessary disk reads for non-existent keys, and sparse indexes for O(1) block lookups in SSTables.
• Background Compaction: Automatically flushes memory to disk and merges (compacts) SSTables in background goroutines, keeping read performance high and reclaiming disk space from Tombstones.
• Seamless Range Scans: Provides a MergeIterator that unifies data from the active MemTable, immutable MemTables, and multiple SSTables, enabling efficient Scan(start, end) operations.
• Zero External DB Dependencies: A pure Go embedded library (using only huandu/skiplist for memory indexing).

🏗️ Architecture Design

graph TD
    Client((Client App))
    
    subgraph "RAM (In-Memory)"
        ActiveMem[Active MemTable <br/> <i>SkipList</i>]
        ImmutableMem[Immutable MemTable <br/> <i>Read-Only</i>]
    end
    
    subgraph "Disk Storage"
        WAL[(Write-Ahead Log <br/> <i>Append-Only + CRC32</i>)]
        SST1[(SSTable)]
        SST2[(SSTable)]
        SST_Compacted[(Compacted SSTable)]
    end
    
    %% Write Path
    Client -- "Put(key, val)" --> WAL
    Client -- "Put(key, val)" --> ActiveMem
    
    %% Flush Mechanism
    ActiveMem -. "Capacity Reached" .-> ImmutableMem
    ImmutableMem -- "Background Flush" --> SST1
    
    %% Compaction
    SST1 -. "Background Compaction" .-> SST_Compacted
    SST2 -. "Background Compaction" .-> SST_Compacted
    
    %% Read Path
    Client -. "Get(key)" .-> ActiveMem
    ActiveMem -. "Miss" .-> ImmutableMem
    ImmutableMem -. "Miss" .-> BloomFilter{Bloom Filter}
    BloomFilter -. "Maybe Present" .-> Index[Sparse Index]
    Index -. "Offset" .-> SST_Compacted
    BloomFilter -. "Not Present" .-> ReturnNil((Return Nil))

Loading

1. Write Request: The client calls Put(key, value). The engine writes the entry to the WAL for durability and inserts it into the Active MemTable.
2. Flush to Disk: Once the MemTable reaches its size limit, it becomes immutable. A new MemTable is created, the WAL is rotated, and a background flusher writes the immutable data to disk as an SSTable.
3. Read Request: The Get operation queries the Active MemTable, then the Immutable MemTable, and finally searches the SSTables (optimized by Bloom Filters and Indexes).
4. Compaction: Background routines merge smaller SSTables into larger ones, discarding deleted keys (tombstones) and older overwritten values.

🚀 Getting Started

Prerequisites

• Go 1.20 or higher

Installation

Import the package into your Go project:

go get github.com/yourusername/lsm-tree-storage

Basic Usage

package main

import (
	"fmt"
	"log"
	"lsmdb"
)

func main() {
	// 1. Configure Options
	opts := lsmdb.DefaultOptions()
	opts.Dir = "./data_dir"

	// 2. Open the Database
	db, err := lsmdb.Open(opts)
	if err != nil {
		log.Fatalf("Failed to open db: %v", err)
	}
	defer db.Close()

	// 3. Write Data
	db.Put([]byte("user:1"), []byte("Alice"))
	db.Put([]byte("user:2"),[]byte("Bob"))

	// 4. Read Data
	val, err := db.Get([]byte("user:1"))
	if err == nil && val != nil {
		fmt.Printf("Found: %s\n", string(val)) // Output: Found: Alice
	}

	// 5. Range Scan
	it, _ := db.Scan([]byte("user:1"),[]byte("user:3"))
	defer it.Close()
	
	for it.Next() {
		fmt.Printf("Key: %s, Value: %s\n", string(it.Key()), string(it.Value()))
	}
}

🛠️ Running the Test Suite / CLI

The repository includes a professional test suite that demonstrates the database's capabilities under load, triggering background flushes and compactions.

# Navigate to the CLI directory
cd cmd/lsm-cli

# Run the test suite
go run main.go

Expected Output:

=== LSM-Tree DB Professional Test Suite ===
Database opened in directory: db_test_storage
Writing 50,000 keys (triggering background flush to disk)...
   ... wrote 10000 keys
   ... wrote 20000 keys
   ... wrote 30000 keys
   ... wrote 40000 keys
Write completed in 450ms
Waiting 2 seconds for background flush to complete...
Verifying reading of specific keys:
   Found: key_00000 = value_data_payload_00000_timestamp_1679123456
   Found: key_25000 = value_data_payload_25000_timestamp_1679123456
   ...
Range scan test from 100 to 105:
   ->[key_00100]: value_data_payload_00100...
   ->[key_00101]: value_data_payload_00101...

File system state (currently on disk):
   sst_1679123458.sst (819200 bytes)
   sst_1679123459.sst (819200 bytes)
   wal.log (1024 bytes)

Test completed successfully!

⚙️ Configuration Options

You can tune the database behavior using lsmdb.Options.

Option	Default	Description
Dir	"data"	The directory where WAL and SSTables are stored.
MemTableSize	4MB	Max size of MemTable before it flushes to disk.
CompactionThreshold	4	Number of SSTables required to trigger compaction.
BloomFilter	true	Enable/Disable Bloom Filter generation for SSTables.
BlockSize	4KB	Logical block size for SSTable index entries.

🧪 Storage Format Details

• SSTable Format: Data blocks followed by a Sparse Index (mapping keys to disk offsets), a serialized Bloom Filter, and a 16-byte fixed footer (IndexOffset + BloomOffset).
• WAL Record: [KeyLen (4B)] [ValLen (4B)] [Key] [Value] [CRC32 (4B)]
• Deletions (Tombstones): Handled via db.Put(key, nil). The compaction process physically removes these records from disk.

📜 License

This project is licensed under the MIT License - see the LICENSE file for details.