블로그 한지 3일째다.

실제 hadoop의 설치나 프로그래밍적 이슈는 언제 다룰 수 있을지는 모르겠다.
하지만 그런것들은 공식 웹싸이트의 getting started 같은 것을 보면 정말 쉽게 수행할 수 있다.

hadoop은 수백대의 클러스터를 구성하여 linux 환경에서 돌리는 것이나 stand alone 환경으로 돌리는 것이나
hdfs와 mr의 큰 개념을 잡기에 전혀 차이가 없다. (매니징은 예외)

개념보다 당장 돌려보고 싶다면 추천! ㅎㅎ


아주 기본적인 Map Reduce의 개념

map reduce의 개념은 크게 어렵지 않다.
예전 우리프로젝트가 hadoop을 도입하기전에 매우 큰단위의 데이터를 처리하기 위해서
일괄적인 기준으로 데이터를 분배하여 분배된 데이터를 일관된 형식으로 처리하는 형식의 프레임웍을 구현한적이 있다.

예를들어서 1부터 1억까지의 임의의 순서로 정렬된 숫자 수열의 모든 숫자를 더하고 싶다고 가정하자 (일반화된 공식을 사용할 수 없고 이터레이팅으로만 계산할 수 있다고 가정하자). 그런데 싱글머신에서 저 이터레이팅 시간의 비용이 많이 든다고 추측되어

n대의 머신에 (1억/n)으로 나눠진 task 만큼 각 머신에 분배하여
1번 머신은 1부터 1000까지
2번 머신은 1001부터 2000 까지
.... 
n대의 머신이 각각 처리되게 한 후 마지막에 각 머신의 결과를 더했다고 가정하자.
그리고 위 사항을 일반화 시켜 x자리의 데이터의 덧셈에 대해 일관되게 작동하게 구현했다고 가정하자.

그렇다! 당신은 해당 계산에 대하여 map reduce를 적용한것이다 ㅎㅎ
(map 과정에 대한 설명이 다소 약한 예제같다)
 

이제부턴 다시 교과서적인 설명을 보도록하자
MapReduce 는 클러스터링 된 컴퓨터 장비에서 페타 바이트 단위의 거대한 데이터를 분산 컴퓨팅 할 수 있는 목적으로 google에 의해 2004년 도입된 소프트웨어 프레임웍이다.

이프레임웍은 일반적으로 함수형 언어에서 사용되는 Map함수와 Reduce함수에서 힌트를 얻어서 만들어졌지만 그 목적이 원래의 그것과 완전히 동일하지 않다.

MR을 c++, c#, 얼랭, 자바, 오캄, 펄, 파이썬, PHP, 루비, F#, R등의 언어로 구현된 라이브러리들이 있다.

MR은 빅데이터(big data)를 많은 컴퓨터군(노드)를 이용하여 병렬처리 하기위한 프레임웍이다.
해당 작업을 파일 시스템(unstructured)이나 데이터베이스(structured)에 저장된 데이터에 대하여 수행 할 수 있다.


MR의 단계

Map 단계 - 마스터 노드는 입력 데이터를 받아 그것을 더 작은 단위로 분할하여 여러 워커 노드들에게 분산한다.
작업을 할당 받은 워커 노드들은 해당 데이터들을 더 작은 단위로 분할하여 다른 워커 노드에 배치하는 멀티레벨 트리 구조로 배치할 수도 있다.
결과적으로 워커 노드가 작은 단위로 분할된 데이터를 처리하고 나면 그 결과를 마스터 노드에게 알려준다.

Reduce 단계 - 마스터 노드는 작은 단위의 문제로 쪼게진 Map의 결과를 결합(combine)하고 수집(collect)하여 우리가 원하는 어떤 output을 만들어낸다.

MapReduce의 특징은 M과 R의 각 단계에서 병렬 처리가 가능 한 것이며. 각 Map의 처리 과정은 다른 Map의 처리과정과 완전 독립적이고 이론적으로 모든 병렬을 실행 할 수 있다. (실제로는 데이터와 CPU의 수에 따라 제한됨)

Reuce단계에서는 Map 단계에의 처리 결과를 키로 정렬하고 Reduce 처리단으로 보내게 되는데 이역시 병렬처리 가능하다.

MR의 일련 과정은 순차실행 알고리즘들에 비해 종종 비효율적으로 생각될 수 있는데 MR은 일반 서버가 취급할수 있는 데이터 양을 훨씬 초월한 데이터를 취급할 수 있다.

많은 서버를 가지고 있으면 MR은 페타 바이트 큐모의 빅 데이터 정렬을 몇시간안에 처리할 수 있으며 프로세스 과정도 병렬이기 때문에 어떤 서버나 스톨리지의 일부에서 장애가 일어난다고 해도 해당 M과 R의 처리 노드만 다시 재할당하여 수행 될 수 있기 때문에 장애에 대해서도 지속적인 복구가 가능하다.
 

논리적 구성

Map Reduce 함수는  key와  value로 구조화된 데이터 페어에 대하여 수행 될 수 있다. (이하 k,v)

Map(k1, v1)  -> list(k2, v2)
Map 함수는 입력 데이터에 대하 완전 병렬적으로 작동되며 해당 결과로 (k2, v2)에 대한 리스트가 생상된다.
MR 프레임웍은 저런식으로 생성된 모든 리스트페어를 수집하여 같은 키에 대한 리스트들을 그룹핑한다.

하나의 그룹은 하나의 키로 가지고 그룹된 v들의 집합이다.

Reduce(k2, list(v2)) -> list(v3)
각 reduce 함수들은 1개의 결과나 결과가 없을수도 혹은 여러개의 결과를 뱉을 수도 있다.

결과적으로 MR 프레임웍은 k,v의 리스트를 다른 value의 리스트로 치환시키는 역할을 한다.
이것이 일반적인 함수형  언어의 맵, 리듀스와 다른점이다.


  예제

간단한 예제를 통하여 MR을 알아보자.
우리는 어떤 단어들이 나열된 문서 파일을 가지고 있다고 가정한다. 각 문서 파일끼린 서로 중복된 단어도 있을 수 있다고 가정한다. 
우리는 모든문서에서 무슨 단어들이 총 몇번 출현했나를 알아보는 것에 관심이 있다고 가정하자.

데이터  형식은 아래와 같다고 가정한다.
doc 1
------
감자
고양이
호랑이
고양이 

doc 2
------
사슴
호랑이
토끼
.....


등 등 

Map 함수와 Reduce 함수는 아래와 같이 작성되었다고 가정한다.
 

void map (String name, String document) :
   / / name : document name
   / / document : document contents
   for each word w in document :
     EmitIntermediate (w "1");
 
void reduce (String word, Iterator partialCounts)
   / / word : a word
   / / partialCounts : a list of aggregated partial counts
   int sum = 0;
   for each pc in partialCounts :
     sum + = ParseInt (pc);
   Emit (word, AsString (sum));

각 응용프로그램들은 아래와 같은 함수들을 정의하여 작동되게 된다.

인풋 리더(Input reader)
맵 함수(Map function)
파티션 함수(partition function)
비교 함수(compare function)
리듀스 함수9Reduce function)
아웃풋 라이터(output writer) 

위의 예제와 위의 함수들을 통하여 상황을 가정해본다.
 

인풋 리더(Input reader)  

인풋리더는 doc들을 적절하게 지정된 사이즈로 데이터를 분할한다. (일반적으로 16mb ~ 128mb) 분할된 데이터는 프레임웍에 의하여 각 Map 함수단으로 넘어가게 된다. input 리더는 key, value 페어의 데이터를 읽을 수 있으며
지금 상황에서는 key가 파일명, value가 내용이라고 가정한다.
예제의 각 doc의 용량은 input reader가 우연찮게 각 파일당으로 분리했다고 가정하자.

그럼 인풋리더는 doc 1에 대하여 map 함수 할당을 요청하게 되고 병렬적으로 doc 2 에 대하여 map 함수 할당을 요청하게 된다. (임으로 doc1이 할당된 맵을 m1, doc2가 할당된 맵을 m2라고 하자)


맵 함수(Map function)

각 맵함수는 key / value 페어 데이터들을 받아 지정된 함수로 처리하고 결과를 리턴한다.
m1~2들은 받은 데이터가 종료될때까지 map(String name, String document) 함수를 call 하게 된다.
그럼 doc1 의 경우 함수 정의에 의하여  (감자, 1), (고양이,2), (호랑이,1) 등을 각각 리턴하게 된다.
doc2 는 (사슴,1), (호랑이,1), (토끼,1)

위와같은 과정에서 key가 단어로 value가 해당 문서에서 단어 출현 횟수로 변경됐다는 사실에 주목한다.


파티션 함수(Parition function)

맵함수의 결과가 리듀스 함수로 정리되어 넘어가게 해주는 역할을 하는 함수이며 Sharding을 목적으로 한다. 파티션 함수는 주어진 key를 지정된 리듀스 개수 만큼 분배하게 된다.
우리는 리듀스 머신 개수를 2개로 가정했다고 하자. 그럼 지정된 방법으로 파티션함수는 key의 값을 분석하여 % 2 (리듀스 머신 개수) 각 reduce 함수에게 처리될 결과들을 전달한다. (일반적으로 key값을 해시하여 모드연산을 취한다)

해당 과정에서 ㄱ,ㅅ으로 시작하는 애들은 머신1에 ㅎ,ㅌ으로 시작하는 애들은 머신2에 분배되었다고 가정한다.


비교 함수(Comparison fuction)

해당과정에서는 지정된 방법에 따라 결과들을 정렬한다. 해당 과정을 세부분화하면, data의 reduce상에서의 순서, 그룹되는 단위 지정들을 할 수 있다. (일반적인 상황에선 신경을 덜 써도 무관할 것이라고 생각된다)
 

리듀스 함수(Reduce function)

맵함수의 결과는 각 키로 정렬되어 reduce 함수에서 수행되게 된다. 위에 말한 것처럼 해당 결과는 0개나 그이상의 결과로 출력될 수 있다.
ㄱ은 r1에 ㅅ은 r2에 ㅎ은r3에 ㅌ은 r4에서 처리 된다고 가정하자. 해당 과정은 머신 단위로 병렬이고 각 머신당 reduce 함수는 순차적으로 호출된다.

예제의 데이터로 따진다면
m1 에 (감자, (1)), (고양이, (2)), (사슴, (1))
m2 에 (토끼, (1)), (호랑이, (1, 1))
와 같이 배치 되고
 
reduce 함수의 결과로  (감자, 1), (고양이, 2), (사슴, 1), (토끼, 1), (호랑이, 2) 와 같은 데이터가 최종 생성되게 된다.


아웃풋 라이터(Output writer)

최종적으로 리듀스 함수의 결과를 아웃풋 라이터가 분산 파일 시스템에 저장하게 된다. 


상당히 길게 쓰여진 것같은데 다시 요약하면

map 과정은 주어진 데이터를 key로 분리하여 reduce 단으로 넘기고
key로 분리된 데이터를 정렬, 그룹화하여 reduce 단에선 해당 그룹에 대한 일관적인 처리를 하게 된다. 


참고
http://en.wikipedia.org/wiki/MapReduce