- 위키 MapReduce 는 이 문서를 기반으로 작성되었다.
mapreduce-osdi04.pdf
http://static.googleusercontent.com/external_content/untrusted_dlcp/research.google.com/ko//archive/mapreduce-osdi04.pdf
google 의 폐쇄성 , Hadoop, Google의 MapReduce 이야기
http://freesearch.pe.kr/archives/1115
Hadoop을 이용한 분산 데이터 처리
http://cafe.naver.com/smartchip/1541
http://en.wikipedia.org/wiki/MapReduce
MapReduce
큰 데이터 셋들을 프로세싱하기 위한 프로그래밍 모델로 구글에 의해 지어진 implementation 모델의 이름이기도 하다.
맵리듀스는 전형적으로 컴퓨터들의 클러스터 집합에서 돌아가는 분산 컴퓨팅에서 사용된다.
이 모델은 functional 프로그래밍에서 흔히 사용되는 map 과 reduce 함수들에 영감을 받았다. (원 map reduce 함수들의 목적이 MapReduce 프레임워크와 다른 목적을 지녔음에도 불구하고)
맵리듀스 라이브러리들은 많은 프로그래밍언어로 짜여져왔으며, 제일 유명한 free implementation 은 Apache Hadoop 이 있다.
Overview
맵리듀스는 매우 큰 수의 컴퓨터들(노드들) 을 사용하는 큰 데이터셋에 분산되어 존재하는 평형화가능한(parallelizable) 문제들을 처리하기 위한 프레임워크이고, 전체적으로(collectively) 클러스터(만약 모든 노드들이 하나의 같은 로컬네트워크 그리고 같은 비슷한 하드웨어를 쓸 경우에 클러스터라고 부른다) 또는 그리드(노드들이 지리학적으로 그리고 행정상으로(경영상으로 : administratively) 분산된 시스템들에 분산되 있고, 성질이 다른 하드웨어들을 사용할땐 그리드라고 부른다)에서 언급된다.
컴퓨터적인 프로세싱은 파일시스템(unstructured)에서나 데이터베이스(structured)에서나 어느 곳이든 저장되어있는 데이터들에서 발생할 수 있다. 맵리듀스는 데이터의 지역성(locality)의 이점을 가질 수 있다. 이는 저장소 주변에서 혹은 그 안에서 진행하는 데이터 프로세싱을 함으로서 데이터의 이동(transmission)을 최소한 감소시킴으로서 이루어 낸다.
"Map" 과정 : '마스터 노드'는 input 을 갖고, 이들을 작은 sub-problem 들로 나누어, 'worker 노드'들에게 분산한다. (maybe HDFS)
worker 노드는 멀티레벨의 트리 구조를 이끌어 이를 한번 더 돌아가면서 실행한다.(실질적 mapping)
( = A worker node may do this again in turn, leading to a multi-level tree structure )
워커노드는 작아진 problem 을 프로세싱하고, 그에 대한 답을(프로세싱의 결과를) 마스터 노드에게 전달한다.
"Reduce" 과정 : 마스터 노드는 모든 sub-problems 에 대한 해결책들을 각각 worker 노드들에게 모아서 이들을 '특정 몇몇의 방법'(= in some way) 을 이용해서 output 포맷으로 결합한다. - output = 맨 처음에 해결하기 위해 노력했던 그 문제 problem 에 대한 답변
맵리듀스는 맵과 리덕션의 분산 처리들을 위해 존재합니다. (allow for) 각각의 맵핑 작업에 제공되는것은 다른 것들과 독립적이기 때문에 모든 맵들은 평형적으로 작업을 수행합니다. - (실질적으로 그 작업들이 독립적인 데이터 자원(source)들의 수에 제한되고, 되거나 (and/or) 각 자원(source)들의 CPU 개수들에 제한되더라도)
비슷하게 리듀서들의 집합은 리덕션 부분을 처리할수있습니다. - '같은 키'들을 공유하는 맵 작업의 결과로서 제공받은 모든 결과들은 동시에 같은 (키의 = key) 리듀서들에게 수여되거나 (be presented to), 혹은 리덕션 함수가 associative 할때. (= 연상일때)
이 프로세스가 더 순차적인 (sequential) 알고리즘에 비교해보았을때 종종 비효율적으로 보일수도 있을 수 있으나, 맵리듀스는 상용 서버들이 다룰 수 있는것보다 매우 더 큰 (significantly larger) 데이터 셋들에 적용될 수 있다. - 큰 서버 팜도 페타바이트 데이터를 단 몇시간만에 분류하기 위해 맵리듀스를 사용할 수 있다.
평형성은 또한 작업중에 발생할 수 있는 서버 혹은 저장소의 부분적인 오류들을 회복할 수 있는 가능성들을 제공한다. : 만약 하나의 맵퍼나 리듀서가 실패한다면, 시행하고 있는 작업은 다시 리스케줄링될 수 있다. (input data 가 아직도 유효하다면)
Logical View
맵리듀스의 맵과 리듀스 함수는 모두 (key, value) 짝으로 표현되는 '데이터 구조'에 관하여, 대하여(with respect to) 정의된다.
Map 은 하나의 데이터 도메인(data domain)에서 하나의 타입을 갖는 하나의 데이터 짝을 가져가고, 앞과는 다른 도메인(different domain)의 짝들의 리스트 한개를 리턴한다. : Map(k1, v1) -> list(k2, v2) /
/ Map(String hello(txt name), String hello.txt) -> list(char word, int x(개수))
/ Map(String mov(mov name), Mov movPart1) -> list(int keypart1, Mov Enc_movPart1)
- 하나의 데이터 도메인 (데이터 도메인의 예로는 gender 에서의 W, M, U 과 같은 요소들을 뜻한다. 즉 특성들을 뜻하는 것으로 이해하면 된다.) 에서 하나의 타입을 갖는 (위의 예를 따르면 M 이 하나의 타입이 된다) 한 쌍의 데이터를 Map 이 take 해간다.
= 예 > input : 하나의 데이터 도메인을 갖는 하나의 짝 = 첫번째 줄(데이터 도메인 = 1)의 문장 = ( 1st sentence = apple is good and orange is bad. )
= 예 > return : 다른 도메인의 짝들의 리스트 한개 = word 들에 대한 리스트 ( 1st sentence's words = ( apple = 1, orange = 2 ) // 2nd sentence's words = ( apple = 2, orange = 7 ))
= 예 > pair = ( a = 3 ), a list of pairs = ( a = 3, b = 4 ... )
맵 함수는 input 데이터셋에 있는 각각의 쌍에 평형적으로 적용된다. 이는 각 call 에 대해 쌍들의 리스트 하나를 생성한다. 그 후에 맵리듀스 프레임워크는 모든 리스트들로 부터 같은 키값을 가진 모든 쌍들을 모아 그들을 묶어 각 키당 하나의 그룹을 생성한다. (one group for each key)
- 맵 함수가 input dataset 에 있는 각각의 pair 들에 대해 평형적으로 적용된다고 하는 말의 뜻은, 각 Mapper 들은 각각 하나의 쌍을 갖고 있고, 맵 함수는 각 Mapper 들에 있는 하나의 쌍에 대해 적용되고, Mapper 의 수는 많으므로 평형적으로 진행된다는 이야기이다.
- 각각의 call 에 대해 짝들의 리스트를 생성한다는건, 하나의 Call은 하나의 Mapper 에게 주어진 일이고, Map 에 대해 설명했듯이 input 은 하나의 a pair 이지만 결과 리턴값은 a list of pairs 라고 했으므로 하나의 call 은 a list of pairs 를 리턴한다는 뜻이다.
- 이렇게 각자의 call 들을 마치고 a list of pairs 를 도출해 낸 뒤에 맵리듀스 프레임워크는 이 각각의 a list of pairs 들을 모아서 모든 all pairs 에 대한 정보들을 수집한다.
= 예 > ( 'A' list of pairs : a = 1, o = 2) + ( 'B' list : a = 2, o = 7, b = 13) = ( ALL list : a = 1, a = 2, o = 2, o = 7, b = 13)
- 그리고 이렇게 다 합친 pair 정보들을 같은 key 를 기준으로 그룹들을 맺어준다.
= 예 > ( 'a' key group = ( a = 1, a = 2 ))
리듀스 함수는 각 그룹에 대해 평형적으로 적용된다. 그 그룹은 같은 도메인(= 같은 데이터 도메인) 상에 있는 값들의 모음을 차례대로 생성한다. : Reduce(k2, list(v2)) -> list (v3) /
/ Reduce(char word, list(x(개수))) -> lsit ([char word,] xsum(총 개수))
= 예 > ( a key group = ( a = 1, a = 2)) --> ( a sum = 3 )
하나의 콜이 하나의 값보다 더 많은것을 리턴하게끔 할당되어 있더라도, 각 리듀스(작업)는 전형적으로 하나의 값 v3 (위 예로 a sum = 3)이나, 빈 리턴값을 생성한다. 모든 콜들의 리턴값들은 원하는(desired) 결과 리스트로 모아진다.
즉, MapReduce 프레임워크는 (key, value)짝들의 리스트를 값들의 리스트로 변환시킨다. (a list of (key, value) pairs -> a list of values) 이 처리(behavior)는 map 과 reduce 의 조합을 전형적인 함수적(functional)으로 프로그래밍하는것 과는 다른것이다. 이 프로그래밍기법은 임의의 값들의 리스트를 받아 map 에 의해 리턴된 모든 값들을 모은 하나의 단일 값을 리턴한다.
MapReduce 를 구현하기위해서 map 과 reduce 들의 구현을 추상화 시키는것은 필요하지만 충분하지는 않다. (it is necessary but not sufficient) MapReduce의 분산 구현은 Map 과 Reduce (map 과 reduce 와는 다르다 (소문자와 대문자)) 단계를 수행할 프로세스들을 연결하는 수단들이 필요하다. 이것이 분산 파일 시스템이다. (distributed file system)
맵핑 결과들을 그 결과들을 query 하는 리듀서들에게 건네주기 위해 mapper 에서 reducer 로 직접 스트리밍 혹은 맵핑 프로세서들을 위한 직접 스트리밍과 같은 다른 옵션들도 가능하다.
Example : Wordcount
function map(String name, String document):
// name: document name
// document: document contents
for each word w in document:
emit (w, 1)
function reduce(String word, Iterator partialCounts):
// word: a word
// partialCounts: a list of aggregated partial counts
sum = 0
for each pc in partialCounts:
sum += ParseInt(pc)
emit (word, sum)
각각의 String document 는 words 들의 집합들로 분리되어 있고, 각각의 단어들은 단어들을 결과 key 값 (단순히 key 를 key 값이라고 표현할것이다. 절대 value 를 뜻하는게 아니다.)으로 사용하는 map 함수에 의해 세어진다. 프레임워크는 같은 key 값을 같는 모든 짝들을 한데 모으고, 그 모은 것들을 리듀스에 대한 같은 콜(the same call to reduce / 같은 콜이라는 의미는 map 작업을 한 애들이 자신에게 할당된 부분 문장에서 얻어낸 key 들에 대한 짝들을 갖고, 그대로 자신이 reduce 작업까지 이어나간다는 것이다.)에다가 넘겨준다. (feed) 이렇게 해서 이 함수는 단어의 전체 존재수들을 찾기 위해 단지 모든 그것의 입력 값들을 더하는것을 필요로한다.
Dataflow
MapReduce 프레임워크의 고정적인 부분은 (frozen part) 대형 분산 정렬이다. 애플리케이션이 정의하는 hot spots 들은 다음과 같다.
an input reader
a Map function
a partition function
a compare function
a Reduce function
an output writer
- 미완성
http://en.wikipedia.org/wiki/MapReduce
http://en.wikipedia.org/wiki/Hadoop#File_Systems
http://developer.yahoo.com/hadoop/tutorial/
http://gmyoul.tistory.com/8
http://www.hadoop.or.kr/?document_srl=1099
http://www.ibm.com/developerworks/kr/library/au-cloud_apache/index.html#figure2
http://www.firstpost.com/topic/place/taiwan-hadoop-in-taiwan-2012mohohan-an-on-line-video-transco-video-1lxE9ZB_LEE-79-1.html
아파치 하둡 위키 : http://wiki.apache.org/hadoop/HadoopMapReduce
HDFS 용어 : http://redju.tistory.com/256
하둡 용어 : http://gmyoul.tistory.com/8
하둡 정의 번역본 : http://www.hadoop.or.kr/?document_srl=1099
