GraphWalker: An I/O-Efficient and Resource-Friendly Graph Analytic System for Fast and Scalable Random Walks

Rui Wang, Yongkun Li, Hong Xie, Yinlong Xu, John C. S. Lui

TL;DR

This paper introduces GraphWalker, a novel system designed for efficient and scalable random walk analysis on massive graphs stored on disk. By employing a state-aware I/O model and asynchronous walk updating, GraphWalker significantly outperforms existing systems in terms of speed and resource utilization, even rivaling distributed solutions on a single machine.

What Problem Does This Paper Address?

Analyzing large graphs, especially those that don't fit into main memory, presents a significant challenge. Traditional graph processing systems often use an "iteration-based model" where data is loaded in chunks, processed, and then discarded. While this reduces random disk I/Os by favoring sequential reads, it's inefficient for random walks. Random walks, a fundamental technique for tasks like PageRank estimation and similarity computation, involve unpredictable traversal patterns. This leads to low I/O utilization because systems might load data blocks that contain few or no active walks. Furthermore, the synchronized, one-step-at-a-time update in the iteration-based model limits the speed at which walks can progress, and managing the dynamic states of numerous walks requires substantial memory, hindering scalability.

Methods

GraphWalker tackles these issues with three core innovations:

  • State-Aware Graph Loading: Instead of sequentially loading graph blocks, GraphWalker intelligently chooses which block to load based on the current locations of the random walks. It prioritizes blocks containing the most active walks, maximizing the chances that loaded data will be actively used, thus improving I/O utilization. This is complemented by a "walk-conscious caching scheme" that keeps frequently accessed blocks in memory.
  • Asynchronous Walk Updating: GraphWalker allows each walk to continue moving as many steps as possible within a loaded block, rather than being restricted to a single step per iteration. This "re-entry" approach, combined with multi-threading, significantly accelerates walk progression. To mitigate the "global straggler problem" (where a few walks lag far behind), a probabilistic approach is introduced to give slower walks a chance to catch up.
  • Block-Centric Walk Management: To reduce memory overhead, GraphWalker uses a lightweight scheme to manage walk states. Walks are encoded into fixed-length buffers, and when these buffers fill up, they are flushed to disk. This avoids the need for massive dynamic arrays and allows GraphWalker to handle billions of walks with minimal memory, even storing walk states on disk.

Datasets

The paper evaluates GraphWalker on six graph datasets:

  • Twitter (TT)
  • Friendster (FS)
  • YahooWeb (YW)
  • Kron30 (K30)
  • Kron31 (K31)
  • CrawlWeb (CW)

These datasets range from real-world social networks and web crawls to synthetically generated large graphs, covering a wide spectrum of sizes and structures. No new benchmarks were introduced; instead, the evaluation focuses on standard random walk-based algorithms.

Key Insights and Ideas

  • Walk State is King for I/O: The most impactful insight is that understanding where the walks are is crucial for efficient disk I/O. By prioritizing blocks with the most walks, GraphWalker dramatically improves I/O utilization, a bottleneck in traditional systems.
  • Asynchronous Progress Unlocks Speed: Breaking free from the synchronized, one-step-at-a-time iteration model allows walks to make much faster progress within loaded data, leading to significant speedups.
  • Memory Efficiency is Key to Scalability: The block-centric walk management, especially storing walk states on disk, is critical for handling billions of walks without running out of memory, a major limitation of previous systems like DrunkardMob.
  • Single Machine Power: GraphWalker demonstrates that with the right optimizations, a single machine can achieve performance comparable to distributed systems for random walk tasks, offering a more cost-effective solution.

Key Results

GraphWalker consistently outperforms existing single-machine systems:

  • Speedup: Achieves 16x to 70x speedup over DrunkardMob, and up to 19x over Graphene.
  • Scalability: Can handle tens of billions of random walks on massive graphs (e.g., 10^10 walks on CrawlWeb in under an hour), a feat that often causes out-of-memory errors in other systems.
  • I/O Utilization: Improves I/O utilization by 2x to 4x compared to DrunkardMob.
  • Walk Updating Rate: Achieves a 3.7x higher walk updating rate than DrunkardMob.
  • Resource Friendliness: Demonstrates comparable performance to the distributed system KnightKing, but on a single machine, making it a more resource-efficient alternative.

Limitations and Future Work

  • Global Straggler Problem: While GraphWalker mitigates local stragglers, a few walks can still lag significantly, potentially increasing I/O. The paper proposes a probabilistic approach to address this, but it involves a trade-off.
  • Distributed Extension: The authors suggest extending the state-aware design to distributed clusters to enable massive parallel processing of analytic tasks.
  • Block Size Tuning: The optimal block size depends on the task (lightweight vs. heavyweight walks), and GraphWalker proposes a method to set it based on the number of walks, but fine-tuning might still be necessary for specific applications.

Summary updated

BibTeX
@inproceedings{wang2020graphwalker,
  author = {Rui Wang and Yongkun Li and Hong Xie and Yinlong Xu and John C. S. Lui},
  title = {{GraphWalker: An I/O-Efficient and Resource-Friendly Graph Analytic System for Fast and Scalable Random Walks}},
  booktitle = {USENIX ATC},
  year = {2020},
}
Figure