GraphD: Distributed Vertex-Centric Graph Processing Beyond the Memory Limit
GraphD: Distributed Vertex-Centric Graph Processing Beyond the Memory Limit
复制标题
DOI：
10.1109/tpds.2017.2743708
复制
发表时间：
2018
影响因子：
5.3
通讯作者：
Da Yan;Yuzhen Huang;Miao Liu;Hongzhi Chen;James Cheng;Huanhuan Wu;Chengcui Zhang
中科院分区：
文献类型：
--
作者：
Da Yan;Yuzhen Huang;Miao Liu;Hongzhi Chen;James Cheng;Huanhuan Wu;Chengcui Zhang
我们提出GraphD，一个类似于pregel的外核系统，目标是通过千兆以太网连接的小型商用pc集群进行高效的大图形处理，这是一个大多数用户都能负担得起的环境。这与最近使用专用硬件进行核外图计算的一些努力形成了对比。在我们的设置中，以顶点为中心的程序通常是数据密集型的，因为计算消息值的CPU成本与传输该消息的网络成本相比可以忽略不计。因此，网络带宽通常是瓶颈，如果可以通过消息传输隐藏磁盘IO开销，则核外执行不会牺牲性能，这是GraphD通过计算和通信的并行性实现的。GraphD将边缘和消息数据流式传输到本地磁盘上，因此占用的内存空间可以忽略不计。对于适用于消息组合器的Pregel算法的广泛类别，GraphD完全消除了任何昂贵的外部内存连接或group-by的需要，这是现有系统（如Pregelix和Chaos）所需要的。大量的实验表明，GraphD在数量级上击败了现有的out- core系统，并且实现了与具有足够内存运行的内存系统相当的性能。
We propose GraphD, an out-of-core Pregel-like system targeting efficient big graph processing with a small cluster of commodity PCs connected by Gigabit Ethernet, an environment affordable to most users. This is in contrast to some recent efforts for out-of-core graph computation with specialized hardware. In our setting, a vertex-centric program is often data-intensive, since the CPU cost of calculating a message value is negligible compared with the network cost of transmitting that message. As a result, network bandwidth is usually the bottleneck, and out-of-core execution would not sacrifice performance if disk IO overhead can be hidden by message transmission, which is achieved by GraphD through the parallelism of computation and communication. GraphD streams edge and message data on local disks, and thus consumes negligible memory space. For a broad class of Pregel algorithms where message combiner is applicable, GraphD completely eliminates the need of any expensive external-memory join or group-by, which is required by existing systems such as Pregelix and Chaos. Extensive experiments show that GraphD beats existing out-of-core systems by orders of magnitude, and achieves comparable performance to in-memory systems running with adequate memory.