Distributed Systems - MapReduce - Nguyen Quang Hung

Nội dung text: Distributed Systems - MapReduce - Nguyen Quang Hung

1. MapReduce Nguyen Quang Hung
2. Outline  Challenges  Motivation  Ideas  Programming model  Implementation  Related works  References
3. MapReduce  Motivation: Large scale data processing – Want to process huge of datasets (>1 TB). – Want to parallelize across hundreds/thousands of CPUs. – Want to make this easy.
4. MapReduce: programming model  Borrows from functional programming  Users implement interface of two functions: map and reduce:  map (k1,v1) list(k2,v2)  reduce (k2,list(v2)) list(v2)
5. reduce() function  After the map phase is over, all the intermediate values for a given output key are combined together into a list  reduce() combines those intermediate values into one or more final values for that same output key  (in practice, usually only one final value per key)
6. MapReduce: execution flows
7. Locality  Master program allocates tasks based on location of data: tries to have map() tasks on same machine as physical file data, or at least same rack (cluster rack)  map() task inputs are divided into 64 MB blocks: same size as Google File System chunks
8. Optimizations (1)  No reduce can start until map is complete: – A single slow disk controller can rate-limit the whole process  Master redundantly executes “slow-moving” map tasks; uses results of first copy to finish Why is it safe to redundantly execute map tasks? Wouldn’t this mess up the total computation?
9. MapReduce: implementations  Google MapReduce: C/C++  Hadoop: Java  Phoenix: C/C++ multithread  Etc.
10. Google MapReduce evaluation (2) Data transfer rates over time for different executions of the sort program (J.Dean and S.Ghemawat shows in their paper [1, page 9])
11. Related works  Bulk Synchronous Programming [6]  MPI primitives [4]  Condor [5]  SAGA-MapReduce [8]  CGI-MapReduce [7]
12. CGL-MapReduce Components of the CGL-MapReduce , extracted from [8]
13. CGL-MapReduce: evaluation HEP data analysis, execution Total Kmeans time against the time vs. the volume of data number of data points (Both (fixed compute resources) axes are in log scale) J.Ekanayake, S.Pallickara, and G.Fox show in their paper [7]
14. Hadoop vs. SAGA-MapReduce C.Miceli, M.Miceli, S. Jha, H. Kaiser, A. Merzky show in [8]
15. Conclusions  MapReduce has proven to be a useful abstraction  Simplifies large-scale computations on cluster of commodity PCs  Functional programming paradigm can be applied to large-scale applications  Focus on problem, let library deal w/ messy details