Building a Transactional, LSM-Backed Storage Engine from First Principles

Foundations & B+Tree Architecture

• Concept Introduction to storage engines and system goals
• Concept Introduction to block storage devices and random/sequential IO
• Concept Understanding file organization and standard kernel IO caches
• Concept Understanding logical in-memory structures vs physical block layouts
• Concept Understanding Binary Search Trees (BST) and memory heights
• Concept Analyzing BST limits for disk-based persistence
• Concept Introduction to B+Tree node layouts and design trade-offs
• Concept Demystifying how database indexes work
• Code Study Production Code Study: Deconstructing boltdb/bolt to see how a production-grade B+Tree engine structures its physical on-disk pages.

LSM Introduction (Hands-on)

Get hands-on by building the core write path of an LSM engine. We will code a thread-safe Memtable and implement an append-only Write-Ahead Log (WAL) to guarantee crash durability.

• Concept Introduction to LSM-Tree architecture and component interactions
• Build Implementing a multi-versioned Memtable and its iterator
• Build Implementing an append-only Write-Ahead Log (WAL)
• Build Implementing crash-resilient state recovery from WAL
• Concept Understanding WAL rotation and implementation patterns
• Code Study Production Code Study: Auditing CockroachDB's pebble or Dgraph's badger repository to see how a production-grade engine structures its concurrent Memtable and commit pipeline.

SSTables & Bloom Filters (Hands-on)

Move data from memory to disk by designing SSTables and optimize reads using Bloom Filters. This session focuses on minimizing read amplification and disk seeks.

• Concept Understanding block-aligned immutable SSTable structure
• Build Implementing key-value data encoding and endianness
• Build Implementing block-level binary search
• Build Implementing block-aligned SSTables and block iterators
• Concept Understanding Bloom Filter theory
• Build Implementing a basic, naive Bloom Filter
• Build Implementing a production-grade in-RAM Bloom Filter
• Build Integrating Bloom Filters into the SSTable read path
• Code Study Production Code Study: Deconstructing Dgraph's badger engine code to look at real-world block-aligned table builders and RAM-to-disk serialization.

Transactions & Compaction (Hands-on)

Implement transactions with Serializable Snapshot Isolation (SSI) and build a Leveled Compaction engine to keep the storage engine optimized. This session completes the transactional LSM engine.

• Concept Understanding ACID guarantees in storage design
• Build Implementing durability and recovery at the transaction layer
• Concept Understanding SQL isolation levels and write anomalies
• Concept Understanding Serializable Snapshot Isolation (SSI) theory
• Build Implementing a singular update queue for safe concurrency
• Build Implementing Serializable Snapshot Isolation
• Build Implementing transactional iterators with multi-version reads
• Concept Introduction to Compaction and delete tombstone management
• Concept Understanding Leveled and Size-Tiered compaction models
• Build Implementing an automated Leveled Compaction executor
• Code Study Production Code Study: Analyzing transaction conflict detection and background compaction in Dgraph's badger.