Report

Investigation of Data Locality and Fairness in MapReduce Zhenhua Guo, Geoffrey Fox, Mo Zhou Outline Introduction Data Locality and Fairness Experiments Conclusions MapReduce Execution Overview Google File System Input file block 0 1 2 Read input data Data locality map tasks Stored locally Shuffle between map tasks and reduce tasks reduce tasks Stored in GFS 3 Google File System Hadoop Implementation HDFS Name node Metadata mgmt. Replication mgmt. Block placement Task scheduler Fault tolerance …… Had oop Operating System MapReduce Job tracker Had oop …… Storage: HDFS - Files are split into blocks. - Each block has replicas. - All blocks are managed by central name node. Compute: MapReduce - Each node has map and reduce slots - Tasks are scheduled to task slots - # of tasks <= # of slots Operating System task slot Worker node 1 4 Worker node N data block Data Locality “Distance” between compute and data Different levels: node-level, rack-level, etc. The tasks that achieve node-level DL are called data local tasks For data-intensive computing, data locality is important Energy consumption Network traffic Research goals Analyze state-of-the-art scheduling algorithms in MapReduce Propose a scheduling algorithm achieving optimal data locality Integrate Fairness Mainly theoretical study 5 Outline Introduction Data Locality and Fairness Experiments Conclusions Data Locality – Factors and Metrics Important factors Symbol Description N the number of nodes S the number of map slots on each node I the ratio of idle slots T the number of tasks to execute C replication factor Metrics the goodness of data locality the percent of data local tasks (0% – 100%) data locality cost the data movement cost of job execution The two metrics are not directly related. The goodness of data locality is good ⇏ Data locality cost is low The number of non data local tasks ⇎ The incurred data locality cost Depends on scheduling strategy, dist. of input, resource availability, etc. Non-optimality of default Hadoop sched. Problem: given a set of tasks and a set of idle slots, assign tasks to idle slots Hadoop schedules tasks one by one Consider one idle slot each time Given an idle slot, schedule the task that yields the “best” data locality Favor data locality Achieve local optimum; global optimum is not guaranteed Each task is scheduled without considering its impact on other tasks Tasks T1 T2 T3 Data block Task to schedule Map slot. If its color is black, the slot is not idle. ...... Node A Tasks T1 Node B T2 Node C (a) Instant system state T3 Node A Node B Node C (b) dl-shed scheduling Tasks T3 T2 T1 Node A Node B Node C (c) Optimal scheduling Optimal Data Locality All idle slots need to be considered at once to achieve global optimum We propose an algorithm lsap-sched which yields optimal data locality Reformulate the problem Use a cost matrix to capture data locality information Find a similar mathematical problem: Linear Sum Assignment Problem (LSAP) Convert the scheduling problem to LSAP (not directly mapped) Prove the optimality Optimal Data Locality – Reformulation m idle map slots {s1,…sm} and n tasks {T1,…Tn} Construct a cost matrix C s1 Cell Ci,j is the assignment cost if task Ti is T1 1 T2 0 assigned to idle slot sj 0: if compute and data are co-located … … Tn-1 0 1: otherwise (uniform net. bw) Tn 1 Reflects data locality Represent task assignment with a function Φ s2 … sm-1 sm 1 … 0 0 1 … 0 1 … … … … 1 … 0 0 0 … 0 1 Given task i, Φ(i) is the slot where it is assigned T C Cost sum: Csum ( ) i 1 i (i ) Find an assignment to minimize Csum g min C sum ( ) lsap-uniform-sched Optimal Data Locality – Reformulation (cont.) Refinement: use real network bandwidth to calculate cost Cell Ci,j is the incurred cost if task Ti is assigned to idle slot sj 0: if compute and data are co-located DS (Ti ) : otherwise max BW ( ND(Ti , c), N ( IS j )) 1i Ri s1 s2 … sm-1 sm T1 1 3 … 0 0 T2 0 2 … 0 2.5 … … … … … … 0.7 … 0 0 … 0 3 Tn-1 0 Tn 1.5 0 Network Weather Service (NWS) can be used for network monitoring and prediction lsap-sched Optimal Data Locality – LSAP LSAP: matrix C must be square When a cost matrix C is not square, cannot apply LSAP Solution 1: shrink C to a square matrix by removing rows/columns Solution 2: expand C to a square matrix If n < m, create m-n dummy tasks, and use constant cost 0 Apply LSAP, and filter out the assignment of dummy tasks If n > m, create n-m dummy slots, and use constant cost 0 Apply LSAP, and filter our the tasks assigned to dummy slots s1 dummy tasks s2 … sm-1 sm s1 … sm sm+1 … sn T1 1.2 2.6 0 T1 1.8 … 0 0 … 0 … … … … … … … … … … … … … Tn 0 2 3 0 0 Ti 0 … 2.3 0 … 0 Tn+1 0 0 0 0 0 0 0 Ti+1 1.3 … 3 0 … 0 … … … … … … … … … … … … … Tm 0 Tn 4 … 0 0 … 0 0 0 (a) n < m 0 0 (b) n > m dummy slots Optimal Data Locality – Proof Do our transformations preserve optimality? Yes! Assume LSAP algorithms give optimal assignments (for square matrices) Proof sketch (by contradiction): 1) 2) 3) 4) The assignment function found by lsap-sched is φ-lsap. Its cost sum is Csum(φ-lsap) The total assignment cost of the solution given by LSAP algorithms for the expanded square matrix is Csum(φ-lsap) as well The key point is that the total assignment cost of dummy tasks is |n-m| no matter where they are assigned. Assume that φ-lsap is not optimal. Another function φ-opt gives smaller assignment cost. Csum(φ-opt) < Csum(φ-lsap). We extend function φ-opt, cost sum is Csum(φ-opt) for expanded square matrix Csum(φ-opt) < Csum(φ-lsap) ⇨ The solution given by LSAP algorithm is not optimal. ⇨ This contradicts our assumption Integration of Fairness Data locality and fairness conflict sometimes Assignment Cost = Data Locality Cost (DLC) + Fairness Cost (FC) Group model Jobs are put into groups denoted by G. Each group is assigned a ration w (the expected share of resource usage) Real usage share: (rti: # of running tasks of group i) Group Fairness Cost: Slots to allocate: (AS: # of all slots) Approach 1: task FC GFC of the group it belongs to Issue: oscillation of actual resource usage (all or none are scheduled) A group i)slightly underuses its ration ii) has many waiting tasks drastic overuse of resources Integration of Fairness (cont.) Approach 2: For group Gi, the FC of stoi tasks are set to GFCi, the FC of other tasks are set to a larger value Configurable DLC and FC weights to control the tradeoff Assignment Cost = α· DLC + ϐ· FC Outline Introduction Data Locality and Fairness Experiments (Simulations) Conclusions Experiments – Overhead of LSAP Solver Goal: to measure the time needed to solve LSAP Hungarian algorithm (O(n3)): absolute optimality is guaranteed Matrix Size Time 100 x 100 7ms 500 x 500 130ms 1700 x 1700 450ms 2900 x 2900 1s Appropriate for small- and medium-sized clusters Alternative: use heuristics to sacrifice absolute optimality in favor of low compute time Experiment – Background Recap Scheduling Algorithm Description dl-sched Default Hadoop scheduling algorithm lsap-uniform-sched Our proposed LSAP-based algorithm (Pairwise bandwidth is identical) lsap-sched Our proposed LSAP-based algorithm (is network topology aware) Metric Description the goodness of data locality the percent of data local tasks (0% – 100%) data locality cost The data movement cost of job execution Example: 10 tasks 9 data-local tasks, 1 non data local task with data movement cost 5 The goodness of data locality is 90% (9 / 10) Data locality cost is 5 Experiment – The goodness of data locality Measure the ratio of data-local tasks (0% – 100%) # of nodes is from 100 to 500 (step size 50). Each node has 4 slots. Replication factor is 3. The ratio of idle slots is 50%. better lsap-sched consistently improves the goodness of DL by 12% -14% Experiment – The goodness of data locality (cont.) Measure the ratio of data-local tasks (0% – 100%) # of nodes is 100 better Increase replication factor ⇒ better data locality More tasks ⇒ More workload ⇒ Worse data locality lsap-sched outperforms dl-sched Experiment – Data Locality Cost With uniform network bandwidth lsap-sched and lsap-uniform-sched become equivalent better better lsap-uniform-sched outperforms dl-sched by 70% – 90% Experiment – Data Locality Cost (cont.) Hierarchical network topology setup 50% idle slots better better Introduction of network topology does not degrade performance substantially. dl-sched, lsap-sched, and lsap-uniform-sched are rack aware lsap-sched outperforms dl-sched by up to 95% lsap-sched outperforms lsap-uniform-sched by up to 65% Experiment – Data Locality Cost (cont.) Hierarchical network topology setup 20% idle slots better lsap-sched outperforms dl-sched by 60% - 70% lsap-sched outperforms lsap-uniform-sched by 40% - 50% With less idle capacity, the superiority of our algorithms decreases. better Experiment – Data Locality Cost (cont.) # of nodes is 100, vary replication factor better Increasing replication factor reduces data locality cost. lsap-sched and lsap-uniform-sched have faster DLC decrease Replication factor is 3 lsap-sched outperforms dl-sched by over 50% better Experiment – Tradeoff between Data Locality and Fairness Fairness distance: Average: Increase the weight of data locality cost Conclusions Hadoop scheduling favors data locality Hadoop scheduling is not optimal We propose a new algorithm yielding optimal data locality Uniform network bandwidth Hierarchical network topology Integrate fairness by tuning cost Conducted experiments to demonstrate the effectiveness More practical evaluation is part of future work Questions? Backup slides MapReduce Model Input & Output: a set of key/value pairs Two primitive operations Each map operation processes one input key/value pair and produces a set of key/value pairs Each reduce operation Merges all intermediate values (produced by map ops) for a particular key Produce final key/value pairs Operations are organized into tasks map: (k1,v1) list(k2,v2) reduce: (k2,list(v2)) list(k3,v3) Map tasks: apply map operation to a set of key/value pairs Reduce tasks: apply reduce operation to intermediate key/value pairs Each MapReduce job comprises a set of map and reduce (optional) tasks. Use Google File System to store data Optimized for large files and write-once-read-many access patterns HDFS is an open source implementation