MapReduce (MR) computing paradigm and its open source implementation Hadoop have become a de facto standard to process big data in a distributed environment. Initially, the Hadoop system was homogeneous in three significant aspects, namely, user, workload, and cluster (hardware). However, with growing variety of MR jobs and inclusion of different configurations of nodes in the existing cluster, heterogeneity has become an essential part of Hadoop systems. The heterogeneity factors adversely affect the performance of a Hadoop scheduler and limit the overall throughput of the system. To overcome this problem, various heterogeneous Hadoop schedulers have been proposed in the literature. Existing survey works in this area mostly cover homogeneous schedulers and classify them on the basis of quality of service parameters they optimize. Hence, there is a need to study the heterogeneous Hadoop schedulers on the basis of various heterogeneity factors considered by them. In this survey article, we first discuss different heterogeneity factors that typically exist in a Hadoop system and then explore various challenges that arise while designing the schedulers in the presence of such heterogeneity. Afterward, we present the comparative study of heterogeneous scheduling algorithms available in the literature and classify them by the previously said heterogeneity factors. Lastly, we investigate different methods and environment used for evaluation of discussed Hadoop schedulers.
DeanJ, GhemawatS. MapReduce: Simplied data processing on large clusters. In: Proceedings of the 6th Symposium on Operating Systems Design & Implementation. San Francisco, CA, 2004. pp. 137–149.
4.
MalewiczG, AusternMH, BikAJ, et al.Pregel: a system for large-scale graph processing. In: Proceedings of the 2010 International Conference in Management of Data—SIGMOD'10. Indianapolis, IN, 2010. pp. 135–146.
5.
Giraph—Welcome To Apache Giraph!. Available online at http://giraph.apache.org (last accessed June29, 2017).
6.
ZahariaM, ChowdhuryM, DasT, DaveA. Resilient distributed datasets: A fault-tolerant abstraction for in-memory cluster computing. NSDI. San Jose, CA, 2012.
7.
Foundation A. 2015. Spark Lightning-fast cluster computing. Spark. Apache.Org. Available online at https://spark.apache.org (last accessed June29, 2017).
8.
The Apache Software Foundation. 2015. Apache Storm. Available online at http://storm.apache.org (last accessed June29, 2017).
ChohanN, CastilloC, SpreitzerM, SteinderM. See spot run: Using spot instances for MapReduce workflows. HotCloud. 2010; 2012:1–7. Available online at http://dl.acm.org/citation.cfm?id=1863110 (last accessed May7, 2017).
11.
LiR, HuH, LiH, et al.MapReduce parallel programming model: A state-of-the-art survey. Int J Parallel Program. 2016; 44:832–866.
12.
ShvachkoK, KuangH, RadiaS, ChanslerR. The Hadoop Distributed File System. In: 2010 IEEE 26th Symposium on Mass Storage Systems and Technologies, MSST2010. Washington, DC, 2010.
13.
Welcome to Apache Pig! Available online at https://pig.apache.org (last accessed June25, 2017).
MoseleyB, DasguptaA, KumarR, SarlósT. On scheduling in map-reduce and flow-shops. In: Proceedings of the 23rd ACM Symposium on Parallelism Algorithms and Architectures—SPAA'11. San Jose, CA, 2011. pp. 289–298.
18.
AggarwalV, XuM, LanT, SubramaniamS. On the optimality of scheduling dependent MapReduce tasks on heterogeneous machines. 2017, arXiv preprint arXiv:1711.09964.
19.
ZhuY, JiangY, WuW, et al.Minimizing makespan and total completion time in MapReduce-like systems. In: Proceedings - IEEE INFOCOM, 2014, pp. 2166–2174.
20.
FischerMJ, SuX, YinY. Assigning tasks for efficiency in Hadoop. In: Proceedings of the 22nd ACM Symposium on Parallelism in Algorithms and Architectures—SPAA'10, New York, NY: ACM Press, 2010, p. 30.
ZahariaM, KonwinskiA, JosephAD, et al.Improving MapReduce performance in heterogeneous environments. In: OSDI'08 Proceedings of the 8th USENIX Conference on Operating Systems and Design and Implementation. San Diego, CA, 2008. pp. 29–42.
YooD, SimKM. A comparative review of job scheduling for MapReduce. In: 2011 IEEE International Conference on Cloud Computing and Intelligence Systems, IEEE, Beijing, China, 2011. pp. 353–358.
25.
HarshithaR, RekhaGS, GuruprasadHS. A survey on scheduling techniques in Hadoop. Int J Eng Dev Res; 3:2321–9939.
26.
MohamedE, HongZ. Hadoop-MapReduce job scheduling algorithms survey. In: Proceedings—2016 7th International Conference on Cloud Computing and Big Data, CCBD 2016, IEEE, Taipa, Macau, China, 2017. pp. 237–242.
27.
VarmaR. Survey on MapReduce and scheduling algorithms in Hadoop. Int J Sci Res. 2013; 14:2319–7064.
28.
NimbalkarPP, GadekarDP. Survey on Scheduling Algorithm in MapReduce Framework. Int J Sci Eng Technol Res. 2015; 4:1226–1230.
29.
ThomasL. Survey on MapReduce scheduling algorithms. Int J Comput Appl. 2014; 95:975–8887.
30.
RaoBT, ReddyLSS. Survey on improved scheduling in Hadoop MapReduce in cloud environments. Int J Comput Appl. 2011; 34:975–8887.
EkanayakeJ, LiH, ZhangB, et al.Twister: a runtime for iterative MapReduce. In: Proceedings of the 19th ACM International Symposium on High Performance Distributed Computing—HPDC'10. Chicago, IL, 2010. pp. 810–818.
35.
Disco MapReduce. Available online at http://discoproject.org (last accessed January10, 2018).
36.
DouA, KalogerakiV, GunopulosD, et al.Misco. In: Proceedings of the 3rd International Conference on PErvasive Technologies Related to Assistive Environments—PETRA'10, New York, NY: ACM Press, 2010. p. 1.
GhodsiA, ZahariaM, HindmanB, et al.Dominant resource Fairness: Fair allocation of multiple resource types maps reduces. In: Proceedings of the 8th USENIX Conference on NSDI. Boston, MA, Vol. 11, p. 24.
VermaA, PedrosaL, KorupoluM, et al.Large-scale cluster management at Google with Borg. In: Proceedings of the Tenth European Conference on Computer Systems—EuroSys'15. Bordeaux, France, 2015. pp. 1–17.
44.
SchwarzkopfM, KonwinskiA. Omega: flexible, scalable schedulers for large compute clusters. In: EuroSys'13 Proceedings of the 8th ACM European Conference on Computer Systems. Prague, Czech Republic, 2013. pp. 351–364.
45.
OusterhoutK, WendellP, ZahariaM, SparrowStoica I.. In: Proceedings of the Twenty-Fourth ACM Symposium on Operating Systems Principles—SOSP'13, New York, NY: ACM Press, 2013. pp. 69–84.
46.
RasooliA, DownDG. Guidelines for selecting Hadoop schedulers based on system heterogeneity. J Grid Comput. 2014; 12:499–519.
47.
RasooliA, DownDG. COSHH: A classification and optimization based scheduler for heterogeneous Hadoop systems. Future Gener Comput Syst. 2014; 36:1–15.
48.
ZahariaM, BorthakurD, SarmaJS, et al.Job Scheduling for Multi-User MapReduce Clusters. EECS Department, University of California, Berkeley Technical Report UCBEECS200955 April 2009; UCB/EECS-2009-55.
LeeG, ChunB, KatzR. Heterogeneity-aware resource allocation and scheduling in the cloud. In: Proceedings of the 3rd USENIX conference on Hot topics in Cloud computing (HotCloud 2011), USENIX Association, Berkeley, CA, 2011.
54.
YaoY, WangJ, ShengB, et al.HaSTE: Hadoop YARN scheduling based on task-dependency and resource-demand. In: IEEE International Conference on Cloud Computing (CLOUD). Anchorage, AK, 2014. pp. 184–191.
55.
ZahariaM, BorthakurD, Sen SarmaJ, et al.Delay scheduling. In: Proceedings of the 5th European Conference on Computer Systems—EuroSys'10, New York, NY: ACM Press, 2010. p. 265.
VermaA, CherkasovaL, CampbellRH. Orchestrating an ensemble of MapReduce jobs for minimizing their makespan. IEEE Trans Dependable Secur Comput. 2013; 10:314–327.
59.
TianW, LiG, YangW, BuyyaR. HScheduler: an optimal approach to minimize the makespan of multiple MapReduce jobs. J Supercomput. 2016; 72:2376–2393.
ChenQ, ZhangD, GuoM, et al.SAMR: A self-adaptive MapReduce scheduling algorithm in heterogeneous environment. In: 2010 10th IEEE International Conference on Computer and Information Technology, IEEE, Bradford, West Yorkshire, UK, 2010. pp. 2736–2743.
62.
ChenQ, GuoM, DengQ, et al.HAT: History-based auto-tuning MapReduce in heterogeneous environments. J Supercomput. 2013; 64:1038–1054.
63.
YangS-J, ChenY-R. Design adaptive task allocation scheduler to improve MapReduce performance in heterogeneous clouds. J Netw Comput Appl. 2015; 57:61–70.
64.
MashayekhyL, NejadMM, GrosuD, et al.Energy-aware scheduling of MapReduce jobs for big data applications. IEEE Trans Parallel Distrib Syst. 2015; 26:2720–2733.
65.
TangZ, ZhouJ, LiK, LiR. MTSD: A task scheduling algorithm for MapReduce base on deadline constraints. In: Proceedings of the 2012 IEEE 26th International Parallel and Distributed Processing Symposium Workshops, IPDPSW 2012, IEEE, Shanghai, China, 2012. pp. 2012–2018.
66.
PoloJ, CastilloC, CarreraD, et al.Resource-aware adaptive scheduling for MapReduce clusters. In: Proceedings of 12th International Middleware Conference. Lisbon, Portugal, 2011. pp. 180–199.
67.
TianC, ZhouH, HeY, ZhaL. A dynamic MapReduce scheduler for heterogeneous workloads. In: 8th International Conference on Grid and Cooperative Computing GCC 2009. Lanzhou, China, 2009. pp. 218–224.
68.
NanduriR, MaheshwariN, ReddyrajaA, VarmaV. Job aware scheduling algorithm for MapReduce framework. In: Proceedings—2011 3rd IEEE International Conference on Cloud Computing Technology and Science (CloudCom) 2011. Athens, Greece, Novemeber 2011. pp. 724–729.
69.
HallM, FrankE, HolmesG, et al.The WEKA data mining software. ACM SIGKDD Explor Newsl. 2009; 11:10.
YaoY, TaiJ, ShengB, MiN. Lsps: A job size-based scheduler for efficient task assignments in Hadoop. IEEE Trans Cloud Comput. 2015; 3:411–424.
72.
ZhangQ, ZhaniMF, YangY, et al.PRISM: Fine-grained resource-aware scheduling for MapReduce. IEEE Trans Cloud Comput. 2015; 3:182–194.
73.
VermaA, CherkasovaL, CampbellRH. ARIA: Automatic resource inference and allocation for MapReduce environments. In: Proceedings of the 8th ACM International Conference on Autonomic Computing—ICAC'11, New York, NY: ACM Press, 2011. p. 235.
74.
HerodotouH, LimH, LuoG, et al.A self-tuning system for big data analytics. Cidr. 2011; 11:261–272.
75.
SunX, HeC, LuY. ESAMR: An enhanced self-adaptive MapReduce scheduling algorithm. In: Proceedings of the International Conference on Parallel and Distributed Systems—ICPADS, Singapore, 2012. pp. 148–155.
76.
WitteveenC, GuptaS, FritzC, et al.ThroughputScheduler: Learning to schedule on heterogeneous Hadoop clusters. In: 10th International Conference on Autonomic Computing ICAC'13, San Jose, CA, June 26th–28th, 2013. pp. 159–165.
77.
KumarKA, KonishettyVK, VorugantiK, RaoGVP. CASH: Context aware scheduler for Hadoop. In: Proceedings of the International Conference on Advances in Computing, Communications and Informatics; ICACCI'12. Chennai, India, 2012. pp. 52–61.
78.
YigitbasiN, DattaK, JainN, WillkeT. Energy efficient scheduling of MapReduce workloads on heterogeneous clusters. In: Green Computing Middleware on Proceedings of the 2nd International Workshop—GCM'11, Lisbon, Portugal, 2011. pp. 1–6.
