[옛 글] [BigData] MapReduce - 조금 더 상세하게.

최초 작성일 : 2013/02/04 13:16 

=======================================================

나름 영문 문서를 해설 식으로 적어보고자 했으나...

가면 갈수록 그냥 문서의 직역이 되고 있네요...ㅠ.ㅠ

양해부탁드립니다.

=======================================================

지난 시간에 살펴본 바와 같이 간단하게 말하면 Map은 논리적 레코드를 key-value형태의 중간 데이터로 만드는 작업을 수행하고

reduce는 key-value를 가공하여 공통된 key를 가진 value들의 집합을 출력하는 작업을 수행한다.

요기에 대해 조금만(많이 하면 골치아픕니다…) 깊게 들어가보도록 하자.

아래와 같은 간단한 샘플코드가 있다.

map(String key, String value): // key: document name
// value: document contents for each word w in value:

      EmitIntermediate(w, "1");

reduce(String key, Iterator values): // key: a word
// values: a list of counts
int result = 0;

    for each v in values:

      result += ParseInt(v);

    Emit(AsString(result));

map함수는 각 단어와 그 단어가 나타나는 횟수를 리턴한다.(여기서는 그 횟수를 간단히 '1'로 하였다.)

reduce 함수는 특정 단어에 대해 리턴된 모든 횟수를 합산한다.

추가로, 개발자들은  input / output 파일 이름을 가진 mapreduce의 사양에 맞도록 객체에 코딩을 하게 되고

이러한 객체를 선택적 인자로 넘겨 줄 수 있다.

이후 개발자는 이 객체를 전달함으로써 MapReduce함수를 호출하게 되는 것이다.

이러한 사용자들의 코드는 MapReduce 라이브러리틀 통해 연결된다.

map과 reduce의 개념적인 input / output 타입은 다음과 같다

map (k1,v1) → list(k2,v2) 
reduce (k2,list(v2)) → list(v2)

이런 단어 세기 외에 다음과 같은 예들이 있다.

Distributed Grep : map 함수에서 특정 패턴과 매칭되는 라인들을 리턴한다. reduce 함수는 중간 데이터를

복사해서 출력하는 것과 유사한 함수로 기능한다.

Count of URL Access Frequency : map 함수는 웹 페이지 요청 로그를 분석하여 <URL, 1>의 결과를 도출하고

reduce는 같은 URL에 대한 value들을 합산하여 <URL, total count>쌍의 결과를 출력한다.

Reverse Web-Link Graph : map 함수는 'source'라는 이름의 페이지 내에서 'target'으로 링크되는 URL을 분석하여

<target, source>라는 쌍을 리턴하고 reduce 함수에서는 target URL과 관련된 모든 source URL들을 모아

<target, list(source)> 쌍을 만들어낸다.

Term-Vector per Host : term vector는 특정 문서 혹은 문서들의 목록 속에서 가장 중요한 단어들을

<word, frequence> 쌍으로 요약하는 것이다.

map 함수는 입력된 문서로부터 <hostname, term vector>쌍을 리턴한다.(hostname은 문서의 URL로부터

추출한 것이다.) reduce 함수는 주어진 host로부터 모든 문서당 term vector를 전달받아 이 term vector들을

함께 모은 후 빈도수가 낮은 용어들을 제거한 후에 최종적으로 <hostname, term vector>의 쌍을 리턴한다.

Inverted Index : map 함수는 각각의 문서들을 분석하여 일련의 <word, document ID>쌍을 리턴한다.

reduce 함수는 주어진 단어에 대해 모든 쌍을 전달받아 그 단어에 상응하는 document ID들을 정렬한 후

<word, list(document ID)>쌍으로 리턴한다. 모든 출력 쌍들의 집합은 간단한 역색인(Inverted index)을 구성하며

단어의 위치 추적을 강화하기가 쉬워진다.

Distributed sort : map 함수는 각각의 레코드로부터 key를 추출하고 <key, record>쌍을 출력한다.

reduce 함수는 변경되지 않은 모든 쌍들을 출력한다. 이 연산은 분할된 설비들에 의존적이다.