4.1.1 Deadline schedulers

These schedulers are specifically designed for special use cases where the deadline constraints are essential requirements in the Service Level Agreement (SLA). The schedulers usually try to predict the near-optimal approximation of the deadline for long-running jobs. Authors (Teng et al., 2014) proposed the paused rate monotonic (PRM) scheduling algorithm that defines a certain response time for deadline constraints services of SLA and provisions coexisting service sharing in a cloud environment. It proposes a real-time scheduling technique to deliver broad formulation and theoretical analysis of Hadoop scheduling. It considers different dimensions of the real-time scheduling problem. First, it models services as a series of map reduce tasks and articulates the problem by identifying the features of tasks, algorithms, and clusters. Second, it develops a PRM scheduling algorithm for priority determined algorithms and to schedule tasks on the basis of their constraints. It pauses the MapReduce job in between the map and reduce phases to optimize the default system by using this time for partitioning, sorting, and combining intermediate results of the map phase. It helps maximize the number of tasks meeting their deadline and analyzed them claiming better performance than other real-time scheduling. In contrast , ParaTimer (Morton et al., Reference Morton, Balazinska and Grossman2010) is designed for Dynamic Acyclic Graphs (DAGs) flair jobs written for Hadoop, and it estimates DAG progress in MapReduce. It distinguishes a critical path that takes longer than others in a comparable query plan. It makes the indicator overlook other shorter paths when approximating progress because the longest path would subsidize the overall execution time. It leads to this rule of thumb about Hadoop performance: ‘making the size of the data block bigger makes Hadoop work faster’.

D-Scheduler (Kc & Anyanwu Reference Kc and Anyanwu2010) is a deadline-based scheduling approach designed to satisfy the problem of long-running Hadoop jobs. In this work, the authors proposed two models to solve this problem. First is a job execution model which considers metrics like mappers and reducers running time, data distribution, and input data; and schedules the jobs on the basis of these metrics. Second is a deadline approximation approach to estimate the deadline for a single job based on certain assumptions, such as homogeneity in cluster, uniform distribution of keys throughout the cluster, data already transferred and stored in HDFS, and asynchronous execution of mappers and reducers; although they allow these assumptions to be broken at a later stage. To meet the response time SLA constraints (i.e., deadline), it is the obligation of the scheduling algorithm to estimate the number of container slots necessary to finish the job within the deadline and stated requirements to ensure the specified job receives those slots. The SLA Constraints algorithm accepts a job only if the estimated minimum number of slots required to meet the deadline SLA are available at its arrival time. After acceptance of a job, the scheduling algorithm maintains the minimum number of tasks running for the job to meet the deadline. It calculates the number of map and reduce tasks ( $$N_{m}^{{min}} $$ , $$N_{r}^{{min}} $$ ) depending on the input data set, output data sizes (σ, Fσ), time required to process the block of data by mapper, time for reduce task execution, and time for Shue phase to transfer data (c _m , c _r , c _d ). It also takes the arrival time of job (A), deadline of job (D), and starting time of map and reduce tasks (s _m , s _r ) into account for calculating the minimum number of mappers and reducers using the following equations.

(1) $$N_{m}^{{min}} {\equals}[{{\sigma \,{\asterisk}\,c_{m} } \over {(S_{r}^{{max}} \,{\minus}\,S_{m} )}}]$$

(2) $$N_{r}^{{min}} {\equals}[{{F\,\sigma \,{\asterisk}\,c_{r} } \over {(A{\plus}D\,{\minus}\,F\sigma \,{\asterisk}\,c_{d} \,{\minus}\,s_{r} )}}]$$

The earliest deadline first algorithm accepts a job if its deadline can be met with the idle containers available after allotting the minimum required container slots to the jobs in the system. The algorithm assigns the necessary slots to jobs in increasing order of their deadlines. All extra free slots are distributed among certain jobs to finish them swiftly before the arrival of the new jobs.

4.1.2 Dynamic schedulers

Dynamic schedulers are the scheduling algorithms that can work in dynamic environments and are able to adopt the changes in the required situations. The default scheduler in Hadoop schedules the reduce tasks of a job the moment one of the map tasks has completed. This often leads to a ‘slot hoarding’ problem where long-running reduce tasks continue waiting for all the map tasks to finish and thus waste CPU resources in busy-waiting. Authors in the multi-user MR job scheduler (Zaharia et al., 2009) propose a different approach from the default one in the case where the reduce task is executed. They split the reduce task into ‘copy’ and ‘compute’ phases and use their new algorithm to schedule the reduce tasks. The copy phase begins to collect the intermediate data after the completion of map tasks, while the compute phases process those intermediate data after they are collected and made available. They set a limit on the number of copy and compute phases running on each node such that the number of compute processes is always higher than that of the copy processes.

Nanduri et al. (2011) propose a task vector-based model, job-aware scheduler, to maintain congruence among jobs in the cluster by allocating tasks to nodes without affecting other tasks. They divide the job into map tasks and reduce tasks based on characteristics of the task, such as CPU-intensive, memory-intensive, disk-intensive, or network-intensive. It uses the task vector for the representation of each task and resource vector for each node. A task vector (T _j ) is the combination of CPU, memory, disk and network utilization variables (CPU _j , mem _j , disk _j , NW _j ) of job j, as shown in the equation below,

(3) $$T_{j} {\equals}CPU_{j} \,{\asterisk}\,e1{\plus}mem_{j} \,{\asterisk}\,e2{\plus}disk_{j} \,{\asterisk}\,e3{\plus}NW_{j} \,{\asterisk}\,e4$$

where e1, e2, e3, and e4 are a weight base for each variable. Similarly, a resource vector is the summation of available resources on the node. The task assignment uses two algorithms to check task compatibility with the requesting node. First, incremental Naive Bayes classifier is used to determine task compatibility with the task tracker specification using its vectors. Second, the heuristic-based algorithm is used to test the compatibility of the task with the task tracker. This is accomplished through computing the T _{availabilityvector} as the difference of T _r (total resource) and T _compoundand finally compute the T _unused (unused resources). Using these heuristics, a combination value is computed and compared to the threshold to determine the compatibility of a task with the specified task tracker. This approach claims a 21% improvement of response time in the heuristic-based technique and a 27% improvement using the machine learning technique.

The dynamic proportional (DP) share (Sandholm & Lai Reference Sandholm and Lai2010) scheduling technique is an extension of the default Hadoop scheduler to provide QoS to users based on certain priorities. It provides a user interface to select which job to schedule and prioritize among the total jobs. It also gives users the capability to adjust their allotted resources to scale-up and scale-down according to the job requirements. It supports preemption to avoid starvation and guarantees extra payment for holding the resources for a long time. It adopts to dynamic job priorities determined from their SLAs. The DP scheduler addresses the problem of Hadoop’s Fair scheduler that is maintaining separate queues for separate pools, guaranteed service over time, and manual priority settings. It ensures that resource consumption is only allowed until the budget for the user is available. Despite being one of the most reliable schedulers that take QoS into account, it does not consider data locality or data replication, which has a firm ground on the dynamic proportional shares scheduling decision much precise and improved performance guarantee.

Dynamic smart speculative (Chen et al., Reference Chen, Liu and Xiao2014) proposed a new speculative execution algorithm to stun the problems that affect the performance for already implemented speculation techniques in Hadoop system, such as data skew, improper phase percentage configuration, and asynchronous start of certain tasks. However, it degrades cluster efficiency which implies a degradation of performance for batch jobs. While job scheduler (Xia et al., 2011) schedules tasks only on healthy nodes that have a lower ratio of error occurrence, it reduces the resource waste from failing tasks. When a healthy node reports an available slot, the Euclidean distance D between characteristic variables of a job is calculated by the following equation,

(4) $$D{\equals}(C_{{idle}} \,{\minus}\,C_{{usage}} )^{2} \,{\plus}\,(I_{{idle}} \,{\minus}\,I_{{usage}} )^{2} {\plus}[{{(M_{{idle}} \,{\minus}\,M_{{usage}} )} \over {(M_{{idle}} )}}]^{2} $$

where C _idle , I _idle , and M _idle are the available resources on the node and C _usage , I _usage , and M _usage are the resources utilized by map and reduce tasks running on the node.

4.1.3 Delay schedulers

These schedulers usually consider delaying some jobs for a certain time, so that other jobs can benefit from the time delay. They attempt to ensure fairness by giving a slot to the job that has the fewest running tasks. Delay-based schedulers reduce starvation for small jobs at the cost of hurting the data locality. The delay scheduler (Zaharia, Borthakur, et al., Reference Zaharia and Borthakur2010) follows the principle of giving a fair share of resources to jobs, including newly arrived jobs. In the Hadoop default FIFO scheduling algorithm, the task is scheduled and launched on any node (even to a non-local node) when it reaches the head of the waiting queue. Delay scheduler interrupts this FIFO principle and allows the task at the head of the queue to wait for its locality by delaying it and executing it at the data local node. Delay scheduler uses long task balancing and hot-spot replication to reduce the chance of a node becoming stuck in long tasks and simultaneous access to a small data file by multiple jobs. In long task balancing, it considers the new jobs as long tasks and identifies them as small tasks if they finish swiftly. In hot-spot replication, it replicates the tiny data file at runtime to be available on numerous nodes and it could be used by multiple jobs simultaneously. Through experimentation, a Facebook workload mix showed that smaller jobs benefit more from the Delay algorithm (Zaharia, Borthakur, et al., Reference Zaharia and Borthakur2010) at the cost of longer jobs. In the case of IO-intensive jobs, those jobs with a large number of map tasks perform better than the jobs with a higher number of reduce tasks. It claims an almost five-times improvement in the response times of small jobs and a two-times increase in throughput for IO-intensive jobs.

4.2.1 Environment-aware schedulers

The environment-aware schedulers are those schedulers which can adopt to a variety of different situations and environment. These environments include the running environment, i.e., homogeneous or heterogeneous environment, data distributions, resource characteristics, job characteristics, etc. There are numerous research efforts in this area including LATE (Zaharia et al., 2008), Self-Adaptive MapReduce (SAMR) (Chen et al., Reference Chen, Zhang, Guo, Deng and Guo2010), Enhanced Self-Adaptive MapReduce (ESAMR ) (Sun et al., Reference Sun, He and Lu2012), and (Ghodsi et al., 2011). We believe that some other reseach proposal from other section can also be considered as part of environment-aware scheduler, but we classify those based on most relevance to a category or subcategory. These and other research efforts in the same category will be explained in detail in the upcoming paragraphs.

LATE (Zaharia et al., 2008), was initially developed for the heterogeneous cluster. It demonstrates that the implicit Hadoop default assumptions could be broken in a heterogeneous (Rao et al., 2012) cluster; for example, default Hadoop assumes nodes that perform roughly at the same rate (i.e., the cluster is composed of homogeneous machines) and constant throughput time could be broken owing to heterogeneity and assumptions, such as no extra cost for launching tasks. LATE exploits the speculative (Chen et al., Reference Chen, Liu and Xiao2014) execution strategy and proposes a new scheduling technique by prioritizing speculative tasks, selecting faster nodes for execution, and limiting the number of speculative copies of tasks using a threshold. It uses heuristics for calculating the Progress Rate (Zaharia et al., 2008) for the identification of faster nodes using the following equation:

(5) $$ProgressRate{\equals}{{ProgressScore} \over {Execution \;Time \;of \;Task}}$$

It schedules the speculative task for only those tasks whose Progress Rate is lower than a threshold based on the slowest task. Furthermore, it schedules the speculative task for the task which has the longest time to completion estimation using the equation below:

(6) $$Time\; to \;Completion{\equals}{{(1\,{\minus}\,ProgressScore)} \over {ProgressRate}}$$

LATE compares the tasks progress rate and maintains a SlowTaskThreshold for the classification of a task as a slow task. It claims to double performance compared to the default Hadoop scheduler in a 200 Amazon’s EC2 (Amazon! 2016d) virtual machine (VM) cluster. Unlike other state-of-the-art research proposals, the estimated remaining execution time for tasks in LATE is based on static information which is not very reliable in many scenarios, leading to improper slower nodes classification within the server.

The SAMR (Chen et al., Reference Chen, Zhang, Guo, Deng and Guo2010) scheduling algorithm proposed to maintain different weights for different map and reduce phases on every node based on task execution time on the specified node. These dynamic weights are used to estimate the time to end of execution of tasks on a specified node. The tasks with the longest time to end are scheduled for speculation. This solves the problem with the LATE (Zaharia et al., 2008) scheduler of using static information for decisions about slow tasks and nodes. SAMR maintains the historical information of each task, and identifies map slow tasks and reduces slow tasks separately. It uses Progress Rate with Average Progress Rate (APR) as

(7) $$PR_{i} \,\lt\,(1\,{\minus}\,STaC)\,{\asterisk}\,APR$$

where STaC is SlowTaskCap ranging from 0 to 1. In the same manner, for the identification of slow TaskTrackers, it uses the following equation:

(8) $$TrR_{{mi}} \,\lt\,(1{\,\minus\,}STrC){\,\asterisk\,}ATrR_{m} $$

where STrC is SlowTrackerCap ranging from 0 to 1. SAMR launches the speculative copies for tasks based on slow tasks and accepts the results of the early finished task of both the original and the speculative copies. It launches the speculative copies on diverse nodes to ensure that they will no longer be slow. SAMR claims a 25% improvement in response time in comparison with the default Hadoop scheduler and a 14% improvement over the LATE (Zaharia et al., 2008) scheduler. However, it often does not consider the type of job, input data size, and nodes types in the calculation of their metrics to be used as the criteria for estimating remaining time of the execution, leading to incorrect classification and poor performance accordingly.

Dynamic scheduling for speculative execution (Jung & Nakazato Reference Jung and Nakazato2014) considers the processing power and system resources of each node to improve the performance while scheduling the speculative copies of the tasks. The authors use the effective speculative execution term to execute backup copies of tasks for a slow node in a heterogeneous environment on faster nodes. They calculate the throughput per second (TPS) (Jung & Nakazato Reference Jung and Nakazato2014) using the following formula,

(9) $$TPS{\equals}{{(Progress_{{i{\plus}1}} {\,\minus\,}Progress_{i} )} \over {(ExecutionTime_{{i{\plus}1}} {\,\minus\,}ExecutionTime_{i} )}}$$

where Progress _i is the ith measurement of task execution ranges from 0 to 1. They calculate the Approximate-time-to-Finish (ATF) as follows,

(10) $$ATF{\equals}{{(1{\,\minus\,}Progress_{i} )} \over {TPS[t]}}$$

and check if the ATF of the specified task tracker is shorter than the first ATF in the ATF list, then a speculative copy of the task will be launched; otherwise it will not launch any copy for the task.

ESAMR (Sun et al., Reference Sun, He and Lu2012) scheduling algorithm is the proposed successor of SAMR (Chen et al., Reference Chen, Zhang, Guo, Deng and Guo2010) and LATE (Zaharia et al., 2008). It solves the issues of LATE and SAMR, such as LATE’s approximation of remaining execution time of tasks not being accurate enough because of its usage of static information which leads to the incorrect classification of slower nodes in the system. ESAMR considers the type of job and input data size in combination with the node type in the calculation of weights for different phases of map and reduce tasks. It categorizes tasks on a node using k-means clustering and stores the weights of different phases of map and reduce tasks for each job class, which in turn is used for estimating time for the completion of each task. From the experimental results, ESAMR claims the lowest error rate in the estimation of time to completion, as compared to SAMR and LATE.

DRF (Ghodsi et al., 2011) was proposed to show highly desirable theoretical properties under Leontief preferences. In DRF, the dominant resource of an entity is the resource for which the entity’s task requires the major fraction of the total availability. DRF aims to maximize the number of allocated tasks, under the constraints that the fraction of the allocated dominant resources (called dominant shares) are equalized. Slowdown Predictor Model (Bortnikov et al., Reference Bortnikov, Frank, Hillel and Rao2012) is another environment-aware approach that improves the Hadoop performance through predicting straggler tasks before they are launched using machine learning. It uses smarter scheduling and avoids unnecessary speculation of tasks, which leads to efficient resource utilization.

4.2.2 Locality-aware schedulers

Data locality is a basic supposition of Hadoop MapReduce framework which critically affects its performance. Hadoop scheduler schedules map and reduce tasks to process data on their local nodes where the input data resides. Execution of tasks locally on the same nodes where the data resides moderates network communication in the cluster in shuing the data across the nodes, which consequently improves the performance of the Hadoop system. The Hadoop system may consist of homogeneous or heterogeneous nodes. There are numerous researchers in academia and industry who consider the performance improvements of Hadoop on the basis of data distribution over the cluster. Purlieus (Palanisamy et al., 2011) proposed a resource allocation system that focuses on clusters of VMs such as Amazon’s elastic compute cloud (EC2) (Amazon! 2016d). They developed an algorithm which improved data locality in the map and reduced phases for the reduction of Hadoop MapReduce network traffic. Their proposed scheme has the following techniques: they place map tasks locally for map-input heavy jobs while reduce tasks can be scheduled on any node in the cluster; schedule reduce tasks locally for the reduce-input heavy jobs; and for the Map-and-Reduce input heavy jobs, both the map and reduce tasks are scheduled in a set of narrowly linked nodes. It introduces a data assignment method in a cloud environment for dynamically assigning VMs to the users, avoiding data redundancy and loading time. It suggests the locality-based cloud service provisioning using VMs placement in an autonomous way. It claims about a 70% reduction in network traffic and a 50% improvement in response time or execution time.

MapReduce Adapted Algorithms to Heterogeneous Environments (MRA++) (Anjos et al., Reference Anjos, Carrera, Kolberg, Tibola, Arantes and Geyer2015) is a new heterogeneity-aware data distribution, task scheduling, and job control mechanism based MapReduce framework design. It uses training tasks to collect information before the distribution of data over the cluster. It adjusts the amount of data processed during the map phase to the distributed computing capability of the nodes. The intermediate data for the Reducer is partitioned into smaller sizes based on the sum of the granularity factors, i.e., the faster nodes process more data than other slower nodes. Owing to the reduction of intermediate data partition sizes, which increases the number of executed tasks and data granularity, a global reduce task queue controls the execution and provides the available nodes with data distribution information for its processing. MRA++ has a higher degree of parallelism for the tasks and higher improvement in the job response time. It achieves a performance gain of approximately 70% in 10-Mbps networks over the native Hadoop system.

The Locality and Network-Aware Reduce Task Scheduling (LoNARS) (Arslan et al., Reference Arslan, Shekhar and Kosar2014) algorithm is proposed for the scheduling of reduce tasks in a Hadoop MapReduce system. It takes data locality and network traffic into consideration while making the scheduling decision. It attempts to schedule the reduce tasks near the map tasks in the system through the data locality approach which implicitly decreases the network traffic. Through network traffic awareness, it distributes the traffic over the whole network and condenses the hot-spots to minimize the effect of the network bottleneck in the Shue phase of Hadoop MapReduce job runtime. LoNARS provides an improvement of approximately 15% in network traffic reduction and 3–4% in total job completion time. Multithreading Task Scheduler (MTL) (Althebyan et al., Reference Althebyan, ALQudah, Jararweh and Yaseen2014) uses a multi-threading technique to schedule the tasks to different data blocks where each thread is assigned to a predetermined block of jobs. It divides the whole cluster into N blocks where each block’s job in the wait queue is scheduled by a specified thread. Each thread searches for the local data block upon the arrival of a job into the ready queue. Threads receive a notification from other threads upon finding the local data for the jobs; hence, other threads stop searching. If none of the threads find a local data block for a task, then that task is scheduled on a non-local node. It acquires its processing advantage through parallel searches by different threads instead of single-threaded processes in similar schedulers. Bi-Hadoop (Yu & Hong Reference Yu and Hong2013) is another locality-based approach which supports dual-map-input applications and attempts to minimize the network resource congestion for such an application.

FIFO with Shareability and Locality-Aware (Wei et al., Reference Wei, Wu, Lee and Hsu2015) scheduling algorithm is a FIFO-based scheduling policy that takes the locality and data sharing probability between tasks into account for its scheduling decisions. The main objective is to gather the tasks that require the same data, batch process them, and reduce the overhead of shuing the data over cluster nodes. The Shared-Input-Policy (Bezerra et al., Reference Bezerra, Hernandez, Espinosa and Moure2013) scheduling algorithm chooses tasks from a waiting queue by investigating the available resources of the cluster to improve cluster performance. Although it cannot predict the resource consumption of waiting jobs, it appropriately submits tasks to the cluster by analyzing the available resources in the cluster.

A variation of the Delay Scheduling algorithm called the Matchmaking (He et al., Reference He, Lu and Swanson2011) algorithm has been proposed to schedule map tasks to improve data locality in the Hadoop system. It provides a fair chance of executing a data-local task to all nodes before launching a non-local task, i.e., it delays the execution on a node until it receives a data-local task instead of delaying a job execution. It always prefers the local map task over non-local tasks. It uses a locality marker for node classification and ensures that all nodes will have a fair chance to seize its local tasks. This has been achieved through relaxation of job scheduling to improve the performance by avoiding data transfer in map tasks.

Hadoop performance in the heterogeneous environment degrades in comparison with a homogeneous cluster. Heterogeneous environment Locality-Aware Scheduler (Zhang et al., 2011) addressed the issues of heterogeneity and locality and proposed a solution to simulate optimal task execution time. It is based on maintaining a tradeoff between task waiting time and transmission time. It first attempts to respond to the Task Tracker request for a task with a task at a local DataNode. In case such task is non-existent, it attempts to assign a task with data closest to the requesting node. It makes this decision based on the metric whether or not waiting time for a task is less than transmission time.

Data-local Reduce Task Scheduler (Geetha et al., Reference Geetha, UdayBhaskar and ChennaReddy2016) proposed to schedule tasks on nodes that tend to result in the least number of bytes shued. This scheduler exploits the index file and heartbeat protocol to gather the information about each map task’s output data stored in the local file system of each Task Tracker node and maintains a data structure of it. For each reduce task ready to be scheduled, the scheduler checks if the requesting Task Tracker is the one that contains the largest amount of intermediate output data. If that is the case, the reduce task is scheduled to that Task Tracker. In other cases, the next requesting Task Tracker is considered, and so on. The modified Job Tracker maintains the data structure that ensures the Task Trackers with the largest intermediate output must run the reducer. Their scheduler minimizes the data-local traffic by 11–80% considering the varying number of mappers and reducers.

USSOP (Su et al., 2011) is a grid-enabled MapReduce framework which provides a set of C-Language based MapReduce APIs and a runtime system for exploiting the computing resources available on public resource grids. The authors proposed Locality-Aware Reduce Scheduling (LARS), specifically designed to minimize data transfer in USSOP. The intermediate data are hashed and stored as regions, as one region may contain different keys. Master node assigns reduce tasks to the grid nodes using the LARS algorithm until all maps are completed, i.e., nodes with the largest region size will be assigned reduce tasks. In this way, LARS avoids transferring large regions out to other nodes. It works better in heterogeneous grid environments. In another research effort, authors of the Minimum Network Resource Consumption (MNRC) (Shang et al., Reference Shang, Chen and Yan2017) model took the liberty of taking two main data streams of slow tasks migration and remote copies of data in the cluster network into consideration using the use case of Hadoop MapReduce clusters. MNRC is used to calculate network resources consumption of reduce tasks to minimize the amount of remote copies of data, in combination with data locality, using their priority scheduling policy for the Reduce task.

In Hadoop, the input data of map tasks are transferred in numerous small parts. Mappers process the first part of the input data upon receiving it and wait until its execution is finished. From there, the next part is transferred and so on, which is a waste of time because data processing and transmission can be carried out in parallel. Improving MapReduce by Data Prefetching (IMPDP) (Gu et al., 2013) introduces a data prefetching mechanism for map tasks using intra-block prefetching in heterogeneous or shared environments. The main objective is to reduce the overhead of data transmission over the network. IMPDP creates a data prefetching thread which requests non-local input data and a prefetching buffer is used to store the temporary data for the task. The data prefetching thread pulls the input data through the network and stores it in the prefetching buffer temporarily, and the map task reads the data from this buffer to process. Experimental results show an approximate 15% improvement in job response time.

4.2.3 Situation-aware schedulers

The situation-aware schedulers are those schedulers which can adopt to different situations among task communications, map execution, shuing, and combining. A number of researchers address situation-awareness in their work in the area of Hadoop optimizations. Certain significant research approaches include Preemption-based Scheduler (Polo et al., 2010), Map Optimizer (Yoo & Sim Reference Yoo and Sim2011), Acclimate MapReduce (Acclimate MR) (Balmin & Beyer Reference Balmin and Beyern.d.), MOMTH (Nita et al., 2015), and Speculative Aware Resource Allocation (SARA) (Ren Reference Ren2015). These research approaches are improving the native Hadoop performance by adapting to situations and using different heuristics. A preemption-based scheduler (Polo et al., 2010) introduces an online job completion time estimator which can be used for fine-tuning the resource provisioning of different jobs. The main objective is performance-driven co-task scheduling in Hadoop MapReduce runtime to provide better resource utilization in a shared environment. The goal is the exploitation of MapReduce’s multiple small tasks capability for the prediction of tasks completion time and characteristics of the wait queue tasks. The fine-tuning of resource provisioning among jobs is based on the estimation of the completion time for individual jobs based on a given set of resources. It also has the capability of preempting other low priority jobs to provision the resources to the high priority job. It allows applications to meet their performance goals without the over-provisioning of physical resources. The scheduler has two strategies to provision resources: a max-scheduler approach, in which all the resources of the Hadoop cluster are allocated when there are enough tasks; and a min-scheduler approach, in which the completion time goal for each job is wisely observed and resources are freed, if possible. Their evaluation is based on four things : job completion time, job with deadlines minimum scheduler, job with deadlines maximum scheduler, and comparison with Facebook’s Fair scheduler.

MOMTH (Nita et al., 2015) expounds on a multi-purpose scheduling algorithm for numerous tasks in the Apache Hadoop big data processing framework. They consider the fine grain functions of users and resources with the constraints of deadline and budget simultaneously. MOMTH addresses the most relevant constraints for Hadoop (i.e., avoiding resource conflict and having a near-optimal cluster workload) and relevant objectives (deadline and budget). This type of scheduler is beneficial when there are cost and time limitations. The authors used a Hadoop integrated tool scheduling load simulator for the evaluation of this research work. They analyzed the performance of MOMTH using MobiWay, which is a collaboration podium to expose the interoperability between a huge number of sensing mobile devices and an extensive variety of mobility applications. SARA (Ren Reference Ren2015) is a distributed and decentralized speculation-aware cluster scheduler. The speculative execution of tasks is a very effective method to mitigate the impact of stragglers, thus far. However, schedulers have to decide between the scheduling of speculative copies of some jobs and original tasks execution of other jobs. They define two guidelines for selecting which tasks should be scheduled for execution in the cluster. The first guideline states that: In the absence of enough slots for every job to maintain its anticipated level of speculation, slots should be dedicated to the smallest jobs, and each job should be given a specified number of slots equal to its virtual size to achieve near-optimal performance. The second guideline states that: In the presence of enough slots to permit every job to maintain its desired level of speculation, slots should be shared proportionally to the virtual sizes of jobs to achieve a near-optimal throughput.

Acclimate MR (Balmin & Beyer Reference Balmin and Beyern.d.) is one of the situation-aware schedulers using the principle of ‘situation awareness in mappers’. It changes the native Hadoop assumption about independent mappers by implementing the mappers which communicate with each other through Distributed Meta Data Store. Unlike the native Hadoop system, the mappers in Acclimate MR communicate for situation awareness. The mappers take a data block for the diminution of initial starting time, Acclimate MR combiner performs local aggregation and caches frequently appearing keys, and their sampling and partitioning (which sample intermediate data and provide well-balanced input to reducers) assists in handling the situation dynamically. The authors claimed evaluation shows that adaptive techniques provide up to three-time performance improvement over native Hadoop, and exponentially improve performance stability across the board.

4.2.4 Replica-aware schedulers

The Hadoop framework uses data replication for the availability and reliability of the system. By default, the replication factor is three, which can be modified using the replication property in the Hadoop configuration file. Replication-awareness is the property of the scheduler which is aware of and changes the behavior of the scheduling policy while taking the number of replicas and distribution information of each replica throughout the cluster. Maestro (Ibrahim et al., 2012) is a probability-based, fine-grained, replica-aware algorithm to alleviate the non-local Map tasks execution problem that relies on the replica-aware execution of Map tasks. It stores the number of unprocessed data blocks in each node j as HCN _j to keep track of all unprocessed data blocks in the cluster. It then calculates the probability of processing a data block non-locally as block weight (WB _i ) using the following equation:

(11) $$WB_{i} {\equals}1{\,\minus\,}\mathop{\sum}\limits_1^r [{1 \over {HCN_{j} }}]$$

where HCN _j represents the number of blocks of data stored in node j of the cluster. Using the replication feature of Hadoop, nodes that share some blocks as replicas present in both the nodes. ShareRate is the number of data blocks a node shares with other nodes and can be calculated as,

(12) $$ShareRateN_{j} {\equals}\mathop {\max }\limits_{1\leq i\leq N} Sb_{j} $$

where Sb _j is the number of shared blocks between N _i and N _j . The scheduler schedules Map task in two phases using the above information: (a) It attempts to ensure Map task executes on all nodes locally. For that reason, it assigns the node-local tasks for blocks with the highest block weights to various nodes in descending order of their shares in the job initialization phase; (b) Upon availability of container at runtime, it schedules an unprocessed block with the highest block weight to minimize the non-local map tasks execution. Maestro demonstrates a 95% improvement in the speculative execution of data local map tasks and a 34% improvement in execution time.

Optimal Task Selection (Suresh & Gopalan Reference Suresh and Gopalan2014) scheduling algorithm is an optimal task selection scheme to assist the scheduler in case multiple local tasks are available for a node. The main objective is to launch the task with the least number of replicas of input data, individual load of disks attached to the node, and the maximum expected waiting time for the next local node to improve the probability of percentage of local tasks launched for a job in future. It shows an improvement of approximately 20% in terms of locality over the HDFS and a significant improvement in fairness without affecting the locality when used with delay scheduling.

Multiple-FIFO (Jin et al., Reference Jin, Yang and Jia2012) based scheduling is an optimization of the native Hadoop’s map assignment mechanism. The Hadoop works on the principle of ‘moving computation to data’; hence, the map task assignments to the free slots on the data node holding the data become a key issue of research. Multiple-FIFO is a two-step technique to optimize the map task assignment mechanism in homogeneous Hadoop clusters. Its technique of scheduling works on: (a) data locality scheduling tactics and (b) replica selection methodologies. It introduces multiple queues in the MapReduce framework to overcome the limitations of FIFO scheduler by their data locality scheduling tactics. Using replica selection methodologies, it estimates the load on nodes for the load balancing in the system using the following equation.

(13) $$load{\equals}A\,{\plus}m_{i} {\,\asterisk\,}B\,{\plus}\,r_{i} {\,\asterisk\,}C$$

where A is the OS overhead, m _i is the ith map task, B is the combined overhead of map tasks, r _i is the ith reduce task, and C denotes the combined overhead of all reduce tasks in the system. They claimed approximately a 2.5-times performance gain over the native Hadoop FIFO scheduler.

4.2.5 Network-aware schedulers

Network-awareness is the property of schedulers to take network traffic information into account while making scheduling decisions. In the Hadoop framework, the network becomes a bottleneck in most situations compared to other resources owing to the shuing of intermediate data over the network. This all-to-all communication in the Shue phase creates the network congestion and degrades the performance of the whole system. Owing to these reasons, adding network awareness to the scheduler to optimize the Hadoop system has become a popular research topic in the last few years. Numerous researchers from academia and industry contributed in the area by adding network-awareness to the native Hadoop system through different techniques to enhance the overall performance of the Hadoop ecosystem. We discuss the key efforts in this area in the following paragraphs in this section.

Recently, Hadoop MapReduce clusters are usually shared among multiple users and jobs for better resource utilization. Job performance in multi-tenant Hadoop cluster is greatly impacted by all-to-all communication in the Shue phase, which leads to network blockage due to heavy network traffic. ShueWatcher (Ahmad et al., Reference Ahmad, Chakradhar, Raghunathan and Vijaykumar2014) is a multi-tenant Hadoop scheduler that minimizes network traffic in the Shue phase while maintaining the particular fairness constraints. It works on the basis of three key techniques. First, it limits intra-job map-shue concurrency to shape network traffic in the Shue phase by procrastinating the Shue phase of a job according to the network traffic load. Second, it favorably allocates a job’s Map tasks to localize the intermediate data to as few nodes as possible by exploiting the minimized intra-job concurrency and flexibility prompted by the replication of map input data for fault tolerance. Third, it exploits a localized map output and delayed shue to reduce the network traffic in Shue phase by preferentially scheduling a job’s Reduce tasks in the nodes holding the intermediate data. It claims a performance gain of 39–46% in cluster throughput and 27–32% in job response time. ShueWatcher works well in shared environment situations, e.g., an overlapping map with Shue phase inter-jobs rather than intra-jobs and adjusting intra-job concurrency for minimized network traffic in the Shue phase.

The BAlance-Reduce (BAR) (Jin et al., 2011) scheduling algorithm introduced a heuristic task scheduling technique which takes a global view and adjusts the data locality of map tasks, vigorously conferring to the network traffic condition and cluster workload. The main objective is to iteratively schedule map tasks to improve the locality of input data, which leads to an improvement in job performance. At the first iteration, the scheduler’s aim is to schedule tasks to local node slots. It considers rack-locality and off-rack locality (non-local execution of tasks) in succeeding iterations. In the case of a poor network situation and overloaded cluster environment, BAR attempts to adjust data locality to enhance resource optimization.

Data locality and the reduce tasks scheduling and partitioning skew may excessively degrade Hadoop performance. The Minimum Transmission Cost Reduce Task Scheduler (MTCRS) (Tang et al., Reference Tang, Wang and Geng2015) proposed a sampling evaluation to solve the issues of partitioning skew and locality of intermediate data for the reduce tasks in the Hadoop system. It uses the transmission cost and waiting time of each reduce task as heuristics for decisions about scheduling reduce tasks in the cluster. It uses the Average Reservoir Sampling algorithm to generate the parameters as sizes and locations of intermediate data partitions to use in a mathematical model for estimating transmission cost as follows,

(14) $$C_{j} (U,v){\equals}\mathop{\sum}\limits_{\matrix{ i{\equals}1 \cr} }^{i{\equals}U} P(i,j){\,\asterisk\,}Dis(U_{i} ,v)$$

where C _j (U, v) symbolizes the estimated transmission cost, P(i, j) denotes partition proportion, and Dis(U _i , v) is the hop distance between node u and node v. U represents the set of nodes containing the intermediate data for a job. This model is used to ultimately calculate the best reduce task launching node in the cluster. MTCRS minimizes approximately 8.4% of the network traffic in the cluster in comparison with Fair scheduler.

High Performance MapReduce Engine (HPMR) (Seo et al., 2009) introduced two optimization schemes, prefetching and pre-shuing, that improve the overall performance in a multi-tenant environment while holding compatibility with the default Apache Hadoop framework. The prefetching exploits the data locality, and pre-shuing aims to minimize the network overhead in all-to-all communication during the Shue phase. The newly introduced prefetching mechanism has two sub-modules. The first one is for the intra-block prefetching to pre-fetch data within a single data block while performing a processing or complex computation. The second is inter-block prefetching to pre-fetch the entire block of replica to a local rack before the processing of that block. The pre-shuing mechanism changes the scheduler to check the map input split and predicts the partitioning of key-value pairs while taking the reducer locations into consideration. The main objective is to schedule map tasks near the future reducer before the map tasks execution. The evaluation results using Yahoo! Grid show a performance gain of approximately 73% in response time over the native Hadoop system.

The default Hadoop scheduler neither considers the data locality of reduce tasks nor addresses the load unbalance among map and reduce tasks, which causes performance degradation. Hammoud & Sakr (Reference Hammoud and Sakr2011) proposed Locality-Aware Reduce Task Scheduling (LARTS), a technique that uses sizes and location of partitions to exploit data locality, i.e., combines data locality with a reduce scheduling policy. It attempts to schedule reducers close to their maximum amount of intermediate input data and conservatively switches to a relaxation strategy seeking a trade-off among the scheduling delay, resource utilization, scheduling skew, and degree of parallelism. It outperforms the native Hadoop performance by an average of 7%. NW-Aware Scheduler (Kondikoppa et al., 2012) introduced a network-aware scheduling algorithm for Hadoop MapReduce system. The transferring of data over the network is costly and causes performance degradation more severely in federated clusters. The authors designed and implemented a network-aware scheduler to be used on federated clusters, improving map tasks scheduling in such environments and accordingly minimized the network traffic overhead leading to an improved performance.

In the Hadoop MapReduce system, if the node creating the intermediate data for a given reduce task is not close to it, then a large amount of data transferring through the network is required to get data to the reduce node, resulting in high network traffic. Another issue is that of the partitioning skew that ascends owing to an unbalanced distribution of map output across nodes, causing a huge amount of input data for some reduce tasks. Both have a negative impact on the application performance. To address these problems, the Centre-of-Gravity Reduce Scheduler (CoGRS) (Hammoud et al., Reference Hammoud, Rehman and Sakr2012) reduce scheduling algorithm is introduced which adds locality and skew awareness to the scheduler. CoGRS schedules reduce tasks to the node based on location closeness to the nodes creating intermediate data for it. They used Weighted-Total-Network-Distance (WTND _r ) for reduce ‘r’ as a heuristic for identifying the appropriate node for the reduce task, and is calculated using the following equation,

(15) $$WTND_{r} {\equals}\mathop{\sum}\limits_{\matrix{ i{\equals}0 \cr} }^n (ND_{i} {\,\asterisk\,}r{\,\asterisk\,}w_{i} )$$

where ‘n’ symbolizes number of partitions that are input to Reducer _r , ND _i denotes network distance to transfer partition i to Reducer _r in the shuffle phase, and w _i is weight assigned to i. In the CoGRS algorithm, the node with the minimum WTND _r is considered to be the Center of Gravity node and the reduce task r is scheduled to it. CoGRS reduce scheduler reduces the network traffic and job response time by approximately 9% and 23%, respectively, as compared to native Hadoop.

4.2.6 Priority schedulers

Priority scheduling is a technique for scheduling progressions based on priority. It involves assigning priorities to different tasks or jobs and then processing them based on the assigned priorities. Hadoop MapReduce has priority based schedulers developed by different researchers. We will explain the significant schedulers in this subsection of the paper. The Task Co-Scheduler (Polo et al., 2010) presented performance-ambitious co-task allocation in Hadoop MapReduce for better resource utilization in a shared environment. The authors exploit Hadoop MapReduce’s several small task’s capability to forecast the completion time for the waiting tasks. Their resource allocation tuning methodology among jobs is centered on the estimated completion time for each job based on some given resources.

Gu et al. (Reference Gu, Tang and Xie2014) introduced Priority scheduler, a priority-based scheduling algorithm for the Hadoop MapReduce framework. They used two parameters as heuristics: the priority of slave nodes, and the distance between the master and compute node. The amount of total data to be processed by the job can be calculated as,

(16) $$S{\equals}\mathop{\sum}\limits_{\matrix{ j{\equals}1 \cr} }^n AvgTaskSize_{j} {\,\asterisk\,}WeightValue_{j} $$

where S is the total amount of data to be processed, AvgTaskSize _j is the average size of a task in the job j, and WeightValue _j indicates the number of tasks based on job weights. The performance evaluation shows that the improved scheduler based on priority minimizes data transfer in the Hadoop cluster, and the response time of jobs.

4.2.7 Energy-aware schedulers

Energy consumption is one of the most important issues in big data and modern world data centers. To handle this issue, certain researchers developed scheduling systems or cluster management systems which take energy consumption into account. Energy-aware scheduling (EAS) techniques are those which take energy consumption of the cluster into account while allocating tasks to different nodes or making scheduling decisions. Several researchers developed energy-aware schedulers for Hadoop MapReduce frameworks, including EA-MapReduce (Li et al., Reference Li, Yang, Luan and Qian2011), MT-MapRed (Althebyan et al., Reference Althebyan, ALQudah, Jararweh and Yaseen2014), and EAS (Liang et al., Reference Liang, Xiao and Li2013). EA-MapReduce (Li et al., Reference Li, Yang, Luan and Qian2011) is an energy-aware scheduler which predicts the energy consumption of MapReduce workloads in the Hadoop cluster. Li et al., (Reference Li, Yang, Luan and Qian2011) used a multivariate linear regression model to analyze the results of the benchmark traces after execution. They used number of instructions, map or reduce tasks written, bytes, etc., and introduced a linear prediction model based on these metrics. Using Word Count and Sort workload with various input data sizes, their evaluation results claim that their prediction model shows an approximately 0.15% inaccuracy in comparison to observed energy consumption.

Liang et al. (Reference Liang, Xiao and Li2013) introduced EAS, an energy-aware vibrant scheduling algorithm that aims at minimizing communication energy utilization through clustering those tasks whose executions depend on each other. The current static schedulers may cause an increase in energy consumption owing to task waiting time, as an estimation of the task’s execution time is difficult. The EAS dynamic scheduling technique tunes the clustering group on the basis of an energy consumption threshold.

4.2.8 Load/fairness-aware schedulers

Load-awareness is the property of the scheduling algorithm which takes the load of the nodes into account while making scheduling decisions in the cluster. Fairness-awareness is the property of schedulers to make scheduling decisions on the basis of Fairness among nodes throughout the cluster or users. Fairness and load-balancing are very important issues in Hadoop scheduling. There are various efforts to optimize Hadoop scheduling while solving these issues. Chintapalli (Reference Chintapalli2014) introduced CRBalancer, a mechanism which distributes input data splits to heterogeneous nodes in the Hadoop cluster according to their computing power capabilities. The main objective is to profile all the nodes in the cluster to identify their computing capabilities, and then balance the load in each node according to their resource capabilities. The balancer first obtains the network topological information and determines the over-utilized and under-utilized nodes to perform load-balancing among them.

In the Hadoop system, by default data blocks are replicated in three different nodes. In this situation, when the data blocks can be found in more than one location in the cluster, a challenging issue is determining which node is assigned the task. To solve this problem, Chen et al., (Reference Chen, Wei, Wei, Chen, Hsu and Shih2013) introduced Locality-Aware Scheduling Algorithm (LaSA), a method that assigns weight to data which is input to the specified task and computes the node weight for data interference accordingly to estimate the weight of data in the specified node. Next, it sorts the nodes in ascending order and schedules the task to the first node in the list to minimize data transmission time for performance optimization. They produced two works for optimizing the default Hadoop scheduler: (a) they introduced a mathematical model of data interference weight in the Hadoop scheduler and (b) they designed and implemented the LaSA algorithm to exploit the weight of data interference to afford data locality-aware resource scheduling in the Hadoop system.

By default, Hadoop does an All-Map-to-All-Reduce communication model in the Shue phase. This strategy usually results in the saturation of network bandwidth while shuing intermediate data from mappers to reducers, called Reducers Placement Problem (RPP). There are several research efforts to improve the performance of Hadoop MapReduce by altering the data flow in transition between mappers and reducers. The Locality-Aware Fairness-Aware Key partitioning (LEEN) (Ibrahim et al., 2010) algorithm is a research effort to address the problem of efficiently partitioning the intermediate keys to minimize the amount of shued data over the network. The accurate partitioning of intermediate data also solves the issue of the RPP. LEEN attenuates the partitioning skew, minimizing data transfer by balancing the data distribution among nodes in the cluster. It also improves the data locality of MapReduce execution efficiency with the use of asynchronous Map and Reduce execution policy. It guarantees a fair distribution of intermediate data throughout all the reducers in the cluster. It attains an approximately 40% improvement on different workloads.

The X-Flex (Wolf et al., Reference Wolf, Nabi, Nagarajan, Saccone, Wagle, Hildrum, Pring and Sarpatwar2014) is a cross-platform scheduler which is developed as an alternative to the DRF (Ghodsi et al., 2011) scheduler currently part of both YARN (Douglas et al., n.d.) and Mesos (Hindman et al., 2011). X-Flex screens instantaneous fairness to grasp the long-term view of the situation. Unlike DRF, the packing of containers into processing nodes is done oine for the improvement of packing quality. X-Flex takes into perspective that some frameworks have adequate structure to make sophisticated scheduling decisions. Therefore, it allows this , and also gives platforms an inordinate amount of freedom over the degree of sharing they will permit with other platforms. X-Flex has considerable qualitative and quantitative advantages over DRF, including durable view of fairness, an apparently more appropriate description of instantaneous fairness, an arithmetically refined off-line vector packing system to produce containers and their owners, flexibility, work with framework-specific scheduling algorithm that can take advantage of the inherent structure, and the ability of applications to share as much or as little as needed.

Optimal Task Selection (Suresh & Gopalan Reference Suresh and Gopalan2014) scheduling algorithm introduced an optimal task selection method to assist the scheduler in the case of multiple local tasks availability for a node. The authors select the task with the least number of replicas for execution to improve the probability percentage of a local task being launched for a job in the future and maintain load balancing in the nodes throughout the cluster. Node-Aware Locality-Aware and Fairness-Aware (NoLFA) (Hanif & Lee Reference Hanif and Lee2016), an efficient key partitioning algorithm, is a recent variance of the LEEN (Ibrahim et al., 2010) algorithm which considers the heterogeneity of the nodes throughout the cluster. NoLFA takes node capabilities as heuristics while making its scheduling decisions to obtain the best available trade-off between the locality and fairness in the system. It achieves approximately a 29% improvement over the native Hadoop scheduler.

4.2.9 Hybrid schedulers

Hybrid schedulers are schedulers that cover both the job and tasks levels while taking the scheduling decisions. These are the most powerful schedulers because they take both coarse-grain and fine-grain scheduling metrics into account when scheduling tasks or jobs to different nodes in the cluster. The broad adoption and universal usage of Hadoop has strained the initial design of Hadoop version 1.0 well beyond its intended goal, uncovering two key limitations: (a) a tightly coupled mechanism of a specified programming model with the resource management organization, compelling developers to abuse the MapReduce programming model and (b) a consolidated handling of the job control flow resulting in endless scalability concerns for the scheduler. YARN (Douglas et al., n.d.) is the new version of Hadoop scheduler which decouples the resource manager from the job scheduler. In this new architecture, the resources are management responsibilities which are given to Resource Manager while the scheduling obligation is handled by the Application Manager which handles all the running and ready applications in the cluster. With the decoupling of the programming model from the resource management infrastructure, YARN became a general-purpose resource management system for the cluster.

Conventionally, each organization has its own isolated cluster that has a satisfactory capacity to meet the organization’s SLA under near peak conditions, which leads to poor utilization of resources. In contrast, sharing a cluster among organizations is a cost-effective policy for running large Hadoop clusters. However, organizations are concerned about the sharing policies of resources so that other organizations should not use their SLA-critical resources at a pivotal time. An engineering group of Yahoo! Researchers proposed Capacity Scheduler (Apache! 2015a), a pluggable Hadoop MapReduce scheduler for multi-tenant sharing clusters where resources are provisioned to applications in a timely manner under the allocated capabilities constraints. The main objective is that the available resources of the cluster should be partitioned among multiple organizations or tenants. The excess capacity can be utilized by a needy organization which is elasticity in a cost-effective manner. It supports multiple job queues, and each has an allocated fraction of the cluster’s resources. Administrators can configure soft and hard limits on the capacity allocated to each queue. It supports job priorities within the queue which is disabled by default and users can enable it optionally. Users can submit jobs to individual queues following strict ACLs for each queue. To ensure the security of users’ jobs, they use safeguards so that users cannot view or modify each other’s jobs.

Facebook developers introduced a new scheduling algorithm called Fair Scheduler, which is part of both Hadoop version 1.0 and YARN version 2.0. Fair Scheduler (Apache! 2015b) aims to provide a fair share of resources to every job throughout the runtime. The system has different pools of a guaranteed minimum number of slots which accepts jobs from the users. Free superfluous slots in a pool are shared among jobs while the idle pool’s resources are shared among other pools. In case of an under-capacity pool needing its share back, the over-capacity pool been preempted to maintain the minimum share among the pools. A job utilizes all the cluster in the case of solo execution, while the resources are divided fairly among the jobs in case of the arrival of new job submissions by users. Fair scheduler allows the short jobs to run within a reasonable period of time and simultaneously, and do not allow the long jobs to starve (Bincy & Binu Reference Bincy and Binu2013). It supports priority scheduling, and the administrator has been given the power of priority enforcement on certain pools. In the case of priority scheduling enabled, the tasks scheduling changes to an interleaved policy of execution based on their assigned priority within the specified pool considering the allocated and minimum share of cluster resources to the specified pool. Fair scheduler keeps track of the ratio of the amount of time resources actually used by a job to the ideal fair allocation of resources to the job. The job with the highest ratio tasks is scheduled accordingly, which ensures fair resource utilization.

Phan et al. (2010) introduced real-time scheduler, a formal model for capturing real-time Hadoop MapReduce applications in Hadoop clusters. It focused on task scheduling optimization in a heterogeneous Hadoop cluster by transforming the problem as a Constraints Satisfaction Problem through identifying key factors affecting real-time scheduling, including data placement, master scheduling overhead, and concurrent users. Heterogeneity-Aware Resource Allocation Scheduler (HARAS ) (Lee et al., Reference Lee, Chun and Katz2011) proves that some resource may have poor job performance with high availability and other resources may have high job performance with low availability. For better performance, the resources should be scheduled on different and separate resources to ensure that each job receives a fair share of resources. The architectural design is to provision resources to a data analytic cluster in the cloud and suggest a metric of share in a heterogeneous cluster to comprehend a scheduling scheme that attains high performance and fairness.

There are numerous unique challenges at Facebook, including scalability (the largest cluster has more than 100 PB of data), processing needs (more than 60,000 Hive queries per day), and their data warehouse has grown by a factor of 2500-times in the last 5–6 years (growth is expected through increasing the user base and the ongoing addition of new features to the site). By early 2011, they began reaching the limits of the Hadoop MapReduce system; therefore, they developed Facebook-CM (Corona) (Facebook! 2015) which is a new scheduling framework that separates cluster resource management from job coordination. Corona proposed a cluster manager that keeps track of the amount of free resources and total working nodes in the cluster. Each job has a committed job tracker which can either run in the same process as the client (for small jobs) or as an isolated process in the cluster (for long jobs). Corona uses push-based scheduling, i.e., cluster manager pushes back the resource allowances to the job tracker upon receiving the resource request. The scheduling in Corona does not involve any periodic heartbeat messages leading to a reduced scheduling latency. The Corona cluster manager has its own fair-share scheduler which considers a full snapshot of clusters and jobs while making its scheduling decisions, which leads to better fairness. It supports pool groups to group scheduling pools in a multi-tenant environment. Only the team which is assigned to that pool group is allowed to manage the pools within their group. This gives every team fine-grained control over their allotted resources.