LazyGraph: Lazy Data Coherency for Replicas in Distributed Graph-Parallel Computation

作     者：Wang, Lei Zhuang, Liangji Chen, Junhang Cui, Huimin Lv, Fang Liu, Ying Feng, Xiaobing 

作者机构：State Key Laboratory of Computer Architecture Institute of Computing Technology Chinese Academy of Sciences China University of Chinese Academy of Sciences China 

出 版 物：《ACM SIGPLAN Notices》 (ACM SIGPLAN Not.)

年 卷 期：2018年第53卷第1期

页      面：276-289页

核心收录：

基　　金：We thank all the reviewers for their valuable comments and suggestions. This work was supported in part by the National Key Research and Development Program of China (2017YFB0202002)  the National Natural Science Foundation of China (61402445  61521092  61432016  61432018  61332009  U1736208) 

主　　题：Graph theory 

摘      要：Replicas 1 of a vertex play an important role in existing distributed graph processing systems which make a single vertex to be parallel processed by multiple machines and access remote neighbors locally without any remote access. However, replicas of vertices introduce data coherency problem. Existing distributed graph systems treat replicas of a vertex v as an atomic and indivisible vertex, and use an eager data coherency approach to guarantee replicas atomicity. In eager data coherency approach, any changes to vertex data must be immediately communicated to all replicas of v, thus leading to frequent global synchronizations and communications. In this paper, we propose a lazy data coherency approach, called LazyAsync, which treats replicas of a vertex as independent vertices and maintains the data coherency by computations, rather than communications in existing eager approach. Our approach automatically selects some data coherency points from the graph algorithm, and maintains all replicas to share the same global view only at such points, which means the replicas are enabled to maintain different local views between any two adjacent data coherency points. Based on PowerGraph, we develop a distributed graph processing system LazyGraph to implement the LazyAsync approach and exploit graph-aware optimizations. On a 48-node EC2-like cluster, LazyGraph outperforms PowerGraph on four widely used graph algorithms across a variety of real-world graphs, with a speedup ranging from 1.25x to 10.69x. © 2018 ACM.