MIT 6.5840 맵 리듀스 MapReduce

맵리듀스는 2004년 Google의 Jeffrey Dean이 발표한 기술이다.

GFS와 같은 분산 파일시스템에서, 사용자가 작성한 맵 함수와 리듀스 함수를 실행하여 결과를 생산해낸다.

디스크에 있는 파일을 읽어 사용자 함수 Map을 실행한다. 중간 결과(인메모리)에서 셔플링을 통해 사용자 함수 Reducer는 매퍼의 결과를 복사한다.

맵리듀스는 다음과 같은 그림으로 도식화 할 수 있다.

 

사용자 프로그램 워커는 Map Phase와 Reduce Phase가 있고 Master 프로그램이 워커에게 알맞은 작업을 부여한다.

여러 스레드나 프로세스에서 동일한 워커에 접근하여 작업을 지시하면 안되므로 Master 프로그램은 강한 격리성을 유지해야하한다. 즉, 병렬 등의 동시성 처리에 취약하면 안된다.

워커들은 일반적으로 2-4GB 머신으로 100 mb/s ~ 1gb/s 정도의 대역폭을 가지고 있다. 대개 수백에서 수천개의 머신들로 이루어져있고 저장장치는 각 머신들에 붙어있는 일반적인 저장장치를 사용한다. GFS와 같은 분산 파일 시스템을 활용하는데, 하드웨어의 가용성 및 신뢰성을 보장하기 위해 replication을 활용한다. 사용자는 스케쥴링 시스템에 작업을 등록하고, 등록된 작업은 머신에서 작업을 수행한다. 

위 Figure1 참고. Map 호출은 입력 데이터를 M 만큼 쪼개서 수행한다. 그리고 Reduce 호출에 전달되는 데이터는 파티션 함수 hash(key) mod % R 을 통해 분배된다. 전체적인 플로우는 위와 같은데 풀어쓰면 다음과 같다.

MapReduce는 파일을 M 개로 쪼갠다 일반적으로 16mb ~ 64mb이다. 그리고 사용자 프로그램을 머신에 복사한다. 그 중 Master 프로그램은 모든 워커들에 명령을 내리는데 M + R 개의 워커들에 명령을 내린다. 유휴 워커를 골라내서 Map 또는 Reduce 작업을 지시한다. Map 작업을 받은 워커는 데이터를 읽고 key/value 쌍을 추출해내고 사용자 함수 Map에 전달한다. Map 함수에서 생산된 중간자 key/value 쌍은 인메모리에 저장된다. 주기적으로, key/value 쌍은 로컬 디스크에 작성되고, 파티션 함수(hash % R) 에 의해 파티셔닝 된다. 이렇게 로컬에 저장된 데이터는 Master에 전달되고, 이 파일의 위치를 Reduce 워커에게 알려준다. Reduce 워커는 마스터에게 작업위치를 알게되면 RPC를 이용하여 Map 워커로부터 데이터를 읽는다. Reduce 워커가 중간자 데이터를 읽을 때, 중간자 키로 정렬을 수행하며 같은 키를 가진 데이터들이 모이도록 한다. 같은 Reduce 작업에 매우 다양한 키가 존재하므로 정렬은 필요하다. 만약 중간자 데이터가 메모리에 담기 너무 크다면 external sort를 활용하기도 한다. Reduce 워커는 key로 정렬된 중간자 key/value 데이터를 사용자가 작성한 Reduce 함수로 보낸다. Reduce 함수 결과물은 Reduce 파티션에 위치한 최종 아웃풋 파일에 출력된다. 모든 Map, Reduce 작업이 끝나면 Master가 사용자 프로그램에게 알리고 사용자 프로그램에서 호출되었던 MapReduce 코드는 사용자 코드로 돌아온다.

 

Master의 자료구조

Master는 idle, in-progress, comleted 상태를 저장하고 worker 머신들의 id를 가지고 있다. 그리고 Map 작업에서 완료된 중간자 데이터를 Reduce 작업으로 전달하는 통로이기도 하다. 그러므로 매 Map 작업이 끝날때 생성되는 R 길이의 파일의 저장위치 및 자료를 저장한다. 

 

Fault Tolerance

MapReduce는 다음과 같은 Fault Tolerance를 가진다. Worker Failure, Master Failure.

 

Locality

네트워크와 같은 I/O 작업은 느리므로 MapReduce는 작업을 해당 장비 근처에서 하려고 수행한다.

키워드는 다음과 같다.

- Pure Programming (Deterministic)
- Shuffle
- Fault Tolerance
- Straggler (느린작업)
- Master Consistency
- Disk - in-memory - Disk
- Locality

여기정도까지다. 그 이후에 있는 내용들은 독자나 미래의 나에게 맡긴다.

 

아래는 제프리 딘 논문과 내가작성한 Lab1 과제 코드이다.

 

readings: https://static.googleusercontent.com/media/research.google.com/ko//archive/mapreduce-osdi04.pdf

codes: https://github.com/ingyeoking13/distributed-systems/tree/main/6.5840/src/mr