一种高效的面向高并发图分析任务的存储系统

作     者：赵进 姜新宇 张宇 廖小飞 金海 刘海坤 杨赟 张吉 王彪 余婷 Jin ZHAO;Xinyu JIANG;Yu ZHANG;Xiaofei LIAO;Hai JIN;Haikun LIU;Yun YANG;Ji ZHANG;Biao WANG;Ting YU

作者机构：华中科技大学大数据技术与系统国家地方联合工程研究中心武汉430074 华中科技大学服务计算技术与系统教育部重点实验室武汉430074 华中科技大学集群与网格计算湖北省重点实验室武汉430074 华中科技大学计算机科学与技术学院武汉430074 School of Sciences University of Southern QueenslandToowoomba 4350Australia 之江实验室杭州311121 

基　　金：国家重点研发计划(批准号:2018YFB1003500) 国家自然科学基金(批准号:61832006,61825202,62072193) 之江实验室开放课题(批准号:2021KD0AB01)、之江实验室PI研究项目(批准号:111007-PI2001) 浙江省自然科学基金(批准号:LZ21F030001)资助项目 

出 版 物：《中国科学：信息科学》 (Scientia Sinica(Informationis))

年 卷 期：2022年第52卷第1期

页      码：111-128页

摘      要：随着现实世界中图计算需求的快速增长,同一平台上往往并发运行着大量迭代图分析任务.然而,现有的图计算系统主要是为了高效执行单个图分析任务而设计的.因此,当多个并发图分析任务同时在同一个底层图上并行执行时,现有图计算系统会面临巨大的数据访问开销.为了提高并发图分析任务的吞吐量,现有的核外并发图处理方案通过共享图数据减少并发任务的数据存储与访问开销.但是,由于现实世界中图的图顶点度数幂律分布特性以及图分析任务之间的差异性,现有方案在访问数据时依旧存在着大量的不必要的冗余I/O开销.这是因为即使静态图分区中绝大部分顶点处于非活跃状态或者只被少数图分析任务共享,现有方法也依旧会将整个分区加载入内存供并发图分析任务处理.为解决上述问题,本文提出了一个面向并发图分析任务的高效存储系统GraphDP.它能够插入到现有核外图计算系统中来透明有效地减少现有图计算系统执行并发图分析任务时的存储消耗与数据访问开销,从而提高并发图分析任务的吞吐量.具体来说,GraphDP使用一种新颖的动态I/O调度策略,能够使系统以最优的I/O访问方式完成图数据的加载,并有效地减少加载到内存和cache的数据.同时,GraphDP通过高效的缓存机制在内存中优先缓存被频繁访问的图数据,从而进一步减少数据访问开销.为证明GraphDP的有效性,我们将GraphDP插入到目前流行的核外图计算系统中,包括GridGraph,GraphChi和X-Stream.实验结果表明,GraphDP分别将GridGraph,GraphChi和X-Stream的吞吐量提高了1.57~2.19倍,1.86~2.37倍和1.62~2.21倍.

主 题 词：迭代图处理 并发任务 存储系统 I/O开销 吞吐量 

学科分类：08[工学] 081201[081201] 0812[工学-测绘类] 

核心收录：

D　O　I：10.1360/SSI-2021-0020

馆 藏 号：203107144...