[옛 글] [BigData] MapReduce - 상세 기능 1

최초 작성일 : 2013/02/26 12:58 

Map과 Reduce 함수를 작성하는 기본 기능이 대부분의 필요를 충족시켜주기는 하지만

여기서 보다 확장된 유용한 기능들을 설명하고자 한다.

Partitioning Function

MapReduce의 사용자는 그들이 원하는 reduce task들과 출력 파일의 수를 ( R )과 같이 명시한다.

Data들은 중간 key를 이용하는 partitioning 함수에 의해 이 task들 상호간에 분할된다.

기본적인 분할 함수는 해싱을 이용해 제공된다.(예를들면 "hash(key) mod R" 과 같은 형태다)

이러한 분할 함수는 꽤 균형이 잘 잡힌 분할을 만들어낸다. 그러나 몇몇 경우에는 다른 함수들이 데이터를

분할하는데 더 유용하다.

예를들면 때때로 출력된 key들은 URL들인 경우가 있고 우리는 단일 호스트에 대한 목록만을 동일한 출력 파일에

정리하고 싶을 때가 있다. 이런 상황을 지원하기 위해 MapReduce 라이브러리 사용자들은 특별한 분할 함수를

제공할 수 있다. 분할 함수를 "hash(Hostname(key)) mod R"과 같이 사용하여 동일한 최종 출력 파일에

동일한 host의 모든 URL을 이끌어낼 수 있다.

Ordering Guarantees

우리는 주어진 분할 영역 내에서 중간 key/value 쌍들이 증가하는 key 값으로 정렬된다는 것을 보장받을 수 있다.

이러한 정렬에 대한 보장은 각각의 분할 영영에서 정렬된 출력 파일을 쉽게 생성하도록 해준다.

이렇게 잘 정렬된 파일은 출력 파일 형태가 키를 이용하여 효율적인 랜덤 엑세스 검색을 지원해야 하거나 사용자가 출력파일이

정렬되어있을 때 편리한 경우에 유용하다.

Combiner Function

어떤 경우에는 각각의 map task가 중간 key들을 생성해 내거나 사용자가 정의한 Reduce 함수가 교환되거나

합쳐지는데 중요한 반복이 생기는 경우가 있다.

이에 대한 좋은 예는 2.1장에서 예시한 단어 세기 예제이다.

단어 발생의 빈도는 *Zipf의 빈도에 따른 경향이 있기 때문에 각각의 map task들은 <the, 1> 쌍으로부터 수백에서

수천의 결과를 만들어낼 수가 있다. 이렇게 생성된 결과의 모든 수는 네트워크를 통해 하나의 reduce task에게 보내지고

하나의 수를 도출하기 위해 Reduce 함수에 의해 서로 더해진다. 우리는 결과물이 네트워크를 통해 전송되기 전에

이 데이터들을 부분적으로 병합할 수 있는 사용자 정의 결합 함수를 사용할 수 있도록 허용하고 있다.

결합 함수는 map task가 수행되는 각각의 머신에서 실행된다. 일반적으로 결함 함수와 reduce 함수는

같은 코드를 이용하여 구현된다. 유일한 차이점이라면 MapReduce 라이브러리가 각각의 출력 결과물을

어떻게 처리하는가이다. reduce 함수의 결과물은 최종 출력 파일에 기록된다. 결합 함수의 결과물은

reduce task로 보내지는 중간 파일에 기록된다.

부분 결합은 MapReduce의 어떤 클래스에서는 상당히 빠르다.

예제는 Appendix A에 수록되어있다.

*Zipf의 법칙 : 어떤 단어들의 집합에서 가장 빈도 수가 높은 단어를 기준으로 했을 때 두 번째로 빈도수가 높은 단어는 첫번째 단어의

1/2, 세 번째로 빈도수가 높은 단어는 첫번째 단어의 1/3…k번째 단어는 1/k가 된다는 법칙

이 법칙은 단어들의 빈도 수 외에 도시들의 인구 순위, 소득 분포, 신문이나 웹사이트의 독자, 지진 등의 빈도에도 적용이 된다.