Build an LSM-Tree Storage Engine
Build a crash-safe key-value storage engine using LSM-tree architecture in Java.
Introduction
30 Second Summary
Every time you save data to an app, something has to guarantee that data survives even if the process crashes mid-write. The technology responsible for this is a storage engine.
In this project, you will build a persistent key-value storage engine from scratch in Java using the LSM-tree architecture. You will write data, simulate a crash, restart the engine, and watch your data come back to life through Write-Ahead Log recovery.
What You'll Build
A persistent key-value storage engine that uses the same LSM-tree architecture powering Cassandra, CockroachDB, and RocksDB.
By the end of this project, you'll have:
- A Write-Ahead Log with fsync durability that guarantees data survives process crashes.
- A MemTable and SSTable implementation that forms the core LSM-tree data flow from sorted memory to immutable files on disk.
- A StorageEngine class that ties the full LSM-tree read and write paths together with put, get, delete, and a crash recovery demo.
- Secret Mission: Add Bloom filters to your SSTables so the read path can skip files that definitely do not contain a key.
Are there any prerequisites?
You need basic programming concepts like variables, loops, and conditionals. No prior Java experience is required. The project introduces Java syntax as you go.
Your machine should have JDK 25, Apache Maven, and IntelliJ IDEA installed.
Create the Maven Project
Before you can write any engine code, you need a project structure that compiles and runs Java.
In this step, you'll scaffold a Maven project, configure it for JDK 25, and create the empty class files that will hold each component of your storage engine.
In this step, get ready to:
- Generate a Maven project using the quickstart archetype.
- Configure the build for Java 25 and add the exec plugin.
- Create empty class files for all five engine components.
Generate the Maven project
Maven's archetype system generates a ready-to-compile project skeleton from a template. You'll use the quickstart archetype to create your project folder, package structure, and initial pom.xml.
- Open your terminal by pressing Cmd+Space (macOS) or the Windows key (Windows), typing Terminal, and pressing Enter.
- Move to your Desktop by running this command:
cd ~/Desktop- Generate the Maven project by running this command:
mvn archetype:generate -DarchetypeGroupId=org.apache.maven.archetypes -DarchetypeArtifactId=maven-archetype-quickstart -DarchetypeVersion=1.5 -DgroupId=com.lsmengine -DartifactId=lsm-engine -DinteractiveMode=falseWhat does this command do?
- archetype:generate tells Maven to create a new project from a template.
- maven-archetype-quickstart is the template name. It gives you a basic Java project structure.
- -DgroupId=com.lsmengine sets your project's Java package name.
- -DartifactId=lsm-engine sets the project folder name and build artifact name.
- -DinteractiveMode=false prevents Maven from asking you interactive questions during setup.
- You should see BUILD SUCCESS at the end of the output. This confirms Maven generated your project.
- Move into your new project folder by running:
cd lsm-engineCommand not found or BUILD FAILURE?
- If you see mvn: command not found, Maven is not installed or not on your PATH. Run mvn --version to confirm Maven is available.
- If you see a network error, check your internet connection. Maven needs to download the archetype template.
Help me troubleshoot my Maven archetype:generate command
Now you have a project folder with a default pom.xml and some placeholder files. Next, you'll configure the build to use Java 25 and add a plugin for running your engine.
- Open IntelliJ IDEA by pressing Cmd+Space (macOS) or the Windows key (Windows), typing IntelliJ, and pressing Enter.
- Click Open on the Welcome screen.
- Navigate to your Desktop and select the lsm-engine folder, then click Open.
- If IntelliJ asks whether to trust the project, click Trust Project.
The archetype generated a default pom.xml targeting an older Java version with test dependencies you don't need. You'll replace it entirely with a clean configuration targeting Java 25.
- In IntelliJ's Project panel on the left, click pom.xml to open it.
- Select all the existing content with Cmd+A (macOS) or Ctrl+A (Windows) and delete it.
- Replace it with the following configuration:
<?xml version="1.0" encoding="UTF-8"?>
<project xmlns="http://maven.apache.org/POM/4.0.0"
xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd">
<modelVersion>4.0.0</modelVersion>
<groupId>com.lsmengine</groupId>
<artifactId>lsm-engine</artifactId>
<version>1.0-SNAPSHOT</version>
<packaging>jar</packaging>
<name>LSM Storage Engine</name>
<properties>
<project.build.sourceEncoding>UTF-8</project.build.sourceEncoding>
<!-- Target Java 25 for compilation -->
<maven.compiler.release>25</maven.compiler.release>
</properties>
<build>
<plugins>
<!-- Allows running the main class with: mvn compile exec:java -->
<plugin>
<groupId>org.codehaus.mojo</groupId>
<artifactId>exec-maven-plugin</artifactId>
<version>3.1.0</version>
<configuration>
<mainClass>com.lsmengine.Main</mainClass>
</configuration>
</plugin>
</plugins>
</build>
</project>What does this configuration do?
- maven.compiler.release set to 25 tells the Java compiler to use JDK 25 language features.
- The exec-maven-plugin lets you run your engine's Main class directly from the terminal with a single Maven command.
- No test dependencies are included because you'll verify your engine by running it, not with unit tests.
- Save pom.xml with Cmd+S (macOS) or Ctrl+S (Windows).
- If IntelliJ shows a popup asking to load Maven changes, click Load Maven Changes (or the refresh icon that appears in the top right of the editor).
IntelliJ showing red underlines in pom.xml?
- Make sure you replaced ALL the original content. Any leftover XML from the archetype's default pom.xml will cause conflicts.
- Click the Maven reload icon (circular arrows) in the top right of the editor to force IntelliJ to re-read the file.
Help me fix red underlines in my pom.xml
Create the engine class files
Your storage engine has five components, each in its own Java class. The archetype generated a placeholder App.java that you don't need. You'll delete it and create the real class files.
- In the Project panel, expand src > main > java > com.lsmengine.
- Right-click App.java and select Delete. Confirm the deletion.
- Right-click the src/test folder and select Delete. You won't need the test directory for this project.
Now create the five class files that will hold your engine components.
- Right-click the com.lsmengine package and select New > Java Class.
- Type WriteAheadLog and press Enter.
- Repeat the same process to create four more classes: MemTable, SSTable, StorageEngine, and Main.
What are these five classes?
- WriteAheadLog records every write to disk before anything else happens. This is your crash safety net.
- MemTable holds recent writes in a sorted in-memory structure for fast access.
- SSTable handles flushing sorted data to disk and reading it back with an index.
- StorageEngine ties all the components together into a single put/get/delete interface.
- Main is the entry point that demonstrates your engine and tests crash recovery.
- Verify your com.lsmengine package now contains exactly five files: Main.java, MemTable.java, SSTable.java, StorageEngine.java, and WriteAheadLog.java.
Each file should contain just a package declaration and an empty class body. IntelliJ generates this automatically when you create a class.
Don't see the New > Java Class option?
- Make sure you right-clicked the com.lsmengine package (shown in blue), not the java or main folder.
- If the src/main/java folder is not marked as a source root (blue icon), right-click it, select Mark Directory as > Sources Root.
Help me create Java classes in IntelliJ
Verify the project compiles
A successful compilation confirms that your pom.xml is valid, Java 25 is targeted correctly, and all class files are well-formed.
- Open IntelliJ's built-in terminal by clicking Terminal in the bottom toolbar (or press Alt+F12 on both macOS and Windows).
- Compile the project by running:
mvn compileWhat does mvn compile do?
This command reads your pom.xml, downloads any plugins it needs (like the exec plugin), and compiles all .java files under src/main/java into bytecode.
The first time you run it, Maven may download several dependencies. This is normal and only happens once.
- You should see BUILD SUCCESS in the terminal output.
Seeing BUILD FAILURE?
- If you see release version 25 not supported, your JDK version is older than 25. Run java --version to check.
- If you see an XML parsing error, double check that your pom.xml matches the code above exactly. A missing closing tag or extra character will break it.
- Make sure the terminal is inside the lsm-engine folder. Run pwd to verify your location.
Help me fix my Maven compilation error
✔️ Awesome, I've got everything!
Great. Double check you've saved all your files.
ⓧ I'd like to double check the full code
Here is the complete pom.xml:
<?xml version="1.0" encoding="UTF-8"?>
<project xmlns="http://maven.apache.org/POM/4.0.0"
xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd">
<modelVersion>4.0.0</modelVersion>
<groupId>com.lsmengine</groupId>
<artifactId>lsm-engine</artifactId>
<version>1.0-SNAPSHOT</version>
<packaging>jar</packaging>
<name>LSM Storage Engine</name>
<properties>
<project.build.sourceEncoding>UTF-8</project.build.sourceEncoding>
<maven.compiler.release>25</maven.compiler.release>
</properties>
<build>
<plugins>
<plugin>
<groupId>org.codehaus.mojo</groupId>
<artifactId>exec-maven-plugin</artifactId>
<version>3.1.0</version>
<configuration>
<mainClass>com.lsmengine.Main</mainClass>
</configuration>
</plugin>
</plugins>
</build>
</project>Each of your five class files should look like this (with its own class name):
package com.lsmengine;
public class WriteAheadLog {
}package com.lsmengine;
public class MemTable {
}package com.lsmengine;
public class SSTable {
}package com.lsmengine;
public class StorageEngine {
}package com.lsmengine;
public class Main {
}Your project skeleton is ready. Every class file compiles, and Maven knows how to run your engine. Next up, you'll build the first real component: the Write-Ahead Log that guarantees crash safety.
Implement the Write-Ahead Log
Your project compiles and the class files are in place. Now it is time to build the first and most critical piece of the storage engine: the Write-Ahead Log.
Every database needs a way to survive crashes. The WAL solves this by writing every operation to disk before anything else happens. If the process dies, the WAL file still contains every write that was accepted, ready to be replayed on restart.
In this step, get ready to:
- Implement the WAL constructor that opens a durable file channel.
- Build an append method that serializes key-value pairs to a binary format with fsync durability.
- Build a replay method that reads back all entries for crash recovery, plus utility methods for clearing and closing the log.
Set up the WAL class with its constructor
The WAL is an append-only binary file. Every entry gets written sequentially, and a FileChannel handles the low-level I/O with no Java-level buffering between your code and the operating system.
- Open WriteAheadLog.java in IntelliJ IDEA (it is inside src/main/java/com/lsmengine/).
- Replace the entire file contents with the following code:
package com.lsmengine;
import java.io.*;
import java.nio.ByteBuffer;
import java.nio.channels.FileChannel;
import java.nio.file.*;
import java.util.ArrayList;
import java.util.AbstractMap;
import java.util.List;
import java.util.Map;
public class WriteAheadLog {
// Path to the WAL file on disk
private final Path walPath;
// Channel for writing entries with fsync support
private FileChannel channel;
public WriteAheadLog(Path dataDir) throws IOException {
// Store the WAL file inside the data directory
this.walPath = dataDir.resolve("wal.log");
// Create the data directory if it doesn't exist yet
Files.createDirectories(dataDir);
// Open the file in append mode so new entries go at the end
this.channel = FileChannel.open(walPath,
StandardOpenOption.CREATE,
StandardOpenOption.WRITE,
StandardOpenOption.APPEND);
}
}What does this code do?
This sets up the WAL class with two fields: the path to the log file, and a FileChannel for writing.
- The constructor resolves a file called wal.log inside whatever data directory is passed in.
- It opens the file with APPEND mode so every write goes to the end of the file, never overwriting earlier entries.
- FileChannel has no Java-level buffer. Writes go directly to the OS, which is exactly what we need for durability.
Why FileChannel instead of a BufferedWriter?
A WAL must guarantee that data reaches the physical disk. FileChannel gives us the force(true) method, which calls fsync at the OS level. This ensures the data is persisted to the storage device, not just sitting in the OS page cache.
A BufferedWriter would add an extra layer of caching in Java, meaning data could be "written" in your code but lost in a crash because it never left the JVM's memory.
You will not see a visible change yet. The next chunk adds the method that actually writes entries.
Add the append method for writing entries
Each WAL entry needs a binary format that can be read back reliably. The format is: 4 bytes for the key length, then the key bytes, then 4 bytes for the value length, then the value bytes. This length-prefixed approach means the reader always knows exactly how many bytes to consume.
- In WriteAheadLog.java, find the closing } of the class (the last line of the file).
- Add the following method above that closing brace:
public void append(String key, String value) throws IOException {
// Convert strings to raw bytes for binary storage
byte[] keyBytes = key.getBytes(java.nio.charset.StandardCharsets.UTF_8);
byte[] valueBytes = value.getBytes(java.nio.charset.StandardCharsets.UTF_8);
// Build a buffer: [keyLen][keyBytes][valueLen][valueBytes]
ByteBuffer buffer = ByteBuffer.allocate(4 + keyBytes.length + 4 + valueBytes.length);
buffer.putInt(keyBytes.length);
buffer.put(keyBytes);
buffer.putInt(valueBytes.length);
buffer.put(valueBytes);
buffer.flip();
// Write to disk and force fsync for crash safety
channel.write(buffer);
channel.force(true);
}What does this code do?
- It converts the key and value strings into raw UTF-8 bytes.
- It allocates a ByteBuffer exactly large enough for both length prefixes (4 bytes each) plus the actual data.
- After filling the buffer, buffer.flip() resets the read position to the start so the channel can read from it.
- Finally, channel.force(true) calls fsync to guarantee the bytes hit the physical disk. This is what makes your WAL crash-safe.
- Save WriteAheadLog.java.
You will not see a runtime change yet. The file compiles but there is no way to verify the append works until the replay method reads entries back.
Seeing red underlines in IntelliJ?
- Make sure the method is inside the class braces but after the constructor's closing brace. Methods cannot be nested inside other methods in Java.
- Check that the import for java.nio.ByteBuffer is at the top of the file. If you replaced the file contents, all imports should already be there.
Help me fix a compile error in my WriteAheadLog append method.
Implement the replay method for crash recovery
The replay method is what makes crash recovery possible. On startup, the engine calls replay to read back every entry that was appended to the WAL but never flushed to an SSTable. It reads the same binary format the append method writes: length-prefixed keys and values, one after another.
- In WriteAheadLog.java, add the following method below the append method (still above the class closing brace):
public List<Map.Entry<String, String>> replay() throws IOException {
List<Map.Entry<String, String>> entries = new ArrayList<>();
// If the WAL file doesn't exist or is empty, nothing to replay
if (!Files.exists(walPath) || Files.size(walPath) == 0) {
return entries;
}
// Open a separate read-only channel to scan the file
try (FileChannel readChannel = FileChannel.open(walPath, StandardOpenOption.READ)) {
ByteBuffer sizeBuffer = ByteBuffer.allocate(4);
// Read entries until we reach end-of-file
while (readChannel.position() < readChannel.size()) {
// Read the key length (4 bytes)
sizeBuffer.clear();
int bytesRead = readChannel.read(sizeBuffer);
if (bytesRead < 4) break;
sizeBuffer.flip();
int keyLen = sizeBuffer.getInt();
// Read the key bytes
ByteBuffer keyBuffer = ByteBuffer.allocate(keyLen);
bytesRead = readChannel.read(keyBuffer);
if (bytesRead < keyLen) break;
keyBuffer.flip();
String key = new String(keyBuffer.array(), java.nio.charset.StandardCharsets.UTF_8);
// Read the value length (4 bytes)
sizeBuffer.clear();
bytesRead = readChannel.read(sizeBuffer);
if (bytesRead < 4) break;
sizeBuffer.flip();
int valueLen = sizeBuffer.getInt();
// Read the value bytes
ByteBuffer valueBuffer = ByteBuffer.allocate(valueLen);
bytesRead = readChannel.read(valueBuffer);
if (bytesRead < valueLen) break;
valueBuffer.flip();
String value = new String(valueBuffer.array(), java.nio.charset.StandardCharsets.UTF_8);
entries.add(new AbstractMap.SimpleEntry<>(key, value));
}
}
return entries;
}What does this code do?
- It first checks if the WAL file exists and has content. If not, it returns an empty list (nothing to recover).
- It opens a separate read-only channel (the write channel stays open for future appends).
- It loops through the file reading the same binary format that append writes: 4-byte length, then that many data bytes, repeated for key and value.
- The if (bytesRead < ...) guards handle a corrupted or truncated file gracefully. If the process crashed mid-write, it simply stops reading.
- Save WriteAheadLog.java.
You still cannot test this in isolation yet. The next chunk adds the final utility methods, then you will compile the full class.
Error about AbstractMap or SimpleEntry?
- Make sure the import java.util.AbstractMap is at the top of the file. This class provides the SimpleEntry helper for creating key-value pairs.
- Check that java.util.Map is also imported. The return type uses Map.Entry.
Help me fix the import errors in my replay method.
Add the clear and close utility methods
The WAL needs two more methods. The clear() method deletes the WAL file after a successful flush to an SSTable (the data is safely on disk elsewhere, so the log is no longer needed). The close() method releases the file handle when the engine shuts down.
- In WriteAheadLog.java, add the following two methods below the replay method (still above the class closing brace):
public void clear() throws IOException {
// Close the current channel before deleting the file
channel.close();
Files.deleteIfExists(walPath);
// Reopen a fresh channel for future writes
this.channel = FileChannel.open(walPath,
StandardOpenOption.CREATE,
StandardOpenOption.WRITE,
StandardOpenOption.APPEND);
}
public void close() throws IOException {
channel.close();
}What does this code do?
- The clear() method closes the channel, deletes the WAL file, then immediately reopens a fresh channel. This ensures the engine can keep accepting writes after a flush.
- The close() method simply releases the file handle. You call this when the storage engine is shutting down cleanly.
- Save WriteAheadLog.java.
- Verify the full class compiles by running this in your terminal (from the lsm-engine project root):
mvn compileYou should see BUILD SUCCESS in the terminal output. This confirms your WAL class is syntactically correct and all imports resolve.
Seeing BUILD FAILURE?
- Check that every method is placed between the class opening brace and the class closing brace. A common mistake is accidentally pasting a method outside the class.
- Make sure you have exactly one closing } for the class at the very end of the file.
- Read the error message carefully. It typically includes the line number and a description like cannot find symbol (missing import) or class, interface, or enum expected (brace mismatch).
Help me fix my WAL compile error.
✔️ Awesome, I've got everything!
Great. Double check you have saved WriteAheadLog.java and that your build succeeded.
ⓧ I'd like to double check the full code
Here is the complete WriteAheadLog.java file. Make sure your version matches exactly:
package com.lsmengine;
import java.io.*;
import java.nio.ByteBuffer;
import java.nio.channels.FileChannel;
import java.nio.file.*;
import java.util.ArrayList;
import java.util.AbstractMap;
import java.util.List;
import java.util.Map;
public class WriteAheadLog {
private final Path walPath;
private FileChannel channel;
public WriteAheadLog(Path dataDir) throws IOException {
this.walPath = dataDir.resolve("wal.log");
Files.createDirectories(dataDir);
this.channel = FileChannel.open(walPath,
StandardOpenOption.CREATE,
StandardOpenOption.WRITE,
StandardOpenOption.APPEND);
}
public void append(String key, String value) throws IOException {
byte[] keyBytes = key.getBytes(java.nio.charset.StandardCharsets.UTF_8);
byte[] valueBytes = value.getBytes(java.nio.charset.StandardCharsets.UTF_8);
ByteBuffer buffer = ByteBuffer.allocate(4 + keyBytes.length + 4 + valueBytes.length);
buffer.putInt(keyBytes.length);
buffer.put(keyBytes);
buffer.putInt(valueBytes.length);
buffer.put(valueBytes);
buffer.flip();
channel.write(buffer);
channel.force(true);
}
public List<Map.Entry<String, String>> replay() throws IOException {
List<Map.Entry<String, String>> entries = new ArrayList<>();
if (!Files.exists(walPath) || Files.size(walPath) == 0) {
return entries;
}
try (FileChannel readChannel = FileChannel.open(walPath, StandardOpenOption.READ)) {
ByteBuffer sizeBuffer = ByteBuffer.allocate(4);
while (readChannel.position() < readChannel.size()) {
sizeBuffer.clear();
int bytesRead = readChannel.read(sizeBuffer);
if (bytesRead < 4) break;
sizeBuffer.flip();
int keyLen = sizeBuffer.getInt();
ByteBuffer keyBuffer = ByteBuffer.allocate(keyLen);
bytesRead = readChannel.read(keyBuffer);
if (bytesRead < keyLen) break;
keyBuffer.flip();
String key = new String(keyBuffer.array(), java.nio.charset.StandardCharsets.UTF_8);
sizeBuffer.clear();
bytesRead = readChannel.read(sizeBuffer);
if (bytesRead < 4) break;
sizeBuffer.flip();
int valueLen = sizeBuffer.getInt();
ByteBuffer valueBuffer = ByteBuffer.allocate(valueLen);
bytesRead = readChannel.read(valueBuffer);
if (bytesRead < valueLen) break;
valueBuffer.flip();
String value = new String(valueBuffer.array(), java.nio.charset.StandardCharsets.UTF_8);
entries.add(new AbstractMap.SimpleEntry<>(key, value));
}
}
return entries;
}
public void clear() throws IOException {
channel.close();
Files.deleteIfExists(walPath);
this.channel = FileChannel.open(walPath,
StandardOpenOption.CREATE,
StandardOpenOption.WRITE,
StandardOpenOption.APPEND);
}
public void close() throws IOException {
channel.close();
}
}Your Write-Ahead Log is complete. It can append entries with crash-safe durability, replay them on startup, and clean itself up after a flush. Next up, you will build the MemTable that keeps those entries sorted in memory for fast reads.
Implement the MemTable
In the last step, you built the WAL to ensure no write is ever lost. Now you need a fast, sorted place to hold those writes in memory before they get flushed to disk.
The MemTable is where all writes live between being logged to the WAL and being persisted to an SSTable. It keeps keys sorted so that when it's time to flush, the data is already in the right order for efficient disk storage.
In this step, get ready to:
- Implement a sorted in-memory store using Java's TreeMap.
- Add size tracking to know when the MemTable is full and needs flushing.
- Provide a sorted entries method that outputs data ready for SSTable writing.
Create the MemTable class with fields and constructor
The MemTable needs a data structure that keeps keys sorted automatically. Java's TreeMap provides exactly this. It's a Red-Black tree that gives you O(log n) reads and writes with keys always in ascending order.
- Open MemTable.java in IntelliJ IDEA.
- Replace the entire contents of the file with this class shell:
package com.lsmengine;
import java.util.*;
public class MemTable {
// Sentinel value representing a deleted key
public static final String TOMBSTONE = "__TOMBSTONE__";
// Flush threshold: 1 KB for testing (production engines use ~64 MB)
private static final int MAX_SIZE_BYTES = 1024;
// Sorted map keeps keys in ascending order automatically
private final TreeMap<String, String> data;
// Tracks approximate byte size of all stored keys and values
private int currentSizeBytes;
public MemTable() {
this.data = new TreeMap<>();
this.currentSizeBytes = 0;
}
}What does this code do?
TOMBSTONE is a special marker string. When you "delete" a key, the MemTable stores this value instead of actually removing the entry. This tells the read path that the key was intentionally deleted.
MAX_SIZE_BYTES is set to 1024 bytes (1 KB) so you can trigger a flush with just a few writes during testing. Production engines like RocksDB set this to 64 MB.
TreeMap handles the sorting automatically. Every time you insert a key, the tree places it in the correct sorted position. This means you can iterate all entries in order without an explicit sort step.
Why TreeMap instead of a HashMap?
When the MemTable is full, its contents get flushed to an SSTable on disk. SSTables require data to be sorted by key for efficient lookups. A TreeMap keeps entries sorted at all times, so flushing is a simple iteration with no sorting overhead.
Production engines like RocksDB use a skip list for the same sorted property with better concurrent write performance. TreeMap gives you the same O(log n) guarantees and is idiomatic Java.
The class compiles but doesn't do anything yet. Next, add the core operations that let you read and write data.
Add put, get, and delete methods
These three methods form the MemTable's public API. Every write passes through put(), every read through get(), and deletes are just puts with a tombstone value.
- In MemTable.java, add the following methods inside the class, below the constructor:
public void put(String key, String value) {
// Subtract old size if key already exists (prevents double-counting)
String existing = data.get(key);
if (existing != null) {
currentSizeBytes -= (key.length() + existing.length());
}
// Insert into sorted tree and track new size
data.put(key, value);
currentSizeBytes += (key.length() + value.length());
}
public String get(String key) {
return data.get(key);
}
public void delete(String key) {
// A delete is just a put with the tombstone marker
put(key, TOMBSTONE);
}What does this code do?
- put() inserts a key-value pair into the TreeMap. It also updates currentSizeBytes to track how much data is stored. If the key already exists, it subtracts the old size first to avoid double-counting.
- get() returns the value for a key, or null if not found. The caller checks whether the value is a tombstone.
- delete() writes the TOMBSTONE string as the value. This tells the storage engine that the key was intentionally removed, even if older SSTables still contain it.
- Save MemTable.java.
- Verify the project still compiles by running:
mvn compileYou should see BUILD SUCCESS in the terminal output.
Seeing a compilation error?
- Check that your methods are inside the class braces. The closing } of the class should be the very last line of the file.
- Make sure the import line says import java.util.*; at the top of the file. Without it, Java cannot find TreeMap.
- Verify that TOMBSTONE is declared as public static final String with a value of "__TOMBSTONE__".
Why won't my MemTable compile in Java?
Add size tracking and capacity checks
The storage engine needs to know when the MemTable is full so it can flush the data to an SSTable on disk. You already track currentSizeBytes in the put() method. Now expose that information through public methods.
- In MemTable.java, add these two methods below the delete() method:
public int size() {
return currentSizeBytes;
}
public boolean isFull() {
// Returns true when stored data reaches the flush threshold
return currentSizeBytes >= MAX_SIZE_BYTES;
}What does this code do?
size() returns the current approximate byte size of all keys and values stored in the MemTable. The StorageEngine will call isFull() after every write to decide whether it's time to flush.
With MAX_SIZE_BYTES set to 1024, just a handful of key-value pairs will trigger a flush. This makes it easy to test the flush path without writing megabytes of data.
- Save MemTable.java.
You won't see a visible change yet. The next chunk adds the final methods and then you'll compile to verify everything together.
Add the sorted entries method for flushing
When the MemTable is full, the StorageEngine needs to grab all entries in sorted order and write them to an SSTable file. Because TreeMap keeps keys sorted, this is just a matter of iterating the map.
- In MemTable.java, add these two methods below isFull():
public List<Map.Entry<String, String>> entries() {
// Returns all key-value pairs in ascending key order
return new ArrayList<>(data.entrySet());
}
public boolean isEmpty() {
return data.isEmpty();
}What does this code do?
entries() returns a new list containing all key-value pairs from the TreeMap. Because TreeMap's entrySet() iterates in ascending key order, the returned list is already sorted. This sorted list is exactly what the SSTable writer needs.
isEmpty() is a guard the StorageEngine uses to avoid flushing an empty MemTable to disk.
- Save MemTable.java.
- Verify everything compiles by running:
mvn compileYou should see BUILD SUCCESS in the terminal output. Your MemTable is complete.
Seeing a type error on entries()?
- Make sure your return type is List<Map.Entry<String, String>>. The angle brackets must match exactly.
- Confirm the import at the top of the file is import java.util.*; which covers both List, ArrayList, Map, and TreeMap.
Help me fix a type error in my MemTable entries() method.
✔️ Awesome, I've got everything!
Great. Double check you've saved MemTable.java and confirmed the build succeeds.
ⓧ I'd like to double check the full code
Here is the complete MemTable.java file. Make sure your code matches this exactly:
package com.lsmengine;
import java.util.*;
public class MemTable {
public static final String TOMBSTONE = "__TOMBSTONE__";
private static final int MAX_SIZE_BYTES = 1024;
private final TreeMap<String, String> data;
private int currentSizeBytes;
public MemTable() {
this.data = new TreeMap<>();
this.currentSizeBytes = 0;
}
public void put(String key, String value) {
String existing = data.get(key);
if (existing != null) {
currentSizeBytes -= (key.length() + existing.length());
}
data.put(key, value);
currentSizeBytes += (key.length() + value.length());
}
public String get(String key) {
return data.get(key);
}
public void delete(String key) {
put(key, TOMBSTONE);
}
public int size() {
return currentSizeBytes;
}
public boolean isFull() {
return currentSizeBytes >= MAX_SIZE_BYTES;
}
public List<Map.Entry<String, String>> entries() {
return new ArrayList<>(data.entrySet());
}
public boolean isEmpty() {
return data.isEmpty();
}
}Your MemTable is ready to accept writes and report when it's full. Next up, you'll build the SSTable writer and reader that persists this sorted data to disk in a binary format with an index for fast lookups.
Implement the SSTable Writer and Reader
Your MemTable keeps sorted data in memory, but memory is volatile. When the MemTable fills up, you need somewhere permanent to put that data.
That permanent destination is an SSTable (Sorted String Table). An SSTable is an immutable file on disk containing key-value pairs in sorted order, with an index at the end for fast lookups. In this step, you will build both the writer (flush from memory to disk) and the reader (look up a key from the file).
In this step, get ready to:
- Write a flush() method that serializes sorted key-value pairs to a binary file with an index.
- Write a get() method that reads the index and retrieves a value by key.
- Verify the SSTable compiles alongside your existing WAL and MemTable.
Write the flush method to serialize data to disk
When the MemTable is full, its sorted entries need to be written to a file in a format you can read back later. The file format has three sections: the data (sequential key-value pairs), the index (a map of keys to their byte offsets in the data section), and an 8-byte footer that stores where the index begins.
- Open SSTable.java in IntelliJ IDEA.
- Replace the entire file contents with the following code:
package com.lsmengine;
import java.io.*;
import java.nio.ByteBuffer;
import java.nio.channels.FileChannel;
import java.nio.charset.StandardCharsets;
import java.nio.file.*;
import java.util.*;
public class SSTable {
public static void flush(List<Map.Entry<String, String>> sortedEntries, Path file) throws IOException {
try (FileChannel channel = FileChannel.open(file,
StandardOpenOption.CREATE,
StandardOpenOption.WRITE,
StandardOpenOption.TRUNCATE_EXISTING)) {
// Track each key's byte offset for the index
Map<String, Long> index = new LinkedHashMap<>();
long offset = 0;
// Write each key-value pair sequentially
for (Map.Entry<String, String> entry : sortedEntries) {
byte[] keyBytes = entry.getKey().getBytes(StandardCharsets.UTF_8);
byte[] valueBytes = entry.getValue().getBytes(StandardCharsets.UTF_8);
// Record this key's position before writing
index.put(entry.getKey(), offset);
// Format: [4-byte key length][key bytes][4-byte value length][value bytes]
ByteBuffer buffer = ByteBuffer.allocate(4 + keyBytes.length + 4 + valueBytes.length);
buffer.putInt(keyBytes.length);
buffer.put(keyBytes);
buffer.putInt(valueBytes.length);
buffer.put(valueBytes);
buffer.flip();
channel.write(buffer);
offset += 4 + keyBytes.length + 4 + valueBytes.length;
}
// Remember where the index section starts
long indexOffset = offset;
// Write the number of index entries
ByteBuffer countBuffer = ByteBuffer.allocate(4);
countBuffer.putInt(index.size());
countBuffer.flip();
channel.write(countBuffer);
// Write each index entry: [4-byte key length][key bytes][8-byte offset]
for (Map.Entry<String, Long> indexEntry : index.entrySet()) {
byte[] keyBytes = indexEntry.getKey().getBytes(StandardCharsets.UTF_8);
ByteBuffer indexBuffer = ByteBuffer.allocate(4 + keyBytes.length + 8);
indexBuffer.putInt(keyBytes.length);
indexBuffer.put(keyBytes);
indexBuffer.putLong(indexEntry.getValue());
indexBuffer.flip();
channel.write(indexBuffer);
}
// Write the footer: 8 bytes pointing to where the index starts
ByteBuffer footerBuffer = ByteBuffer.allocate(8);
footerBuffer.putLong(indexOffset);
footerBuffer.flip();
channel.write(footerBuffer);
// Ensure everything reaches disk
channel.force(true);
}
}
}What does this code do?
The flush() method writes sorted key-value pairs to a binary file with a specific layout:
- The data section comes first. Each entry is stored as 4 bytes for the key length, the key bytes, 4 bytes for the value length, then the value bytes. This is the same binary format your WAL uses.
- A LinkedHashMap tracks the byte offset of every key as it is written. This becomes the index.
- The index section follows the data. It stores the count of entries, then each key paired with its byte offset (as a long).
- The last 8 bytes of the file (the footer) store where the index section begins. A reader can jump to the end of the file, read 8 bytes, and immediately know where to find the index.
Why put the index at the end?
You cannot know the byte offsets until after you have written all the data. Writing the index at the end means you can stream entries in a single pass without buffering the entire file in memory.
Production databases like RocksDB use the same footer-based approach. The reader reads the footer first, then jumps to the index, then jumps to the data entry it needs.
- Save SSTable.java.
Seeing red underlines in IntelliJ?
Make sure you replaced the entire file contents including the imports at the top. The FileChannel and StandardCharsets classes come from the java.nio package, which the import lines bring in.
help me fix import errors in my SSTable.java file
Write the get method to read a value by key
Writing data to disk is only useful if you can read it back. The get() method needs to find a specific key in the SSTable file without scanning every entry in the data section. It does this by reading the index first, finding the target key's byte offset, then jumping directly to that position.
- In SSTable.java, find the closing brace of the flush() method.
- Add the following get() method below it, inside the class:
public static String get(String key, Path file) throws IOException {
try (FileChannel channel = FileChannel.open(file, StandardOpenOption.READ)) {
long fileSize = channel.size();
// Read the footer to find where the index starts
ByteBuffer footerBuffer = ByteBuffer.allocate(8);
channel.position(fileSize - 8);
channel.read(footerBuffer);
footerBuffer.flip();
long indexOffset = footerBuffer.getLong();
// Jump to the index section
channel.position(indexOffset);
// Read how many entries are in the index
ByteBuffer countBuffer = ByteBuffer.allocate(4);
channel.read(countBuffer);
countBuffer.flip();
int entryCount = countBuffer.getInt();
// Scan the index for the target key
long dataOffset = -1;
ByteBuffer sizeBuffer = ByteBuffer.allocate(4);
for (int i = 0; i < entryCount; i++) {
sizeBuffer.clear();
channel.read(sizeBuffer);
sizeBuffer.flip();
int keyLen = sizeBuffer.getInt();
ByteBuffer keyBuffer = ByteBuffer.allocate(keyLen);
channel.read(keyBuffer);
keyBuffer.flip();
String indexKey = new String(keyBuffer.array(), StandardCharsets.UTF_8);
ByteBuffer offsetBuffer = ByteBuffer.allocate(8);
channel.read(offsetBuffer);
offsetBuffer.flip();
long entryOffset = offsetBuffer.getLong();
// Stop scanning once we find the target key
if (indexKey.equals(key)) {
dataOffset = entryOffset;
break;
}
}
// Key not found in this SSTable
if (dataOffset == -1) {
return null;
}
// Jump to the data entry and read the value
channel.position(dataOffset);
sizeBuffer.clear();
channel.read(sizeBuffer);
sizeBuffer.flip();
int keyLen = sizeBuffer.getInt();
// Skip past the key bytes
ByteBuffer keyBuffer = ByteBuffer.allocate(keyLen);
channel.read(keyBuffer);
// Read the value length and value bytes
sizeBuffer.clear();
channel.read(sizeBuffer);
sizeBuffer.flip();
int valueLen = sizeBuffer.getInt();
ByteBuffer valueBuffer = ByteBuffer.allocate(valueLen);
channel.read(valueBuffer);
valueBuffer.flip();
return new String(valueBuffer.array(), StandardCharsets.UTF_8);
}
}What does this code do?
The get() method reads an SSTable file in three jumps:
- First, it reads the last 8 bytes of the file (the footer) to learn where the index starts.
- Second, it jumps to the index and scans through each key-offset pair until it finds a match. If no match is found, it returns null.
- Third, it jumps to the matched key's byte offset in the data section, skips past the key bytes, and reads the value bytes.
This avoids reading the entire data section. The reader only touches the footer, the index, and the single data entry it needs.
- Save SSTable.java.
Seeing a compile error about duplicate variables?
Make sure you placed the get() method inside the SSTable class (before the final closing brace) but after the flush() method's closing brace. Each method should be complete and separate.
help me fix my SSTable.java structure
Verify the SSTable compiles
Your SSTable now has both a writer and a reader. Before moving on, confirm everything compiles together with the WAL and MemTable you built earlier.
- In your terminal, make sure you are inside the lsm-engine project directory.
- Compile the project by running:
mvn compile- You should see BUILD SUCCESS in the output. This confirms your SSTable class compiles cleanly alongside the existing WAL and MemTable.
BUILD FAILURE?
Check that your SSTable.java has the correct package declaration (package com.lsmengine;) and all six import lines at the top. A missing import for StandardCharsets or FileChannel is the most common cause.
help me fix my SSTable compilation error
✔️ Awesome, I've got everything!
Great. Double check you have saved SSTable.java and that mvn compile passes.
ⓧ I'd like to double check the full code
Here is the complete SSTable.java file:
package com.lsmengine;
import java.io.*;
import java.nio.ByteBuffer;
import java.nio.channels.FileChannel;
import java.nio.charset.StandardCharsets;
import java.nio.file.*;
import java.util.*;
public class SSTable {
public static void flush(List<Map.Entry<String, String>> sortedEntries, Path file) throws IOException {
try (FileChannel channel = FileChannel.open(file,
StandardOpenOption.CREATE,
StandardOpenOption.WRITE,
StandardOpenOption.TRUNCATE_EXISTING)) {
Map<String, Long> index = new LinkedHashMap<>();
long offset = 0;
for (Map.Entry<String, String> entry : sortedEntries) {
byte[] keyBytes = entry.getKey().getBytes(StandardCharsets.UTF_8);
byte[] valueBytes = entry.getValue().getBytes(StandardCharsets.UTF_8);
index.put(entry.getKey(), offset);
ByteBuffer buffer = ByteBuffer.allocate(4 + keyBytes.length + 4 + valueBytes.length);
buffer.putInt(keyBytes.length);
buffer.put(keyBytes);
buffer.putInt(valueBytes.length);
buffer.put(valueBytes);
buffer.flip();
channel.write(buffer);
offset += 4 + keyBytes.length + 4 + valueBytes.length;
}
long indexOffset = offset;
ByteBuffer countBuffer = ByteBuffer.allocate(4);
countBuffer.putInt(index.size());
countBuffer.flip();
channel.write(countBuffer);
for (Map.Entry<String, Long> indexEntry : index.entrySet()) {
byte[] keyBytes = indexEntry.getKey().getBytes(StandardCharsets.UTF_8);
ByteBuffer indexBuffer = ByteBuffer.allocate(4 + keyBytes.length + 8);
indexBuffer.putInt(keyBytes.length);
indexBuffer.put(keyBytes);
indexBuffer.putLong(indexEntry.getValue());
indexBuffer.flip();
channel.write(indexBuffer);
}
ByteBuffer footerBuffer = ByteBuffer.allocate(8);
footerBuffer.putLong(indexOffset);
footerBuffer.flip();
channel.write(footerBuffer);
channel.force(true);
}
}
public static String get(String key, Path file) throws IOException {
try (FileChannel channel = FileChannel.open(file, StandardOpenOption.READ)) {
long fileSize = channel.size();
ByteBuffer footerBuffer = ByteBuffer.allocate(8);
channel.position(fileSize - 8);
channel.read(footerBuffer);
footerBuffer.flip();
long indexOffset = footerBuffer.getLong();
channel.position(indexOffset);
ByteBuffer countBuffer = ByteBuffer.allocate(4);
channel.read(countBuffer);
countBuffer.flip();
int entryCount = countBuffer.getInt();
long dataOffset = -1;
ByteBuffer sizeBuffer = ByteBuffer.allocate(4);
for (int i = 0; i < entryCount; i++) {
sizeBuffer.clear();
channel.read(sizeBuffer);
sizeBuffer.flip();
int keyLen = sizeBuffer.getInt();
ByteBuffer keyBuffer = ByteBuffer.allocate(keyLen);
channel.read(keyBuffer);
keyBuffer.flip();
String indexKey = new String(keyBuffer.array(), StandardCharsets.UTF_8);
ByteBuffer offsetBuffer = ByteBuffer.allocate(8);
channel.read(offsetBuffer);
offsetBuffer.flip();
long entryOffset = offsetBuffer.getLong();
if (indexKey.equals(key)) {
dataOffset = entryOffset;
break;
}
}
if (dataOffset == -1) {
return null;
}
channel.position(dataOffset);
sizeBuffer.clear();
channel.read(sizeBuffer);
sizeBuffer.flip();
int keyLen = sizeBuffer.getInt();
ByteBuffer keyBuffer = ByteBuffer.allocate(keyLen);
channel.read(keyBuffer);
sizeBuffer.clear();
channel.read(sizeBuffer);
sizeBuffer.flip();
int valueLen = sizeBuffer.getInt();
ByteBuffer valueBuffer = ByteBuffer.allocate(valueLen);
channel.read(valueBuffer);
valueBuffer.flip();
return new String(valueBuffer.array(), StandardCharsets.UTF_8);
}
}
}You now have all three data structures of the LSM write path built: the WAL for durability, the MemTable for fast sorted access, and the SSTable for permanent storage. Next, you will wire them all together into a single StorageEngine class that coordinates the full write and read paths.
Wire Everything Together in StorageEngine
You have three fully functional components: a WAL for durability, a MemTable for fast sorted access, and SSTables for persistent disk storage. Right now they exist in isolation.
The StorageEngine class is the orchestrator that ties them into one cohesive system. It manages the complete lifecycle: accepting writes, deciding when to flush, and searching the right places for reads.
In this step, get ready to:
- Build the engine constructor with WAL replay and SSTable discovery on startup.
- Implement the write path with automatic MemTable-to-SSTable flushing.
- Implement the LSM read path that searches MemTable then SSTables newest-to-oldest.
Implement the constructor and startup logic
When the engine starts, it needs to recover any state left behind by a previous run. This means finding existing SSTable files on disk and replaying any WAL entries that were not yet flushed.
- Open StorageEngine.java in the src/main/java/com/lsmengine/ directory.
- Replace the entire file contents with the following startup skeleton:
package com.lsmengine;
import java.io.*;
import java.nio.file.*;
import java.util.*;
import java.util.stream.Collectors;
public class StorageEngine {
private final Path dataDir;
private WriteAheadLog wal;
private MemTable memTable;
private final List<Path> sstables;
private int sstableCounter;
public StorageEngine(Path dataDir) throws IOException {
this.dataDir = dataDir;
Files.createDirectories(dataDir);
this.memTable = new MemTable();
this.sstables = new ArrayList<>();
this.sstableCounter = 0;
// Discover any SSTables from previous runs
loadExistingSSTables();
// Open the WAL and replay any unflushed entries
this.wal = new WriteAheadLog(dataDir);
replayWAL();
}
private void loadExistingSSTables() throws IOException {
if (!Files.exists(dataDir)) return;
// Find all SSTable files, sorted by name (oldest first)
List<Path> existingFiles = Files.list(dataDir)
.filter(p -> p.getFileName().toString().startsWith("sstable_"))
.sorted(Comparator.comparing(p -> p.getFileName().toString()))
.collect(Collectors.toList());
sstables.addAll(existingFiles);
// Set counter to continue after the last existing file
if (!existingFiles.isEmpty()) {
String lastFile = existingFiles.get(existingFiles.size() - 1)
.getFileName().toString();
String numberPart = lastFile.replace("sstable_", "").replace(".dat", "");
sstableCounter = Integer.parseInt(numberPart) + 1;
}
}
private void replayWAL() throws IOException {
// Restore MemTable state from WAL entries that survived a crash
List<Map.Entry<String, String>> entries = wal.replay();
for (Map.Entry<String, String> entry : entries) {
memTable.put(entry.getKey(), entry.getValue());
}
if (!entries.isEmpty()) {
System.out.println("Recovered " + entries.size() + " entries from WAL");
}
}
}What does this code do?
The constructor orchestrates three startup tasks in a specific order.
- It creates the data directory if it does not exist, then initializes an empty MemTable and SSTable tracking list.
- loadExistingSSTables() scans the data directory for files named sstable_00000.dat, sstable_00001.dat, etc. It sorts them by filename so the list is ordered oldest-to-newest. It also sets the counter so the next flush gets a unique name.
- replayWAL() reads back any entries from the WAL file and inserts them into the fresh MemTable. This is how the engine recovers data that was written but never flushed to an SSTable before a crash.
Why does startup order matter?
SSTable loading happens before WAL replay because the WAL only contains entries that are NOT yet in an SSTable. If you replayed the WAL first, you would not know which counter value to assign the next flush.
- Save StorageEngine.java.
The file will not compile yet because the class has no write or read methods. You will add those next.
Implement the write path with automatic flushing
Every write in an LSM-tree follows the same two-step contract: append to the WAL for durability, then insert into the MemTable for fast access. When the MemTable fills up, the engine automatically flushes it to a new SSTable.
- In StorageEngine.java, add the following methods inside the class body, after the replayWAL() method:
public void put(String key, String value) throws IOException {
// Durability first: WAL ensures this write survives a crash
wal.append(key, value);
memTable.put(key, value);
checkFlush();
}
public void delete(String key) throws IOException {
// Deletes are writes too: store a tombstone marker
wal.append(key, MemTable.TOMBSTONE);
memTable.delete(key);
checkFlush();
}
private void checkFlush() throws IOException {
if (memTable.isFull()) {
flushMemTable();
}
}
private void flushMemTable() throws IOException {
if (memTable.isEmpty()) return;
// Generate a unique filename with zero-padded counter
String fileName = String.format("sstable_%05d.dat", sstableCounter++);
Path sstablePath = dataDir.resolve(fileName);
// Write sorted MemTable contents to a new SSTable file
SSTable.flush(memTable.entries(), sstablePath);
sstables.add(sstablePath);
// WAL is no longer needed since data is safely in the SSTable
wal.clear();
memTable = new MemTable();
System.out.println("Flushed MemTable to " + fileName);
}
public void close() throws IOException {
wal.close();
}What does this code do?
- put() writes to the WAL first (crash safety), then to the MemTable (fast access), then checks if a flush is needed.
- delete() works the same way but stores a TOMBSTONE sentinel value instead of the real data. This marks the key as deleted without removing it from older SSTables.
- flushMemTable() takes all sorted entries from the MemTable, writes them to a new SSTable file, adds the file path to the tracking list, clears the WAL (those entries are now safe in the SSTable), and creates a fresh empty MemTable.
- The filename format sstable_%05d.dat produces names like sstable_00000.dat, sstable_00001.dat. The zero-padding ensures alphabetical sort matches chronological order.
- Save StorageEngine.java.
The file still will not compile because the compiler expects the get() method you will add next.
Seeing a red underline on MemTable.TOMBSTONE?
Make sure your MemTable.java has the line public static final String TOMBSTONE = "__TOMBSTONE__"; declared as a public static field. If it is private or missing, the StorageEngine cannot reference it.
help me fix a TOMBSTONE reference error in StorageEngine
Implement the LSM read path
The read path is where the LSM-tree architecture pays off. Instead of scanning one giant file, the engine checks the fastest source first (the in-memory MemTable) and only falls through to disk if needed.
- In StorageEngine.java, add the get() method after the delete() method and before the checkFlush() method:
public String get(String key) throws IOException {
// Check MemTable first (fastest, most recent data)
String value = memTable.get(key);
if (value != null) {
if (value.equals(MemTable.TOMBSTONE)) {
return null; // Key was deleted
}
return value;
}
// Search SSTables from newest to oldest
for (int i = sstables.size() - 1; i >= 0; i--) {
value = SSTable.get(key, sstables.get(i));
if (value != null) {
if (value.equals(MemTable.TOMBSTONE)) {
return null; // Found a tombstone in an SSTable
}
return value;
}
}
// Key does not exist anywhere
return null;
}What does this code do?
- First it checks the MemTable. If the key is there and it is a tombstone, the key was recently deleted so it returns null. If it is a real value, it returns immediately without touching disk.
- If the MemTable has no entry for the key, the method searches SSTables from newest (highest index) to oldest (index 0). This ordering guarantees the most recent version of the key is found first.
- If a tombstone is found in any SSTable, it means the key was deleted before that SSTable was flushed. The method returns null even if older SSTables contain a real value for the same key.
- Save StorageEngine.java.
- Verify the project compiles by running:
mvn compileYou should see BUILD SUCCESS in the terminal output.
Build failing with compilation errors?
- Check that you have both opening and closing braces for every method and the class itself. A missing brace is the most common cause of cascading errors.
- Verify your imports at the top of the file include java.util.stream.Collectors. The loadExistingSSTables() method uses Collectors.toList().
- Make sure the get() method is placed inside the class body and not accidentally outside the final closing brace.
help me fix StorageEngine compilation errors
✔️ Awesome, I've got everything!
Great. Double check you have saved StorageEngine.java and that mvn compile passes.
ⓧ I'd like to double check the full code
package com.lsmengine;
import java.io.*;
import java.nio.file.*;
import java.util.*;
import java.util.stream.Collectors;
public class StorageEngine {
private final Path dataDir;
private WriteAheadLog wal;
private MemTable memTable;
private final List<Path> sstables;
private int sstableCounter;
public StorageEngine(Path dataDir) throws IOException {
this.dataDir = dataDir;
Files.createDirectories(dataDir);
this.memTable = new MemTable();
this.sstables = new ArrayList<>();
this.sstableCounter = 0;
loadExistingSSTables();
this.wal = new WriteAheadLog(dataDir);
replayWAL();
}
private void loadExistingSSTables() throws IOException {
if (!Files.exists(dataDir)) return;
List<Path> existingFiles = Files.list(dataDir)
.filter(p -> p.getFileName().toString().startsWith("sstable_"))
.sorted(Comparator.comparing(p -> p.getFileName().toString()))
.collect(Collectors.toList());
sstables.addAll(existingFiles);
if (!existingFiles.isEmpty()) {
String lastFile = existingFiles.get(existingFiles.size() - 1)
.getFileName().toString();
String numberPart = lastFile.replace("sstable_", "").replace(".dat", "");
sstableCounter = Integer.parseInt(numberPart) + 1;
}
}
private void replayWAL() throws IOException {
List<Map.Entry<String, String>> entries = wal.replay();
for (Map.Entry<String, String> entry : entries) {
memTable.put(entry.getKey(), entry.getValue());
}
if (!entries.isEmpty()) {
System.out.println("Recovered " + entries.size() + " entries from WAL");
}
}
public void put(String key, String value) throws IOException {
wal.append(key, value);
memTable.put(key, value);
checkFlush();
}
public void delete(String key) throws IOException {
wal.append(key, MemTable.TOMBSTONE);
memTable.delete(key);
checkFlush();
}
public String get(String key) throws IOException {
String value = memTable.get(key);
if (value != null) {
if (value.equals(MemTable.TOMBSTONE)) {
return null;
}
return value;
}
for (int i = sstables.size() - 1; i >= 0; i--) {
value = SSTable.get(key, sstables.get(i));
if (value != null) {
if (value.equals(MemTable.TOMBSTONE)) {
return null;
}
return value;
}
}
return null;
}
private void checkFlush() throws IOException {
if (memTable.isFull()) {
flushMemTable();
}
}
private void flushMemTable() throws IOException {
if (memTable.isEmpty()) return;
String fileName = String.format("sstable_%05d.dat", sstableCounter++);
Path sstablePath = dataDir.resolve(fileName);
SSTable.flush(memTable.entries(), sstablePath);
sstables.add(sstablePath);
wal.clear();
memTable = new MemTable();
System.out.println("Flushed MemTable to " + fileName);
}
public void close() throws IOException {
wal.close();
}
}Your storage engine is fully wired. Next up, you will build a demo that proves crash recovery actually works by writing data, simulating a crash, and reading it back.
Demonstrate Crash Recovery
You have a fully wired LSM-tree storage engine with a WAL, MemTable, and SSTables working together.
Now it is time to prove the engine actually works. You will write a demo that stores data, simulates a process crash, and then reopens the engine to show that the Write-Ahead Log recovers every entry.
In this step, get ready to:
- Write a crash simulation that stores data and exits without flushing the MemTable.
- Write a recovery mode that reopens the engine and reads back all keys from the WAL.
- Run the full demo and observe crash recovery in action.
Write the crash simulation method
The Main.java file currently exists as an empty class. You will replace it with a demo that has two modes: a write-and-crash mode and a recovery mode, selected via a command-line argument.
- Open Main.java in IntelliJ IDEA.
- Replace the entire contents with the following code:
package com.lsmengine;
import java.io.IOException;
import java.nio.file.Path;
public class Main {
// Directory where the engine stores WAL and SSTable files
private static final Path DATA_DIR = Path.of("data");
public static void main(String[] args) throws IOException {
// Route to recovery mode if "recover" argument is passed
if (args.length > 0 && args[0].equals("recover")) {
recoverAndRead();
} else {
writeAndCrash();
}
}
private static void writeAndCrash() throws IOException {
StorageEngine engine = new StorageEngine(DATA_DIR);
// Write four key-value pairs to the engine
System.out.println("=== Writing data ===");
engine.put("name", "Alice");
engine.put("city", "Tokyo");
engine.put("language", "Java");
engine.put("project", "LSM-Engine");
// Read them back to confirm they are in memory
System.out.println("\n=== Reading back ===");
System.out.println("name = " + engine.get("name"));
System.out.println("city = " + engine.get("city"));
System.out.println("language = " + engine.get("language"));
System.out.println("project = " + engine.get("project"));
// Close without flushing MemTable to SSTable
System.out.println("\n=== Simulating crash (not flushing MemTable) ===");
System.out.println("Data is in WAL but NOT in an SSTable yet.");
System.out.println("Run with 'recover' argument to see WAL recovery in action.");
engine.close();
}
}What does this code do?
DATA_DIR points to a data/ folder in your project root. The engine stores its WAL and SSTable files here.
The main() method checks for a recover argument to decide which mode to run. Without it, the default mode writes data and simulates a crash.
The writeAndCrash() method stores four key-value pairs. These four entries total well under 1024 bytes, so they stay in the MemTable without triggering a flush to an SSTable. When engine.close() runs, the MemTable data disappears from memory. The WAL on disk still has every entry.
This file will not compile yet because main() references recoverAndRead() which you have not written yet. You will add it in the next substep.
Add the recovery mode
The recovery method simulates what happens when a database process restarts after a crash. Opening a new StorageEngine instance automatically triggers WAL replay in the constructor, restoring all entries that were never flushed to an SSTable.
- In Main.java, add the following method below the closing brace of writeAndCrash():
private static void recoverAndRead() throws IOException {
System.out.println("=== Opening engine (WAL recovery will happen) ===");
// Creating a new StorageEngine triggers replayWAL() in the constructor
StorageEngine engine = new StorageEngine(DATA_DIR);
// Read back the same keys that were written before the crash
System.out.println("\n=== Reading data after recovery ===");
System.out.println("name = " + engine.get("name"));
System.out.println("city = " + engine.get("city"));
System.out.println("language = " + engine.get("language"));
System.out.println("project = " + engine.get("project"));
engine.close();
System.out.println("\n=== Recovery successful! All data intact. ===");
}What does this code do?
The method creates a brand new StorageEngine instance pointing at the same data/ directory. The constructor automatically calls replayWAL(), which reads every entry from wal.log back into the fresh MemTable.
After replay, the get() calls find all four keys in the MemTable as if the crash never happened. This is the core guarantee of Write-Ahead Logging: any write that was acknowledged is recoverable.
- Save Main.java.
- Verify the project compiles by running:
mvn compileYou should see BUILD SUCCESS in the output.
Seeing a compilation error?
If you see cannot find symbol: method recoverAndRead(), make sure the recoverAndRead() method is inside the Main class but outside writeAndCrash().
Check that you have exactly two closing braces at the bottom of the file: one for recoverAndRead() and one for the Main class itself.
help me fix a compilation error in Main.java
✔️ Awesome, I've got everything!
Great. Double check you have saved Main.java before continuing.
ⓧ I'd like to double check the full code
package com.lsmengine;
import java.io.IOException;
import java.nio.file.Path;
public class Main {
private static final Path DATA_DIR = Path.of("data");
public static void main(String[] args) throws IOException {
if (args.length > 0 && args[0].equals("recover")) {
recoverAndRead();
} else {
writeAndCrash();
}
}
private static void writeAndCrash() throws IOException {
StorageEngine engine = new StorageEngine(DATA_DIR);
System.out.println("=== Writing data ===");
engine.put("name", "Alice");
engine.put("city", "Tokyo");
engine.put("language", "Java");
engine.put("project", "LSM-Engine");
System.out.println("\n=== Reading back ===");
System.out.println("name = " + engine.get("name"));
System.out.println("city = " + engine.get("city"));
System.out.println("language = " + engine.get("language"));
System.out.println("project = " + engine.get("project"));
System.out.println("\n=== Simulating crash (not flushing MemTable) ===");
System.out.println("Data is in WAL but NOT in an SSTable yet.");
System.out.println("Run with 'recover' argument to see WAL recovery in action.");
engine.close();
}
private static void recoverAndRead() throws IOException {
System.out.println("=== Opening engine (WAL recovery will happen) ===");
StorageEngine engine = new StorageEngine(DATA_DIR);
System.out.println("\n=== Reading data after recovery ===");
System.out.println("name = " + engine.get("name"));
System.out.println("city = " + engine.get("city"));
System.out.println("language = " + engine.get("language"));
System.out.println("project = " + engine.get("project"));
engine.close();
System.out.println("\n=== Recovery successful! All data intact. ===");
}
}Run the demo and observe crash recovery
You will run the engine twice. The first run writes data and exits. The second run reopens the engine and proves the WAL recovered everything.
- First, delete any leftover data/ directory from earlier testing by running:
rm -rf data- Run the write-and-crash mode by executing:
mvn compile exec:javaYou should see output showing all four keys written and read back successfully, followed by the crash simulation message.
What should I see?
The output shows === Writing data === followed by the four key-value pairs being read back (e.g. name = Alice). Then it prints that the data is in the WAL but not in an SSTable.
At this point, the data/wal.log file on disk contains all four entries. No sstable_*.dat files exist because the MemTable never hit the 1024-byte threshold.
- Now run the recovery mode by passing the recover argument:
mvn compile exec:java -Dexec.args="recover"You should see Recovered 4 entries from WAL followed by all four keys read back with their correct values.
Why does this prove crash recovery works?
Between the two runs, the MemTable was gone. It only existed in the first process's memory. The second run created a brand new StorageEngine with an empty MemTable.
The constructor's replayWAL() call read every entry from wal.log and loaded them back into the MemTable. This is the same mechanism that real databases like RocksDB use to recover from power failures and process crashes.
Seeing null values after recovery?
If get() returns null for your keys after recovery, check that your WriteAheadLog.replay() method correctly reads all four length-prefixed entries from the file.
Also confirm that DATA_DIR uses Path.of("data") in Main.java. Both runs must point at the same directory for recovery to find the WAL.
help me debug WAL recovery returning null values
Secret mission
Add Bloom Filters for Read Optimization
Your read path currently checks every SSTable file one by one. What if you had hundreds of them? Add Bloom filters so your engine can skip files that definitely do not contain a key, just like RocksDB does in production.
Clean Up Your Resources
Clean Up Your Resources
This project runs entirely locally, so there are no ongoing costs. Decide whether to keep your project files for future experimentation, or delete them to free up disk space.
Resources you used:
- The lsm-engine Maven project folder on your Desktop.
- The data/ directory containing WAL and SSTable files.
- JDK 25 installed on your system.
- Apache Maven installed on your system.
- IntelliJ IDEA installed on your system.
Keep everything running
No action needed. Choose this if you want to keep experimenting with your storage engine, add compaction, or try different MemTable sizes.
- Your project folder stays on your Desktop.
- JDK, Maven, and IntelliJ IDEA remain installed for future Java projects.
- The data/ directory keeps your WAL and SSTable files for continued testing.
Pause - I'll come back to this later
Keep the project files but clean up the generated data so your engine starts fresh next time.
- Delete the data/ directory inside your project folder. This removes all WAL and SSTable files.
- Keep JDK, Maven, and IntelliJ IDEA installed. They take minimal disk space and are useful for other projects.
- When you return, run mvn compile exec:java to regenerate fresh data files.
Delete - I don't want to use this again
Remove all project files and optionally uninstall the development tools.
- Delete the entire lsm-engine folder from your Desktop.
- Optionally uninstall IntelliJ IDEA if you do not plan to use it for other Java projects.
- Keep JDK and Maven installed if you plan to do other Java or Maven-based projects in the future. They consume minimal resources when not in use.
Nice Work!
Nice Work!
You just built a persistent key-value storage engine from scratch. This is the same architecture that powers some of the most demanding databases in the world, including RocksDB, Cassandra, and CockroachDB.
You've learned how to:
- Implement a Write-Ahead Log with fsync durability that guarantees crash recovery by replaying entries on startup.
- Build a sorted MemTable and flush it to immutable SSTables with a binary format and index for O(log n) lookups.
- Wire the full LSM-tree read and write paths together in a cohesive StorageEngine that survives simulated process crashes.
- Secret Mission: Added Bloom filters to skip SSTables that cannot contain a key, dramatically improving read performance.
Ready to quiz yourself?