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

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-01 发布日期:2014-08-10
通讯作者: 廖彬
作者简介:廖彬(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-01 Published:2014-08-10
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]. 计算机应用, 0, (): 0-0.
[4]	王周恺, 张炯, 马维纲, 王怀军. 面向高速列车监测数据的并行解压缩算法[J]. 计算机应用, 2021, 41(9): 2586-2593.
[5]	李卓, 宋子晖, 沈鑫, 陈昕. 边缘计算支持下的移动群智感知本地差分隐私保护机制[J]. 计算机应用, 2021, 41(9): 2678-2686.
[6]	赵津宋文爱邰隽杨吉江王青李晓丹雷毅邱悦. 儿童阻塞性睡眠呼吸暂停计算机人脸辅助诊断综述[J]. 计算机应用, 0, (): 0-0.
[7]	张妮韩萌王乐李小娟程浩东. 基于正负效用划分的高效用模式挖掘方法综述[J]. 计算机应用, 0, (): 0-0.
[8]	武鹏, 吴尽昭. 基于线性误差断言的推理方法[J]. 计算机应用, 2021, 41(8): 2199-2204.
[9]	孙蕊, 韩萌, 张春砚, 申明尧, 杜诗语. 含负项top-k高效用项集挖掘算法[J]. 计算机应用, 2021, 41(8): 2386-2395.
[10]	王梓森, 梁英, 刘政君, 谢小杰, 张伟, 史红周. 科研项目同行评议专家学术专长匹配方法[J]. 计算机应用, 2021, 41(8): 2418-2426.
[11]	赵全, 汤小春, 朱紫钰, 毛安琪, 李战怀. 大规模短时间任务的低延迟集群调度框架[J]. 计算机应用, 2021, 41(8): 2396-2405.
[12]	康军, 黄山, 段宗涛, 李宜修. 时空轨迹序列模式挖掘方法综述[J]. 计算机应用, 2021, 41(8): 2379-2385.
[13]	陈静, 毛莺池, 陈豪, 王龙宝, 王子成. 基于改进单点多盒检测器的大坝缺陷目标检测方法[J]. 计算机应用, 2021, 41(8): 2366-2372.
[14]	马华, 陈跃鹏, 唐文胜, 娄小平, 黄卓轩. 面向工作者能力评估的众包任务分配方法的研究进展综述[J]. 计算机应用, 2021, 41(8): 2232-2241.
[15]	李莉吴怡杨祉坤陈云鹏. 基于分区型区块链医疗电子病历共享方案[J]. , 0, (): 0-0.

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

Task scheduling and resource selection algorithm with data-dependent constraints

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics