Recommendation-Graph BFS: Graph Traversal Algorithms at Web Scale

Table of Contents

1. The Context / The Problem
2. The Deep-Dive / Root Cause Analysis
3. The Implementation / Architecture
4. Lessons Learned & Best Practices
5. References

The Context / The Problem

Exploring large-scale recommendation graphs requires traversing dynamic web topology without succumbing to memory explosions or exponential frontier runaway. When building a media discovery indexing pipeline, our crawler traversed recommendation edges between related content nodes across multiple media networks.

Because popular content nodes act as massive hubs with thousands of outgoing edges, an unconstrained Breadth-First Search (BFS) algorithm quickly encounters exponential branching factors ($O(b^d)$). In our initial Python implementation, crawling to depth 4 from fifty seed channels expanded the frontier queue to over 14 million URLs within 20 minutes, exhausting available host RAM and triggering Linux OOM kills.

Furthermore, naive graph traversals frequently loop through bidirectional recommendation cycles (A recommends B, and B recommends A), causing worker pools to repeatedly re-crawl the same clusters while starving edge nodes. We needed a bounded, priority-weighted async graph crawler in Rust capable of real-time frontier pruning, distributed cycle detection, and polite domain rate-limiting.

The Deep-Dive / Root Cause Analysis

Analyzing the memory dynamics of web-scale BFS revealed three distinct failure modes in naive frontier management:

1. Unbounded Frontier Queue Growth

When average out-degree $b \approx 28$, breadth-first queues grow exponentially:

• Depth 1: 50 nodes
• Depth 2: 1,400 nodes
• Depth 3: 39,200 nodes
• Depth 4: 1,097,600 nodes
• Depth 5: 30,732,800 nodes

Storing 30 million unresolved frontier entries in an in-memory queue consumed over 8 gigabytes of memory purely in string allocations and pointer overhead.

2. High-Degree Hub Polarization

Popular mainstream nodes dominate outbound recommendations. Without degree normalization, workers spent 85% of their network budget fetching nodes that had already been crawled through hundreds of alternative paths.

The Implementation / Architecture

We redesigned the graph traversal engine in async Rust using Tokio, a two-tier frontier queue (memory-bounded priority heap + disk-backed spillover), and an in-memory visited set encoded with Roaring Bitmaps.

1. Priority-Weighted Graph Frontier

Rather than strict FIFO BFS, nodes are scored by a discovery heuristic that prioritizes low-degree novelty over high-degree hubs:

use std::cmp::Ordering;
use std::collections::BinaryHeap;

#[derive(Debug, Clone, Eq, PartialEq)]
pub struct FrontierNode {
    pub id: u64,
    pub depth: u8,
    pub priority: u32,
}

impl Ord for FrontierNode {
    fn cmp(&self, other: &Self) -> Ordering {
        self.priority.cmp(&other.priority)
    }
}

impl PartialOrd for FrontierNode {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}

pub struct BoundedFrontier {
    heap: BinaryHeap<FrontierNode>,
    max_size: usize,
}

impl BoundedFrontier {
    pub fn new(max_size: usize) -> Self {
        Self {
            heap: BinaryHeap::with_capacity(max_size),
            max_size,
        }
    }

    pub fn push(&mut self, node: FrontierNode) {
        if self.heap.len() < self.max_size {
            self.heap.push(node);
        } else if let Some(lowest) = self.heap.peek() {
            if node.priority > lowest.priority {
                self.heap.pop();
                self.heap.push(node);
            }
        }
    }

    pub fn pop(&mut self) -> Option<FrontierNode> {
        self.heap.pop()
    }
}

2. Concurrent Graph Worker Loop

Workers asynchronously fetch node metadata, extract outbound edges, and feed novel neighbor nodes back into the frontier channel:

use tokio::sync::mpsc;
use std::sync::Arc;

pub async fn crawl_graph_worker(
    worker_id: usize,
    mut work_rx: mpsc::Receiver<FrontierNode>,
    frontier_tx: mpsc::Sender<FrontierNode>,
    visited: Arc<parking_lot::RwLock<roaring::RoaringBitmap>>,
) {
    while let Some(node) = work_rx.recv().await {
        // Step 1: Check visited bitmap
        {
            let r = visited.read();
            if r.contains(node.id as u32) {
                continue;
            }
        }

        // Step 2: Mark visited
        {
            let mut w = visited.write();
            w.insert(node.id as u32);
        }

        // Step 3: Fetch recommendation edges
        if let Ok(neighbors) = fetch_recommendation_edges(node.id).await {
            for neighbor_id in neighbors {
                let priority = calculate_priority(node.depth + 1, neighbor_id);
                let next_node = FrontierNode {
                    id: neighbor_id,
                    depth: node.depth + 1,
                    priority,
                };
                let _ = frontier_tx.send(next_node).await;
            }
        }
    }
}

Lessons Learned & Best Practices

1. Strict FIFO BFS Collapses on Scale-Free Graphs: Natural web graphs follow power-law distributions. A priority-bounded queue that penalizes over-connected hubs prevents graph crawlers from getting stuck in celebrity loops.
2. Roaring Bitmaps Provide Dense Set Representation: Storing 50 million visited integer IDs in RoaringBitmap required only 24 MB of RAM compared to 400+ MB in a raw HashSet<u64>.
3. Cooperative Rate Limiting Per Outbound Domain: Wrapping HTTP clients in token-bucket rate limiters per target domain avoided IP bans while maximizing overall concurrency across disparate hosts.

References

• Roaring Bitmaps: Fast, Compressed Bitsets
• Graph Traversal and Breadth-First Search Theory
• Tokio Concurrency Patterns & Bounded Channels