A data-locality-aware task scheduler for distributed social graph queries
A data-locality-aware task scheduler for distributed social graph queries
复制标题
用于分布式社交图查询的数据局部性感知任务调度程序
DOI：
10.1016/j.future.2018.04.086
复制
发表时间：
2019
影响因子：
7.5
通讯作者：
Song Aibo
中科院分区：
文献类型：
--
作者：
Jin Jiahui;Luo Junzhou;Du Mingyang;Dang Yongcheng;Li Feng;Zhang Jinghui;Song Aibo
对于Facebook和Twitter等大型在线社交网络，网络分析通常使用图查询来提取网络信息。由于所需的工作和内存，这类查询通常以分布式方式执行。然而，现有的大多数分布式图计算系统都针对离线图分析而不是在线图查询进行优化。这种方法的问题是，图查询任务必须在短时间内传输大量数据并交互地回答查询。为了解决这一问题，我们提出了一种新的数据局部性感知任务调度算法，该算法优化了交互式分布式图查询。该调度算法综合考虑了数据布局和图拓扑结构，降低了数据传输成本。在一个实际的分布式图计算系统中实现了该调度算法，并通过仿真和真实社交图查询对该任务调度器的有效性进行了评估。结果表明，我们的调度器将查询时间减少了一个数量级。
For large-scale online social networks such as Facebook and Twitter, network analysis often uses graph queries to extract network information. Because of the work and memory required, usually such queries are performed in a distributed manner. However, most existing distributed graph computation systems optimize for offline graph analysis rather than online graph queries. The problem with this approach is that graph query tasks then must transfer a large volume of data and interactively answer queries within a short time frame. To resolve this, we propose a novel data-locality-aware task scheduling algorithm that optimizes interactive distributed graph queries. The scheduling algorithm jointly considers data placement and graph topology to reduce data transfer costs. After implementing the scheduling algorithm in a real-world distributed graph computation system, we evaluate the task scheduler’s effectiveness through simulations and real-life social graph queries. Results show that our scheduler reduces the querying time by one order of magnitude.