ارائه یک الگوریتم زمانبندی جدید برای کاهش زمان محاسبات در محیط هادوپ

پاکیزه, سید رضا; عارفی نژاد, سیدمجید

ارائه یک الگوریتم زمانبندی جدید برای کاهش زمان محاسبات در محیط هادوپ

نوع مقاله : مقاله پژوهشی

نویسندگان

¹ مربی گروه کامپیوتر، دانشگاه علمی‌– کاربردی، دهدشت، ایران

² دانشجوی کارشناسی‌ارشد، دانشگاه افسری و تربیت پاسداری امام حسین(ع)

چکیده

امروزه پروژه متن‌باز هادوپ به‌همراه چهارچوب نگاشت-کاهش در بین مؤسسات، سازمان‌ها و محققین محبوبیت زیادی دارد که برای پردازش حجم انبوهی از داده‌ها به‌صورت موازی بر روی خوشه‌ای از کامپیوتر‌ها بسیار مناسب است. نگاشت-کاهش برای حل مشکلات محاسبات داده‌های حجیم معرفی شده است که از قاعده تقسیم-غلبه پیروی می‌کند. مانند هر جای دیگر، مبحث زمان و زمان‌بندی در نگاشت-کاهش از اهمیت بسیار بالایی برخوردار است. به‌همین دلیل در دهه اخیر الگوریتم‌های زمانبندی متعددی در این زمینه تدارک یافته است. ایده اصلی این الگوریتم‌ها افزایش نرخ محلی‌‌سازی داده، همزمان‌سازی، کاهش زمان پاسخ و زمان اتمام وظایف می‌باشد. اکثر این الگوریتم‌ها تک هدفه می‌باشند و فقط یکی از موارد ذکر شده را مورد هدف قرار می‌دهند. الگوریتمهای چند هدفه موجود فقط بر روی یکی از فازهای اول یا دوم نگاشت-کاهش تمرکز دارند. در این مقاله، یک الگوریتم زمانبندی ترکیبی مبتنی بر اولویت‌بندی پویا کار‌ها و محلی‌‌سازی داده در محیط نگاشت‌-کاهش به نام "HSMRPL" ارائه می‌‌شود که هدف اصلی آن افزایش نرخ محلی‌سازی داده و کاهش زمان محاسبات می‌باشد. در این الگوریتم از دو روش اولویت‌بندی پویا و شناسه محلی‌‌سازی استفاده می‌شود. برای ارزیابی الگوریتم پیشنهادی، آن‌ را با الگوریتم‌های پیش‌فرض هادوپ و به کمک محک‌های استاندارد مقایسه کردیم. نتایج حاصله نشان می‌دهد که الگوریتم پیشنهادی ما نرخ محلی‌سازی را نسبت به الگوریتم FIFO، 5/18 درصد و نسبت به الگوریتم Fair، 4/10 درصد افزایش داده است. همچنین، الگوریتم پیشنهادی ما نسبت به الگوریتم FIFO، 8/3 درصد و نسبت به Fair، 4/13 درصد سریعتر است.

کلیدواژه‌ها

20.1001.1.23224347.1399.8.2.5.7

عنوان مقاله [English]

A New Scheduling Algorithm to Reduce Computation Time in Hadoop Environment

نویسندگان [English]

S. R. Pakize ¹
S. M. Arefi Nejad ²

¹ Master of Computer Architecture, Scientific and Research Center, Sepah Fath, Kohgiluyeh and Boyer Ahmad, Iran.

² Master of Electrical-Control ,Scientific and Research Center, Sepah Fath, Kohgiluyeh and Boyer Ahmad, Iran.

چکیده [English]

Nowadays, the Hadoop open-source project with the MapReduce framework has become very popular as it processes vast amounts of data in parallel on large clusters of commodity hardware in a reliable and fault-tolerant manner. MapReduce was introduced to solve large-data computational problems, and is dependent on the divide and conquer principle. Time and scheduling are always the most important aspects, hence in the past decades in the MapReduce environment, many scheduling algorithms have been proposed. The main ideas of these algorithms are increasing data locality rate, and decreasing response time and completion time. In this research we have proposed a new hybrid scheduling algorithm (HSMRPL) which uses dynamic job priority and identity localization techniques, and focuses on increasing data locality rate and decreasing completion time. We have evaluated and compared our algorithm with hadoop default schedulers by running concurrent workloads consisting of the WordCount and Terasort benchmarks. The results show that our proposed algorithm has increased the localization rate by 10.4% and 18.5% and the speed by 3.14% and 3.3% compared to the FIFO algorithm and the Fair algorithm respectively.

کلیدواژه‌ها [English]

MapReduce Scheduling
Hybrid Algorithm
Data Locality
Dynamic Priority
Hadoop Scheduling

مراجع

[1] J. Dean and S. Ghemawat, “MapReduce: Simplified Data Processing On Large Clusters,” Communications of the ACM, vol. 51(1), pp. 107-113, 2008.##

[2] M. Zaharia, A. Konwinski, A. D. Joseph, R. H. Katz, and I. Stoica, “Improving MapReduce Performance in Heterogeneous Environments,” In OSDI, vol. 8, no. 4, p. 7, 2008.##

[3] T. White, “Hadoop: The definitive guide,” O'Reilly Media, Inc., 2012.##

[4] S. Perera, “Hadoop MapReduce Cookbook,” Packt Publishing Ltd, 2013.##

[5] S. R. Pakize, “A Comprehensive View of Hadoop Map Reduce Scheduling Algorithms,” International Journal of Computer Networks and Communications Security, ISSN, pp. 2308-9830, 2014.##

[6] V. Prajapati, “Big Data Analytics with R and Hadoop,” Packt Publishing Ltd, 2015.##

[7] I. Hashem, T. Abaker, et al., “MapReduce Scheduling Algorithms: a review,” The Journal of Supercomputing, pp. 1-31, 2018.##

[8] K. Hadjar and A. Jedidi, “A New Approach for Scheduling Tasks and/or Jobs in Big Data Cluster,” 4th MEC International Conference on Big Data and Smart City (ICBDSC), IEEE, 2019.##

[9] M. Zaharia, D. Borthakur, J. Sen Sarma, K.Elmeleegy, S. Shenker, and I. Stoica, “Delay Scheduling: A Simple Technique for Achieving Locality and Fairness in Cluster Scheduling,” In Proceedings of the 5th European conference on Computer systems, pp. 265-278, 2010.##

[10] Q. Chen, D. Zhang, M. Guo, Q. Deng, and S. Guo, “Samr: A Self-adaptive Mapreduce Scheduling Algorithm in Heterogeneous Environment,” In Computer and Information Technology (CIT), IEEE 10th International Conference on, pp. 2736-2743, 2010.##

[11] L. Lei, T. Wo, and C. Hu, “CREST: Towards Fast Speculation of Straggler Tasks in MapReduce,” In e-Business Engineering (ICEBE), IEEE 8th International Conference on, pp. 311-316, 2011.##

[12] C. He, Y. Lu, and D. Swanson, “Matchmaking: A new Mapreduce Scheduling Technique,” In Cloud Computing Technology and Science (CloudCom), IEEE Third International Conference on, pp. 40-47, 2011.##

[13] P. Nguyen, T. Simon, M. Halem, D. Chapman, and Q. Le, “A Hybrid Scheduling Algorithm for data Intensive Workloads in a Mapreduce Environment,” In Proceedings of the IEEE/ACM Fifth International Conference on Utility and Cloud Computing, pp. 161-167, 2012.##

[14] S. Ibrahim, H. Jin, L. Lu, B. He, G. Antoniu, and S. Wu, “Maestro: Replica-aware Map Scheduling for Mapreduce,” In Cluster, Cloud and Grid Computing (CCGrid), 12th IEEE/ACM International Symposium on, pp. 435-442, 2012.##

[15] F. Ahmad, S. Lee, M. Thottethodi, and T. N. Vijaykumar, “MapReduce with Communication Overlap (MaRCO),” Journal of Parallel and Distributed Computing, vol. 73(5), pp. 608-620, 2013.##

[16] A.Rasooli and D. G. Down, “COSHH: A Classification and Optimization Based Scheduler for Heterogeneous Hadoop systems,” Future Generation Computer Systems, vol. 36, pp. 1-15, 2014.##