'combiner'에 해당되는 글 2건

최초 작성일 : 2013/05/30 15:24 


맵 리듀스 개요

맵 : 
- 원시 데이터를 key-value 쌍의 중간 파일로 만든다.
- 입력데이터가 있는 노드에서 맵 함수가 수행되는 것이 가장 좋다 (지역성 최적화)
- 맵 함수에 전달되는 입력 데이터는 라인 offset을 키로, 해당 라인 내용을 value로 하는 형태로 구성된다.
- 맵 함수는 이 입력값들로부터 필요로 하는 key와 value를 추출한다.
- 이 과정에서 잘못된 레코드를 제거하는 기능도 수행한다.
- 맵 task의 실행 결과는 HDFS가 아닌 로컬 디스크에 저장된다. (HDFS와 로컬 디스크의 개념을 명확히 구분하자)
  이유는 맵의 결과물은 단지 리듀스 함수로 전달하기 위한 중간 결과물일 뿐이며 모든 잡이 완료되면
  버려도 되는 데이터이기 때문이다.

리듀스 : 
- 각 맵 task들의 결과물들을 입력으로 받아 최종 결과물을 생성한다.
- 각 노드에 있는 맵 task의 결과물들을 입력으로 받으므로 지역성 최적화의 영향이 없다.
- 리듀스의 결과물은 안정성을 위하여 HDFS에 저장된다.


셔플 : 
- 맵 task의 결과물을 리듀스 task로 보내기 전의 중간 가공 단계
- key에 대한 정렬이나 그룹화 및 파티셔닝 작업이 이루어진다.
- 정렬은 말 그대로 정렬이며 그룹화는 같은 key로 묶는 것, 그리고 파티셔닝은 리듀스 task가 2개 이상인 경우
  결과물을 각각의 리듀스 task에 분배하기 위해 특정 기준으로 쪼개는 작업이다.
- 때때로 셔플 작업이 없을 수도 있으며 이런 경우에는 리듀스 task도 없는 맵 task만으로 이루어진
  job이 수행된다. 또한 이 상태에서는 맵 task의 결과가 HDFS에 저장된다.

컴바이너 : 
- 맵 task의 결과물을 네트워크를 통해 리듀스 task로 이동시키는 과정을 최적화하기 위한 방법 중 하나
- 같은 key를 가진 value들을 리스트로 묶어 새로운 key-value쌍을 만든다.
  즉 {key1, value1}, {key1, value2}를 {key1, list(value1, value2)}의 형태로 만드는 것이다.
- 주로 연합 연산(합계, 카운팅, 최대값 등)에 사용된다.
- 컴바이너를 사용하게 되면 맵 task 결과물의 사이즈를 줄일 수 있다. 즉 네트워크의 트래픽량을 줄일 수
  있게 되는 것이다.

블로그 이미지

마즈다

이미 마흔을 넘어섰지만 아직도 꿈을 좇고 있습니다. 그래서 그 꿈에 다가가기 위한 단편들을 하나 둘 씩 모아가고 있지요. 이 곳에 그 단편들이 모일 겁니다...^^

최초 작성일 : 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가 된다는 법칙

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

블로그 이미지

마즈다

이미 마흔을 넘어섰지만 아직도 꿈을 좇고 있습니다. 그래서 그 꿈에 다가가기 위한 단편들을 하나 둘 씩 모아가고 있지요. 이 곳에 그 단편들이 모일 겁니다...^^