Amethyst LSM-Tree (Tiered Implementation)

A purely tiered implementation of an LSM-Tree storage engine in Go. This serves as a control for benchmarking against adaptive compaction strategies.

Features

• Write-Ahead Log (WAL): Durability guarantees
• Memtable: In-memory sorted buffer
• SSTable: Sorted String Table persistence
• Sparse Index: Efficient key lookup
• Tiered Compaction: Pure tiered strategy for all compactions
• Benchmark Controllers: Static tiered strategies for comparison

Architecture

Write Path: Put() → WAL → Memtable → Flush → SSTable (TIERED)
Read Path:  Get() → Memtable → SSTable (with sparse index)
Compaction: Background merge (TIERED → TIERED)

Usage

Run the main demo:

cd amethyst
go run ./cmd/amethystd

Compare compaction strategies:

cd amethyst
go run test_strategies.go

Run tests:

cd amethyst
go test ./...

Project Structure

amethyst/
├── cmd/amethystd/          # Main executable
├── internal/
│   ├── benchmarks/         # Static strategy controllers
│   ├── compaction/         # Compaction logic (director + executor)
│   ├── engine/            # Core LSM engine
│   ├── memtable/          # In-memory buffer
│   ├── metadata/          # Segment tracking
│   ├── sstable/           # SSTable reader/writer
│   ├── sparseindex/       # Efficient key indexing
│   ├── segmentfile/       # Disk I/O management
│   └── wal/               # Write-ahead log
└── test_strategies.go     # Strategy comparison tool

Compaction Strategies

Base LSM (Built-in Tiered):

• Triggers on write count > 50
• Always compacts to TIERED strategy

Static Tiered (Original) (benchmark):

• Triggers on write count > 50
• Stays TIERED after compaction

Static Tiered (Base LSM) (benchmark):

• Triggers on write count > 50
• Compacts to TIERED strategy (same as base LSM)

Extending for Benchmarking

To add new compaction strategies, implement the Controller interface:

type Controller interface {
    ShouldRewrite(meta *common.SegmentMeta) (bool, common.CompactionType, string)
}

Then use it with:

director := compaction.NewDirector(meta, yourController)