Day 2: Sort Multi-Gigabyte Crawl Logs on Disk — and Avoid Memory Exhaustion with External Merge Sort

Day 2: Sort Multi-Gigabyte Crawl Logs on Disk — and Avoid Memory Exhaustion with External Merge Sort

In Day 1, we packed our raw unstructured web crawl metadata into a contiguous, high-density byte array buffer to maximize CPU cache locality. That worked beautifully because our dataset fit entirely within our laptop's RAM.

But in production, crawl logs do not fit in RAM. If your crawler runs for a week, it will produce hundreds of gigabytes of metadata. If you attempt to load that entire dataset into an in-memory sorting algorithm like Quicksort or Timsort, the operating system's Out-Of-Memory (OOM) killer will instantly terminate your process.

Today, we build the engine that solves this: an External Merge Sort. This algorithm sorts datasets of arbitrary size using a fixed, strictly bounded memory footprint by leveraging sequential disk I/O.

+-----------------------------------------------------------------------+
|                         EXTERNAL MERGE SORT                           |
+-----------------------------------------------------------------------+
                                                                         
  [ Raw Crawl Log File (Multi-GB) ]                                      
                 |                                                       
                 |  1. Split into RAM-sized chunks                       
                 v                                                       
    +-------------------------+                                          
    | RAM Buffer (Bounded)    | <-- Sorts chunks in memory (Quicksort)   
    +-------------------------+                                          
                 |                                                       
                 |  2. Spill sorted runs to disk                         
                 v                                                       
    [ Run 1 ]  [ Run 2 ]  [ Run 3 ]  ... [ Run K ] (Sorted files)        
                 |          |          |                                 
                 +----------+----------+                                 
                            |                                            
                            | 3. Stream head of each run into Min-Heap   
                            v                                            
                     +-------------+                                     
                     |  Min-Heap   | <-- Tracks smallest element         
                     +-------------+                                     
                            |                                            
                            | 4. Stream output sequentially              
                            v                                            
             [ Sorted Crawl Log File (Multi-GB) ]                        
                                                                         
  * Note: Memory remains O(K) where K is the number of runs,            
    independent of the input file size.                                 

The Real-World Anchor: PostgreSQL's work_mem and Disk Spills

When you execute an ORDER BY or a GROUP BY query on a massive table in PostgreSQL, the database engine must sort the result set. To protect the host from running out of memory, PostgreSQL limits the amount of RAM a single query operation can consume. This limit is controlled by the work_mem configuration parameter (which defaults to a conservative 4MB).

If the dataset being sorted fits within work_mem, Postgres uses an in-memory Quicksort. The moment the estimated dataset size exceeds work_mem, Postgres switches to an external merge sort. It writes intermediate sorted runs to temporary files on disk under the pgsql_tmp directory, then merges them.

If work_mem is misconfigured too low, Postgres spills to disk unnecessarily, transforming a fast sub-millisecond in-memory operation into a slow, disk-bound sequence of system calls. If it is set too high, concurrent queries can allocate gigabytes of RAM simultaneously, starving the operating system and triggering the Linux OOM killer—bringing down the entire database instance.

The Core Mechanics: Runs and N-Way Merging

An External Merge Sort operates in two distinct phases:

1. 1.Run Generation (Split & Sort): We read the input file sequentially in chunks that fit within our memory budget (e.g., 64MB). We sort each chunk in memory using a standard sorting algorithm, then serialize and write that sorted chunk to disk as a temporary "run file."

2. 2.N-Way Merge: We open all run files simultaneously. We read the first record of each run file and place them into a min-heap (a priority queue). We then repeatedly pop the smallest record from the heap, write it to our final sorted output file, and read the next record from the run file that produced the popped record, inserting it back into the heap.

Why Sequential I/O Saves Your Disk

This design exploits a fundamental physical reality of storage media: sequential I/O is orders of magnitude faster than random I/O. Even on modern NVMe SSDs, jumping to random addresses (random seeks) incurs significant controller overhead and page translation latency compared to reading a contiguous block of memory.

By streaming run files sequentially, the operating system can aggressively prefetch pages into the page cache. The min-heap ensures we only ever hold one active record per run file in memory, keeping our memory usage bounded at $O(K)$, where $K$ is the number of run files.

Architectural Blueprint

We will implement a binary-safe log sorter. Our crawl logs contain records structured with a custom binary layout:

• Timestamp: 8-byte big-endian unsigned integer (uint64)

• Payload Size: 4-byte big-endian unsigned integer (uint32)

• URL Length: 2-byte big-endian unsigned integer (uint16)

• URL: Variable-length UTF-8 string

The Stream Parser

To avoid loading entire files, we must stream records byte-by-byte. This snippet demonstrates how we read a single binary record from an active file stream without buffering the rest of the file:

# Stream Parser: Extracting a single binary record from a disk stream
header_bytes = stream.read(14)  # 8 (timestamp) + 4 (payload) + 2 (len)
if not header_bytes:
    return None

timestamp, payload_size, url_len = struct.unpack(">QIH", header_bytes)
url_bytes = stream.read(url_len)
serialized_record = header_bytes + url_bytes

return (timestamp, serialized_record)

The Min-Heap Merge Loop

During the merge phase, we maintain a min-heap. Python's heapq module provides a binary heap over a standard list. To prevent comparison errors when two records have the exact same timestamp, we store tuples containing the timestamp, a unique run identifier, and the raw serialized record:

# Heap element structure: (timestamp, run_index, serialized_record)
while heap:
    timestamp, run_id, record = heapq.heappop(heap)
    output_stream.write(record)
    
    # Immediately replenish the heap from the run that yielded this record
    next_record = read_next_record(run_streams[run_id])
    if next_record:
        next_timestamp, next_serialized = next_record
        heapq.heappush(heap, (next_timestamp, run_id, next_serialized))

Trade-off Analysis: Run Size vs. Merge Fan-In

When designing an external sort, you must balance the size of your in-memory buffer against the number of temporary run files generated:

• Large Run Buffer (High Memory): Generates fewer run files. This reduces the "fan-in" (the number of files open simultaneously during the merge phase). The merge phase completes faster because the min-heap is smaller, and the disk heads (or SSD controllers) do not have to multiplex reads across hundreds of open file descriptors.

• Small Run Buffer (Low Memory): Keeps the system safe from OOM limits but generates thousands of small run files. This can exhaust the operating system's file descriptor limits (ulimit -n) and force the merge phase to perform random-like disk reads as it switches between thousands of active file streams.

If your dataset is so massive that the number of run files exceeds your file descriptor limit, you must perform a multi-pass external merge sort. Instead of merging all runs at once, you merge subsets of runs into larger intermediate run files, and then merge those intermediate runs in a final pass.

What We Cut for the Laptop Version

In a production-grade storage engine (like RocksDB's SSTable compaction or ClickHouse's MergeTree engine), several optimizations are implemented that we omit here for clarity:

1. 1.Direct I/O (O_DIRECT): Production engines bypass the OS page cache entirely to prevent the merge phase from evicting hot web-serving data from memory.

2. 2.Double Buffering / Asynchronous I/O: While the CPU is sorting a run in memory, a background thread is writing the previous run to disk using asynchronous system calls (io_uring or aio_write), ensuring the CPU never idles waiting for disk writes.

3. 3.Zero-Copy Serialization: Instead of parsing bytes into high-level language objects (like Python tuples) and serializing them back, production engines sort pointers directly within a contiguous raw memory buffer.

Assignment: Implement a Buffered Block Writer

Currently, our merge phase writes every single popped record directly to disk. This triggers a high frequency of small write system calls, forcing the CPU to repeatedly transition between user space and kernel space.

Your task is to implement a Buffered Block Writer for the merge phase.

Requirements

1. 1.Modify the merge loop to write records into an in-memory byte buffer (e.g., 64KB).

2. 2.Only call the underlying file descriptor's write method when this buffer is full, or when the merge phase completes (flushing the remaining bytes).

3. 3.Measure the execution time before and after your optimization using the benchmark command provided in the Implementation Guide.

Hints

• You can use Python's built-in io.BufferedWriter to wrap your output file, or implement a manual bytearray buffer that you track and flush when len(buffer) >= TARGET_SIZE.

• A 64KB buffer aligns cleanly with typical OS page cache boundaries and disk block allocations.

Solution Guide

To implement the manual Buffered Block Writer:

1. 1.Maintain an internal bytearray named write_buffer.

2. 2.Define a threshold, such as 65536 bytes (64KB).

3. 3.Inside your merge loop, instead of calling output_file.write(record), append the raw bytes to your write_buffer.

4. 4.Check if the length of write_buffer exceeds the threshold. If it does, write the entire buffer to disk and clear it:

   pythonCopy

   write_buffer.extend(record)
   if len(write_buffer) >= 65536:
       output_file.write(write_buffer)
       write_buffer.clear()
   

5. 5.Crucial step: After the merge loop finishes and the heap is empty, write any remaining bytes left in write_buffer to the file before closing it. This is called "flushing" the buffer. If you forget this, your output file will be truncated and corrupt!

In Day 3, we will write a high-performance binary search parser over this newly sorted, contiguous disk-backed buffer to achieve sub-millisecond lookups without loading the index into memory.