crawlyx, in depth: the data structure story

crawlyx is a web crawler that turns pages into markdown for llms. i built it to test one idea: does the right data structure change the result? yes. everything people benchmark, speed, memory, duplicates, is downstream of a shape decision. you pick a structure by deciding where the wait happens. pick wrong and the machine waits in the wrong place.

the snorlax, crawlyx's pride and joy

reference benchmarks, 200 pages:

the visited table

the naive version everyone starts with is a HashSet behind one lock.

it fails twice at 32 workers.

first, one lock means every worker that touches a url waits on every other worker's url. the mutex becomes the bottleneck. the fix: split the map into 64 maps, hash the url, pick a shard, lock only that one. a url never waits on a lock about a different url.

picking the shard is the interesting part. a bitmask, not a modulo.

pub fn shard_for<K: Hash + ?Sized>(key: &K) -> usize {
    let mut hasher = AHasher::default();
    key.hash(&mut hasher);
    (hasher.finish() as usize) & SHARD_MASK
}

hash & 63 is exactly hash % 64, in one instruction instead of a division. it only works because the shard count is a power of two. a const assert on NUM_SHARDS.is_power_of_two() makes that a compile error instead of a silent bug. and each shard is cache-padded, because two locks on the same cache line invalidate each other every time either one is written. that showed up in the flamegraph, not the design.

second failure is a correctness one. a HashSet can't say "i'm working on it". so two workers can both check the set, both miss, both fetch, both push the same page. the same page twice means wasted time and a wrong graph.

so the set becomes a state machine.

pub enum UrlState { InFlight, Visited }

and insert returns whether you won the right to crawl it:

pub fn insert(&self, url: &str) -> bool {
    let index = shard_for(url);
    let mut map = self.shards[index].write().unwrap();
    match map.entry(url.to_string()) {
        Entry::Vacant(e) => { e.insert(UrlState::InFlight); true }
        Entry::Occupied(_) => { false }
    }
}

the check and the insert happen under one lock, through entry. that bool is a compare-and-set. two workers want the same url, both hit the shard lock, only one gets true, only the winner pushes. there's no gap between checking and claiming, so there's nothing to race on.

the state flow is None -> InFlight -> Visited. a url that's being fetched right now is invisible to every other worker. a set has two states, "not seen" and "seen". this has three, and the third one replaces an entire locking protocol. the dedup is cheap because the state lives in the data.

the graph

this one took weeks, mostly a deadlock.

the graph holds the whole crawl. every page, its markdown, what links to what.

pub type Node = Arc<Mutex<NodeData>>;

pub struct NodeData {
    pub id: usize,
    pub url: String,
    pub data: Option<String>,
    pub parents: Vec<Node>,
    pub children: Vec<Node>,
    parent_ids: HashSet<usize>,
    child_ids: HashSet<usize>,
    pub depth: usize,
}

two lock domains on purpose. to get a node you take a short read lock on the node map, grab the Arc, let go of the map. everything that mutates, edges and content, lives in the per-node mutexes. a single lock over the whole graph would bottleneck like the single visited lock, except worse, because adding an edge would be a full-graph operation.

every node gets a unique id from a global atomic counter. that gives a total order over every node that will ever exist.

adding an edge touches two nodes, which means taking two locks. two threads taking two locks in opposite order is a deadlock: A holds the parent, waits for the child, B holds the child, waits for the parent. the fix is one rule:

// Always lock lower ID first — this is the deadlock prevention rule.
if parent_id < child_id {
    parent.lock().unwrap().insert_child(Arc::clone(child));
    child.lock().unwrap().insert_parent(Arc::clone(parent));
} else {
    child.lock().unwrap().insert_parent(Arc::clone(parent));
    parent.lock().unwrap().insert_child(Arc::clone(child));
}

everyone always locks in ascending id order. if every thread acquires locks in the same global order, a circular wait is impossible. and because ids come from one atomic counter, there are no ties. one tie breaks the ordering and the deadlock comes back.

two threads, the same two nodes, opposite order. a circle with no exit

the parents and children are vecs for order, with twin sets of ids for dedup. add the same edge twice and it's a no-op. cycles are legal too, and they have to be. the web has cycles, so the graph has to hold them without falling over.

the tree is derived, never built during the crawl. a tree can't have shared parents or cycles. the graph is the honest shape of what happened. so during the crawl i only build the graph, one node per url, and at the end i walk it once to produce a tree, breaking cycles with a plain set. that set is fine because it's single-threaded and the data is done moving. store what the crawl is, present what the reader needs.

the queue

the flat memory claim is mostly this.

pub struct InProcessQueue {
    tx: Sender<WorkUnit>,
    rx: Mutex<Receiver<WorkUnit>>,
    count: AtomicUsize,
}

a tokio mpsc channel with a capacity of 2048. mpsc is single-receiver, and that's exactly the shape of this pipeline: every worker pushes, only the dispatcher pops. workers never coordinate with each other on the queue, they only push, so mpsc handles it natively with no extra lock between workers.

count is an atomic that answers is_empty() in one load. asking the real receiver would mean locking it at 32 workers.

the bound is the backpressure valve. when the queue is full, a worker's push awaits. the crawl regulates itself instead of ballooning. an unbounded queue eats ram the moment you hit a page with a thousand links. that's the memory creep in the comparison crawlers. their queue literally can't say no.

one dispatcher, N workers, a semaphore counting them, a notify waking the sleeper

the dispatcher doesn't poll:

if is_empty {
    state.notify.notified().await;
    continue;
}

workers call notify_one() when they enqueue, and the dispatcher sleeps in the scheduler until then. no busy loop, no sleep poll. the semaphore, the channel, the notify, they're all handshakes with a queue between them. wait or signal.

the exit condition looks simple and is the subtlest logic in the file:

if is_empty && in_flight == 0 { break; }

the queue being empty is not the same as being done. a worker could be mid-fetch and about to push. the terminator is "queue empty AND nobody working". in_flight is the state that stops you from exiting early and losing pages. check emptiness alone and you quit and half the crawl silently never happens.

the normalizer

no locks, no threads. still the piece that makes the visited set work.

a visited set is only as good as the strings fed into it. different string, same page, and all the shard math above is wasted. every url passes through this before it can enter the visited table:

url = scheme_host::lowercase_scheme_host(&url);
url = relative::resolve_relative(&url, base_url);
url = port::remove_default_port(&url);
url = fragment::remove_fragment(&url);
url = query::sort_query_params(&url);
url = trailing_slash::normalize_trailing_slash(&url);

six small functions, each with one job. query sorting is the one that matters most: /page?a=2&b=1 and /page?b=1&a=2 are the same page to most servers, and a raw hashmap would crawl it twice. sort the query params and string equality becomes page equality. the normalizer's whole job is keeping another data structure honest, a pipeline of tiny transforms that exist so the hashmap can tell the truth.

and inside the parser there's a size tradeoff: per-page link lists are small, so deduping them with a hash set is allocation overhead. sort() then dedup() is O(n log n) on a handful of links and gives stable ordering for free. the right structure depends on the size of the problem. for the size of a page, sort wins.

what actually got faster

which decision owns which number:

• no double crawls: the visited state machine. every duplicate is a full wasted fetch cycle, so this is the worst-case multiplier.
• two lanes full: parsing on a blocking pool keeps fetchers hungry and the cpu fed.
• 53s instead of ~90s: the notify handshake. no idle spinning.
• flat memory: the bounded queue plus the sharded table. the difference between finishing 200 pages and creeping.
• the graph: per-page dedup and idempotent edges. a docs site crawls in one pass instead of re-crawling its nav on every page.

the flamegraph. reqwest and tokio hold the whole show, my code is a thin layer

the flamegraph showed reqwest and tokio doing all the work. my code was a thin layer between two things that already know how to be fast. all the data structures did was not be the bottleneck. don't serialize the workers, don't re-crawl, don't poll, don't grow. that's the whole job: decide where the wait happens, and spend the budget well.

the trade

every shape bought something and charged for it.

the sharded table is 64 locks, a power-of-two rule, and a cache-padded vec. the graph is a lock-ordering discipline you can't switch off. the queue is backpressure that will slow a crawl rather than let it eat ram. the normalizer is six files where one regex would do.

the honest limit: a hand-rolled Vec<CachePadded<RwLock<...>>> is where concurrency bugs go to live. the whole thing holds together on rules that nothing enforces at runtime. the real cost isn't the loc, it's keeping the rules true while everything touches everything.

crawlyx is fast because each data structure fits exactly one job. the speed is the shapes working.