[번역] 맵리듀스(MapReduce) - 2
데이터 과학자를 꿈꾸며
2004년 구글에서 발표한 논문입니다.
MapReduce
: Simplified Data Processing on Large Clusters
Jeffrey Dean and Sanjay Ghemawat
jeff@google.com
sanjay@google.com
Google, Inc.
번역: 채규병
2. 프로그래밍 모형
계산 방법은 이렇다.
입력(input) 키/값 쌍들의 집합을 가지고 산출(output) 키/값 쌍들의 집합을 생산한다.
맵리듀스 라이브러리의 사용자는 이를 맵 그리고 리듀스, 두 개의 기능으로 표현한다. 사용자에 의해 쓰인 맵 함수는 입력(input) 쌍을 가지고 중간키/값 쌍의 집합을 생산한다. 맵리듀스 라이브러리는 같은 중간키 I(대문자 i)와 연관된 모든 중간값을 그룹화하고 이를 리듀스 함수에 넘겨준다.
마찬가지로 사용자에 의해 쓰인 리듀스 함수는 중간키 I와 그 키의 값들의 집합을 받는다. 그리고 그 값들을 가능한 더 작은 집합으로 만들기 위해서 통합한다. 대개는 각 리듀스 실행(invocation)마다 단지 0 또는 하나의 output값만이 생산된다. 여기서 중간값들은 iterator를 통해 사용자의 리듀스 함수에 공급된다. 이는 너무 커서 메모리에 안 맞는 값들의 리스트를 사용자가 다룰 수 있게 한다.
2.1 예시
방대한 문서 더미에서 사용된 단어의 개수를 세는 문제에 대해서 생각해보자.
아마 사용자는 다음과 같은 쓰도(pseudo) 코드를 사용할 것이다.
map(String key, String value):
// key(키): 문서 이름
// value(값): 문서 내용
for each word w in value:
EmitIntermediate(w, "1");
reduce(String key, Iterator values):
// key(키): 단어
// values(값들): 횟수들의 리스트
int result = 0;
for each v in values:
result += ParseInt(v);
Emit( AsString(result) );
맵(map) 함수는 각 단어별로 나타난 개수를 더해서 내보낸다. (위의 "1"은 예시다). 리듀스(reduce) 함수는 각 단어별로 내보내진 모든 개수를 더한다.
추가적으로, 사용자는 맵리듀스 정의 객체(a mapreduce specification object)를 작성하기 위해 입력/산출(input and output) 파일들의 이름들과, 선택적 조정(tuning) 매개변수들을 작성한다. 그다음 사용자는 정의 객체에 함수를 넘겨줌으로써 맵리듀스 함수를 실행(invokes)한다. 사용자의 코드는 맵리듀스 라이브러리(C++에서 실행된다)와 함께 연결된다. 부록 A는 이 예시에 대한 전체 프로그램 텍스트가 들어 있다.
2.2 자료형
비록 이전의 쓰도 코드가 일련의 문자열로 된 input과 output으로 작성되었지만, 사용자에 의해 제공된 맵과 리듀스 함수는 개념적으로 자료형들과 연관되어 왔다:
map (k1, v1) → list(k2, v2)
reduce ( k2, list(v2) ) → list(v2)
즉, 투입(input) 키와 값은 산출(output) 키/값과 달리 다른 영역(a different domain)에서 도출된다. 반대로 중간키/값은 마치 산출키/값처럼 같은 영역에서 나온다.
우리의 C++ 구현(implementation)은 사용자 정의된 함수로 문자열을 주고받고, 이를 문자열 자료형에서 적절한 자료형으로 변형하기 위해 사용자 코드에 남겨둔다.
Figure 1: 실행 개요2.3 더 많은 예시들
여기에 몇몇 간단한 예제가 있다. 이 예제들은 흥미로우면서 MapReduce 컴퓨테이션을 쉽게 표현하는 프로그램들과 관련이 있다.
Distributed Grep(분산된 Grep) :
map 함수는 공급된 패턴과 일치한다면 결과를 뱉어낸다. reduce함수는 단지 중간 데이터를 결과값으로 공급해주는 식별 함수이다.
Count of URL Access Frequency(URL 접근 빈도 세기):
map함수는 웹 페이지 요청 및 결과값 <URL, 1>의 로그를 처리한다. reduce함수는 같은 URL의 모든 값을 같이 더하여 <URL, 총 개수> 쌍 형식으로 결과를 뱉어낸다.
Reverse Web-Link Graph:
map함수는 source라고 이름 붙여진 페이지 안에서 검색된 각각의 target URL로 연결된 링크에 대한 <target, source> 쌍들을 결과로 낸다. reduce함수는 모든 source URL들의 리스트를 이어 붙인다. 그리고 주어진 target URL을 관련시키고 이 쌍을 뱉어낸다: <target, list(source)>
Term-Vector per Host(호스트 별 용어 벡터):
용어 벡터는 문서나 문서 세트에서 발생하는 가장 중요한 단어들을 <word, frequency> 쌍의 리스트로서 요약한다. map 함수는 각각의 인풋 문서에 대한 <hostname, term vector> 쌍을 뱉어낸다 (그 문서에서 호스트네임은 문서의 URL에서 추출된다). reduce 함수는 주어진 호스트에 대한 모든 각 문서 용어 벡터들을 건네받는다. 그리고 이러한 용어 벡터들을 같이 더하면서 빈도가 적은 용어를 버리거나 마지막 <hostname, term vector> 쌍을 뱉어낸다.
Inverted Index(역 인덱스):
map함수는 각 문서를 분해하면서 일련의 <word, document ID>를 뱉어낸다.
reduce함수는 이 주어진 단어에 대한 모든 쌍을 받아들이면서, 연관된 문서 ID를 정렬한다. 그리고 <word, list(document ID)> 쌍을 뱉어낸다. 모든 아웃풋 쌍들의 집합은 간단한 inverted index를 형성한다. 이는 단어 위치를 추적하기 위한 계산을 증대시키기 쉽다.
Distributed Sort(분산된 정렬):
map 함수는 각각의 기록으로부터 키를 추출하며 <key, record> 쌍을 뱉어낸다. reduce함수는 변하지 않은 모든 쌍들을 뱉어낸다. 이 계산은 섹션4.1에서 소개할 구분된(파티셔닝된) 설비에 달려있다. 그리고 순서 속성들은 4.2 섹션에 에서 소개한다.
