Tombstones & Deletions

Till now we have only added documents to our engine. What about deleting them?

But wait. In the Lucene architecture, our segment files on disk are completely immutable. They are read-only. How do you delete data from a read-only file without rewriting the entire file and blocking concurrent searches?

You don’t.

Instead of actually deleting the data, we use a Write-Once strategy with Soft Deletes (Tombstones).

The Concept

When a deletion request comes in, we don’t touch the immutable segments. We simply record the Document ID in a “Tombstone Set”.

When a search query runs, we still find the deleted document in the segment file, but before we score it and add it to our Min-Heap, we check the Tombstone Set. If the ID is in the set, we skip it. The document effectively becomes invisible to the user, even though the raw bytes are technically still sitting on the hard drive.

Furthermore, how do we handle document updates? Simple: an update is just a Delete + Insert. You add the old Document ID to the Tombstone Set, and insert the newly updated text as a brand new document in your active RAM buffer.

Your Task

1. Delete Endpoint (DELETE /document/{id}): Add this new endpoint. When called, it should append the {id} to an in-memory Set of deleted IDs. Return 204 No Content.
2. Persistence: Just like the RAM buffer, if the server crashes, we lose our tombstones. You must persist this set to disk (e.g., appending to a tombstones.del file).
3. Filter Searches (GET /search): Update your search logic. Before you score a matching document and push it into your Top-K Min-Heap, check if its ID exists in the Tombstone set. If it does, ignore it.
4. Handling Updates (POST /document/{id}): If a POST request comes in for an ID that already exists (an update), you must “kill” the old version existing in the disk segments, and insert the new text into your active RAM buffer.

Note

The Update Trap: If you blindly add doc1 to a global Tombstone set, and then insert the new doc1 into the RAM buffer, your search logic might accidentally filter out the new version too because the ID is exactly the same! How do you tombstone the old disk version but keep the new RAM version alive?

The Solution (The Precedence Rule): Make your Tombstone set only apply to disk segments.

• If the old version is in the RAM buffer: You don’t even need tombstones! Because the RAM buffer is a mutable data structure, just physically delete or overwrite the old document’s data in the RAM buffer.
• If the old version is on disk: Add it to the Tombstone set. When aggregating search results later, if doc1 is found in the active RAM buffer, it automatically takes precedence. You only check the Tombstone set when evaluating hits from the immutable disk segments.

Note

What about Global Stats? When you soft-delete a document, do not try to decrement the global N (total documents) or avgdl. Doing so would require scanning the immutable segment to find the length of the deleted document, which is terrible for performance. Real engines allow these stats to become slightly inaccurate (stale) until a background Compaction (next stage) physically removes the data.

5. Update your Reset Endpoint (Again): Don’t forget to update your DELETE /index endpoint! It must now clear your in-memory Tombstone set (and delete the persistent .del file from disk) along with the segment files and RAM buffer.

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 tombstones