一种高效的跨平台工作流优化方法

doi:10.19678/j.issn.1000-3428.0064163

摘要/Abstract

摘要： 为了应对复杂的数据分析任务，研究人员设计开发出结合多个平台的跨平台数据处理系统。系统跨平台工作流中算子的平台选择对于系统性能至关重要，因为算子在不同平台上的实现会产生性能间的显著差异。目前多使用基于成本的优化方法来实现跨平台工作流的平台选择，但现有的成本模型由于无法挖掘跨平台工作流的潜在信息而导致成本估计不准确。提出一种高效的跨平台工作流优化方法，采用GGFN模型作为成本模型，以算子特征和工作流特征作为模型输入，利用图注意力机制捕捉有向无环图型跨平台工作流的结构信息和算子邻居节点信息，同时结合门控循环单元记忆算子的运行时序信息，从而实现准确的成本估计。在此基础上，根据跨平台工作流的特点设计算子实现平台的枚举算法，利用基于GGFN的成本模型和延迟贪婪剪枝方法进行枚举操作，为每个算子选择合适的实现平台。实验结果表明，该方法可以将跨平台工作流的执行性能提升3倍，运行时间缩短60%以上。

关键词: 跨平台工作流, GGFN模型, 图注意力机制, 门控循环单元, 枚举算法

Abstract: To manage complex data analysis tasks, cross-platform data processing systems combining multiple platforms are being developed.The platform selection of operators in the cross-platform workflow of the system is critical to the system performance, because the implementation of operators on different platforms will result in significantly different performances.Currently, cost-based optimization methods are primarily applied in cross-platform workflow optimization to achieve platform selection;however, the existing cost models cannot mine the potential information of cross-platform workflows, thus resulting in inaccurate cost estimation.Hence, a more efficient cross-platform workflow optimization method is proposed herein.This method uses the GAT-BiGRU-FC Network(GGFN) model as the cost model, which uses both operator and workflow features as model inputs.The model uses a graph attention mechanism to capture the structure information of the Directed Acyclic Graph(DAG)-type cross-platform workflow and the information of the neighbor nodes of the operator.The gated recurrent unit is used to memorize the operation timing information of operators to achieve accurate cost estimations.Subsequently, the enumeration algorithm of the operator implementation platform is designed and implemented based on the characteristics of the cross-platform workflow.The algorithm utilizes the GGFN-based cost model and delay-greedy pruning method to perform enumeration and selects the appropriate implementation platform for each operator.Experiments show that this method can improve the execution performance of cross-platform workflows by 3x and reduce the runtime by more than 60%.

Key words: cross-platform workflow, GGFN model, graph attention mechanism, Gated Recurrent Unit(GRU), enumeration algorithm

中图分类号:

TP391

杜清华, 张凯. 一种高效的跨平台工作流优化方法[J]. 计算机工程, 2022, 48(7): 13-21,28.

DU Qinghua, ZHANG Kai. An Efficient Cross-Platform Workflow Optimization Method[J]. Computer Engineering, 2022, 48(7): 13-21,28.

https://www.ecice06.com/CN/Y2022/V48/I7/13

图/表 12

20220806175819

20220806175822

20220806175825

20220806175829

20220806175832

20220806175836

20220806175839

20220806175843

20220806175847

20220806175851

20220806175856

20220806175859

参考文献

[1] AGRAWAL D, CHAWLA S, CONTRERAS-ROJAS B, et al.RHEEM:enabling cross-platform data processing[J].Proceedings of the VLDB Endowment, 2018, 11(11):1414-1427.
[2] GOG I, SCHWARZKOPF M, CROOKS N, et al.Musketeer:all for one, one for all in data processing systems[C]//Proceedings of the 10th European Conference on Computer Systems.New York, USA:ACM Press, 2015:1-16.
[3] MATEI Z, MOSHARAF C, TATHAGATA D, et al.Resilient distributed datasets:a fault-tolerant abstraction for in-memory cluster computing[C]//Proceedings of USENIX Symposium on Networked Systems Design and Implementation.[S.1.]:USENIX Association, 2012:15-28.
[4] 屠要峰, 陈小强, 周士俊, 等.Geno:基于代价的异构融合查询优化器[J].软件学报, 2022, 33(3):774-796. TU Y F, CHEN X Q, ZHOU S J, et al.Geno:cost-based heterogeneous fusion query optimizer[J].Journal of Software, 2022, 33(3):774-796.(in Chinese)
[5] DOKA K, PAPAILIOU N, GIANNAKOURIS V, et al.Mix ‘n’ match multi-engine analytics[C]//Proceedings of IEEE International Conference on Big Data.Washington D.C., USA:IEEE Press, 2016:194-203.
[6] 孟小峰, 马超红, 杨晨.机器学习化数据库系统研究综述[J].计算机研究与发展, 2019, 56(9):1803-1820. MENG X F, MA C H, YANG C.Survey on machine learning for database systems[J].Journal of Computer Research and Development, 2019, 56(9):1803-1820.(in Chinese)
[7] KRUSE S, KAOUDI Z, CONTRERAS-ROJAS B, et al.RHEEMix in the data jungle:a cost-based optimizer for cross-platform systems[J].The VLDB Journal, 2020, 29(6):1287-1310.
[8] WANG J J, BAKER T, BALAZINSKA M, et al.The myria big data management and analytics system and cloud services[C]//Proceedings of the 8th Biennial Conference on Innovative Data Systems Research.Washington D.C., USA:IEEE Press, 2017:2467-1476.
[9] KAOUDI Z, QUIANÉ-RUIZ J A, CONTRERAS-ROJAS B, et al.ML-based cross-platform query optimization[C]//Proceedings of the 36th IEEE International Conference on Data Engineering.Washington D.C., USA:IEEE Press, 2020:1489-1500.
[10] SUN J, LI G L.An end-to-end learning-based cost estimator[J].Proceedings of the VLDB Endowment, 2019, 13(3):307-319.
[11] MARCUS R, NEGI P, MAO H Z, et al.BAO:making learned query optimization practical[C]//Proceedings of 2021 International Conference on Management of Data.New York, USA:ACM Press, 2021:1275-1288.
[12] MARCUS R, PAPAEMMANOUIL O.Plan-structured deep neural network models for query performance prediction[J].Proceedings of the VLDB Endowment, 2019, 12(11):1733-1746.
[13] MARCUS R, NEGI P, MAO H Z, et al.Neo:a learned query optimizer[J].Proceedings of the VLDB Endowment, 2019, 12(11):1705-1718.
[14] 余翔, 柴成亮, 张辛宁, 等.AlphaQO:鲁棒的学习型查询优化器[J].软件学报, 2022, 33(3):814-831. YU X, CHAI C L, ZHANG X N, et al.AlphaQO:robust learned query optimizer[J].Journal of Software, 2022, 33(3):814-831.(in Chinese)
[15] ZHANG J, LIU Y, ZHOU K, et al.An end-to-end automatic cloud database tuning system using deep reinforcement learning[C]//Proceedings of 2019 International Conference on Management of Data.Washington D.C., USA:IEEE Press, 2019:415-432.
[16] HUANG D X, LIU Q, CUI Q, et al.TiDB[J].Proceedings of the VLDB Endowment, 2020, 13(12):3072-3084.
[17] SPARKS E R, VENKATARAMAN S, KAFTAN T, et al.KeystoneML:optimizing pipelines for large-scale advanced analytics[C]//Proceedings of the 33rd IEEE International Conference on Data Engineering.Washington D.C., USA:IEEE Press, 2017:535-546.
[18] 毕里缘, 伍赛, 陈刚, 等.基于循环神经网络的数据库查询开销预测[J].软件学报, 2018, 29(3):799-810. BI L Y, WU S, CHEN G, et al.Database query cost prediction using recurrent neural network[J].Journal of Software, 2018, 29(3):799-810.(in Chinese)
[19] SIDDIQUI T, JINDAL A, QIAO S, et al.Cost models for big data query processing:learning, retrofitting, and our findings[C]//Proceedings of 2020 ACM SIGMOD International Conference on Management of Data.New York, USA:ACM Press, 2020:99-113.
[20] BEGOLI E, CAMACHO-RODRÍGUEZ J, HYDE J, et al.Apache calcite:a foundational framework for optimized query processing over heterogeneous data sources[C]//Proceedings of 2018 International Conference on Management of Data.Washington D.C., USA:IEEE Press, 2018:221-230.
[21] ELMORE A, DUGGAN J, STONEBRAKER M, et al.A demonstration of the BigDAWG polystore system[J].Proceedings of the VLDB Endowment, 2015, 8(12):1908-1911.
[22] HUTCHISON D, HOWE B, SUCIU D.LaraDB:a minimalist kernel for linear and relational algebra computation[C]//Proceedings of the 4th ACM SIGMOD Workshop on Algorithms and Systems for MapReduce and Beyond.New York, USA:ACM Press, 2017:1-10.
[23] PETAR V, GUILLEM C, ARANTXA C, et al.Graph attention networks[C]//Proceedings of the 6th International Conference on Learning Representations.Washington D.C., USA:IEEE Press, 2018:5421-5436.
[24] THOMAS N, MAX W.Semi-supervised classification with graph convolutional networks[C]//Proceedings of International Conference on Learning Representations.New York, USA:ACM Press, 2017:325-337.
[25] CHO K, VAN MERRIENBOER B, GULCEHRE C, et al.Learning phrase representations using RNN encoder-decoder for statistical machine translation[C]//Proceedings of 2014 Conference on Empirical Methods in Natural Language Processing.Stroudsburg, USA:Association for Computational Linguistics, 2014:1078-1083.
[26] RHEINLÄNDER A, HEISE A, HUESKE F, et al.SOFA:an extensible logical optimizer for UDF-heavy data flows[J].Information Systems, 2015, 52:96-125.
[27] VENTURA F, KAOUDI Z, QUIANÉ-RUIZ J A, et al.Expand your training limits!Generating training data for ML-based data management[C]//Proceedings of 2021 International Conference on Management of Data.New York, USA:ACM Press, 2021:1865-1878.

选择文件类型/文献管理软件名称

选择包含的内容