Process over MapReduce

ref) MapReduce: Simplefied Data Processing on Large Clusters (2004).

3.1. Execution Overview를 읽어보면 아래와 같이 정리할 수 있다.

1. Splits the input files into M pieces.

16MB ~ 64MB 정도의 input split 조각들로 나눈다.
HDMS의 block이 물리단위라면 input split은 논리 단위가 된다.

2. The master picks idle workers and assigns each one a map/reduce task.

master는 쉬고 있는 worker들에게 map또는 reduce task를 할당한다.

3. A worker invoke user-defined Map function

Map 작업을 받은 worker는 사용자가 정의한 Map 작업을 시행한다.
이 때 intermediate key/value 쌍이 생성되어 buffer에 쌓인다.

4. Periodically, the buffered pairs are written to local disk, partitioned into R regions

주기적으로 버퍼에 저장된 key/value 쌍들은 로컬 디스크에 저장(spill)되며,
partition function에 의해 R개의 조각으로 나누어진다. (보통 key hash % R 로써 분류된다.)
작업이 끝나면 reduce worker에게 spill된 파일의 위치를 알린다.

5. A reduce worker read all intermediate data, it sorts by the intermediate keys

4번 작업에 의해 spill된 파일의 위치를 연락받은 reduce worker는 RPC를 이용하여 데이터를 읽고,
intermediate key를 기준으로 정렬을 한다. 이 과정에서 같은 키를 가지는 값들이 뭉칠 것이다.
만약 데이터 양이 너무 많은 경우에는 exteranl sort가 사용된다고 한다.

6. The reduce worker iterates over the sorted intermediate data and invoke user-defined Reduce function

정렬된 intermediate data를 iterate 하면서 각 유일키 별로 Reduce 작업을 시행한다.
이 때 결과인 reduce partition은 최정 결과물에 더해진다.

7. If MapReduce finished, the master wakes up the user program.

작업이 끝나면 다시 사용자 코드로 돌아가게 된다.
결과로 총 R개의 output file이 생기게 될 것이다.