LSMDB - Log-Structured Merge-Tree Database

A high-performance, persistent key-value database implemented in Go using the Log-Structured Merge-tree (LSM-tree) data structure. This database provides efficient writes through in-memory tables and background compaction for optimal read performance.

Features

• LSM-Tree Architecture: Optimized for write-heavy workloads with efficient background compaction
• Write-Ahead Logging (WAL): Ensures durability and crash recovery
• Multi-Level Compaction: Automatic background compaction across multiple levels
• Concurrent Access: Thread-safe operations with read-write locks
• Configurable Parameters: Tunable memory table size, compaction intervals, and level configurations
• CLI Interface: Interactive command-line interface for database operations

Architecture

Core Components

1. MemTable: In-memory hash table for recent writes
2. SSTable: Sorted String Tables stored on disk for persistent data
3. WAL: Write-Ahead Log for crash recovery and durability
4. Compaction: Background process to merge and optimize SSTables across levels

Data Flow

Write → WAL → MemTable → (when full) → SSTable Level 0 → Background Compaction → Higher Levels

Installation

Prerequisites

• Go 1.24.4 or higher

Setup

git clone <repository-url>
cd lsmdb
go mod tidy

Configuration Parameters

Parameter	Description	Default
mem_table_size	Size threshold for MemTable flush	512 bytes
data_dir	Data storage directory	"./data"
max_level	Maximum compaction levels	3
level_size	SSTables per level before compaction	2
compact_interval	Compaction frequency (seconds)	5

Usage

CLI Interface

Start the interactive CLI:

make dev
# or
go run cmd/cli/main.go

Available commands:

set <key> <value>  # Store a key-value pair
get <key>          # Retrieve value for a key
del <key>          # Delete a key
exit               # Exit the CLI

Example Session

$ make dev
LSM Database CLI
  set <key> <value> - Set a key-value pair
  get <key>         - Get value for a key
  del <key>         - Delete a key
  exit              - Exit the CLI

> set user1 john_doe
OK
> set user2 jane_smith
OK
> get user1
john_doe
> del user1
OK
> get user1
nil
> exit

Project Structure

lsmdb/
├── cmd/cli/main.go      # CLI application
├── memtable/            # In-memory table implementation
├── sstable/             # Persistent table implementation
├── wal/                 # Write-ahead log implementation
├── db.go                # Main database logic
├── config.yaml          # Configuration file
└── Makefile            # Build automation

Building

# Run development version
make dev

# Build binary
go build -o lsmdb cmd/cli/main.go

Future Enhancements

• Bloom filters for improved read performance
• Range queries and iteration support
• Compression for SSTable storage
• Metrics and monitoring
• Distributed/replicated configurations
• Snapshot and backup functionality

---