00_MIT_6824_분산시스템_입문_가이드 논문 MapReduce: 대규모 클러스터에서의 간소화된 데이터 처리에 관하여
논문 링크 : https://pdos.csail.mit.edu/6.824/papers/mapreduce.pdf
이 논문은 Google의 Jeffrey Dean과 Sanjay Ghemawat가 2004년에 발표한 고전적인 분산 시스템 논문으로, 대규모 데이터 처리를 위한 프로그래밍 모델 및 구현을 소개합니다.
- MapReduce의 핵심 목표 및 배경
MapReduce는 Google의 엔지니어들이 웹에서 크롤링된 문서, 웹 요청 로그 등 테라바이트(terabytes) 규모의 방대한 원시 데이터를 처리하여 역 인덱스(inverted indices), 웹 문서의 그래프 구조 분석, 인기 검색어 요약 등 다양한 종류의 파생 데이터를 계산하는 수백 가지 특수 목적 연산을 구현했던 경험에서 비롯되었습니다.
핵심 문제점: 이러한 연산들은 개념적으로는 간단하지만, 합리적인 시간 내에 완료하기 위해 수백, 수천 대의 컴퓨터에 걸쳐 분산되어야 했기 때문에, 병렬화, 데이터 분산, 그리고 **장애 처리(handling failures)**와 같은 복잡한 세부 사항들로 인해 원래의 단순했던 계산이 복잡한 코드로 가려지게 되는 문제가 있었습니다.
MapReduce의 해결책: 이러한 복잡성에 대한 반응으로, MapReduce는 병렬화, 내결함성(fault-tolerance), 데이터 분산, 그리고 부하 분산(load balancing)과 같은 복잡하고 번거로운 세부 사항들을 라이브러리(library) 내부에 숨기는 새로운 추상화를 설계했습니다.
• 프로그래밍 모델: MapReduce는 Lisp 및 기타 함수형 언어에 존재하는 map 및 reduce 기본 요소를 기반으로 합니다.
• 쉬운 사용: 이 모델 덕분에 병렬 및 분산 시스템에 대한 경험이 전혀 없는 프로그래머도 대규모 분산 시스템의 자원을 쉽게 활용할 수 있게 되었습니다.
- MapReduce 프로그래밍 모델
사용자는 MapReduce 라이브러리를 사용하여 두 가지 함수, Map과 Reduce를 정의함으로써 컴퓨테이션을 표현합니다.
| 함수 | 입력 (Input Pair) | 출력 (Intermediate Key/Value Pairs) | 역할 |
| Map | (k1, v1) (입력 키/값 쌍) | list(k2, v2) (중간 키/값 쌍 목록) | 입력 쌍을 처리하여 중간 키/값 쌍 목록을 생성합니다. |
| Reduce | (k2, list(v2)) (중간 키와 해당 키의 모든 값 목록) | list(v2) (최종 출력 값 목록, 보통 0개 또는 1개) | 동일한 중간 키와 연결된 모든 값을 병합하여 최종 결과(출력 키/값 쌍)를 생성합니다. |
예시: 단어 출현 횟수 계산 (Word Count)
-
Map 함수: 문서 이름(
key)과 문서 내용(value)을 받아, 문서 내의 각 단어(w)에 대해(w, "1")쌍을 내보냅니다 (EmitIntermediate). -
Reduce 함수: 단어(
key)와 해당 단어의 ‘1’ 목록(values, 즉 횟수 목록)을 받아, 이 ‘1’들을 모두 합산(result)하여 최종 횟수를 내보냅니다 (Emit(AsString(result))). -
MapReduce 구현 및 실행 흐름 (Execution Overview)
MapReduce 작업은 **하나의 마스터(Master)**와 여러 개의 **워커(Worker)**로 구성된 대규모 상용(commodity) 머신 클러스터에서 실행됩니다.
MapReduce 작업이 실행되는 단계별 순서는 다음과 같습니다 (그림 1 참조):
-
입력 분할 (Splitting Input Files): 사용자 프로그램의 MapReduce 라이브러리가 입력 파일을 **M개의 분할(splits)**로 나눕니다. 분할 크기는 일반적으로 16MB에서 64MB입니다.
-
마스터 및 작업 할당 (Master Assignment): 프로그램의 복사본 중 하나가 마스터로 지정되며, 나머지는 워커가 됩니다. 마스터는 유휴 워커를 선택하여 M개의 Map 작업이나 R개의 Reduce 작업을 할당합니다.
-
Map 작업 실행 (Map Phase): Map 작업을 할당받은 워커는 해당 입력 분할 내용을 읽고, 이를 사용자 정의 Map 함수에 전달합니다. Map 함수가 생성한 중간 키/값 쌍은 메모리에 버퍼링됩니다.
-
로컬 디스크에 쓰기 (Local Write): 주기적으로, 버퍼링된 쌍들은 R개 영역으로 분할되어 워커의 로컬 디스크에 쓰입니다. 이 R개 영역으로의 분할은 파티셔닝 함수(
hash(key) mod R등)를 사용하여 이루어집니다. -
데이터 셔플링 (Shuffle / Remote Read): Map 작업이 완료되면, 마스터는 중간 파일 영역의 위치를 Reduce 워커에게 전달합니다. Reduce 워커는 **원격 프로시저 호출(Remote Procedure Calls, RPC)**을 사용하여 Map 워커의 로컬 디스크로부터 버퍼링된 데이터를 읽어옵니다.
-
Reduce 작업 실행 (Reduce Phase): Reduce 워커는 모든 중간 데이터를 읽어온 후, 중간 키를 기준으로 데이터를 정렬하고 그룹화합니다. 그런 다음, 각 고유한 중간 키와 해당 값들의 집합을 사용자 정의 Reduce 함수에 전달합니다. Reduce 함수의 출력은 이 Reduce 파티션의 최종 출력 파일에 추가됩니다.
-
완료: 모든 Map 및 Reduce 작업이 완료되면, 마스터는 사용자 프로그램에 알리고 MapReduce 호출이 반환됩니다.
-
핵심 최적화 및 내결함성
MapReduce의 구현은 대규모 환경에서 효율성과 안정성을 보장하기 위한 여러 가지 중요한 기능을 포함하고 있습니다.
4.1. 내결함성 (Fault Tolerance)
MapReduce는 수백 또는 수천 대의 머신을 사용하기 때문에 머신 장애를 우아하게 허용하도록 설계되었습니다.
• 워커 장애: 마스터는 워커에게 주기적으로 **핑(pings)**을 보내 상태를 확인합니다. 응답이 없으면 해당 워커는 실패로 표시됩니다.
◦ Map 작업 재실행: 실패한 워커가 완료한 Map 작업은 그 출력이 실패한 머신의 로컬 디스크에 저장되어 접근할 수 없기 때문에 유휴(idle) 상태로 재설정되고 다른 워커에 재할당됩니다.
◦ Reduce 작업 재실행: 완료된 Reduce 작업은 그 출력이 **전역 파일 시스템(global file system)**에 저장되므로 재실행할 필요가 없습니다.
• 마스터 장애: 마스터는 주기적으로 데이터 구조의 체크포인트를 작성하지만, 마스터는 하나뿐이므로 그 실패는 드물다고 보고, 현재 구현에서는 마스터 실패 시 MapReduce 컴퓨테이션을 중단시키고 클라이언트가 재시도하도록 할 수 있습니다.
• 결정론적 연산의 의미론: 사용자 제공 Map 및 Reduce 연산자가 결정론적 함수일 경우, 분산 구현은 장애가 없는 순차적 실행과 동일한 출력을 생성한다는 것이 보장됩니다. 이는 각 작업이 임시 파일에 출력을 작성하고, 완료 시 원자적으로 최종 파일로 이름을 바꾸는 방식으로 달성됩니다.
4.2. 데이터 지역성 (Locality)
네트워크 대역폭은 Google의 컴퓨팅 환경에서 상대적으로 희소한 자원이었습니다. MapReduce는 네트워크 대역폭을 절약하기 위해 다음과 같은 지역성 최적화를 수행합니다.
• GFS 활용: 입력 데이터는 클러스터 머신의 로컬 디스크에 저장되는 **Google File System (GFS)**에 의해 관리됩니다. GFS는 파일을 64MB 블록으로 나누고 여러 복사본(일반적으로 3개)을 다른 머신에 저장합니다.
• Map 작업 스케줄링: MapReduce 마스터는 입력 파일의 위치 정보를 고려하여, 해당 입력 데이터의 복제본을 포함하고 있는 머신에 Map 작업이 스케줄링되도록 시도합니다.
• 결과: 이 최적화 덕분에 클러스터 워커의 상당 부분에서 대규모 MapReduce 연산을 실행할 때, 대부분의 입력 데이터는 로컬에서 읽히며 네트워크 대역폭을 소모하지 않습니다.
4.3. 느린 머신 처리 (Straggler Mitigation)
계산 완료 시간을 늘리는 흔한 원인 중 하나는 “지연 머신(straggler)“입니다. 이는 비정상적으로 오랜 시간이 걸려 마지막 몇 Map 또는 Reduce 작업 중 하나를 완료하는 머신을 의미합니다.
• 백업 작업 (Backup Tasks): MapReduce 연산이 완료에 가까워지면, 마스터는 남은 진행 중인 작업들에 대해 백업 실행을 스케줄링합니다. 주 실행이나 백업 실행 중 먼저 완료되는 작업이 해당 작업을 완료한 것으로 표시됩니다. 이 메커니즘은 전체 완료 시간을 상당히 단축하는 데 도움이 되었습니다 (예: 정렬 프로그램 실행 시간을 44% 단축).
4.4. 프로그래밍 모델 정제 (Refinements)
• 파티셔닝 함수 (Partitioning Function): 사용자는 Reduce 작업의 수(R)를 지정하며, 중간 키는 파티셔닝 함수를 사용하여 R개 파티션으로 분할됩니다. 기본 함수는 해싱을 사용하지만(예: hash(key) mod R), 사용자는 특정 호스트의 모든 URL이 동일한 출력 파일에 저장되도록 사용자 정의 함수를 제공할 수 있습니다.
• 순서 보장 (Ordering Guarantees): MapReduce는 주어진 파티션 내에서 중간 키/값 쌍이 키의 오름차순으로 처리됨을 보장합니다. 이는 정렬된 출력을 생성하거나 키를 통한 효율적인 무작위 접근 조회(random access lookups)를 지원하는 데 유용합니다.
• 결합 함수 (Combiner Function): Map 작업이 생성하는 중간 키에 상당한 반복이 있고 Reduce 함수가 교환법칙 및 결합법칙을 따를 때 (예: 단어 카운트), 선택적 **결합 함수(Combiner function)**를 지정할 수 있습니다. 이 함수는 네트워크를 통해 보내기 전에 각 Map 워커 머신에서 부분적인 병합을 수행하여 네트워크 대역폭을 크게 절약합니다.
- 적용 사례
MapReduce는 Google 내에서 광범위하게 적용되었으며:
• 대규모 기계 학습 문제
• Google News 및 Froogle 제품 클러스터링
• 인기 쿼리 보고서 생성
• 웹 페이지 속성 추출 (지역화된 검색을 위한 지리적 위치 추출 등)
• Google 프로덕션 인덱싱 시스템 전체 재작성: 인덱싱 프로세스는 5~10개의 MapReduce 연산 순서로 실행되었으며, MapReduce를 사용함으로써 **코드의 단순성(C++ 코드가 3800라인에서 700라인으로 감소)**과 운영 용이성이 향상되었습니다.