Day 5: Map the Web Graph using an Adjacency List — and Traverse Paths via Memory-Bounded BFS

Day 5: Map the Web Graph using an Adjacency List — and Traverse Paths via Memory-Bounded BFS

In Day 4, we packed 100,000 crawled web records into a contiguous binary file to eliminate pointer-chasing overhead and execute high-speed binary searches. However, web pages do not exist in isolation; they form a massive, highly connected directed graph. To rank these pages or discover paths between them, we must map this web graph and traverse it.

If you build a graph engine using naive academic representations—such as object-oriented node classes linked by pointer-heavy lists—you will quickly saturate your CPU cache with misses and exhaust your system's memory. When traversing this graph using an unconstrained Breadth-First Search (BFS), hitting a highly connected hub (like a major directory or social media profile) can cause your queue size to explode exponentially.

Today, we will build a production-honest, memory-efficient graph engine using a flat, contiguous Adjacency List layout. We will then implement a memory-bounded BFS traversal algorithm designed to protect your services from Out-Of-Memory (OOM) crashes when traversing highly connected subgraphs.

The Production Stakes: The "Query of Death"

In 2013, during the roll-out of Facebook’s early Graph Search, engineers encountered a recurring production hazard: the "Query of Death." When a user queried relationships across deeply connected entities, the underlying graph traversal engine would execute a BFS to find paths. If the traversal hit a "super-node"—such as a celebrity profile with millions of followers or a highly connected public page—the BFS queue would grow exponentially ($O(b^d)$, where $b$ is the average branching factor and $d$ is the path depth).

Without strict boundaries, these unconstrained queues consumed gigabytes of memory in milliseconds. This triggered severe garbage collection (GC) thrashing, elevated API latencies across unrelated services, and ultimately caused daemon processes to be terminated by the kernel's Out-Of-Memory (OOM) killer.

To prevent this, production-grade graph databases and search engines (such as Facebook’s TAO or LinkedIn’s Liquid graph engine) enforce strict limits on traversal depth, visited set sizes, and queue lengths. If a query exceeds these budgets, the engine gracefully halts, returning a partial result or a deterministic error, rather than crashing the node.

Memory Layout: Compact Adjacency List

A standard academic adjacency list uses a hash map of lists: Map<Node, List<Node>>. In languages with managed memory, this structure is a disaster. Every map entry, list wrapper, and node reference introduces pointer overhead. This scatters your data across the heap, destroying CPU cache locality.

To maximize performance, we pack our graph into a variation of the Compressed Sparse Row (CSR) layout. We map our URLs to sequential integer IDs, and store all outgoing edges in a single, contiguous flat array.

By storing edges contiguously, we ensure that when the CPU fetches a node's neighbors, it loads them into the L1/L2 cache in a single memory access, eliminating pointer-chasing latency.

The Mechanism: Memory-Bounded Traversals

Our BFS algorithm must traverse this compact structure while respecting strict, user-defined memory limits. We track two critical metrics during execution:

1. The Queue Size: The number of nodes currently scheduled for exploration.

2. The Visited Set Size: The total number of unique nodes tracked to prevent cycles.