The K-Way Merge (Optimal Compaction)

Remember our /merge endpoint from Segment Merging (Compaction)? We were loading all segment files into a giant RAM Hash Map, combining them, and writing them out. Indexes can grow to hundreds of GigaBytes, or even TeraBytes!

A user just triggered a merge on a 50GB index and the server OOM crashed instantly.

Streaming Compaction

Because our segment files are now strictly sorted alphabetically line-by-line (thanks to Alphabetical Segments & Disk-Seeking), we can perform a streaming K-Way Merge. This is the exact algorithm Lucene uses to merge terabytes of data using almost zero RAM.

Instead of loading files into RAM, we load Iterators. An Iterator just holds a pointer to a file and fetches one line at a time. By comparing the current line of K iterators, we can merge infinite amounts of data!

Concurrent Merging (Background Compaction)

Concurrent Merging: Real engines run compaction algorithms asynchronously in the background so writes are never blocked.

If a merge takes 5 minutes to complete on a 100GB index, your /merge HTTP endpoint cannot block for 5 minutes. It must spawn a background thread/goroutine to perform the compaction and immediately return a 200 OK (or 202 Accepted) to the user.

Your Task

Rewrite your /merge endpoint logic to use a background K-Way merge:

1. Async Trigger: When POST /merge is called, spawn a background thread to do the work and return the HTTP response immediately so the API remains responsive.
2. Setup Iterators: Open a file reader/iterator for every single segment file. Read the very first line (term) from each file into an array (or a Min-Heap) of “current values”.
3. Find the Smallest: Look at the current term for each iterator and find the alphabetically smallest term among all of them (e.g., apple is smaller than banana).
4. Merge Duplicates & Tombstones:
   • What if apple is the smallest term, but it exists in 3 different segment files? You must combine their postings lists together!
   • Crucially, if any Document IDs in those postings lists exist in your .del Tombstone set, drop them permanently. This is how you purge deleted data from the disk!
5. Write & Record: Write the finalized, combined postings list for apple to the new segment file. Record its new byte offset in your RAM Term Dictionary.
6. Advance: Advance the iterators that held apple so they read their next line.
7. Repeat: Loop from step 3 until all files reach EOF.
8. Cleanup: Delete the old segment files and clear your Tombstone set.

Important

Run the below docker command to test your solution. Note: The test runner will trigger the /merge endpoint and then wait for 1 second before querying the index. Your background thread must complete the merge within this 1000ms window!

docker run \
  --rm \
  --add-host host.docker.internal:host-gateway \
  -v /tmp/buildit_segments:/file_serving \
  codeberg.org/level0/buildit/search-engine:latest \
  --addr host.docker.internal:8080 \
  --until k_way_merge