Google MapReduce

Google MapReduce Overview 1

Google MapReduce가 실제 어떻게 실행이 되는지 시스템 아키텍쳐 측면에서 살펴보자.

 

master가 HDFS의 namenode와 비슷하게 MapReduce 실행을 관장하는 master 역할을 하는 것이고, Hadoop에서는 이것을 jobtracker라고 표현한다. 그리고 worker들은 hadoop에서 tasktracker라고 표현한다. 왼쪽 worker들은 Map 단계를 수행하고, 오른쪽 worker들은 Reduce 단계를 수행한다. 그럼 어떤식으로 흘러가는 것일까 보면, (맨 왼쪽 부터 시작) 입력파일들이 주어지게 된다. 입력파일이 주어지게 되면은 입력파일을 input split으로 쪼개게(partitioning) 된다. worker에서는 split 0, 1두개를 실행시킨다. Input split이라고 하는 것은 HDFS에서 block size랑 같다고 했으니까 대개의 경우에는 64mb 데이터 파일을 읽어들어서 처리하게 된다. (위 그림상) input split이 5개 이니까 5개의 mapper가 뜰건데, 그 mapper안에 정의되어 있는 map함수를 적용하는 것이 바로 worker의 역할이다. 그러면 key/value pair를 parsing해서 각각의 pair를 user-defined(user defined) map function으로 보내주는 것이다. wordcount 같은 경우는 intermediate key/value는 “단어,1”이런식으로 내보냈다. 그러면 worker가 mapper를 통해서 하나의 input split을 처리하면서 나오는 그러한 intermediate key/value pair들은 일단 메모리에 버퍼가 된다. 그런데 메모리에 용량이 부족해질 수 있으니까 주기적으로 버퍼된 pair(buffered pair)들이 로컬 디스크에 R개의 region으로 분할(partitioning)되어서 저장이 된다. intermediate key space를 reducer 개수만큼 partitioning 한다고 했는데 현재 여기서는 reducer가 두개가 돈다고 보면 된다. reducer가 두개일 때 잘 보면 로컬에 저장된것도 조각이 두개이다.(partitioning 되어서 저장된것이다) 그러면 예를 들어서 wordcount 예시를 들어보면 bear와 car는 왼쪽 조각에, deer와 river는 오른쪽 조각에있고 각각 다른 reduce단계의 worker로 갈 수 있다고 생각하면된다. map단계에서 모두 끝나고나면 로컬디스크에 파티셔닝 되어있는 데이터가 있을 것이다. 각각의 데이터가 reduce로 전달되는 것일 뿐이다. map단계가 끝나고 나면 파티셔닝된 데이터가 있을것이고 각각의 데이터가 결과적으로 reduce로 전달되는 것일 뿐인데, 어떻게 전달이 되느냐하면, reduce의 worker가 master로 부터 notification을 받는다. 그러면 remote procedure call을 통해서 퍼버링된 데이터를 map worker의 로컬디스크로 부터 가져가는 것이다.

 

정리하자면 input split 개수만큼 mapper가 실행되고 (이 그림에서 현재 mapper가 5개가 실행돼야하는데 3개만 보여주고있는상황) mapper가 하는일은 input split에 있는 logical record를 하나씩 읽어서 사용자가 정의한 map함수를 적용하고 그 결과로 나오는 intermediate key/value pair를 reduce의 개수만큼 partitioning 해놓은 것이다. (Partitioning 함수는 기본적으로 주어져 있다. ) reducer개수가 하나라는 얘기는 partition 자체를 할 필요가 없다는 얘기이다. Partition data를 로컬디스크에 잘 저장하고 있다가 모든 map단계가 끝나면 reducer가 각각의 maper에게 연락해서 가져간다. 그러면 결과적으로 reduce의 개수만큼 file이 생기게된다.

 

Google MapReduce Overview 2

하나의 input split을 받아서 map 함수를 거치면 메모리에 버퍼링되는 intermediate key/value pair들이 나온다. 이것들이 결국 partition하고 sorting해서 저장하게 된다. 결국 디스크에 merge 되어있고 세 칸인거 보니깐 reducer가 세 개 돌고있는 것 같다. 그러면 첫 번째 partition은 첫번째 reduce한테 주고  두번째 partition은 두번째 reduce… 이렇게 준다. 이런식으로 다른 mapper들도 세 개로 쪼갠 partition을 가지고 있을 것이고 첫번째 파티션이 한쪽에 모일 것이다. (오른쪽 그림이 첫번째 파티션에 해당되는 데이터를 처리하는 reduce이기 때문) 내부적으로 merge, sort 하면서 reduce단계로 넘어가서 최종 output을 생산해내는 단계로 가게 된다.

 

Shuffling 단계가 MapReduce실행에 가장 복잡한 단계이다. 또 다르게 말하면 가장 overhead가 큰 단계이다. fetch같은 것들이 많이 일어나니까 network 통신이 많이 일어나기 때문이다. 

 

파티션에 데이터가 없을 수 있다. 이점은 데이터가 어떻게 구성되느냐에 따라 달라진다.