DEV Community: Gagandeep Singh Ahuja

Building SaarDB, Part 3: Compaction

Gagandeep Singh Ahuja — Mon, 20 Jul 2026 04:25:08 +0000

In Parts 1 and 2, we built a storage engine: WAL for durability and LSM tree for efficient disk reads.

This works. But there is a problem growing quietly in the background.

Problem: SSTable Files Keep Growing

Every memtable flush creates a new SSTable file. After 10 flushes, you have 10 files. After 1000 flushes, you have 1000 files.

Now consider what happens when you serve a GET request:

GET user_42

Search SSTable 1000 (newest) → not found
Search SSTable 999           → not found
Search SSTable 998           → not found
...
Search SSTable 1             → found!

In the worst case, we search ALL 1000 files before finding the key (or confirming it doesn't exist). Each search binary searching the index block, and potentially reading a data block from disk.

This is called read amplification: the ratio of total data read to the actual data requested. We wanted 1 key-value pair. We had to touch 1000 files to find it.

As the number of SSTable files grows, read performance degrades linearly.

Problem: Duplicate Keys Waste Space

There is a second problem. Consider this write pattern:

PUT user_1 Alice     → flushed to SSTable 1
PUT user_1 Bob       → flushed to SSTable 2
PUT user_1 Charlie   → flushed to SSTable 3

Three SSTable files each contain a value for user_1. But only the newest value (Charlie in SSTable 3) matters. The entries in SSTables 1 and 2 are pure waste. They consume disk space but will never be returned to a reader.

This is called space amplification: the ratio of total storage used to the actual live data size. If a key is updated 100 times, we store 100 copies. Space amplification = 100x for that key.

Append-only writes are fast, but they accumulate garbage over time.

Solution: Merge Files Periodically

The idea is straightforward:

Read multiple SSTable files
For each key, keep only the newest value
Write a single compacted file with the deduplicated data
Delete the old files

Before compaction:
SSTable 1: [user_1=Alice, user_2=Bob]
SSTable 2: [user_1=Charlie, user_3=Dave]
SSTable 3: [user_2=Eve, user_4=Frank]

After compaction:
SSTable 5: [user_1=Charlie, user_2=Eve, user_3=Dave, user_4=Frank]

Fewer files means faster reads (less read amplification). Deduplicated keys means less wasted space (less space amplification).

But compaction introduces a new cost: write amplification. We are reading and rewriting data that has not changed. user_3=Dave and user_4=Frank were perfectly fine in their original files. We read them, wrote them again, and deleted the originals. This is extra I/O for data that was already correct.

Compaction trades write amplification for reduced read and space amplification.

This creates a three-way tension:

Read Amplification ←→ Write Amplification ←→ Space Amplification
       ↑                       ↑                      ↑
  (more files =             (compaction             (duplicates
   slower reads)             rewrites data)          waste space)

You cannot minimize all three simultaneously. Every compaction strategy is a different point in this tradeoff space.

Problem: When Do We Trigger Compaction?

If we compact after every single flush, we minimize read and space amplification but maximize write amplification because we are constantly rewriting data.

If we never compact, write amplification is zero but read and space amplification grow forever.

We need a middle ground. Think about what changes as you increase the threshold:

Threshold = 2: Almost every flush triggers compaction. You rewrite data constantly. Write amplification is very high for marginal read benefit.
Threshold = 4: You batch a few files before merging. Compaction happens less frequently, and you amortize the I/O cost across more files.
Threshold = 8 or 10: Compaction is rare, so write amplification is low. But reads degrade because you search through 8-10 files before compaction kicks in. And when compaction finally runs, it is a bigger burst of I/O.

Our implementation uses 4 as a simple learning threshold. Production systems use more sophisticated compaction policies.

Compaction Runs in the Background

Up until now, we have been discussing compaction at a conceptual level: what it does, why it helps, when to trigger it. The implementation is where things get interesting. Since compaction runs concurrently with reads and writes, we need to be careful about shared state.

Compaction is expensive. It reads all data blocks from multiple files, merges them, and writes a new file. We cannot block all reads and writes while this happens, so it runs in a background goroutine.

What is shared state?

Shared state means that multiple goroutines can read and write the same variables concurrently. Without a mutex lock, this leads to data races and unexpected behaviour.
Within compaction, the list of files, the index blocks and index offsets are all shared variables.

All of these follow the same access pattern: they are read by the Get function and written by flush during writes. We saw this in our previous blog. Now compaction adds another writer running in parallel, deleting old files and replacing them with new ones.

Side Note
go test -race ./... is a great way to identify shared state if we are not able to spot it ourselves.

Read and Write Locks

Before deep-diving into race condition and potential problems, we should be aware of the two ways of acquiring mutex locks: read (shared) locks and write (exclusive) locks.

Multiple processes can hold read locks on the same key simultaneously. But a write lock is exclusive, meaning no other process can hold any lock on that key while a write lock is active.

This is because, two readers cannot corrupt each other since neither is modifying data. But a writer must be alone because any concurrent reader would see a partially updated or inconsistent value.

Hence, from a performance perspective it is critical that we use write lock only when a write operation is being used.

Golang provides RLock and Lock in sync.Mutex package for read lock and write lock respectively. You will see more of this being used especially in the next blog where we will require acquiring locks within database rows.

Race Conditions Due To Shared State

Before diving into implementation, we need to better understand the shared state and potential race conditions that can come up.

Problem 1: New files can arrive mid-compaction

Let's say we start compacting files [1, 2, 3, 4]. While the merge is running, a new write triggers a memtable flush, creating file 5. File 5 was not part of our compaction. Compaction also created a file 6 as its output. If compaction blindly replaces the entire file list with its output, file 5 disappears and there is only a single file 6 with lost data.

Solution: Snapshot the file list before compaction starts
We snapshot the file list at the start. Snapshot here just means that we store the list of files being compacted in an in-memory variable. We also acquire a read lock while doing so.

Later, when we swap out old files and add the newly compacted file, we know exactly which files were part of compaction and should be deleted. Files that were not part of the snapshot (like file 5) are left untouched.

The entire swap operation should also be behind a write lock, since regular flushes could be happening at the same time.

Problem 2: Order of the files

In the last blog, we ensured that file names are monotonically increasing. This was important to identify the newest file. But in the above example, compaction's output file gets ID 6 (next auto-incremented), while the flush that happened during compaction created file 5. File 5 has the newest data but a lower numeric ID than file 6. File names are no longer an indicator of how new the data is.

Solution
We maintain a manifest.json file (and an in-memory reference) that tracks the expected search order. In the above case, the order should be [5, 6]: file 5 (newest data from the flush) is searched first, file 6 (compacted older data) is searched after.

Our swap function should update the file list in this order and persist it to manifest.json.

Problem 3: Two compactions can start at once

While compaction is running, a series of flushes happening in parallel can push the file count above the threshold again. Now two compactions are merging overlapping file sets.

Solution
We need a guard to ensure only one compaction runs at a time. We maintain a flag called compacting. A new compaction can only start when this flag is false.

compacting is itself a shared variable and should be read or written via a mutex lock. We set it to true when compaction starts and back to false when it ends. Our shouldRunCompaction function checks this flag in addition to checking the file count.

Problem 4: Readers might be using files we want to delete.

Let's say compaction finishes and wants to delete files 1 to 4. But a GET request is currently reading file 1's data block. If we delete the file now, that reader gets a corrupted read or a crash.

Solution
We need to make sure all in-flight reads are done before we swap out the old files. Our swap function takes a write lock before replacing the file list. Since readers hold a read lock for the duration of their Get call, the write lock blocks until every in-flight reader releases their lock. Only then does the swap proceed.

All four problems are solved with Go's sync.RWMutex and a compacting flag. Let's look at the implementation.

Implementation

When to trigger compaction

The compaction process should only start when memtable is being flushed to SSTable. We also require two additional checks: enough files to justify the cost (4 in this case), and no compaction already in progress.

Note that the go keyword in go db.ssTable.RunCompaction() in Golang is used to trigger a goroutine (a light-weight thread) in parallel in Golang.

func (db *DB) flushMemtableToSsTable() error {
    ssTableFile, err := db.ssTable.NewFile()
    if err != nil {
        return err
    }

    err = db.ssTable.Write(ssTableFile, db.memTable.Iterate)
    if db.ssTable.ShouldRunCompaction() {
        go db.ssTable.RunCompaction()
    }
    return err
}

func (st *SsTable) ShouldRunCompaction() bool {
    st.mutex.RLock()
    defer st.mutex.RUnlock()
    return !st.compacting && len(st.firstLevelFiles) >= 4
}

Compaction Logic

func (st *SsTable) RunCompaction() {
    // 1. Set compacting flag
    st.mutex.Lock()
    st.compacting = true
    st.mutex.Unlock()

    defer func() {
        st.mutex.Lock()
        st.compacting = false
        st.mutex.Unlock()
    }()

    // 2. Snapshot files to compact
    st.mutex.RLock()
    filesToCompact := make([]*os.File, len(st.firstLevelFiles))
    copy(filesToCompact, st.firstLevelFiles)
    st.mutex.RUnlock()

    // 3. Build compacted map
    compactedMap, err := st.buildCompactedMap(filesToCompact)
    if err != nil {
        return
    }

    // 4. Sort keys for ordered SSTable output
    sortedKeys := sortedKeys(compactedMap)

    // 5. Create iterator and write compacted file
    iterator := func(fn func(key, value string)) {
        for _, key := range sortedKeys {
            fn(key, compactedMap[key])
        }
    }
    compactedFile, _ := st.NewFile()
    compactedIndexOffset, compactedIndexBlock, _ := st.writeToFile(compactedFile, iterator)

    // 6. Atomic swap of file and index arrays
    st.atomicSwap(compactedFile, filesToCompact, compactedIndexBlock, compactedIndexOffset)

    // 7. Delete old files
    for _, file := range filesToCompact {
        file.Close()
        os.Remove(file.Name())
    }
}

Step 1 sets the compacting flag so that ShouldRunCompaction returns false for the duration. This prevents double compaction (problem 3).

Step 2 snapshots the file list under a read lock. This is the fix for the "new file arrives mid-compaction" problem (problem 1). Any files flushed after this point are not part of filesToCompact and will be preserved during the swap in step 6.

Steps 3-5 are the actual merge. buildCompactedMap reads all data blocks from the snapshotted files, oldest to newest. Since it iterates oldest-first, newer values for the same key naturally overwrite older ones in the map:

func (st *SsTable) buildCompactedMap(files []*os.File) (map[string]string, error) {
    compactedMap := map[string]string{}
    for _, file := range files {
        indexOffset, _ := st.getIndexOffset(file)
        buf := make([]byte, indexOffset)
        file.ReadAt(buf, 0)
        for i := 0; i < len(buf); {
            key, _ := extractValueFromSsTable(buf, i)
            i += (4 + len(key))
            value, _ := extractValueFromSsTable(buf, i)
            i += (4 + len(value))
            compactedMap[key] = value  // newer file's value overwrites older
        }
    }
    return compactedMap, nil
}

Step 6 is the most critical part. This is where we solve the concurrent reader problem (problem 4):

func (st *SsTable) atomicSwap(compactedFile *os.File, oldFiles []*os.File,
    compactedIndexBlock []indexBlockEntry, compactedIndexOffset int) {
    st.mutex.Lock()
    defer st.mutex.Unlock()

    oldFilesMap := map[string]bool{}
    for _, file := range oldFiles {
        oldFilesMap[file.Name()] = true
    }

    // Compacted file first (oldest data), then new files created during compaction
    swappedFiles := []*os.File{compactedFile}
    swappedIndexBlocks := [][]indexBlockEntry{compactedIndexBlock}
    swappedIndexOffsets := []int{compactedIndexOffset}

    for i, file := range st.firstLevelFiles {
        if !oldFilesMap[file.Name()] {
            swappedFiles = append(swappedFiles, file)
            swappedIndexBlocks = append(swappedIndexBlocks, st.indexBlocks[i])
            swappedIndexOffsets = append(swappedIndexOffsets, st.indexOffsets[i])
        }
    }

    st.firstLevelFiles = swappedFiles
    st.indexBlocks = swappedIndexBlocks
    st.manifest.FileNames = fileNames
    st.saveManifest()
}

The write lock ensures no reader is mid-read during the swap. Readers hold RLock during their entire read operation, so acquiring Lock here blocks until all in-flight reads complete. After the swap, new readers see the compacted file. Old readers have already finished.

The compacted file is placed first in the list because it contains the oldest data. Any files created during compaction (not in oldFilesMap) are appended after it. This preserves the newest-to-oldest search order that Get() relies on (solves problem 2).

After swap has successfully happened in step 6, we don't need the old files which got compacted and hence it is safe to delete them in step 7.

Benchmark Results

We benchmarked read performance with and without compaction. The setup writes repeated keys to generate duplicate entries, then the benchmark measures bulk Get operations (without compaction, with compaction):

Metric	With Compaction	Without Compaction	Improvement
Iterations	3,104	656	~4.7x more throughput
Time/op	386,022 ns	1,573,801 ns	~4.1x faster
Memory/op	203,957 B	848,196 B	~4.2x less memory
Allocs/op	3,459	13,429	~3.9x fewer allocations

The improvement is across the board. Without compaction, each read potentially searches through many more files. The extra file I/O shows up in time, memory (more buffers), and allocations.

Known Limitations

Our compaction implementation is simple and has several limitations worth acknowledging:

buildCompactedMap loads everything into memory. Production databases use streaming merge iterators that read entries from multiple files in sorted order without loading everything at once. Our approach works for small datasets but would blow up RAM with large ones.
No tombstones. We have no way to represent deletes. If a key is deleted, its old value still lives in SSTables until it happens to be overwritten. A proper implementation would write a tombstone marker that compaction can use to discard the key entirely.
No leveled compaction. We merge all L0 files into one. Production LSM trees like LevelDB and RocksDB use tiered or leveled compaction with multiple levels (L0, L1, L2...), where each level is progressively larger. This gives much better control over the amplification tradeoffs.

What's Next

We now have a complete storage engine:

WAL for durability
Memtable for fast in-memory writes
SSTables for efficient disk reads
Compaction to keep file count and duplicate keys manageable

These are the basics of a persisted key-value store. But for building a relational database, we need ACID guarantees and we have only focused on durability till now.

What happens when you need multiple writes to succeed or fail together? (Atomicity) What happens when two users read and write the same key concurrently? (Isolation)

In Part 4, we will build transactions with Two-Phase Locking: atomic multi-key writes, isolation from concurrent readers, and rollback on failure.

The code for SaarDB is available here:
GitHub: https://github.com/gagandeepahuja09/saardb

Building SaarDB, Part 2: LSM Trees

Gagandeep Singh Ahuja — Sat, 11 Jul 2026 07:16:25 +0000

In Part 1, SaarDB had two pieces:

a Write Ahead Log (WAL) for durability,
an in-memory map for serving reads and writes.

That works as a starting point, but it has limits.

The in-memory map cannot grow forever, we are bounded by RAM limitations.
Replaying a larger WAL on every startup gets slower.

So the next problem is:

How do we keep writes simple, but move older data into a searchable disk format?

Why WAL Alone Is Not Enough

WAL is fundamentally an append-only log. This is excellent for durability and sequential disk writes, but eventually it creates two major problems.

Problem 1: Repeated Keys

Imagine the following operations:

PUT user_1 Alice
PUT user_2 Bob
PUT user_1 Charlie
PUT user_1 David

The WAL now contains multiple values for the same key.

[user_1 -> Alice]
[user_2 -> Bob]
[user_1 -> Charlie]
[user_1 -> David]

But during reads, only the latest value matters.

user_1 -> David

As updates increase, the WAL keeps growing while also accumulating stale values. Even if we periodically delete stale values, another much bigger problem still remains.

Problem 2: Startup Gets Slow, and Memory Runs Out

Suppose the database has accepted millions of writes.

The WAL keeps growing on disk. The in-memory map also keeps growing because every live key-value pair is kept in RAM.

During normal reads, this is fast:

GET user_987654

The database can simply check the in-memory map.

But now imagine the process restarts.

To rebuild that in-memory map, the database has to read the WAL from the beginning and replay every write:

PUT user_1 Alice
PUT user_2 Bob
PUT user_1 Charlie
...

For a small WAL, this is fine.

For a huge WAL, startup becomes slow because the database must process a large file before it can serve reads. And after replay finishes, all live keys still need to fit in memory.

Could we avoid rebuilding the full in-memory map?

We can do that by reading directly from the WAL during GET.

But that is slow. The WAL is not sorted or indexed by key. It is just a long list of writes. So finding one key means scanning WAL entries one by one, on disk. And because older entries may be followed by newer updates for the same key, the database may need to keep scanning to know the latest value.

That turns every read into a linear search over a growing file.

So WAL alone gives us two bad choices:

Replay the entire WAL on startup and keep everything in memory.
Avoid replaying everything, but make reads slow because they must search through the WAL.

Neither works well once the data grows.

A WAL is great for remembering writes in order. It is not a good long-term format for searching keys.

So we need a second structure:

Keep recent writes in memory, but move older data to disk in a format that can be searched efficiently.

That disk format should help us quickly narrow down where a key may exist. The most common way to reduce search space efficiently is:

Binary Search

But this leads to another interesting problem.

The Real Challenge: How Do You Apply Binary Search On Disk?

Binary search is trivial in memory. Arrays support:

direct indexing,
constant-time jumps,
cheap random access.

Disk files do not naturally behave like arrays. The fundamental reason is that entries are variable-length. In an array, every element is the same size, so computing the position of the Nth element is trivial. But in a disk file storing key-value pairs, each entry can be a different size. Without reading and parsing every entry before it, there is no way to know where the Nth entry begins.

So the real challenge becomes:

How do we structure data on disk such that binary search becomes possible?

LSM (Log-Structured Merge) tree storage solves this using:

SSTables (on disk)
Memtables (in memory)

SSTable: Making Disk Reads Efficient

SSTable stands for Sorted String Table.
The key idea is simple:

Store keys on disk in sorted order to allow efficient search.

But applying binary search directly on one huge disk file is still not straightforward. So SSTables organize data carefully.

How SSTables Are Structured

Instead of storing one massive blob of sorted data, SSTables divide data into smaller blocks. Typically:

each block is bounded by size (for example ~100 KB),
keys inside each block remain sorted.

Example:

Data Block 1:
[user_1]
[user_2]
[user_3]

Data Block 2:
[user_4]
[user_5]
[user_6]

Data Block 3:
[user_7]
[user_8]
[user_9]

Notice something important:

All keys in Block 2 > all keys in Block 1
All keys in Block 3 > all keys in Block 2

This ordering enables efficient lookup.

The Index Block: The Real Enabler

Each SSTable also contains an Index Block. The index block stores:

the starting key of every data block,
the offset of that block inside the file.

Example:

user_1 -> offset 0
user_4 -> offset 1024
user_7 -> offset 2048

Now suppose we want:

GET user_5

We first load the index block into memory.

Then we binary search the block-start keys:

user_1, user_4, user_7

The largest key less than or equal to "user_5" is:

user_4

So we immediately know:

If "user_5" exists, it must exist in the block starting with "user_4".

Instead of searching the entire SSTable, we reduced the search space to a single block. This is the core idea behind SSTables.

Once the correct block is found, entries within the block are scanned sequentially till we either find the required key (key found case) or till the entire block is completely read (key not found case).

This leads us to the core lookup rule used in SSTables:

Find the largest block-start key less than or equal to the input key.

SSTable File Layout

A typical SSTable layout looks like this:

+-------------+
| Data Block 1|
+-------------+
| Data Block 2|
+-------------+
| Data Block 3|
+-------------+
| Index Block |
+-------------+
| Footer      |
+-------------+

Why Do We Need A Footer?

Interesting problem:

How do we know where the index block starts?

The index block is usually near the end of the file. But during reads, we don't want to scan the entire file just to find it.

So SSTables store a small Footer Block at the end. Index block can of variable bytes, hence there is no way to know the position of index block until we store the index block offset. On the other hand, if we store the index block offset at the start (header) or end (footer) of the file, we can easily find the index block offset. This is because header and footer are fixed positions in the file.

The footer typically contains:

index block offset,
metadata about the SSTable.

This allows readers to directly jump to the index block.

Memtable: How Data Enters the SSTable

SSTables require their keys to be sorted. So how does data get into an SSTable in sorted order?

This is where the Memtable comes in. A Memtable is simply an in-memory sorted map.

In-memory means we are bounded by RAM. We cannot keep writing to memory indefinitely. At some point, data must be written to disk.

Sorted is what makes the flush to disk efficient. Because the Memtable maintains keys in order, when it is time to write an SSTable, the data is already sorted. There is no need for an expensive sort step. The Memtable simply iterates its keys in order and writes them out sequentially.

The primary purpose of keeping the Memtable sorted is not to speed up reads. It is to make the flush to SSTable efficient.

Whenever writes arrive:

They are appended to WAL for durability.
They are inserted into Memtable for fast reads/writes.

Because Memtable is sorted, keys are always maintained in order. Example:

user_1  -> Alice
user_2  -> Bob
user_3  -> Charlie
user_4  -> David

But we cannot keep growing Memtable forever because RAM is limited. So eventually:

Memtable is flushed to disk as an SSTable.

Write Path

Now let's connect the intuition with implementation.

Challenge: How Do We Flush a Memtable to an SSTable?

When Memtable reaches a size threshold:

a new SSTable file is created,
Memtable contents are written in sorted order,
Memtable is reset.
WAL can be cleared because those key-values no longer need to be replayed from the log.

Since Memtable is already sorted, SSTable creation becomes efficient.

Writing Data Blocks

While flushing:

Memtable keys are iterated in sorted order.
Key-value pairs are written sequentially into data blocks.
Once the block size threshold is reached, a new block is started.

This is different from the Memtable threshold. The Memtable threshold decides when a flush starts. The block threshold only decides how the new SSTable file is split into smaller data blocks.

During the part 1, we saw the following encoding format while writing to disk:

[length_of_key][key][length_of_value][value]

Example:

[5][apple][2][10]

Length prefixes are important because:

keys and values are variable-sized

Indicating length of the key before the start of the key enables readers to know how many bytes to read.

While writing data blocks, we also maintain:

block starting key,
block offset.

These are later used to build the index block.

Here is the core loop from our implementation (sstable/sstable.go) that writes data blocks:

iteratorFunc(func(key, value string) {
    if blockFirstKey == "" {
        blockFirstKey = key
    }
    // [length_of_key][key][length_of_value][value]
    ssTableEntryBuf := []byte{}
    ssTableEntryBuf = binary.BigEndian.AppendUint32(ssTableEntryBuf, uint32(len(key)))
    ssTableEntryBuf = append(ssTableEntryBuf, []byte(key)...)
    ssTableEntryBuf = binary.BigEndian.AppendUint32(ssTableEntryBuf, uint32(len(value)))
    ssTableEntryBuf = append(ssTableEntryBuf, []byte(value)...)
    offset += len(ssTableEntryBuf)
    blockLength += len(ssTableEntryBuf)
    ssTableBlockBuf = append(ssTableBlockBuf, ssTableEntryBuf...)
    if blockLength > st.blockLength {
        // one data block completed
        indexBlock = append(indexBlock, indexBlockEntry{
            key:    blockFirstKey,
            offset: blockStartOffset,
        })
        file.Write(ssTableBlockBuf)

        // start new block
        blockStartOffset = offset
        blockFirstKey = ""
        blockLength = 0
        ssTableBlockBuf = []byte{}
    }
})

Notice how this single loop handles the work inside a Memtable flush: length-prefix encoding each entry, accumulating entries into a block buffer, writing the current data block to the SSTable file when the block size threshold is exceeded, and tracking the first key and offset for the index block.

Writing Strategy: Preserving Sequential Writes

One of the biggest reasons WAL performs well is that it relies on append-only sequential disk writes. SSTable creation preserves this exact property. During a Memtable flush, we create a new file and write data blocks, then the index block, then the footer. All are written sequentially, never going back to modify earlier parts of the file:

    [Data Blocks][Index Block][Footer Block]

So even though SSTables solve the problem of efficient reads, they still preserve the append-only write pattern that made WAL fast in the first place.

Writing Index Block And Footer Block

Using the same length-prefix encoding from data blocks, each index block entry stores:

the starting key of a data block,
the offset of that block within the SSTable file.

This leads to the following structure:

[length_of_start_key][start_key][offset]

Notice an important distinction here.

The start_key is variable-sized, so we prefix it with its length.

However, offset is a fixed-size unsigned 32-bit integer.

Since the size of the offset is already known during reads, we do not need to prefix it with a length.

This leads to an important encoding rule commonly used in storage systems:

Variable-sized data types usually require length prefixes.

Fixed-sized data types usually do not.

The footer block follows the same idea.

Since the footer only stores the index block offset, its structure simply becomes:

[index_offset]

During reads, this footer allows us to directly jump to the index block without scanning the entire SSTable.

Read Path

Problem: A Key Can Exist In Multiple Places

An interesting property of LSM Trees is that the same key can exist:

in Memtable,
in multiple SSTables,
and potentially with different values.

This happens because updates do not immediately overwrite older values on disk.

For example:

PUT user_1 Alice
PUT user_1 Charlie
PUT user_1 David

Older SSTables may still contain stale values:

SSTable 1 -> user_1 = Alice
SSTable 2 -> user_1 = Charlie
Memtable  -> user_1 = David

During reads, only the latest value matters.

So while serving a GET key query, the database must search in an order that guarantees the newest value is found first.

This leads to the following mental model for reads:

Memtable -> Newest SSTable -> Older SSTables

As soon as the key is found, the search stops.

Challenge: How Do We Search Efficiently Inside An SSTable?

Naively reading:

footer,
then index block,
during every query would still create repeated disk reads.

So databases usually cache:

index blocks,
metadata,
file handles in memory.

This makes reads significantly faster.

Searching Inside A File

Once the index block is in memory, searching an SSTable for a key involves four steps:

Step 1: Binary search the index block. We use the same "largest key less than or equal to the input" rule from earlier.

Step 2: Calculate the exact byte range to read. Once we know which data block to search, we need to figure out:
* where it starts and
* ends on disk.
The start offset comes directly from the matched index entry. The end offset comes from the next index entry's offset. Or if this is the last data block, the end offset is the start of the index block itself (which we already stored in memory during startup).

Step 3: Read only that one block from disk. This is the key insight. We use file.ReadAt() golang function to read exactly the bytes between the start and end offsets. We are not reading the entire file. We are not even reading from the beginning of the file. We jump directly to the relevant block.

Step 4: Sequential scan within the block. Once the block is in memory, we decode entries one by one using the length-prefix format. Which is to:
* read the key length,
* read that many bytes for the key,
* read the value length,
* read that many bytes for the value
* and then check if the key matches.

Here is the Get() function from our implementation (sstable/sstable.go):

func (st *SsTable) Get(key string) (string, error) {
    // newest file to oldest file
    for i := len(st.firstLevelFiles) - 1; i >= 0; i-- {
        file := st.firstLevelFiles[i]
        ssTableIndex := st.indexBlocks[i]
        lowerBoundSliceIndex := getLowerBound(key, ssTableIndex)
        if lowerBoundSliceIndex == -1 {
            continue
        }
        endOffset := st.indexOffsets[i]
        if lowerBoundSliceIndex < len(ssTableIndex)-1 {
            endOffset = ssTableIndex[lowerBoundSliceIndex+1].offset
        }
        value, err := st.getValueFromSsTableDataBlock(file, key,
            ssTableIndex[lowerBoundSliceIndex].offset, endOffset)
        if value == "" && err == nil {
            continue
        }
        return value, err
    }
    return "", nil
}

A few things to notice:

Reverse iteration (len - 1 down to 0): Newest files are searched first so that the most recent value for a key is found first.
getLowerBound returning -1: The key is smaller than every block-start key in this file. No point reading any block, so we continue to the next file.
endOffset calculation: If the matched block is the last data block, the end offset defaults to indexOffsets[i]: the start of the index block. Otherwise, it uses the next index entry's offset. This gives us the precise byte range for the block we need to read.
continue on empty value with no error: The key wasn't found in this file's candidate block, so we try the next (older) file.

If we exhaust all files without finding the key, Get() returns an empty string with no error. Which just means that the key simply doesn't exist in the database.

Startup: Preparing SSTables for Reads

Earlier, we saw that SSTable reads depend on two things being ready in memory for efficient reads:

open file handles,
index blocks.

We need to prepare both of them during database startup.

1. Open existing SSTable files. These files were created by earlier Memtable flushes. The database opens them in the order it needs for reads.

2. Keep file handles open. Instead of opening and closing files on every Get(), the database keeps handles ready for reuse.

3. Load index blocks into memory. For each SSTable, it reads the footer, which is exactly the last 4 bytes of the file. That footer tells us where the index block starts. Then the database reads that index block and parses it into memory.

This is the function that loads the index block for one SSTable file:

func (st *SsTable) buildIndexFromFile(file *os.File) (int, []indexBlockEntry, error) {
    info, err := os.Stat(file.Name())
    if err != nil {
        return 0, nil, err
    }
    fileSize := info.Size()
    indexOffset, err := st.getIndexOffset(file)
    if err != nil {
        return 0, nil, err
    }

    indexBlockLength := (fileSize - 4) - int64(indexOffset)
    indexBlockBuf := make([]byte, indexBlockLength)
    if _, err = file.ReadAt(indexBlockBuf, int64(indexOffset)); err != nil {
        return 0, nil, err
    }

    ssTableIndex := []indexBlockEntry{}
    for i := 0; i < int(indexBlockLength); {
        keyLengthBuf := indexBlockBuf[i : i+4]
        keyLength := binary.BigEndian.Uint32(keyLengthBuf)

        i += 4
        key := string(indexBlockBuf[i : i+int(keyLength)])

        i += int(keyLength)
        offsetBuf := indexBlockBuf[i : i+4]
        offset := binary.BigEndian.Uint32(offsetBuf)

        ssTableIndex = append(ssTableIndex, indexBlockEntry{key: key, offset: int(offset)})
        i += 4
    }
    return int(indexOffset), ssTableIndex, nil
}

Footer read: getIndexOffset reads the last 4 bytes to find where the index block starts.
Precise byte range: reads exactly the bytes between indexOffset and fileSize - 4: no more, no less.
Same length-prefix decoding: the loop mirrors the data block decoding pattern: 4-byte key length, key bytes, 4-byte offset and builds the in-memory index entry by entry.

After this, the earlier Get() implementation has everything it expects: file handles it can reuse and index blocks it can search without first scanning the SSTable file.

Replaying WAL into the Memtable

SSTables cover data that has already been flushed. But writes after the last flush still live only in the WAL.

This is the same recovery idea from Part 1. On startup, SaarDB replays WAL entries from oldest to newest.

The only difference is the target:

in Part 1, replay rebuilt a plain in-memory hashmap,
now, replay rebuilds the current Memtable.

Because the Memtable is sorted, those replayed writes are immediately ready for reads and for the next SSTable flush.

After startup, the full picture is:

recent writes: rebuilt from WAL into the Memtable,
older writes: already stored in SSTables,
SSTable index blocks: loaded into memory for reads.

What's Next

At this point, we have a working storage engine. WAL gives us durability. Memtable gives us fast in-memory writes with sorted ordering. SSTables give us efficient disk lookups using index blocks and binary search. And on startup, all the index blocks are pre-loaded so that reads only touch one candidate data block per SSTable checked.

But several problems remain:

The number of SSTable files keeps growing. Every Memtable flush creates a new file. Over time, the number of files on disk keeps increasing.
Duplicate keys accumulate across files. If a key is updated 100 times, 100 different SSTable files may contain a value for it. Only the newest matters. The rest are wasted space.
Reads slow down. Every Get() call may need to search through more and more files before finding the key (or confirming it doesn't exist).
Deletes don't exist yet. In an append-only system, what does "delete" even mean? We can't go back and erase a key from an already-written SSTable file.

In upcoming parts, we will cover:

Compaction: to be covered in part 3: merging multiple SSTables into fewer, larger ones, eliminating duplicates and reclaiming space.
Tombstones: a way to represent deletes in an append-only world.
Bloom filters: a probabilistic data structure that lets us skip SSTable files that definitely don't contain a key, without reading anything from them.
Tuning flush size and block size: how large should the Memtable grow before flushing? How large should each data block be? These are not arbitrary choices and involve careful tradeoffs.

Building SaarDB, Part 1: Write-Ahead Log (WAL)

Gagandeep Singh Ahuja — Sat, 04 Jul 2026 17:08:25 +0000

SaarDB is a learning project: build a relational database from first principles in Go, one layer at a time.

The goal is not to build a production database. The goal is to make database internals feel intuitive by building the core ideas directly and explaining the tradeoffs along the way.

When we think of a relational database, it is tempting to start with SQL parsing, tables, data types, and query execution. But that starts with the interface before understanding the storage layer underneath it.

So Part 1 starts smaller: a key-value store. From there, we will hit the first serious database problem: how do we make writes survive a crash?

Where to Start: Why a Key-Value Store?

The initial instinct may be to start with the query layer. This includes SQL parsing, operations like CREATE TABLE, multiple data types, and so on. But the storage layer is the foundation beneath all of that.

The key insight is that:

A key-value store can be extended to support everything a relational database needs.

This can feel surprising at first. How can a relational database, with tables and rows and SQL, start from something as small as key-value operations?

The reason for this is that every SQL operation can be mapped to a key-value operation. For example:

CREATE TABLE payments (...) can be mapped to storing the schema as a value under key _schema:payments. The value can be stored in a serialized manner and can be deserialized when we need to read it.
INSERT INTO payments VALUES (1, 500, 'pending') can be mapped to a PUT operation: PUT payments:1 <serialized_row>. This design also ensures efficient lookup by primary key.

If this mapping still feels abstract, that is fine. Later posts will come back to this when we build more of the SQL layer on top of the storage engine.

Starting Simple: An In-Memory Key-Value Store

Whatever problem we are solving, we start with the simplest thing that works.

Correctness before performance. Performance before scale.

The simplest database is a hashmap in memory to support GET and PUT commands. We will build a REPL (Read-Eval-Print-Loop) around it so users can interact via the command line.

Building the REPL

A REPL is just a loop: accept input, process it, print the result, repeat. In Go, bufio.Scanner reads from STDIN line by line:

func main() {
    db := map[string]string{}
    scanner := bufio.NewScanner(os.Stdin)
    for scanner.Scan() {
        line := scanner.Text()
        args := strings.SplitN(line, " ", 3)
        cmd := args[0]
        switch cmd {
        case "GET":
            fmt.Println(db[args[1]])
        case "PUT":
            db[args[1]] = args[2]
        case "EXIT":
            return
        default:
            fmt.Println("command not supported")
        }
    }
}

This works. We can store and retrieve data. But there is an obvious problem.

The First Problem: Memory Is Volatile

If we kill the process and restart it, everything is gone. The hashmap lived in memory and memory does not survive process restarts.

How do we make data survive crashes?

This is the problem of durability: guaranteeing that once a write succeeds, the data is permanently saved.

The answer is straightforward: write to disk. Memory is volatile. Disk is not. But this raises a new question.

Choosing the Write Order

For every PUT, we need two updates:

Write to disk so the data survives a crash.
Write to the in-memory map so reads are fast.

The order matters.

If we update memory first, there is a dangerous window where memory contains data that disk does not. If the process crashes in that window, the update disappears after restart.

Even without a crash, if the disk write fails after the memory update, we now have to undo the memory change. That makes the write path more complicated.

If we write to disk first, the rule is simpler: only update memory after the durable write succeeds.

So the rule is: write to disk first, then update memory.

Why Append-Only Writes Help

There is a golden rule for database performance:

Sequential writes are significantly faster than random writes.

Let's go over what sequential and random writes actually are and why that is the case.

Sequential write means that while writing data, we write in such a way that the data is stored in adjacent blocks on the storage drive.

On the other hand, random write means that the data is written in a scattered way across non-contiguous locations.

For HDDs, random writes are slow because the disk head has to physically jump around. SSDs do not have a moving head, but the file-write pattern still matters.

Consider two updates to the same key:

PUT user_1 Alice
PUT user_1 Bob

Suppose the file already contains:

[user_1 = Alice]

Now we want to update user_1 to Bob. If we overwrite the old value in place, we first have to find the old bytes, check whether the new value fits in the same space, and handle the case where it does not.

A simpler approach is to never rewrite old bytes. Just append the new value to the end of the file and treat the latest value as the source of truth:

[user_1 = Alice]
[user_1 = Bob]

The fastest possible write pattern is append-only: always add data to the end of the file, never go back to modify earlier data.

Yes, we store the key twice. That is wasted space. But the write is fast, and we know the latest value is always at the end. We will deal with the duplication problem later.

This append-only file is called a Write-Ahead Log (WAL).

Encoding WAL Entries

We need to write a command like PUT user_1 Alice to the file. The naive approach is to use a separator like a space or newline:

PUT user_1 Alice\n
PUT user_2 Bob\n

This looks readable, but it hides two different problems.

Problem 1: Where Does One WAL Record End?

Suppose the value contains a newline:

PUT user_1 Alice
Bob

If our WAL reader treats newline as the end of an entry, it will think Bob is a separate command. So the first thing we need is a way to say: this WAL record is exactly N bytes long.

The solution is a length prefix around the whole WAL payload:

[wal_payload_length][wal_payload]

Here is a concrete byte-level example. Suppose the WAL payload is "PUT a 1" (7 bytes):

[00 00 00 07][50 55 54 20 61 20 31]
 └─ length ─┘└──── WAL payload ────┘
     = 7        P  U  T     a     1

The WAL reader knows: read 4 bytes for the length (7), then read exactly 7 bytes for the payload. This removes ambiguity about where this WAL record ends.

In plain English: the first 4 bytes say, "the next chunk is 7 bytes long."

That solves record boundaries. But it does not yet solve how to parse the command inside the payload.

Problem 2: How Do We Parse the Command Inside the Payload?

If the payload itself is still a string like this:

PUT user_1 Alice Bob

we are back to the same problem. Is the value Alice? Or is the value Alice Bob?

So the payload also needs length prefixes for its internal fields:

[cmd_len][cmd][key_len][key][value_len][value]

For example, PUT user_1 "Alice Bob" becomes:

[3][PUT][6][user_1][9][Alice Bob]

The exact bytes use 4-byte integers for the lengths, but conceptually this is the format. First we read the command, then the key, then the value. Spaces and newlines inside the value are just bytes; they do not confuse the parser.

In Go, the write flow looks like:

func appendLengthPrefixedString(buf []byte, value string) []byte {
    buf = binary.BigEndian.AppendUint32(buf, uint32(len(value)))
    buf = append(buf, []byte(value)...)
    return buf
}

func serialisePutCommand(key, value string) []byte {
    buf := []byte{}
    buf = appendLengthPrefixedString(buf, "PUT")
    buf = appendLengthPrefixedString(buf, key)
    buf = appendLengthPrefixedString(buf, value)
    return buf
}

Think of buf as a growing byte slice: a resizable list of bytes. For each field, we first append its 4-byte length, then append the actual bytes.

And for reading one length-prefixed field:

func readLengthPrefixedString(buf []byte, offset *int) (string, error) {
    valueLen := binary.BigEndian.Uint32(buf[*offset : *offset+4])
    *offset += 4

    value := string(buf[*offset : *offset+int(valueLen)])
    *offset += int(valueLen)
    return value, nil
}

Here, offset is just a cursor. It remembers where the next field starts inside the byte slice.

The important idea is that we use length prefixes at two levels:

The WAL layer frames the whole record.
The database command layer frames the fields inside that record.

This pattern of [length][data] shows up everywhere in storage systems. We will use it again in future blogs.

Handling Partial Writes

Let's consider this scenario:

We start writing a 100-byte payload
The OS writes the 4-byte length header: [00 00 00 64]
The process crashes after writing only 50 bytes of the payload

The file now contains:

...[valid entries]...[00 00 00 64][50 bytes of partial data]

This is where the length prefix helps. Because the payload length is written before the payload, the reader knows exactly how many bytes to expect:

[wal_payload_length][wal_payload]

The writer side looks like this:

func (w *Wal) WriteEntry(payload []byte) error {
    buf := make([]byte, 4+len(payload))
    binary.BigEndian.PutUint32(buf[0:4], uint32(len(payload)))
    copy(buf[4:], payload)

    _, err := w.file.Write(buf)
    return err
}

Here, buf[0:4] stores the length header. buf[4:] stores the payload right after it.

The reader uses the length to read exactly the expected number of bytes:

func (w *Wal) ReadEntry() ([]byte, error) {
    lengthBuf := make([]byte, 4)
    _, err := io.ReadFull(w.file, lengthBuf)
    if err == io.EOF {
        return nil, io.EOF
    }
    if err == io.ErrUnexpectedEOF {
        return nil, errors.New("partial write: incomplete length")
    }
    if err != nil {
        return nil, err
    }

    payloadLength := binary.BigEndian.Uint32(lengthBuf)

    payload := make([]byte, payloadLength)
    _, err = io.ReadFull(w.file, payload)
    if err == io.ErrUnexpectedEOF {
        return nil, errors.New("partial write: incomplete payload")
    }
    if err != nil {
        return nil, err
    }

    return payload, nil
}

If the length says 100 bytes but only 50 bytes exist, io.ReadFull returns io.ErrUnexpectedEOF. That tells us the last WAL record was only partially written.

Detecting Corrupted Bytes

A partial write is about missing bytes.

A corrupted write is different: all bytes may be present, but some bytes are wrong. This is not just a theory. Disks, SSDs, filesystems, OS crashes, power loss, and storage controllers can all fail in ways that leave bad bytes behind.

Most writes work fine. But databases are built for the cases where bytes are missing or wrong. The length prefix catches missing bytes. It does not prove that the bytes we read are the correct bytes.

How does the reader know the bytes are correct?

A checksum solves this. A checksum is a small fingerprint computed from data. If the payload bytes are the same, the checksum will be the same. If even one byte changes accidentally, the checksum will most likely change.

For example, suppose the writer stores this payload:

PUT user_1 Alice

The writer computes a checksum from these bytes and stores it next to the payload. Later, if the payload somehow becomes:

PUT user_1 Aljce

the length may still be valid, but the checksum will likely be different. That tells us the payload bytes are not trustworthy.

Now we extend the same WAL record by adding a 4-byte checksum at the end:

[wal_payload_length][wal_payload][checksum]

This problem is commonly solved in storage systems using CRC32, which is a fast checksum algorithm. The writer computes the CRC32 checksum over the payload bytes and appends it. The reader reads the payload, independently computes the checksum, and compares it with the stored checksum.

On the writer side, the length and payload logic stays the same. We only add space for the checksum, compute it from the payload, and append it:

func (w *Wal) WriteEntry(payload []byte) error {
    buf := make([]byte, 4+len(payload)+4)

    // ...same length and payload writes as before...
    binary.BigEndian.PutUint32(buf[0:4], uint32(len(payload)))
    copy(buf[4:4+len(payload)], payload)

    // New part: append checksum after the payload.
    checksum := crc32.ChecksumIEEE(payload)
    binary.BigEndian.PutUint32(buf[4+len(payload):], checksum)

    _, err := w.file.Write(buf)
    return err
}

buf[4+len(payload):] means "start writing after the 4-byte length header and the payload." That is where the checksum goes.

With length prefixes and checksums together, the reader can handle these failure modes:

Incomplete length (less than 4 bytes written): io.ReadFull returns io.ErrUnexpectedEOF. We know this is a partial write.
Incomplete payload: Length says 100 bytes but only 50 exist. Same error.
Incomplete checksum: Payload looks complete but checksum is truncated.
Corrupted data: All bytes present but checksum does not match. Data is bad.

After the reader has already read the length and payload, the checksum check is the extra part:

// ...same length and payload reads as before...

checksumBuf := make([]byte, 4)
_, err = io.ReadFull(w.file, checksumBuf)
if err == io.ErrUnexpectedEOF {
    return nil, errors.New("partial write: incomplete checksum")
}
if err != nil {
    return nil, err
}

storedChecksum := binary.BigEndian.Uint32(checksumBuf)
computedChecksum := crc32.ChecksumIEEE(payload)
if storedChecksum != computedChecksum {
    return nil, errors.New("corrupt: checksum mismatch")
}

return payload, nil

The intended recovery strategy is: if we detect a partial write at the end of the file, we can truncate it because it was the last write that did not complete. In the current implementation, we detect and return the error first; truncating the partial tail is a follow-up cleanup. On the other hand, if corruption is detected mid-file, that is a more serious problem (bit rot, hardware failure) that requires manual intervention.

Making Writes Actually Reach Disk

There is one more subtlety. Consider this code:

file.Write(buf)
// process reports "write successful"
// power goes out

Did the data actually reach the disk? No, not necessarily.

When we call file.Write(), the OS copies the data into a page cache (a buffer in RAM). The OS returns success immediately. It will eventually flush the page cache to the physical disk, but "eventually" might be seconds or minutes later. If power fails before that flush, the data is gone despite Write() returning success.

file.Write() guarantees the data reached the OS. It does not guarantee the data reached the disk.

The solution is fsync:

file.Write(buf)
file.Sync() // forces OS to flush page cache to physical disk

file.Sync() (which calls the fsync system call) blocks until the OS confirms the data is on the physical storage device. Only after Sync() returns, we can be confident that the data is durable.

There is a tradeoff though. fsync is expensive. On an HDD, it can take 5-10ms. On an SSD, it is faster but still significant. Calling it after every single write gives maximum durability but reduces throughput. Production databases like PostgreSQL batch multiple writes before a single fsync, trading a small window of vulnerability for much higher throughput.

For our database, we call file.Sync() after every WAL entry. This means maximum safety and simpler reasoning but with performance tradeoff.

The Write Path

Now we can put it all together. When a user calls PUT key value:

Serialize the command payload into bytes: [cmd_len][cmd][key_len][key][value_len][value]
Append it as a WAL record: [wal_payload_length][wal_payload][checksum] and fsync
Insert into the in-memory hashmap

func (db *DB) Put(key, value string) error {
    // Step 1-2: Write to WAL (disk first)
    walPayload := serialisePutCommand(key, value)
    if err := db.wal.WriteEntry(walPayload); err != nil {
        return err
    }
    // Step 3: Write to memory
    db.data[key] = value
    return nil
}

The WAL write happens first (disk before memory). If it fails, we return an error so that the user knows the write did not succeed.
If the process crashes after the WAL write but before the in-memory map is updated, the data is safe on disk and will be recovered on restart.

The Read Path

Reads are simple right now. We just look up the in-memory map:

func (db *DB) Get(key string) (string, error) {
    value, ok := db.data[key]
    if !ok {
        return "", nil // key not found
    }
    return value, nil
}

The WAL is never read during normal operation. It is purely a durability mechanism for writes. The in-memory map serves all reads.

Application Init: Rebuilding State from WAL

When the database process starts, the in-memory hashmap is empty. But the WAL on disk contains every write since the last checkpoint. We need to replay it:

func (db *DB) buildInMemoryMapFromWal() (map[string]string, error) {
    data := map[string]string{}
    for {
        payload, err := db.wal.ReadEntry()
        if err == io.EOF {
            return data, nil // reached end of WAL
        }
        if err != nil {
            return nil, err // corruption or partial write
        }

        offset := 0
        cmd, err := readLengthPrefixedString(payload, &offset)
        if err != nil {
            return nil, err
        }
        if cmd == "PUT" {
            key, value, err := deserialisePutCommand(payload, &offset)
            if err != nil {
                return nil, err
            }
            data[key] = value
        }
    }
}

This is the only time the WAL is read. The loop reads entries from oldest to newest.
For duplicate keys, the newest value naturally overwrites the older one in the hashmap, which is exactly the behavior we want.

After replay, the in-memory map contains the same state as before the crash. The database is ready to serve reads.

The full initialization sequence:

Open WAL file
Replay all WAL entries into a fresh in-memory map
Start accepting reads and writes

What's Next

WAL gives us durability and fast writes (append-only, sequential). Reads go through the in-memory hashmap.

But we run into multiple issues at scale.

The WAL grows forever. Every update to the same key adds another entry, leading to a lot of redundant data.
An in-memory hashmap gives us O(1) lookups but cannot scale beyond RAM.
Replaying the entire WAL during application startup becomes painfully slow.

In Part 2, we will introduce LSM trees, which solve these problems by adding sorted in-memory structures and searchable disk files.

The code for SaarDB is available here:
GitHub: https://github.com/gagandeepahuja09/saardb