Pensieve: Skewness-Aware Version Switching for Efficient Graph Processing

Multi-version graph processing has recently attracted much research efforts. Existing multi-version graph storage designs use either copy-based schemes or delta-based schemes. A copy-based scheme stores every version separately and may lead to expensive space cost due to high storage redundancy. On the contrary, a delta based scheme only stores incremental deltas between different versions and relies on delta computation for version switching. In this work, we observe: 1) high degree vertices incur much more significant storage overheads during graph version evolving compared to low degree vertices; 2) the skewed access frequency among graph versions greatly influences the system performance for version reproducing. Based on the observations, we propose Pensieve, a skewness-aware multi-version graph processing system. Two factors contribute to the efficiency of Pensieve. First, Pensieve leverages a differentiated graph storage strategy that stores low degree vertices using copy-based scheme while stores high degree ones using delta-based scheme. Such a design achieves a good trade-off between storage cost and version switching time for multi-version graph processing. Second, the Pensieve graph storage exploits the time locality of graph version access and designs a novel last-root version switching scheme, which significantly improves the access efficiency for recent versions. We implement Pensieve on top of Ligra, and conduct comprehensive experiments to evaluate the performance of this design using large-scale datasets collected from real world systems. The results show that Pensieve substantially outperforms state-of-the-art designs in terms of memory consumption and version switching time.