[옛 글] [BigData] MapReduce의 구현

최초 작성일 : 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(key) mod 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 수행의 입력파일로 사용되거나

다수의 파일들에 분할된 입력값을 다룰 수 있는 다른 분산 어플리케이션에 사용되기 때문이다.