Task scheduling and resource selection algorithm with data-dependent constraints

doi:10.11772/j.issn.1001-9081.2014.08.2260

Journal of Computer Applications ›› 2014, Vol. 34 ›› Issue (8): 2260-2266.DOI: 10.11772/j.issn.1001-9081.2014.08.2260

Previous Articles Next Articles

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

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

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

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

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

Abstract

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.

摘要：

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

CLC Number:

TP311
TP274

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.

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

References

［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]	. Research advances in blockchain consensus mechanisms and improvement algorithms [J]. Journal of Computer Applications, 0, (): 0-0.
[2]	. Blockchain-based identity management system for internet of things [J]. Journal of Computer Applications, 0, (): 0-0.
[3]	Bo LI, Jianqiang HUANG, Dongqiang HUANG, Xiaoying WANG. Adaptive computing optimization of sparse matrix-vector multiplication based on heterogeneous platforms [J]. Journal of Computer Applications, 2024, 44(12): 3867-3875.
[4]	Ziqian CHEN, Kedi NIU, Zhongyuan YAO, Xueming SI. Review of blockchain lightweight technology applied to internet of things [J]. Journal of Computer Applications, 2024, 44(12): 3688-3698.
[5]	Tingting GAO, Zhongyuan YAO, Miao JIA, Xueming SI. Overview of on-chain and off-chain consistency protection technologies [J]. Journal of Computer Applications, 2024, 44(12): 3658-3668.
[6]	Miao JIA, Zhongyuan YAO, Weihua ZHU, Tingting GAO, Xueming SI, Xiang DENG. Progress and prospect of zero-knowledge proof enabling blockchain [J]. Journal of Computer Applications, 2024, 44(12): 3669-3677.
[7]	Kedi NIU, Min LI, Zhongyuan YAO, Xueming SI. Review of blockchain consensus algorithms for internet of things [J]. Journal of Computer Applications, 2024, 44(12): 3678-3687.
[8]	Jinhui CAI, Zhongxu YIN, Guoxiao ZONG, Junru LI. Integrated method of inference and taint analysis for nested branch breakthrough [J]. Journal of Computer Applications, 2024, 44(12): 3823-3830.
[9]	. Heterogeneous Environment Aware Streaming Graph Partitioning for Power-Law Graphs [J]. Journal of Computer Applications, 0, (): 0-0.
[10]	. Source code vulnerability detection method based on Transformer-GCN [J]. Journal of Computer Applications, 0, (): 0-0.
[11]	. Partial label regression algorithm integrating feature attention and residual connection [J]. Journal of Computer Applications, 0, (): 0-0.
[12]	. Cloud-edge collaborative data storage and retrieval architecture for industrial scenarios [J]. Journal of Computer Applications, 0, (): 0-0.
[13]	Jinxing TU, Zhixiong LI, Jianqiang HUANG. Dynamic partition algorithm for diagonal sparse matrix vector multiplication based on GPU [J]. Journal of Computer Applications, 2024, 44(11): 3521-3529.
[14]	Li ZENG, Jingru YANG, Gang HUANG, Xiang JING, Chaoran LUO. Survey on hypergraph application methods： issues， advances， and challenges [J]. Journal of Computer Applications, 2024, 44(11): 3315-3326.
[15]	. Two-stage data selection method for classifier with high performance and low energy consumption [J]. Journal of Computer Applications, 0, (): 0-0.

Task scheduling and resource selection algorithm with data-dependent constraints

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

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics