Alphabetical Segments & Disk-Seeking

The engine is working, but it takes 15 minutes to start up. Why? Because on startup, we are deserializing 50GB of segment files from disk into a massive in-memory Hash Map.

By loading everything into RAM, we are duplicating data that is already safely sitting on the SSD. We need to let the OS handle memory.

Memory Mapping and Disk Seeking

Real engines like Apache Lucene use mmap (Memory-Mapped Files). This tells the Operating System: “Map this file directly into virtual memory. If I read a byte, you load that page from disk into the OS Page Cache. If memory gets tight, evict it silently.”

To do this efficiently, our files cannot be a random JSON blob like { "apple": [...], "banana": [...] }. JSON parsers must read the entire file into memory to parse it. We need a flat, strictly sorted, line-by-line format.

How to Calculate Byte Offsets

Instead of holding the data in RAM, we only hold a Term Dictionary in RAM. This dictionary acts as an index to the index. It simply maps a term to the exact byte offset where that term’s data begins on disk.

When you flush your RAM buffer to a segment file:

1. Extract all terms from your buffer and sort them alphabetically.
2. Open a new file for writing.
3. For each term, serialize its postings list to a string (e.g., apple:green_apple.txt=1,red_apple.txt=2,rolling.txt=1\n).
4. Before writing, record the file’s current size (which is the current byte offset). Most languages provide a file.tell() or file.position() method. Alternatively, you can just maintain a running counter of the bytes you have written so far.
5. Write the serialized string to the file.
6. Add the mapping (apple -> offset) to your in-memory Term Dictionary. The offset represents where the term apple starts.

Your Task

1. Sort & Serialize: Change how you write segment files. Serialize them line-by-line, strictly sorted alphabetically by term.
2. The Term Dictionary (Offset Map): Maintain the Term -> Byte Offset map in memory for each segment file. (e.g., apple starts at byte 0, banana starts at byte 25, cherry starts at byte 60).
3. Disk Seeking on Query: When a search query comes in for banana, look up its byte offset (25) in your RAM map. Open the segment file, use your language’s seek() function to jump directly to byte 25, and read exactly one line to get banana’s postings list!

By doing this, your engine’s memory footprint will plummet. You are now leaving the heavy lifting to the OS Page Cache and disk I/O controllers.

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 disk_seek