본문 바로가기
공부(~2016)/그밖에

MapReduce 기본

by soy; 2016. 2. 13.

MapReduce

- 대용량 데이터를 다루는 문제가 주어졌을 때, 여러대의 프로세서에 분산시켜 병렬적으로 처리할 수 있다.

- MapReduce는 이러한 문제를 해결하기 위해 사용하는 하나의 프로그래밍 모델이다. 또는 이러한 프로그래밍 모델을 구현한 프레임워크이다.

- Map() 함수와 Reduce() 함수로 구성된다. Map() 함수를 통해 원하는 데이터를 추출하고, Reduce() 함수를 통해 summarize 한다는 컨셉이다.



MapReduce example

- 아래와 같이 1~5 단계가 순차적으로 수행된다.


1. prepare the Map() input

- storage(파일시스템, DBMS 등)에서 raw data를 읽어온다.

- raw data를 적당한 크기의 chunk 단위로 쪼갠다. 

- 각 chunk들을 각각의 Map() 프로세서들에게 할당한다.

- 예) 파일시스템으로부터 파일을 읽어와서 line 단위로 쪼갠다.


2. Map(key, value) 

- 각각의 input에 대하여 병렬적으로 Map() 함수가 수행된다. 

- Map() 함수의 내용은 사용자가 원하는 방향으로 구현한다.

- 각 input에 대한 처리를 통해 새로운 key-value 쌍을 output으로 만들어낸다. 이 때 key-value 쌍은 0개일수도, 여러개일수도 있다.

- 예) 문장에서 나오는 단어 갯수를 카운트하는 경우

input:  { "line1" : "word1 word2 word2 word3 word3 word3 ..." }

output:  { "word1" : "1", "word2" : "2", "word3" : "3" }



3. Shuffle the Map() output to the Reduce() input

- Map() 함수가 만들어낸 모든 output에 대하여, key를 기준으로 grouping한다.

- grouping한 각각의 데이터를 Reduce() 프로세서들에게 할당한다.

- 예)

Map() output 1:   { "word1" : "1", "word2" : "2", "word3" : "3" } 

Map() output 2:  { "word2" : "4", "word3" : "5", "word4" : "6" }


Shuffle's result:   { "word1" : ["1"] },  "word2" : ["2", "4"] },  { "word3" : ["3" , "5"] },  "word4" : ["6"] }



4. Reduce(key, list of values)

- 각각의 input에 대하여 병렬적으로 Reduce() 함수가 수행된다.

- Reduce() 함수의 내용은 사용자가 원하는 방향으로 구현한다. 일반적으로 input data에 대한 summary를 만든다.

- 예)

input:  "word3" : ["3" , "5"]  }

output:  "word3" : "8" }



5. Produce final output

- Reduce() 함수가 만들어낸 모든 output을 취합하여 원하는 형태의 최종 output을 만들어 낸다.

- 예)

Reduce() output 1:   "word2" : "6" }

Reduce() output 2:  "word3" : "8" }


final output:  { "word2" : "6" },  "word3" : "8" } }



# References: https://en.wikipedia.org/wiki/MapReduce

댓글0