Segment Merging (Compaction)

You’ve built a robust, thread-safe, immutable search engine.

But over time, performance starts to degrade. Search latency increases from 10 ms to 2,000 ms, and the operating system begins terminating the process with a Too many open files error.

Why? Because every time your 5-document RAM buffer filled up, you flushed a new segment file. You now have 50,000 tiny segment files on disk. Every time a user searches, your engine has to open and scan 50,000 separate files.

Furthermore, your .del tombstone file has grown to 500MB because 50% of the documents in your index have been deleted, but their raw bytes are still wasting space inside those immutable segments.

We need Log-Structured Merge Compaction.

The Concept

Because flushing creates many small files over time, real engines use a background process called a MergePolicy to clean things up. It combines several small segment files into one larger segment file. Crucially, during this process, it physically strips out any documents that were marked as deleted in the Tombstone set. (This physical removal is the “hard delete” that finally makes us GDPR compliant!)

Your Task

1. Merge Endpoint (POST /merge): Add this endpoint. (In reality this happens automatically in a background thread, but we use an endpoint so the test runner can trigger it deterministically).
2. Combine Data: When called, read every single segment file from disk into memory.

   Note

   Wait, read everything into memory? For now, yes. You can just deserialize all segments into a giant Hash Map in RAM, combine them, and write it back. The next lessons will teach you how to avoid this.

3. Purge Tombstones: As you combine the Inverted Indices, drop any Document IDs that exist in your .del Tombstone set. Do not include their stats in the new N or avgdl.
4. Write New Segment: Write this newly combined, fully-purged Inverted Index back to disk as a single new segment file.
5. Cleanup: Delete all the old, tiny segment files from disk. Empty your Tombstone set (and delete the .del file).

Return 200 OK.

Tip

After merging, your search engine should behave exactly as it did before, but it will only be reading from 1 file instead of 50,000, and the deleted data will finally be physically gone.

Important

Run the below docker command to test your solution.

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 merging