최초 작성일 : 2013/05/30 15:24 


맵 리듀스 개요

맵 : 
- 원시 데이터를 key-value 쌍의 중간 파일로 만든다.
- 입력데이터가 있는 노드에서 맵 함수가 수행되는 것이 가장 좋다 (지역성 최적화)
- 맵 함수에 전달되는 입력 데이터는 라인 offset을 키로, 해당 라인 내용을 value로 하는 형태로 구성된다.
- 맵 함수는 이 입력값들로부터 필요로 하는 key와 value를 추출한다.
- 이 과정에서 잘못된 레코드를 제거하는 기능도 수행한다.
- 맵 task의 실행 결과는 HDFS가 아닌 로컬 디스크에 저장된다. (HDFS와 로컬 디스크의 개념을 명확히 구분하자)
  이유는 맵의 결과물은 단지 리듀스 함수로 전달하기 위한 중간 결과물일 뿐이며 모든 잡이 완료되면
  버려도 되는 데이터이기 때문이다.

리듀스 : 
- 각 맵 task들의 결과물들을 입력으로 받아 최종 결과물을 생성한다.
- 각 노드에 있는 맵 task의 결과물들을 입력으로 받으므로 지역성 최적화의 영향이 없다.
- 리듀스의 결과물은 안정성을 위하여 HDFS에 저장된다.


셔플 : 
- 맵 task의 결과물을 리듀스 task로 보내기 전의 중간 가공 단계
- key에 대한 정렬이나 그룹화 및 파티셔닝 작업이 이루어진다.
- 정렬은 말 그대로 정렬이며 그룹화는 같은 key로 묶는 것, 그리고 파티셔닝은 리듀스 task가 2개 이상인 경우
  결과물을 각각의 리듀스 task에 분배하기 위해 특정 기준으로 쪼개는 작업이다.
- 때때로 셔플 작업이 없을 수도 있으며 이런 경우에는 리듀스 task도 없는 맵 task만으로 이루어진
  job이 수행된다. 또한 이 상태에서는 맵 task의 결과가 HDFS에 저장된다.

컴바이너 : 
- 맵 task의 결과물을 네트워크를 통해 리듀스 task로 이동시키는 과정을 최적화하기 위한 방법 중 하나
- 같은 key를 가진 value들을 리스트로 묶어 새로운 key-value쌍을 만든다.
  즉 {key1, value1}, {key1, value2}를 {key1, list(value1, value2)}의 형태로 만드는 것이다.
- 주로 연합 연산(합계, 카운팅, 최대값 등)에 사용된다.
- 컴바이너를 사용하게 되면 맵 task 결과물의 사이즈를 줄일 수 있다. 즉 네트워크의 트래픽량을 줄일 수
  있게 되는 것이다.

블로그 이미지

마즈다

이미 마흔을 넘어섰지만 아직도 꿈을 좇고 있습니다. 그래서 그 꿈에 다가가기 위한 단편들을 하나 둘 씩 모아가고 있지요. 이 곳에 그 단편들이 모일 겁니다...^^

최초 작성일 : 2013/02/14 14:49 


==================================================================

내용이 어려워짐에 따라 번역은 점점 발번역으로 치닫고 있습니다...ㅠ.ㅠ

첫 글에 링크해드린 원문 문서를 참조해서 보세요...

==================================================================


Master Data Structure


master 프로그램은 몇가지 데이터 구조를 유지한다. 각각의 map task와 reduce task에 대해

master는 그 상태(비가동, 프로세스 진행 중 또는 완료)와 그 작업자 머신의 식별자를  저장한다.

(유휴 작업이 없도록 하기 위해)


master는 map task로부터 reduce task로 중간 파일 영역의 저장 위치를 전달해주는 전달자이다.

그러므로 각각의 완료된 map task에 대해 master는 map task가 생산해낸 R개의 중간 파일 영역의

위치와 크기를 저장한다. 이러한 위치와 크기 정보는 map task가 완료될 때마다 업데이트된다.

이 정보는 프로세스가 진행 중인 reduce task를 가진 작업자에게 점차 부하를 주게 된다



Fault Tolerance (고장 허용 범위)


MapReduce 라이브러리가 수백, 수천대의 머신에서 매우 커다란 양의 데이터를 처리하기 위해 디자인된

이후 머신의 고장에 대해 훌륭하게 대처해왔다.


Worker Failure

master는 주기적으로 모든 작업자들에게 ping을 날린다.

일정 시간 동안 작업자로부터 응답이 없는 경우 master는 이 작업자가 고장이라고 판단한다.

작업자에 의해 완료된 map task들은 다시 초기 유휴상태로 재설정되며 다른 작업자에게

스케쥴링 될 수 있는 상태가 된다. 이와 유사하게 고장이 발생한 작업자상에 있는 프로세스 진행 중인

map task 또는 reduce task들은 역시 유휴 상태로 재설정되어 스케쥴링 가능한 상태가 된다.


완료된 map task들은 고장난 머신상에 출력 파일을 저장하고 고장난 머신 상의 파일은

접근을 할 수 없기 때문에 재실행 되도록 한다. 하지만 완료된 reduce task는 파일을 전역적인

파일 시스템에 저장하기 때문제 재실행 할 필요가 없다.


map task가 A 작업자에게서 실행되다가 A가 고장이 나서 다시 B 작업자에게 실행되는 경우

reduce task를 수행 중인 모든 작업자들은 재실행에 대한 통지를 받는다.

이 중 아직 A 작업자로부터 데이터를 읽지 않은 reduce task들은 B 작업자로부터 데이터를 읽게 된다.


MapReduce는 대규모 작업자들의 고장에 탄력적이다.

일례로 어떤 MapReduce 작업은 수행되는 동안 실행중인 클러스터상의 네트워크 유지보수 작업이 원인이 되어

80대로 구성된 그룹들이 동시에 몇 분 동안 unreachable 상태가된 상황이 발생한 적이 있는데, 이 MapReduce의

master는 간단하게 unreachable 상태인 작업자들에 의해 수행되던 작업들을 완료하고 작업을 계속 수행해서

결국 MapReduce 작업을 완료하였다.


Master Failure

master가 위에 기술한 것과같이 주기적으로 master 데이터 구조의 체크포인트를 작성하도록 하는 것은 쉽다.

만일 master가 죽는다면 마지막에 확인된 상태로부터 새로운 복사이 시작 될 수 있다. 그러나 단지 하나의

master만 작동하는 상태에서 이 master의 고장은 예상 밖의 문제를 가져온다.

그러므로 현재 우리가 구현한 방식에서는 만일 master가 고장이 나면 MapReduce 연산을 취소시킨다.

사용자들은 이 상태를 감지할 수 있고 언제든지 그들이 원하는 때에 MapReduce 업무를 다시 시작할 수 있다.


Semantics in the Presence of Failures

사용자가 제공한 map과 reduce 작업 프로그램이 입력값에 대한 동일한 출력을 보장 할 때(*deterministic)

우리의 분산 구현 역시 전체 프로그램의 오류 없는 순차적인 실행을 통해 같은 결과물을 생산해 낼 수 있다.


우리는 이런 속성을 만족시키기 위해 map과 reduce task 출력의 개별적인 수행에 의존해야 한다.

각각의 실행 중인 task는 그 결과물을 자신만의 임시 파일에 쓴다.

하나의 reduce task는 이런 파일을 하나만 생성하고 map task는 이런 파일을  (하나의 reduce task에 대해)R개

생성한다.

map task가 완료되었을 때 작업자는 R개의 임시 파일의 이름들을 포함한 메시지를 master에게 보내게 된다.

master가 이미 업무가 종료된 map task로부터 종료 메시지를 받게되면 master는 그 메시지를 무시한다.

만약 그렇지 않으면 master는 master 데이터 구조에 R개의 파일의 이름들을 기록하게 된다.


reduce task가 완료되었을 때 reduce 작업자는 임시파일을 개별적으로 이름을 붙여 최종 출력 파일로 만든다.

만일 동일한 reduce task가 여러대의 머신에서 수행되고 있는 경우 동일한 최종 출력 파일을 위해

이름 변경 작업이 여러 곳에서 실행되는데 기본적인 파일 시스템이 하나의 reduce task로부터 생성된 데이터만을

최종 파일 시스템 상태에 저장하도록 보장해준다.


map과 reduce 작업 프로그램의 대다수는 동일 입력에 대해 동일 출력을 보장하며(deterministic)

순차적인 실행과도 동일한 이러한 의미는 프로그래머들이 자신들이 개발한 프로그램의 행위를 예측하는 것을

매우 쉽게 해준다.


map과(또는) reduce 업무가 입력에 대한 출력을 보장하지 못하는 경우에라도(**non-deterministics)

우리의 시스템은 보다 약하지만 여전히 합리적인 의미체계를 제공해 줄 수 있다.

비결정적인 업무의 존재하에서 특정 reduce R1에 대한 출력은 비결정적 프로그램의 순차적인 실행을 통해

생산된 출력 R1과 동일하다. 그러나 다른 reduce task  R2 을 위한 출력은 또 다른 비결정적인 프로그램의

순차적인  실행에 의해 생산된  R2 를 위한 출력과 부합할 것이다.


map task M과 reduce task R그리고  R2 를 생각해보자.
e(Ri)이 commit된  Ri 을 실행하도록 하면.(정확히 한 번만 실행을 한다)  e(R1)은 M의 실행 중 하나로부터
생성된 출력을 읽게될 것이고 e(R2)는 M의 다른 실행으로부터 생성된 출력을 읽게 되는 약한 의미체계가
발생하게 된다.

==========================================================

*deterministic algorithm

예측한 그대로 동작하는 알고리즘이다. 어떤 특정한 입력이 들어오면 언제나 똑같은 과정을 거쳐서 언제나 똑같은 결과를 내놓는다. 결정론적 알고리즘은 실제 기계에서 돌릴 수 있는 효율적인 알고리즘일 뿐 아니라, 가장 오랫동안 연구되었으며 가장 친숙한 알고리즘이다.

**non-deterministic algorithm

결과가 한 가지로 정의되지 않고 명시된 집합에 속한 하나의 값이 선택되는 연산을 포함하는 알고리즘.

블로그 이미지

마즈다

이미 마흔을 넘어섰지만 아직도 꿈을 좇고 있습니다. 그래서 그 꿈에 다가가기 위한 단편들을 하나 둘 씩 모아가고 있지요. 이 곳에 그 단편들이 모일 겁니다...^^

최초 작성일 : 2013/02/05 15:23 


==============================================
오늘은 MapReduce라이브러리와 이 라이브러리를 사용하는, 개발자가 작성한
Map / Reduce 함수의 전체적인 프로세스를 설명하는 부분이며 삽입된 그림을
기반으로 일련의 작업 순서를 설명하고 있습니다.

입력 데이터

사용자 프로그램 - master - map worker - reduce worker - 중간데이터

출력데이터

요러한 요소들의 관계를 집어가면서 보시면 될겁니다.

글이 긴 만큼 번역이 개판인데...그냥 그림 참조하셔서 보세요...^^;;;
==============================================

MapReduce 인터페이스는 다양한 형태로 구현할 수 있는데 어떤 구현을 사용할 것인가 하는 것은
운영 환경에 따라 달라진다.

예를 들면 적은 용량의 공유메모리를 가진 머신이나 큰 NUMA(메모리와 CPU가 한 셋을 이루는 프로세서)
다중 프로세서를 가진 머신, 혹은 대량의 네트워크 머신들의 집합 등과 같이 각각의 환경에 따라
다른 구현이 쓰이는 것이다.

이번 글에서는 구글에서 널리 쓰이는 switch 이더넷으로 연결된 상용 PC들의 커다란 클러스터 
환경 하에서의 구현에 초점을 두고 살펴보도록 하겠다.

일단 환경은 이렇다 :

1. 일반적으로 각각의 머신은 듀얼코어의 X86 프로세서에 2~4Gb의 시스템 메모리를 가지고 있으며 운영체제는 리눅스이다.

2. 네트워크 장비는 일반적으로 각 머신 수준에서 100Mb 랜이나 기가비트 랜을 사용하나
평균적인 속도는 전체 양 끝단의 대역폭에 비해 상당히 느리다.

3. 하나의 클러스터는 수 백 대에서 수 천 대로 구성되므로 머신의 오작동은 일반적인 일이다.

4. 저장 공간은 각각이 머신에 직접 장착된 저가의 IDE 하드 디스크이다. 구글에서 개발된
분산 파일 시스템은 이 디스크들에 저장된 데이터를 관리하게 된다. 이 분산 파일 시스템은
신뢰할 수 없는 머신 상에서 효용성과 신뢰성을 제공하기 위해 데이터의 '복제'를 이용한다.

5. 사용자들은 스케쥴링 시스템에 job을 제출한다. 각각의 job은 일련의 task로 구성되고
스케쥴러에 의해 클러스터 내의 사용 가능한 일련의 머신들에 매핑된다.


MapReduce의 실행 개요

Map 호출코드는 입력 데이터들을 M개로 나누어진 세트로 분할하면서 자동으로 다수의 머신들에 분산된다.
이렇게 입력된 분할체들은 가각의 서로 다른 머신에서 병렬로 처리될 수 있다.
Reduce 호출코드는 분할 함수(예를 들면 hash(keymod R)를 통해 중간형태의 key 영역을
R개의 조각에 분할하여 넣음으로써 역시 다수의 머신에 분산된다.





위 그림은 구글에서 구현한 MapReduce 운용에 대한 흐름을 보여준다.
사용자의 프로그램이 MapReduce 함수를 호출하면 아래와 같은 일련의 action이 발생한다.


1. 사용자 프로그램에 포함된 MapReduce 라이브러리가 우선 입력 파일을 분할하여

 M 조각들로 집어넣는다 조각들은  16~64Mb 정도의 크기를 가지며  크기는

사용자들이 옵션 인자를 통해 조절 가능하다그리고나서  프로그램의 복사본들이

클러스터 내의 머신들로 복사되기 시작한다.


2.  복사본들  하나는 master라고 하여 특별한 기능을 수행한다.

나머지의 것들은 master 의해 할당된 작업을 수행하는 작업자들이다.

M개의 map task R개의 reduce task 할당 되었다고 해보자. master 쉬고있는

작업자들을 찾아내  map task reduce task  하나를 할당한다.


3. map task 할당된 작업자는 입력 분할체에 해당하는 contents 읽는다.

 작업자는 읽어들인 contents로부터 key/value 쌍을 뽑아내고 각각의 쌍들을 사용자가

작성한 Map 함수로 전달한다이렇게 Map 함수로부터 생성된 중간형태의 key/value쌍은

메모리 버퍼에 저장된다.


4. 주기적으로 버퍼에 저장된 쌍들은 로컬 디스크에 저장되며 분할 함수에 의해 R개의

영역으로 분할된다버퍼에 저장된 쌍들이 로컬 디스크에 저장된 위치는 다시 master에게

전달되며 master 책임지고 전달받은  위치를 reduce 업무를 할당받은 작업자에게 할당해준다.


5. reduce 작업자가 master로부터  위치에 대해 알림을 받으면  작업자는

원격 프로시져 콜을 이용해 map 작업자의 로컬 디스크로부터 저장된 버퍼 데이터를 읽어들인다.

reduce 작업자가 모든 중간데이터를 읽어들이고난  reduce 작업자는 중간데이터의

key 중심으로 데이터를 정렬하게 되고 존재하는 모든 동일키는 그룹으로 묶인다.

보통 많은 서로 다른 맵의 키들이 같은 reduce task 전달되기 때문에 정렬이 필요하다.

만일 데이터가 너무 커서 메모리가 부족할 경우에는 외부(외부 저장장치를 사용한정렬이

사용되기도 한다.


6. reduce 작업자는 모든 정렬된 중간 데이터에 걸쳐서 유일한 중간 키가 도출될 때까지

 작업을 반복하며 이렇게 도출된 키와 키에 해당하는 중간 값들의 세트를 사용자가

작성한 Reduce 함수로 전달한다. Reduce 함수의 출력값은 최종 출력 파일에 추가된다.


7. 모든 map task reduce task 완료되면 master 사용자 프로그램을 호출하게 되고

 시점에서 MapReduce 호출은 사용자의 코드를 반환하게 된다.




이 일련이 과정들이 성공적으로 완료된 후 mapreduce 실행의 결과는 R개의 출력 파일 내에서

볼 수 있을 것이다.(한 개의 reduce task당 R개의 파일이 생성되면 파일명은 사용자가 정의한다)



이렇게 출력된 R개의 출력 파일을 하나로 묶을 필요는 없다.
보통은 이 파일들을 또다른 MapReduce 수행의 입력파일로 사용되거나
다수의 파일들에 분할된 입력값을 다룰 수 있는 다른 분산 어플리케이션에 사용되기 때문이다.

블로그 이미지

마즈다

이미 마흔을 넘어섰지만 아직도 꿈을 좇고 있습니다. 그래서 그 꿈에 다가가기 위한 단편들을 하나 둘 씩 모아가고 있지요. 이 곳에 그 단편들이 모일 겁니다...^^

최초 작성일 : 2013/02/04 13:16 


=======================================================

나름 영문 문서를 해설 식으로 적어보고자 했으나...

가면 갈수록 그냥 문서의 직역이 되고 있네요...ㅠ.ㅠ

양해부탁드립니다.

=======================================================


지난 시간에 살펴본 바와 같이 간단하게 말하면 Map은 논리적 레코드를 key-value형태의 중간 데이터로 만드는 작업을 수행하고

reduce는 key-value를 가공하여 공통된 key를 가진 value들의 집합을 출력하는 작업을 수행한다.


요기에 대해 조금만(많이 하면 골치아픕니다…) 깊게 들어가보도록 하자.


아래와 같은 간단한 샘플코드가 있다.


map(String key, String value): // key: document name
// value: document contents for each word w in value:

      EmitIntermediate(w, "1");

reduce(String key, Iterator values): // key: a word
// values: a list of counts
int result = 0;

    for each v in values:

      result += ParseInt(v);

    Emit(AsString(result));


map함수는 각 단어와 그 단어가 나타나는 횟수를 리턴한다.(여기서는 그 횟수를 간단히 '1'로 하였다.)

reduce 함수는 특정 단어에 대해 리턴된 모든 횟수를 합산한다.


추가로, 개발자들은  input / output 파일 이름을 가진 mapreduce의 사양에 맞도록 객체에 코딩을 하게 되고

이러한 객체를 선택적 인자로 넘겨 줄 수 있다.

이후 개발자는 이 객체를 전달함으로써 MapReduce함수를 호출하게 되는 것이다.

이러한 사용자들의 코드는 MapReduce 라이브러리틀 통해 연결된다.


map과 reduce의 개념적인 input / output 타입은 다음과 같다


map (k1,v1)  list(k2,v2) 
reduce (k2,list(v2))  list(v2)

이런 단어 세기 외에 다음과 같은 예들이 있다.


Distributed Grep : map 함수에서 특정 패턴과 매칭되는 라인들을 리턴한다. reduce 함수는 중간 데이터를

복사해서 출력하는 것과 유사한 함수로 기능한다.


Count of URL Access Frequency : map 함수는 웹 페이지 요청 로그를 분석하여 <URL, 1>의 결과를 도출하고

reduce는 같은 URL에 대한 value들을 합산하여 <URL, total count>쌍의 결과를 출력한다.


Reverse Web-Link Graph : map 함수는 'source'라는 이름의 페이지 내에서 'target'으로 링크되는 URL을 분석하여

<target, source>라는 쌍을 리턴하고 reduce 함수에서는 target URL과 관련된 모든 source URL들을 모아

<target, list(source)> 쌍을 만들어낸다.


Term-Vector per Host : term vector는 특정 문서 혹은 문서들의 목록 속에서 가장 중요한 단어들을

<word, frequence> 쌍으로 요약하는 것이다.

map 함수는 입력된 문서로부터 <hostname, term vector>쌍을 리턴한다.(hostname은 문서의 URL로부터

추출한 것이다.) reduce 함수는 주어진 host로부터 모든 문서당 term vector를 전달받아 이 term vector들을

함께 모은 후 빈도수가 낮은 용어들을 제거한 후에 최종적으로 <hostname, term vector>의 쌍을 리턴한다.


Inverted Index : map 함수는 각각의 문서들을 분석하여 일련의 <word, document ID>쌍을 리턴한다.

reduce 함수는 주어진 단어에 대해 모든 쌍을 전달받아 그 단어에 상응하는 document ID들을 정렬한 후

<word, list(document ID)>쌍으로 리턴한다. 모든 출력 쌍들의 집합은 간단한 역색인(Inverted index)을 구성하며

단어의 위치 추적을 강화하기가 쉬워진다.


Distributed sort : map 함수는 각각의 레코드로부터 key를 추출하고 <key, record>쌍을 출력한다.

reduce 함수는 변경되지 않은 모든 쌍들을 출력한다. 이 연산은 분할된 설비들에 의존적이다.

블로그 이미지

마즈다

이미 마흔을 넘어섰지만 아직도 꿈을 좇고 있습니다. 그래서 그 꿈에 다가가기 위한 단편들을 하나 둘 씩 모아가고 있지요. 이 곳에 그 단편들이 모일 겁니다...^^

최초 작성일 : 2013/02/01 17:15


==============================================

워낙에 영어 알레르기가 있는 놈이 영문 문서 보면서 발번역 하느라 토쏠립니다...ㅠ.ㅠ
이점 감안하고 보시기 바랍니다...
==============================================
우선 앞선 글(http://www.prapps.net/587)에서 위키백과에서 정의한 내용을 간단하게
적어보았다. 다음과 같은 내용이다.
구글에서 분산 컴퓨팅을 지원하기 위한 목적으로 제작하여 2004년 발표한 소프트웨어 프레임워크다. 이 프레임워크는 페타바이트 이상의 대용량 데이터를 신뢰할 수 없는 컴퓨터로 구성된 클러스터 환경에서 병렬 처리를 지원하기 위해서 개발되었다. 이 프레임워크는 함수형 프로그래밍에서 일반적으로 사용되는 Map과 Reduce라는 함수 기반으로 주로 구성된다.

현재 MapReduce는 Java와 C++, 그리고 기타 언어에서 적용이 가능하도록 작성되었다.


오늘은 여기서 약간만 더 내용을 심화 시켜 보도록 하겠다.
오늘의 글은 다음 링크에 링크된 문서에서 발췌, 번역 한 것이다.

http://research.google.com/archive/mapreduce-osdi04-slides/index.html

우선 소개 글에서 맵리듀스가 생겨나게된 배경을 설명하고 있다.
쉽게 말해

' 5년간 구글 인간들이 엄청난 양의 미가공 데이터를 파생테이터로
만들기 위해 특별한 목적의 많은 프로그램을 구현하였는데 사실 이 작업 자체는
매우 쉬운 작업이지만 이 작업을 적절한 시간에 끝내기 위해서는 분산된 많은
서버들 상에서 이루어져야 했고 이 것은 엄청 골치 아픈 일이었다.

그래서 잡다하고 복잡한 기능들(병렬화, 내고장성, 데이터 분산처리, 로드 밸런싱 등)은
라이브러리에 다 숨기고 간단하 연산만을 수행하도록 개념을 잡았다.

이러한 개념은 Lisp 및 다른 언어에서의 기본형 데이터에 대한 표현인 Map과 Reduce에서
그 영감을 얻었다.

그래서 입력값인 각각의 논리적인 레코드들을 중간형태의 key/value 형태로 만들기 위해
map을 적용 시켰고. 다시 여기에서 같은 key들을 공유하는 value들을 적절한 파생 데이터로
조합하기 위해 reduce를 적용 시켰다.

그렇다!
도대체 map이 뭐고 reduce가 뭔지 무지 궁금했는데...
바로 이거였던 것이다.

Map : 논리적 레코드를 key/value형태의 중간 데이터로 만드는 작업
Reduce : key/value 형태의 중간 데이터를 key를 중심으로 재분류하여 분석하는 작업

간단히 말하면 이런 것이다.

그리고 이렇게 만들어진 맵리듀스는

대량의 연산을 자동으로 병렬처리 및 분산처리가 가능하게 해주고, 또 그 인터페이스들의 구현들을 조합하는 경우 대량의 상업용PC(비교적 저가의 PC) 클러스터에서
고성능을 발휘할 수 있는 간단하고도 강력한 인터페이스를 만들어 낸 데에 그 의의가 있다.

이상 MapReduce에 대한 간단한 개념을 알아 보았고.

다음 시간에는 조금 더 기술적인 내용을 확인해보도록 하겠다.

블로그 이미지

마즈다

이미 마흔을 넘어섰지만 아직도 꿈을 좇고 있습니다. 그래서 그 꿈에 다가가기 위한 단편들을 하나 둘 씩 모아가고 있지요. 이 곳에 그 단편들이 모일 겁니다...^^