Project 2: Log-Structured Key-Value Store (Mini LSM-Tree)

Build a persistent key-value store using append-only log segments and background compaction.

Quick Reference

Attribute Value
Difficulty Expert
Time Estimate 2-3 weeks
Language C
Prerequisites File I/O, hash tables, C memory management
Key Topics append-only logs, SSTables, compaction

1. Learning Objectives

By completing this project, you will:

  1. Implement append-only log segments with durable writes.
  2. Build an in-memory index mapping keys to file offsets.
  3. Generate sorted segment files (SSTable-style).
  4. Compact multiple segments into a single sorted run.

2. Theoretical Foundation

2.1 Core Concepts

  • Log-structured storage: Sequential writes outperform random updates on disk.
  • Indexing: A hash map in memory provides fast lookup to log offsets.
  • Compaction: Merges multiple segments into a single sorted structure.

2.2 Why This Matters

This is how real storage engines like LevelDB and RocksDB achieve fast writes and acceptable reads.

2.3 Historical Context / Background

LSM-trees were designed to leverage sequential I/O and minimize random disk access.

2.4 Common Misconceptions

  • “Append-only is inefficient”: It avoids random writes and improves throughput.
  • “Compaction is optional”: Without it, reads degrade as segments pile up.

3. Project Specification

3.1 What You Will Build

A persistent key-value store that writes to log segments, keeps a memory index, and compacts segments to maintain read performance.

3.2 Functional Requirements

  1. Support PUT key value and GET key.
  2. Append records to a log file with length-prefix or checksum.
  3. Build an in-memory index on startup by scanning the log.
  4. Perform compaction to produce a sorted segment.

3.3 Non-Functional Requirements

  • Durability: Use fsync or explicit flush on write.
  • Performance: Keep writes sequential.
  • Reliability: Recover on restart by log replay.

3.4 Example Usage / Output

$ ./mini_lsm put user:1 Alice
OK
$ ./mini_lsm get user:1
Alice

3.5 Real World Outcome

You will insert records, restart the process, and still retrieve them from disk:

$ ./mini_lsm put user:1 Alice
OK
$ ./mini_lsm get user:1
Alice

4. Solution Architecture

4.1 High-Level Design

PUT -> append log -> update mem index
GET -> index lookup -> read offset
Compaction -> merge segments -> replace with SSTable

4.2 Key Components

Component Responsibility Key Decisions
Log writer Append records Use length + checksum
Index Map key -> (segment, offset) Hash table
Segment manager Rotate logs Size-based rotation
Compactor Merge sorted runs Background or manual

4.3 Data Structures

typedef struct {
    uint32_t key_len;
    uint32_t value_len;
    // key bytes, value bytes follow
} record_hdr_t;

4.4 Algorithm Overview

Key Algorithm: Compaction Merge

  1. Read sorted entries from segments.
  2. Merge by key, keeping newest value.
  3. Write a new compacted segment.

Complexity Analysis:

  • Time: O(n) for merge
  • Space: O(1) streaming merge

5. Implementation Guide

5.1 Development Environment Setup

gcc --version

5.2 Project Structure

project-root/
├── src/
│   ├── log.c
│   ├── index.c
│   ├── compact.c
│   └── main.c
└── README.md

5.3 The Core Question You’re Answering

“Why do storage engines favor append-only logs with compaction instead of in-place updates?”

5.4 Concepts You Must Understand First

Stop and research these before coding:

  1. Sequential vs random I/O
  2. Write-ahead logging concepts
  3. Merge algorithms for sorted runs

5.5 Questions to Guide Your Design

Before implementing, think through these:

  1. How will you detect partial writes on crash?
  2. How do you resolve duplicate keys across segments?
  3. When do you trigger compaction?

5.6 Thinking Exercise

Simulate log replay

Write a tiny log file and re-scan it to rebuild the index. Verify the newest value wins.

5.7 The Interview Questions They’ll Ask

Prepare to answer these:

  1. “Why do LSM trees prefer sequential writes?”
  2. “How does compaction work?”
  3. “What are the read tradeoffs of LSM vs B-tree?”

5.8 Hints in Layers

Hint 1: Use fixed headers Store lengths so you can skip records quickly.

Hint 2: Store offsets Index value should include segment id and offset.

Hint 3: Start with manual compaction Provide a command to run it before automating.

5.9 Books That Will Help

Topic Book Chapter
LSM design “Designing Data-Intensive Applications” Ch. 3
Merge algorithms “Algorithms” Ch. 2.2
Sequential I/O “CS:APP” Ch. 6

5.10 Implementation Phases

Phase 1: Foundation (4-5 days)

Goals:

  • Append-only log with replay.

Tasks:

  1. Write and read records.
  2. Rebuild index on startup.

Checkpoint: Data survives restart.

Phase 2: Core Functionality (1 week)

Goals:

  • Multiple segments and rotation.

Tasks:

  1. Rotate log after size threshold.
  2. Track segment ids.

Checkpoint: GET finds values across segments.

Phase 3: Polish & Edge Cases (4-5 days)

Goals:

  • Compaction and cleanup.

Tasks:

  1. Merge segments into SSTable.
  2. Delete old segments after success.

Checkpoint: Reads still work after compaction.

5.11 Key Implementation Decisions

Decision Options Recommendation Rationale
Index type hash vs tree hash Fast lookup
Compaction manual vs background manual first Easier to verify

6. Testing Strategy

6.1 Test Categories

Category Purpose Examples
Persistence Restart test PUT/GET after restart
Compaction Merge correctness Duplicate keys
Recovery Partial write Truncated log

6.2 Critical Test Cases

  1. Latest value wins after multiple PUTs.
  2. Compaction removes stale entries.
  3. Crash during write does not corrupt earlier data.

6.3 Test Data

Keys: a, b, c with updates

7. Common Pitfalls & Debugging

7.1 Frequent Mistakes

Pitfall Symptom Solution
No length prefix Corrupt parsing Store sizes in header
No fsync Data loss Flush on commit
Compaction bug Missing keys Keep newest by segment id

7.2 Debugging Strategies

  • Add a log dump tool to print records.
  • Validate index entries by reading offsets.

7.3 Performance Traps

Replaying the full log on every start can be slow; add checkpoints later.

8. Extensions & Challenges

8.1 Beginner Extensions

  • Add DELETE tombstones.
  • Add a stats command.

8.2 Intermediate Extensions

  • Implement a simple bloom filter.
  • Background compaction thread.

8.3 Advanced Extensions

  • Add WAL checksum validation.
  • Build a multi-level LSM tree.

9. Real-World Connections

9.1 Industry Applications

  • Storage engines in databases and log platforms.
  • LevelDB: https://github.com/google/leveldb
  • RocksDB: https://rocksdb.org

9.3 Interview Relevance

  • LSM tree and compaction knowledge is highly valued.

10. Resources

10.1 Essential Reading

  • Designing Data-Intensive Applications - storage engines chapter
  • LSM-tree papers (search “LSM tree”)

10.2 Video Resources

  • LSM tree talks (search “LSM tree compaction”)

10.3 Tools & Documentation

  • fsync(2) - man 2 fsync

11. Self-Assessment Checklist

11.1 Understanding

  • I can explain log-structured storage.
  • I can describe compaction.
  • I can explain LSM read/write tradeoffs.

11.2 Implementation

  • Data persists across restarts.
  • Compaction works correctly.
  • Index lookup is correct.

11.3 Growth

  • I can explain how to improve read performance.
  • I can extend with bloom filters.

12. Submission / Completion Criteria

Minimum Viable Completion:

  • Append-only log with replayable index.

Full Completion:

  • Multi-segment support and compaction.

Excellence (Going Above & Beyond):

  • Multi-level compaction and bloom filters.

This guide was generated from SPRINT_4_5_REAL_WORLD_PROJECTS.md. For the complete learning path, see the parent directory.