MultiLyra: Scalable Distributed Evaluation of Batches of Iterative Graph Queries
MultiLyra: Scalable Distributed Evaluation of Batches of Iterative Graph Queries
复制标题
DOI：
10.1109/bigdata47090.2019.9006359
复制
发表时间：
2019-12
期刊：
影响因子：
--
通讯作者：
Abbas Mazloumi;Xiaolin Jiang;Rajiv Gupta
中科院分区：
文献类型：
--
作者：
Abbas Mazloumi;Xiaolin Jiang;Rajiv Gupta
图分析越来越多地用于分析表示许多领域中的实体和关系的大规模网络。已经开发了各种分布式图处理框架来为单个迭代图查询的评估提供可扩展的性能。但在实践中，我们可能需要评估许多查询。在本文中，我们开发了 MultiLyra，这是一个分布式框架，可以有效地评估一批图查询。为了提供高性能，该系统旨在分摊跨多个查询的分布式查询评估的通信和同步成本。我们在由四台 32 核机器组成的集群上使用 MultiLyra 对四种迭代算法进行的实验显示了以下结果。用于分摊通信和同步成本的基本批处理技术可在不同的批量大小、算法和输入图上产生从 3.08 美元到 5.55 美元的最大加速。在采用提高昂贵阶段的可扩展性并在分布式计算中执行重用的优化后，改进的最大加速范围从 $7.35 \times $ 到 $11.86 \times $。 MultiLyra 还提供比 Quegel 批处理系统更出色的可扩展性。
Graph analytics is being increasingly used for analyzing large scale networks representing entities and relationships in many domains. Various distributed graph processing frameworks have been developed to deliver scalable performance for evaluation of individual iterative graph queries. In practice though, we may need to evaluate many queries. In this paper we develop MultiLyra, a distributed framework that efficiently evaluates a batch of graph queries. To deliver high performance, this system is designed to amortize the communication and synchronization costs of distributed query evaluation across multiple queries. Our experiments with MultiLyra for four iterative algorithms on a cluster of four 32-core machines show the following. Basic batching technique for amortizing communication and synchronization costs yield maximum speedups ranging from $3.08 \times $ to $5.55 \times $ across different batch sizes, algorithms and input graphs. After employing optimizations that improve scalability of expensive phases and perform reuse across the distributed computation, the improved maximum speedups range from $7.35 \times $ to $11.86 \times $. MultiLyra also delivers superior scalabilty than the Quegel batch processing system.