TL;DR
This paper introduces CGraph, a novel system designed to significantly boost the performance of concurrent iterative graph processing (CGP) jobs. By exploiting spatial and temporal correlations in data access patterns among these jobs, CGraph reduces redundant data loading and cache interference, leading to substantial throughput improvements over existing solutions.
What Problem Does This Paper Address?
Iterative graph processing is crucial for many applications, from social network analysis to recommendation systems. As datasets grow and the need for real-time insights increases, running multiple iterative graph processing (CGP) jobs concurrently on the same graph has become common. However, existing systems struggle with this scenario. When multiple CGP jobs access the same graph structure simultaneously, they often independently fetch and cache the same data, leading to significant cache interference and memory wall bottlenecks. This results in a high data access cost relative to computation, severely limiting overall throughput. The paper aims to address this inefficiency by enabling CGP jobs to collaboratively and efficiently share graph data.
Methods
The core of CGraph's approach is a data-centric Load-Trigger-Pushing (LTP) model. This model decouples the graph structure data from the job-specific vertex states. Key aspects include:
- Shared Graph Structure: The graph structure is loaded into the cache once and shared among all relevant CGP jobs.
- Correlations Exploitation: CGraph explicitly identifies and leverages two types of correlations:
- Spatial Correlation: Different CGP jobs often access overlapping sets of graph partitions within an iteration.
- Temporal Correlation: Certain graph partitions might be accessed by multiple jobs within a short time frame.
- Core-Subgraph Scheduling: A novel scheduling algorithm prioritizes loading graph partitions based on their usage frequency by CGP jobs and the degree of vertices within them. This aims to maximize cache utilization.
- Parallel Trigger and State Pushing: Once a graph partition is loaded, related CGP jobs are triggered concurrently to process their vertex states. After processing, vertex states are pushed for synchronization.
- Straggler Identification: To further optimize parallel execution, CGraph identifies "straggler" jobs (those with the most unprocessed vertices) and redistributes their workload to free cores.
- Evolving Graph Handling: CGraph supports evolving graph structures by maintaining snapshots, where updates are visible to jobs submitted after the update.
Datasets
The paper evaluates CGraph using four popular iterative graph algorithms (PageRank, SSSP, SCC, and BFS) on real-world graph datasets:
- Friendster
- uk2007
- uk-union
- hyperlink14
These datasets vary significantly in size, ranging from millions to billions of vertices and edges.
Key Insights and Ideas
- The "Cache Interference" Bottleneck: The most significant insight is that concurrent graph processing jobs, when run independently, create massive redundancy in cache usage. This is the primary performance killer, not necessarily the computation itself.
- Correlations are Key: The paper demonstrates that by explicitly modeling and exploiting spatial and temporal correlations in data access, substantial performance gains are achievable. This moves beyond simply optimizing individual job performance to optimizing the collective behavior of multiple jobs.
- Shared Data is the Goal: The fundamental idea is that if multiple jobs need the same piece of graph data, it should only be loaded and processed once for the entire group, rather than multiple times for each job.
- Smart Scheduling Matters: Simply sharing data isn't enough; how and when partitions are loaded is critical. The core-subgraph scheduling prioritizes partitions that are most likely to be used by many jobs, maximizing the benefit of shared caching.
Key Results
CGraph demonstrates significant performance improvements:
- Throughput Improvement: CGraph improves the throughput of CGP jobs by up to 2.31 times compared to Seraph, and even higher (up to 4.32 times) compared to CLIP and Nxgraph.
- Reduced Cache Miss Rate: The last-level cache miss rate for CGraph is substantially lower than competing systems. For example, on the hyperlink14 dataset with eight jobs, CGraph's cache miss rate is only 29.6%, compared to 89.5% for Nxgraph.
- Lower Data Access Cost: CGraph achieves a much lower data access cost to computation ratio, meaning more time is spent computing and less time waiting for data.
- Scalability: CGraph exhibits better scalability with an increasing number of workers compared to other systems.
- Performance on Evolving Graphs: CGraph maintains strong performance even when graph structures change, outperforming other systems like Seraph-VT.
Limitations and Future Work
The authors acknowledge several limitations and suggest future directions:
- Static Graph Processing Focus: The current work primarily focuses on static graph processing. Future research will explore optimizing for evolving graph analysis.
- Distributed and Heterogeneous Platforms: The paper suggests extending CGraph to distributed platforms and heterogeneous environments (e.g., incorporating GPUs) to achieve even higher throughput.
- Dynamic Job Submission: While CGraph allows adding new jobs at runtime, further optimization for highly dynamic job submission scenarios could be explored.
Summary updated