Building SaarDB, Part 3: Compaction

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:

1. Read multiple SSTable files
2. For each key, keep only the newest value
3. Write a single compacted file with the deduplicated data
4. 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):

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:

1. 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.

2. 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.

3. 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