LSM

A high-performance key-value storage engine based on the LSM-Tree architecture, written in Go.

LSM-Tree uses a log-structured merge-tree storage model:

• Write: Append-only writes to MemTable with WAL for durability
• Read: Search MemTable → Immutable MemTables → SSTables (L0 to Ln)
• Compaction: Background leveled compaction merges and reclaims space

Features

Core

• High-performance read/write with MemTable (SkipList-based)
• SSTable with block-based storage format
• Sparse index for efficient key lookup
• Bloom filter to reduce disk IO
• Write-Ahead Log (WAL) for crash recovery
• Leveled compaction strategy

Storage

• Configurable MemTable size threshold
• Multi-level SSTable organization (L0-L6)
• Automatic compaction when L0 file limit exceeded
• Tombstone-based deletion with cleanup at max level

Reliability

• CRC32 checksum for data integrity
• Manifest file for metadata persistence
• Atomic flush and compaction operations
• Graceful shutdown with data flush

Quick Start

opts := lsm.DefaultOptions("./data")
opts.MemTableSize = 4 * 1024 * 1024     // 4MB MemTable
opts.Level0FileLimit = 4                 // trigger compaction at 4 L0 files

db, err := lsm.Open(opts)
if err != nil {
    log.Fatal(err)
}
defer db.Close()

// Basic operations
db.Put([]byte("name"), []byte("lsm-tree"))
val, err := db.Get([]byte("name"))
db.Delete([]byte("name"))

// Iterator
iter := db.NewIterator()
for iter.Rewind(); iter.Valid(); iter.Next() {
    fmt.Printf("%s = %s\n", iter.Key(), iter.Value())
}
iter.Close()

// Manual compaction
db.Compact()

Architecture

┌─────────────────────────────────────────────────────┐
│                      Client                         │
└─────────────────────┬───────────────────────────────┘
                      │
┌─────────────────────▼───────────────────────────────┐
│                    DB API                           │
│              Put / Get / Delete                     │
└─────────────────────┬───────────────────────────────┘
                      │
┌─────────────────────▼───────────────────────────────┐
│                   MemTable                          │
│              (SkipList-based)                       │
│  ┌─────────────────────────────────────────────┐   │
│  │              Active MemTable                 │   │
│  └─────────────────────────────────────────────┘   │
│  ┌─────────────────────────────────────────────┐   │
│  │          Immutable MemTables                 │   │
│  └─────────────────────────────────────────────┘   │
└─────────────────────┬───────────────────────────────┘
                      │ Flush
┌─────────────────────▼───────────────────────────────┐
│                   SSTable                           │
│  ┌─────────────────────────────────────────────┐   │
│  │  Level 0: Unsorted, may overlap              │   │
│  └─────────────────────────────────────────────┘   │
│  ┌─────────────────────────────────────────────┐   │
│  │  Level 1-6: Sorted, non-overlapping          │   │
│  └─────────────────────────────────────────────┘   │
└─────────────────────────────────────────────────────┘

SSTable Format

┌──────────────────────────────────────┐
│           Data Blocks                │
│  ┌────────────────────────────────┐  │
│  │ Block 1: [entries...]          │  │
│  │ Block 2: [entries...]          │  │
│  │ ...                            │  │
│  └────────────────────────────────┘  │
├──────────────────────────────────────┤
│           Bloom Filter               │
├──────────────────────────────────────┤
│           Sparse Index               │
├──────────────────────────────────────┤
│           Metadata                   │
├──────────────────────────────────────┤
│           Footer (48 bytes)          │
│  - Magic Number                      │
│  - Meta/Index/Bloom Offsets          │
└──────────────────────────────────────┘

Command Line Tool

# Build
go build -o lsm-cli ./cmd/lsm

# Usage
./lsm-cli -dir ./data

# Commands
> put key value
> get key
> delete key
> scan
> compact
> stats
> exit

Benchmarks

Run benchmarks:

go test -bench=. -benchmem ./...

Dependencies

• github.com/huandu/skiplist - SkipList implementation
• github.com/bits-and-blooms/bloom - Bloom filter

License

MIT