MapReduce

 

Mapreduce processing 하는 것은 데이터를 처리해서 insight를 얻기 위함이다. 그리고 분산되어 있는 큰 데이터들을 어떻게 하면 빠르게 병렬 처리하고 높은 through put 을 낼 수 있는 것을 고민한 결과이다. 그리고 기본적인 빅데이터 처리 모델이다.

 

그 전 포스트에서는 하둡(Hadoop)이 빅데이터를 어떻게 저장하는지에 대해 배웠고 이제는 분산파일 시스템에 저장되어있는 데이터를 어떻게하면 효율적으로 병렬처리할 수 있으면서 전체적인 through put을 높일 수 있는 방안에 대해 고민한 MapReduce 프레임워크에 대해서 살펴볼 것이다.

Hadoop project라고 하는 것은 distributed file system이고 very large data set을 analysis 하고 transformation 할 수 있는 MapReduce라고 하는 페러다임을 가지고 있다. 사실은 MapReduce라고 하는 것은 클라우드 프로그램밍 모델인 동시에 runtime system이라고 할 수 있다. 그래서 데이터만 partitioning 하는 것이 아니라 computation도 분할해서 수천개 이상의 호스트들에게 분산해서 실행하는 것이다. 즉 분산돼서 데이터도 저장하고 분산해서 실행하는 것이다.

 

MapReduce의 큰 특징중 하나는 애플리케이션에 computation(task 어떤 분산시스템에 작업단위를 job이라고 표현했다)들이 되도록 병렬하게 동시다발적으로 실행될 수 있도록 하므로써 전체적인 시스템에 성능을 높인다. 데이터와 최대한 가깝게 처리하고 싶은 것이 MapReduce의 목적이다. 데이터와 가깝다는 것은 data locality 장점을 보는 것이다. 가깝다는 것을 어떻게 표현했냐면, 같은 노드에 있으면 distance가 0였고 다른 노드라고 하더라도 똑같은 rack에 속해있으면 distance가 2다. 그리고 rack마다 달라지면 distance가 4로 늘어난다 이런식으로 표현한다.

 

하둡에서는 가깝다는 개념, distance라는 개념을 실제 runing time시 bandwidth를 측정하는 것이 어렵기 때문에 그렇게 하지 않고 데이터센터에 네트워크 토폴로지를 반영한 심플한 모델을 사용한다. 그래서 하나의 Hadoop cluster라고 하는 것은 단순히 commodity server(어디서나 구할 수 있는 흔해 빠진 서버) 를 계속 추가해 나가면 hdfs가 저장할 수 있는 storage capacity가 IO bandwidth만 늘어나는게 아니라 MapReduce가 실행할 수 있는 computation capacity 까지도 함께 늘어날 수 있는 scale out 아키텍쳐를 가지고 있다.

 

 

MapReduce는 프로그래밍 모델(programming model)

MapReduce라고 하는 것은 프로그래밍 모델이다. 왜 프로그래밍 모델이라고 하냐면 모든 computation을 Map과 Reduce라고 하는 두 개의 함수로만 표현하기 때문에 프로그래밍 할 수 있는 일종의 범위(scope)을 확 줄여놓았다. 이런 관점에서 보면은 프로그래밍 모델이다 라고 말할 수 있다. 또한 이와 관련된 구현 결과물인데 어디에 대한 결과물이냐면, 굉장히 대용량의 데이터를 처리하고 생산해 낼 수 있는, MapReduce의 결과로 다른 데이터가 생성될 수 있다. 이런 목적으로 탄생한 프레임워크가 바로 MapReduce이다. 왜 Map과 Reduce냐면, 개발자는 Map function과 reduce function을 개발해야한다.(코딩해야한다) 이것은 MapReduce 프레임워크는 사용자가 정의해준 Map과 Reduce function을 잘 적용하는 역할을 수행하는 것이지 더 많은 책임을 지는 것은 아니다. Map과 Reduce는 특징이 뭐냐면 입력과 결과가 항상 key, value pair형태로 표현하고 이런 표현으로 통신하게 된다.  

 

 

MapReduce를 개발하게된 동기(motivation)을 살펴보자.

MapReduce를 개발하기 이전에는 어떤식으로 구글이 작업했는지에 대한 이야기를 해보자.

 

구글은 세계 최고의 검색엔진 회사이다. 그래서 구글이 웹 다큐먼트를 크롤링 해와서 상당히 raw data가 많이 쌓이고 이걸 통해서 여러가지 일들을 수행하는 회사인데, 구글이 MapReduce이전에 했던 것들을 보면, 특수목적형 계산 프로그램(special purpose computations)들 수백개를 계속 만들어왔다. 이런것들은 굉장히 큰 규모의 raw data들을 처리하는 것들인데 크롤링된 document라던지 웹 리퀘스트 로그(web request log)라던지 이런것들을 분석/처리해서 다양한 형태의 결과물(derived data)을 뽑아내는데, inverted index(inverted indices)라던지, 아니면 web document를 그레프(그래프 graph) 형태로 표현한다든지, 아니면 호스트당 크롤링된 페이지의 통계를 구한다던지, 아니면 하루에 가장 자주 들어온 query를 찾아낸다던지 이런 여러가지 일을 한다. 

이렇게 수행이 되고 있었는데 문제가 뭐였냐 하면,

구글이 대용량의 raw data를 처리하기 위해서 이런 개발물들(computations)자체가 개념적으로 그렇게 어려운 것이 아니다(conceptually straightforward)이다. 그런데 입력(input) 데이터가 매우 크다 그리고 어느정도 감내할만한 시간내에 끝내게 하려면 수백 수천대 이상의 머신에 분산되어서 computation이 실행 되어야 한다. 어쩔 수 없는 것이다. 데이터가 너무 많다 보니까 이거를 하나의 노드에서 처리한다는 것은 불가능 하기 때문이다. Hdfs때 많이 얘기 했지만, 결국은 분산파일시스템 자체가 데이터가 한 노드에 다 저장되지 못하기 때문에 나온 것이기 때문이다. 마찬가지로 computation 계산과정에서 봐도 데이터가 너무 크면 분산처리 할 수 밖에 없다. 그러니까 구글이 하고자하는 일들이 아주 복잡한 형태는 아니었음에도 불구하고 input data가 너무 커서 computation을 분산시키다 보니까 분산 컴퓨팅(distributed computing)으로 인한 overhead가 너무 컸던 것이다. 어떤 오버헤드(overhead)가 있냐면, hdfs에서도 다루었지만 일단 분산 시키는 순간 failure가 가장 문제가 된다. 노드가 죽거나 한참 열심히 실행하다가 노드가 죽으면 어떡하지? 그리고 특히 프로세싱 측면에서 봤을 때는 로드벨런싱(load balancing)도 굉장히 어려운 문제이다. 무슨 얘기이냐면, 내가 열 개의 노드에 열심히 분산시켜서 실행 하고 있는데 어떤 1~2 노드가 성능이 딸려서 그런건지 늦게 실행이 되면은 전체적인 프로세스에 영향을 받는다. 그런 관점에서 봤을 때 구글도 분산처리를 관리하는데 상당히 힘들었던 것이다. 이것을 좀 더 편리하게 할 수 없을까? 뭔가 추상화 레벨을 높여서 run time system 이런것들을 해주면 좋겠는데 라는 어려움이 있었기 때문에 map reduce라고 하는 프로그래밍 모델인 동시에 관련된 구현결과물(run time system)인 새로운 프레임워크가 구글에서 탄생하게 되었다고 보면된다. 

 

 

Map Reduce는 프로그래밍 모델인 동시에 구현결과물(runtime system)인데, large data set을 생성하고 처리하는데 사용되는 것이다.

그래서 MapReduce라고 하는 것은 결과적으로 단순한 형태의 computation을 어떻게 하면 잘 표현할 수 있을까 추상화를 고민하는 것이다. 구글이 하고자하는 대용량의 raw data를 처리하는 많은 작업들(computation)의 특징이 뭐였냐면, conceptually straightfoward 한것이다. 개념상으로는 아주 어려운 문제를 푸는 것임이 아니었음에도 불구하고 단순히 input데이터가 너무 크기때문에 분산처리하는 영역이 있는 것이다. 

그래서 추상화를 하면서 어떻게 하느냐면, 분산처리를 하다보면 messy한 디테일들인 병렬화(parallelization), 고장 감내(fault tolerance), 데이터를 어떻게 분산시킬것인가(data distribution) and 로드벨런스(load balancing) 이런것들을 처리해야 한다. 즉 정리하자면 simple한 computation을 잘 표현할 수 있는 길을 열어주고 parallelization, fault tolerance같이 분산처리 하면서 발생할 수 있는 messy한 문제들을 개발자로 부터 감춰주면 좋겠다.(감춰준다는 의미는 사용자가 직접 하는 것이 아닌 분산처리 문제는 MapReduce가 알아서 해준다는 의미) 사용자가 풀고자 하는 문제를 Map과 Reduce에 맞게 개발하면 된다는 것이 MapReduce의 철학이다.

 

MapReduce는 Lisp라고 하는 functional language에서 있던 Map과 Reduce라고 하는 개념을 가져온 것이다.

그래서 첫번째 단계에서 map이라는 operation은 사용자가 정의해줘야 하는 것이다.(틀만 있다) 각각의 record에 대해서 map operation을 적용하고, 적용한 결과로 뭐가 나오냐면 intermediate key/value pair가 생성된다. 즉 map과 reduce에서는 항상 input과 output에서 key/value로 통신한다. record라고 하면 데이터베이스에서 튜플이다. mapreduce에서 말하는 데이터는 주로 비정형 데이터이기 때문에 텍스트 문서의 한줄한줄을 logical record라고 생각하면 된다.(거기 어떤 내용이 들어있던 상관없이) 사용자가 정의한 logical record를 읽어서 사용자가 정의한 map function을 적용하면 결과물로써 intermediate key/value pair가 생성된다.

이러면 reduce단계로 넘어가야 하는데 reduce라고 하는 것은 aggregation 연산을 수행하게 되는데 map과 reduce중간에 shuffling이라는 단계가 들어간다. shuffling이라고 하는 것은 map reduce 프레임워크가 알아서 해주는 것인데, 

뭘 헤주냐면, 같은 키를 공유하는 모든 value들을 묶어준다. 다시 말해 intermediate key/value pair중에서 같은 키값을 갖는 value들은 다 왕창 묶어준다는 얘기이다. 제대로된 aggregation 연산이 이루어 진다고 볼 수 있는 예시가 wordcount 문제였다. 같은 키를 공유하는 value들의 리스트를 받아서  어떤형태로든 combine 연산을 수행하면 되는 것이다. shuffling에서 중요한 부분은 뭐냐면 같은 키를 공유하는 value들은 반드시 한꺼번에 묶여서 온다는 것이다. key가 같은데 value 들의 set이 분할될 수는 없다는 것이 철학이다. 만약에 분할이 되면 최종 통계를 낼 때 할 수 가 없다. 그러니까 반드시 같은 중간 키값을 공유하는 모든 value들은 하나의 reducer로 전달되게 된다. reducer가 전체시스템 하나라면 문제가 없겠지만 두 개 이상이 될 경우에는 두 개의 reducer에  분할돼서 같의 집은 key를 갖는 value들합이 쪼개지면 결코 안되는 것이고 이것은 MapReduce프로그램이 guarantee해준다. 

 

사용자 입장에서는, 구글이 고민했던 messy detail들을 MapReduce가 감춰준다고 했기 때문에 사용자들은 Map Reduce가 제공하는 프로그래밍 모델에 맞게 적절하게 Map과 Reduce함수를 구현해주고 key/value pair를 어떻게 정할건지 내가 원하는 aggregation연산을 수행하려면 어떻게  할건지만 고민하면된다고 보면 된다.

 

결과적으로

추상화 레밸을 높이면서 분산컴퓨팅 어플리케이션을 개발하는 개발자에게 도움을 주고자 했던것이 구글의 고민이었고 그 결과물이 바로 MapReduce이다.