NosWalker: A Decoupled Architecture for Out-of-Core Random Walk Processing

Running billions of random walkers over a graph too big for memory means streaming it from SSD, but every existing system loads the graph in fixed blocks and advances whichever walkers happen to sit in the loaded block — so the block goes cold in a step or two and the disk thrashes; this work from Tsinghua flips the design to be walker-oriented, pre-sampling each vertex's edges into a tiny reserved pool so a handful of walkers can keep moving even after their graph blocks are evicted, and generating walkers on the fly instead of storing them all, reaching up to two orders of magnitude fewer disk reads per step and finishing walks that took the prior systems a day.

Why this problem is worth solving

The thing being computed here is deceptively humble but sits under a great deal of modern graph machine learning.

The second half of the problem is where the data lives when it no longer fits in memory.

What people did before, and where it broke

• DrunkardMob, the first out-of-core random walk system. Built on the GraphChi engine, it streams the graph block by block and holds every walker’s state in memory, advancing all walkers in the loaded block one step per epoch. Where it broke. Keeping every walker state resident caps scalability — it cannot even process the largest graphs — and one-step-per-epoch reloads most of the graph many times over.
• GraphWalker, the prior state of the art. It loads the block with the most walkers first and lets a walker take as many steps as it can before leaving that block, with asynchronous updates and a small walker buffer that spills to disk when full. Where it broke. The block still cools within a step or two, so hot-block-first only delays the thrash, and swapping walker states in and out of the buffer accounts for up to 60 percent of the total disk I/O.
• Dynamic partitioning, as in DynamicShards. Reshape the blocks on the fly to avoid loading useless data each iteration. Where it broke. It stays graph-oriented and block-centric, so even a single active walker in a block forces the whole block to load, and random walk’s sampling does not fit the value-propagation tricks these systems rely on.
• On-demand block skipping, as in Graphene. Skip loading any block that contains no walkers, an I/O-saving overlay on the general engine. Where it broke. It still iterates only through the loaded data in on-disk order, giving low I/O utilization for scattered walkers — NosWalker runs up to 80 times faster.
• The gap. Every one of these is a random-walk workload bolted onto a general graph engine, so all inherit the block-centric, graph-oriented schedule whose core assumption — that computation stays inside a loaded block — is precisely what random walk violates. What was missing was an architecture built around the walkers themselves, one that could keep a few of them moving without waiting on the block they happen to need.

How NosWalker works

The idea

Turn a vertex’s edges into a pool of pre-drawn samples, and decouple sampling from walking. The waste in the old design comes from coupling two things that need not be coupled: to move a walker one step you must have its vertex’s block in memory, so the graph loader and the walker mover march in lockstep, and the loader dominates. NosWalker breaks the coupling with pre-sampling. When a vertex’s edges are read, the system does not just take the one sample the current walker needs; it draws several and reserves the surplus in a small pool. Those reserved samples are a succinct stand-in for the vertex’s whole edge list — a few destinations instead of thousands of edges — so the same scarce memory holds vastly more forward motion, and a walker landing on that vertex later can move without any disk read at all. Separating the sampling of the graph from the computation that consumes the samples is the same decoupling the GPU graph-neural-network sampling work covered elsewhere on this site performs, pulling the neighbor sampling out of the training step so the expensive resource is never left waiting on it.

Make the walker, not the graph block, the unit of scheduling. Once sampling is decoupled, the scheduler no longer has to serve blocks — it can serve walkers. The old systems ask, in effect, which block should I load so that the walkers inside it can move, and the answer keeps going stale because walkers leave. NosWalker instead asks how do I keep some walkers moving, and answers by holding only a small, always-active set of walkers and topping it up from a fresh supply as walkers finish, so their states never swap to disk. It does not care that most walkers are momentarily stuck; it only needs a handful able to step at any instant, because the metric that matters is total steps per second, not walkers touched. Reframing the schedule around keeping the scarce resource continuously busy, rather than around a rigid unit inherited from a different workload, is the same shift the DNN-training-pipeline work covered elsewhere on this site makes when it restructures execution so the expensive stage never stalls waiting on a fixed schedule.

Bend the software to the SSD’s split personality instead of fighting it. A modern SSD can deliver high sequential bandwidth or high random-access IOPS, but not both at the same time, and the two phases of a random walk want different things. While walkers are dense, nearly every block is useful, so big sequential reads win; in the long tail, only a sliver of each block matters, so many tiny precise reads win. NosWalker measures walker density and switches between a coarse-block mode and a 4-kilobyte fine-grained mode driven by a bitmap that marks exactly which small blocks hold a stalled walker, skipping the rest. It is shaping the access pattern around what the storage device is actually good at in each regime. Co-designing the software around the concrete strengths of the storage hardware, rather than treating the device as an opaque box, is the same instinct the SSD-deduplication work covered elsewhere on this site follows, leaning on what the drive already does well instead of paying to reinvent it in software.

Following the reasoning through NosWalker

One step per walker per epoch means the same blocks are reloaded repeatedly, most of their edges untouched each time.

Why it works

• A pool of pre-sampled edges packs far more forward motion into the same memory. Caching raw graph blocks stores whole edge sets just to extract one hop each → but pre-sampling a vertex once yields many ready-to-use destinations that are a succinct stand-in for its edges → so the same bytes of precious memory buy many more walker steps than a cached block would.
• Decoupling sampling from movement lets walkers advance after the graph is gone. In block-centric systems a walker can only step while its block sits in memory → but a reserved pre-sample pool is not tied to any loaded block → so a handful of walkers keep stepping straight out of the pool even as blocks are evicted, and the disk stops gating progress.
• Generating walkers on demand erases the cost of storing them. Holding or swapping billions of walker states is enormous vertex-data I/O, up to 60 percent of the total in the prior system → but because walkers are independent, only a small set need exist at once and new ones are spawned as old ones finish → so walker state never spills to disk and that whole I/O term collapses toward zero.
• Matching I/O granularity to walker density uses the SSD as it actually is. An SSD gives high sequential throughput or high random IOPS but not both at once → so NosWalker loads coarse blocks while walkers are dense and switches to 4-kilobyte fine blocks, guided by a bitmap, once they thin out → which turns the long-tail phase from a thrash of near-empty big reads into precise small ones.
• Spending the reserved budget on the vertices walkers actually revisit makes skew an ally. Real graphs are power-law, so a few high-degree vertices soak up most of the visits → but NosWalker reserves more pre-samples for exactly those vertices, estimated from their running visit counts → so skipping just 18 percent of steps through the pool cut disk I/O by about 60 percent, because those steps sat on vertices of average degree 382 against the graph’s 32.

What it costs (trade-offs and scope)

• The gains lean on power-law skew. Pre-sampling pays off because a few high-degree vertices absorb most visits; on flatter graphs it helps far less, and on a road-like graph of average degree 2.5 pre-sampling cut I/O by only about 9 percent. The headline numbers assume a natural, heavy-tailed degree distribution.
• “Up to two orders of magnitude” is a best case. The typical speedup over GraphWalker on the big out-of-core graphs is 6 to 64 times, and 3.6 to 7.9 times on graphs that already fit in memory. The 100-times regime shows up specifically when walkers are sparse or the graph carries edge properties.
• Against in-memory systems it wins only on total time. The in-memory ThunderRW is about 1.5 times faster in pure computation; NosWalker leads, by roughly 32 percent, only once ThunderRW’s graph-loading time is counted. So its edge is I/O pipelining and cost, not raw compute speed.
• The memory budget has a floor. At 10 percent of the graph there is little room left for the pre-sample pool and the speedup shrinks; it improves markedly going from a 10 percent to a 20 percent budget, so the technique needs some slack to breathe.
• Pre-sample buffers are rebuilt, not appended. Because the on-disk and in-memory formats are static CSR, refilling discards a buffer even when some pre-samples are still unconsumed and builds a new one. The authors argue this waste is acceptable since pre-samples are far smaller than the graph, but it is real overhead.
• The results are software on a particular setup. They come from Xeon servers with an NVMe SSD or a seven-drive RAID and a 64-gigabyte budget; the low-IOPS RAID already trims the gains to 15 to 41 times. No new hardware is required, but the exact numbers are configuration-specific.
• Correctness rests on samples being interchangeable. Reserving surplus draws is sound only because a vertex’s out-edges are sampled independently from the same distribution, so a batch of pre-samples can serve several later visits. The second-order (history-dependent) case does not fit directly and needs an added rejection-sampling step to stay correct.

The evaluation

Check yourself

Sources

The paper is “NosWalker: A Decoupled Architecture for Out-of-Core Random Walk Processing” by Shuke Wang, Mingxing Zhang, Ke Yang, Kang Chen, Shaonan Ma, Jinlei Jiang, and Yongwei Wu, published at ASPLOS 2023, pages 466 to 478, DOI 10.1145/3582016.3582025. The authors are at Tsinghua University, with one also affiliated with Beijing HaiZhi XingTu Technology.

This explainer is written from the full 17-page text. Everything above comes from the paper’s own sections: the introduction’s account of graph-oriented versus walker-oriented scheduling and the memory-layout contrast in Figure 1; the background on random walk as an upstream task that is often more than 90 percent of a graph-learning pipeline’s cost, the economics of out-of-core processing (memory near ten dollars per gigabyte against an SSD near thirteen cents, an almost ninefold storage saving at a tenth-of-graph budget), and the cooling and long-tail measurements for DrunkardMob and GraphWalker; the design section’s decoupled architecture around the pre-sampled edge buffer, the four-function programming model (GenerateWalker, Sample, Active, Action), and the optimizations for adaptive block granularity (coarse versus 4-kilobyte fine blocks, with the switching condition and the default unevenness factor of four), the compact CSR-like pre-sample data structure with its visit-count-weighted reallocation, dynamic memory recycling from finished walkers, special handling of low-degree vertices, and reuse of loaded edges; and the evaluation on Twitter, YahooWeb, Kron30, Kron31, CrawlWeb, a weighted Kron30, and two flatter synthetic graphs, reporting 6-to-64-times and 3.6-to-7.9-times speedups over GraphWalker, up to two orders of magnitude when walkers are sparse, 30-to-95-times across walk lengths, 15-to-41-times on a low-IOPS RAID, the optimization breakdown (total I/O falling from 1263 to 274 gigabytes on the billion-walker workload, with pre-sampling skipping 18 percent of steps to save about 60 percent of I/O because those steps sat on vertices of average degree 382), the second-order Node2Vec comparison of 3 to 49 times over GraSorw, and the in-memory comparisons against ThunderRW and KnightKing.