数据依赖约束下的任务调度资源选择算法

doi:10.11772/j.issn.1001-9081.2014.08.2260

计算机应用 ›› 2014, Vol. 34 ›› Issue (8): 2260-2266.DOI: 10.11772/j.issn.1001-9081.2014.08.2260

数据依赖约束下的任务调度资源选择算法

廖彬¹,于炯²,张陶³,杨兴耀²

1. 新疆财经大学统计与信息学院，乌鲁木齐830012；
2. 新疆大学软件学院，乌鲁木齐830008；
3. 新疆医科大学医学工程技术学院，乌鲁木齐830011；

收稿日期:2014-02-12 修回日期:2014-04-15 发布日期:2014-08-10 出版日期:2014-08-01
通讯作者: 廖彬
作者简介:廖彬(1986-),男,四川内江人,博士研究生,主要研究方向：数据库、云计算、绿色计算；于炯(1964-),男,北京人,教授,博士生导师,博士,主要研究方向：网络安全、网格与分布式计算；张陶(1988-),女,新疆乌鲁木齐人,硕士,主要研究方向：分布式计算、网格计算；杨兴耀(1984-),男,新疆乌鲁木齐人,博士研究生,主要研究方向：分布式计算、网格计算与推荐系统。
基金资助:
国家自然科学基金资助项目;新疆维吾尔自治区自然科学基金资助项目

Task scheduling and resource selection algorithm with data-dependent constraints

LIAO Bin¹,YU Jiong²,ZHANG Tao³,YANG Xingyao²

1. College of Statistics and Information, Xinjiang University of Finance and Economics, Urumqi Xinjiang 830012, China;
2. School of Software, Xinjiang University, Urumqi Xinjiang 830008, China;
3. Medical Engineering College, Xinjiang Medical University, Urumqi Xinjiang 830011, China;

Received:2014-02-12 Revised:2014-04-15 Online:2014-08-10 Published:2014-08-01
Contact: LIAO Bin

摘要/Abstract

摘要：

大数据环境下的计算任务往往具有一定数据依赖性关系(如MapReduce)，现有的分布式存储系统任务资源选择策略选择离请求者最近的数据块响应服务，忽略了对数据块所在服务器CPU、磁盘I/O与网络等资源负载状态的考虑。在分析研究系统集群结构、文件分块、数据块存储机制的基础上，定义了集群节点矩阵、CPU负载矩阵、磁盘I/O负载矩阵、网络负载矩阵、文件分块矩阵、数据块存储矩阵与数据块存储节点状态矩阵，为任务与数据之间的依赖性构建了基础数据模型，提出了一种数据依赖约束下的最优资源选择算法(ORS2DC)。任务调度节点负责维护基础数据，MapReduce任务与数据块读取任务由于依赖资源不同而采取不同的选择策略。实验结果表明：所提算法能够为任务选择质量更高的资源，提高任务完成质量的同时减轻了NameNode负担，减小了单点故障发生的概率。

Abstract:

Like MapReduce, tasks under big data environment are always with data-dependent constraints. The resource selection strategy in distributed storage system trends to choose the nearest data block to requestor, which ignored the server's resource load state, like CPU, disk I/O and network, etc. On the basis of the distributed storage system's cluster structure, data file division mechanism and data block storage mechanism, this paper defined the cluster-node matrix, CPU load matrix, disk I/O load matrix, network load matrix, file-division-block matrix, data block storage matrix and data block storage matrix of node status. These matrixes modeled the relationship between task and its data constraints. And the article proposed an optimal resource selection algorithm with data-dependent constraints (ORS2DC), in which the task scheduling node is responsible for base data maintenance, MapRedcue tasks and data block read tasks take different selection strategies with different resource-constraints. The experimental results show that, the proposed algorithm can choose higher quality resources for the task, improve the task completion quality while reducing the NameNode's load burden, which can reduce the probability of the single point of failure.

中图分类号:

TP311
TP274

廖彬于炯张陶杨兴耀. 数据依赖约束下的任务调度资源选择算法[J]. 计算机应用, 2014, 34(8): 2260-2266.

LIAO Bin YU Jiong ZHANG Tao YANG Xingyao. Task scheduling and resource selection algorithm with data-dependent constraints[J]. Journal of Computer Applications, 2014, 34(8): 2260-2266.

参考文献

［1］MENG X, CI X. Big data management: concepts, techniques and challenges ［J］. Journal of Computer Research and Development, 2013: 50(1): 146-149.(孟小峰,慈祥.大数据管理：概念、技术与挑战［J］.计算机研究与发展,2013,50(1):146-149.)
［2］GHEMAWAT S, GOBIOFF H, LEUNG S. The Google file system ［C］// Proceedings of the 19th ACM Symposium on Operating System Principles. New York: ACM Press, 2003: 29-43.
［3］DHRUBA B. The Hadoop distributed file system: architecture and design ［EB/OL］.(2007-07-01)［2014-01-20］. http://hadoop.apache.org/common/docs/r0.18.2/hdfs_design.pdf.
［4］CHANG F, DEAN J, GHEMAWAT S, et al. Bigtable: a distributed storage system for structured data ［C］// OSDI'06: Proceedings of the 7th USENIX Symposium on Operating Systems Design and Implementation. Berkeley: USENIX Association, 2006: 205-218.
［5］WANG P, MENG D, ZHAN J, et al. Review of programming mod-els for data-intensive computing ［J］. Journal of Computer Research and Development, 2010, 47(11): 1993-2002.(王鹏,孟丹,詹剑锋,等.数据密集型计算编程模型研究进展［J］.计算机研究与发展,2010,47(11):1993-2002.)
［6］DEAN J, GHEMAWAT S. MapReduce: simplified data processing on large clusters ［C］// OSDI'04: Proceedings of the 6th Symposium on Operating System Design and Implementation. Berkeley: USENIX Association, 2004: 137-150.
［7］LUDASCHER B, ALTINTAS I, BERKEY C, et al. Scientific workflow management and the Kepler system ［J］. Concurrency and Computation: Practice and Experience, 2005, 18(10): 1039-1065.
［8］OINN T, ADDIS M, FERRIS J, et al. Taverna: a tool for the composition and enactment of bioinformatics workflows ［J］. Bioinformatics, 2004, 20(17): 3045-3054.
［9］WIECZOREK M, PRODAN R, FAHRINGER T. Scheduling of scientific workflows in the ASKALON grid environment ［J］. SIGMOD Record, 2005, 34(3): 56-62.
［10］FEDAK G, HE H, CAPPELLO F. BitDew: a programmable environment for large-scale data management and distribution ［C］// Proceedings of the 2008 ACM/IEEE Conference on Supercomputing. Piscataway: IEEE Press, 2008: 1-12.
［11］YUAN D, YANG Y, LIU X, et al. A data placement strategy in scientific cloud workflows ［J］. Future Generation Computer Systems, 2010, 26(8): 1200-1214.
［12］ZHENG P, CUI L, WANG H, et al. A data placement strategy for data-intensive applications in cloud ［J］. Chinese Journal of Computers, 2010, 33(8): 1472-1480.(郑湃,崔立真,王海洋,等.云计算环境下面向数据密集型应用的数据布局策略与方法［J］.计算机学报,2010,33(8):1472-1480.)
［13］MOTWANI R, WIDOM J, ARASU A, et al. Query processing, approximation, and resource management in a data stream management system ［C］// Proceedings of the 1st Biennial Conference on Innovative Data Systems Research. Waltham: Morgan Kaufmann Publishers, 2003: 245-256.
［14］ABADI D, CARNEY D, CETINTEMEL U, et al. Aurora: a new model and architecture for data stream management ［J］. The VLDB Journal, 2003, 12(2): 120-139.
［15］CHNDRASEKARAN S, COOPER O, DESHPANDE A, et al. TelegraphCQ: continuous dataflow processing for an uncertain world ［C］// Proceedings of the 1st Biennial Conference on Innovative Database Systems Research. Waltham: Morgan Kaufmann Publishers, 2003: 269-280.
［16］CARNEY D, CETINTEMEL U, CHERNIACK M. Monitoring streams: a new class of data management applications ［C］// Proceedings of the 28th International Conference on Very Large Data Bases. Waltham: Morgan Kaufmann Publishers, 2002: 215-226.
［17］SUTHERLAND T, PIELECH B, ZHU Y, et al. An adaptive multi-objective scheduling selection framework for continuous query processing ［C］// Proceedings of the 9th International Database Engineering and Applications Symposium. Washington, DC: IEEE Computer Society, 2005: 445-454.
［18］SCHMIDT S, BERTHOLD H, LEHNER W. QStream: deterministic querying of data streams ［C］// Proceedings of the Thirtieth International Conference on Very large Data Bases. Waltham: Morgan Kaufmann Publishers, 2005: 1365-1368.
［19］WU S, YU G, LYU Y, et al. A deterministic QoS guaranteeing approach for data stream processing ［J］. Journal of Software, 2008, 19(8), 2066-2079.(武珊珊,于戈,吕雁飞,等.数据流处理中确定性QoS的保证方法［J］.软件学报,2008,19(8):2066-2079.)
［20］LIAO B, YU J, ZHANG T, et al. Energy-efficient algorithms for distributed file system HDFS ［J］. Chinese Journal of Computers, 2013, 36(5): 1047-1064.(廖彬,于炯,张陶,等.基于分布式文件系统HDFS的节能算法［J］.计算机学报,2013,36(5):1047-1064.)
［21］LIAO B, YU J, QIAN Y, et al. The node failure recovery algorithm for distributed file system based on measurement of data availability ［J］. Computer Science, 2013, 40(1): 144-149.(廖彬,于炯,钱育蓉,等.基于可用性度量的分布式文件系统节点失效恢复算法［J］.计算机科学,2013,40(1):144-149.)
［22］LIAO B, YU J, SUN H, et al. Energy-efficient algorithms for distributed storage system based on data storage structure reconfiguration ［J］. Journal of Computer Research and Development, 2013: 50(1): 3-18.(廖彬,于炯,孙华,等.基于存储结构重配置的分布式存储系统节能算法［J］.计算机研究与发展,2013,50(1):3-18.)
［23］CALHEIROS R, RANJAN R, BELOGLAZOV A, et al. Cloud-Sim: a toolkit for modeling and simulation of cloud computing environments and evaluation of resource provisioning algorithms ［J］. Software: Practice and Experience, 2010, 41(1): 23-50.

[1]	高威刘丽华和斌涛邓方安. 区块链共识机制与改进算法研究进展[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[2]	翟社平朱鹏举杨锐刘佳一腾. 基于区块链的物联网身份管理系统[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[3]	李博, 黄建强, 黄东强, 王晓英. 基于异构平台的稀疏矩阵向量乘自适应计算优化[J]. 《计算机应用》唯一官方网站, 2024, 44(12): 3867-3875.
[4]	陈姿芊, 牛科迪, 姚中原, 斯雪明. 适用于物联网的区块链轻量化技术综述[J]. 《计算机应用》唯一官方网站, 2024, 44(12): 3688-3698.
[5]	高婷婷, 姚中原, 贾淼, 斯雪明. 链上链下一致性保护技术综述[J]. 《计算机应用》唯一官方网站, 2024, 44(12): 3658-3668.
[6]	贾淼, 姚中原, 祝卫华, 高婷婷, 斯雪明, 邓翔. 零知识证明赋能区块链的进展与展望[J]. 《计算机应用》唯一官方网站, 2024, 44(12): 3669-3677.
[7]	牛科迪, 李敏, 姚中原, 斯雪明. 面向物联网的区块链共识算法综述[J]. 《计算机应用》唯一官方网站, 2024, 44(12): 3678-3687.
[8]	蔡锦辉, 尹中旭, 宗国笑, 李俊儒. 面向嵌套分支突破的推断与污点分析融合的方法[J]. 《计算机应用》唯一官方网站, 2024, 44(12): 3823-3830.
[9]	杨巍白璐宁俊义董建军单春海信俊昌. 异构环境感知的幂律图流划分方法[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[10]	梁辰王奕森魏强杜江. 基于Transformer-GCN的源代码漏洞检测方法[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[11]	吴海峰陶丽青程玉胜. 集成特征注意力和残差连接的偏标签回归算法[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[12]	秦学程刘春颜李宝赵蕴龙. 面向工业场景的云边协同数据存储与检索架构[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[13]	涂进兴, 李志雄, 黄建强. 基于GPU对角稀疏矩阵向量乘法的动态划分算法[J]. 《计算机应用》唯一官方网站, 2024, 44(11): 3521-3529.
[14]	曾蠡, 杨婧如, 黄罡, 景翔, 罗超然. 超图应用方法综述：问题、进展与挑战[J]. 《计算机应用》唯一官方网站, 2024, 44(11): 3315-3326.
[15]	崔双双王宏志朱加昊吴昊. 面向低能耗高性能的分类器两阶段数据选择方法[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.

数据依赖约束下的任务调度资源选择算法

Task scheduling and resource selection algorithm with data-dependent constraints

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics