Data Science and Engineering (DSE)是由中国计算机学会(CCF)主办，数据库专业委员会承办，施普林格·自然(Springer Nature)集团出版的开放获取(OA)期刊。本篇文章精选自DSE最新一期发文，得到中新赛克赞助文章处理费。

文章介绍

 随着互联网和社交媒体的不断发展，图数据的规模与日俱增。传统的集中式数据存储无法满足巨量的并发查询操作，分布式数据存储则逐渐成为了主流。针对在分布式系统中进行高效的图数据分区问题，已进行了广泛而深入地研究。由于流式图数据分区方法能够在有限的资源下扩展到非常大的图，因此它成为目前研究的热点。然而，大多数方法没有考虑到工作负载和图数据特征，导致节点负载的不平衡和节点间的通信开销增加，从而降低查询性能。此外，已有的工作负载感知方法没有考虑实际环境中的动态变化，导致无法提供良好的性能。

 针对上述问题和挑战，本文提出了一种新的工作负载自适应流数据分区器WASP，它结合了在线查询的动态工作负载特性和图的拓扑特征，实现了低延迟和高吞吐的在线图数据查询。WASP有两个主要特征：（1）能根据频繁查询模式和图拓扑特征来管理节点的重新分配，为了保持分布式图数据的分区质量，本文的重新分配策略是动态的而非一次性的；（2）对于重新分配的计算任务，本文采用增量式的元数据管理，主要的权重计数信息通过Redis保持在内存中，以保证快速存储和访问。因此，耗时的计算任务可以被不断更新的权值取代。总的来说，对于动态工作负载，本文提出的方法比最新的图存储速度快得多，并增加了访问高级别图节点的并行能力。

实验效果

图1展示了WASP和相关工作在不同工作负载下的分区质量对比，其中SW表示静态工作负载，DW表示动态工作负载。可以看到，（1）对于静态工作负载，WASP是优于Hermes的简单哈希分区策略，但是没有Peng的分区方法好，这是由于其把工作负载信息作为先验知识，但是实际情形是不可能的。（2）对于动态工作负载，WASP全面领先于两个对比方法，在静态工作负载下表现的极为优秀的Peng的方法则性能非常糟糕，这是由于之前的先验知识无法适应动态变化的工作负载。

图1 不同工作负载下的IPT率对比图

 图2展示了不同分区器在静态负载下的负载平衡情况。可以看出，WASP全面领先Hermes和Peng的方法，不同分区间的负载不平衡情况是最低的。尽管其他方法也采取了一定的负载平衡措施，但由于高度顶点的所有边都被分组在一起，导致聚集高度顶点的机器节点会有大量的计算任务而超载。

图2 静态负载下的不平衡因子对比图

 图3展示了WASP在各项阈值下对实际性能的影响，其中重新分配阈值控制顶点重新分配过程的触发，边日志大小则会影响活动边缘的寿命和分区的质量。图3(a)-3(c)为重分配阈值对边割率、顶点重分配数目以及实际查询执行时间三个重要指标的影响。从图3(a)可以看出，重分配阈值越大，对应的边割率就越高。这是由于阈值的增大，会导致重分配频次降低，进而影响了活跃顶点的及时重分配，从而边割率直线上升。和图3(a)相反，图3(b)中的顶点重分配数目则是随着重分配阈值的增加而急剧降低。从图3(c)可以看出阈值变化和实际执行时间成V字形变化。这是由于执行时间受到前面边割率和顶点重分配数据两个因素的共同影响，因此重分配阈值为10时，实际效果最佳。

图3 重分配阈值分析和边日志大小分析图

 图4展示了顶点分裂阈值对顶点平均复制数目的影响，而分裂阈值控制着高度顶点的分裂，虽然它可以减轻计算负载时的不平衡，但分裂边会导致高阶顶点数据的复制，从而带来额外的网络开销。实验结果表明，随着分裂阈值的增加，复制的顶点数目减少，导致平均复制数急剧减少。然而，在这两个数据集中，平均副本数几乎不敏感的拆分阈值大于100，本文的实验选择100作为分裂阈值。

图4 分区阈值分析对比图

 图5展示了WASP在有无自适应挖掘频繁查询模式对实际执行时间的影响。从图中可以看出，去掉自适应策略后，查询执行时间随着查询数目的增长而急剧上升。相对而言，在使用自适应策略后，其累计执行时间显著减少了近6倍，一旦我们的方法开始适应，大多数未来的查询将在较少的网络开销中得到解决。对比两个不同数据集，二者行为则没有显著差异，也就是说，WASP自适应策略对数据集是不敏感的。

图5 WASP自适应性对比图

       图6展示了数据集大小对WASP性能的影响，其中图6(a)为自适应和无自适应方法在查询时间性能的对比，图6(b)是在吞吐量性能的对比。从图中可以看出，随着数据集的规模变大，每个查询的平均响应时间增加，1分钟内回答的查询数量相应减少。然而，与无自适应方法相比，自适应方法的增减速度是渐进的。因此可以说查询性能和吞吐量在不同图规模下是可伸缩的。

图6 不同数据规模下的性能表现

结语

本文提出了一种新的工作负载自适应流分区器WASP，能够提供低延迟和高吞吐量的在线查询。作者计划通过工作负载驱动的复制策略来提高静态工作负载中查询的性能。

作者简介

Ali Davoudian，加拿大卡尔顿大学计算机学院博士。主要研究方向为大数据管理与分析。

陈柳，武汉大学计算机学院博士研究生，主要研究方向为大数据管理和RDF流数据处理。

涂宏伟，武汉大学计算机学院硕士研究生，主要研究方向为大数据管理。

刘梦赤，华南师范大学教授、杰青。主要研究方向为数据库系统、大数据管理与分析。

期刊简介

Data Science and Engineering（DSE）是由中国计算机学会（CCF）主办、数据库专业委员会承办、施普林格 自然（Springer Nature）出版的Open Access期刊。为了迎合相关领域的快速发展需求，DSE致力于出版所有和数据科学与工程领域相关的关键科学问题与前沿研究热点，以大数据作为研究重点，征稿范畴主要包括4方面：（1）数据本身，（2）数据信息提取方法，（3）数据计算理论，和（4）用来分析与管理数据的技术和系统。

目前期刊已被ESCI与SCOPUS收录，CiteScore2020为4.9，在Computer Science Applications领域排名#181/693（73^rd Percentile）。稿件处理费由赞助商中新赛克（Sinovatio）承担，欢迎大家免费下载阅读期刊全文，并积极投稿。

原文链接：

https://link.springer.com/article/10.1007/s41019-021-00156-2