How Hadoop Works (Computation)

숭실대학교 컴퓨터학부 박영택 교수님의 <빅데이터 분산 컴퓨팅> 강의를 듣고 정리했다.

What is MapReduce? 

• 여러 노드에 태스크를 분배하는 방법
• 각 노드 프로세스 데이터는 해당 노드에 저장 (가능한 경우)
• 두 단계로 구성(Map, Reduce)

 

MapReduce는 fork-join이다. f라는 task를 할 때 일을 나누고(fork), 다시 합치는(join) 방식이다.

예를 들어 Alphago와 이세돌에 관한 글에서 알파고라는 단어와 이세돌이라는 단어가 각각 몇 번 쓰였는지 확인하는 작업을 하겠다. 

긴 text를 64MB의 block으로 자르고, 각각의 block마다 Alphago가 몇 번, 이세돌이 몇 번 나왔는지 확인한다. 이후 block을 합치며 alphago의 언급 횟수를 합치고, 이세돌의 언급 횟수도 똑같이 합쳐준다. 이렇게 자르고 합치는 과정이 바로 MapReduce 이다.

 

MapReduce는 Hadoop 클러스터의 데이터를 처리하기 위한 시스템이다.

2개의 phase로 구성이 되어 있다. :Map, Reduce (Map 과 Reduce 사이에는 shuffle 과 sort라는 스테이지가 있다.)

각 Map task는 전체 데이터 셋에 대해서 별개의 부분에 대한 작업을 수행한다.

   -기본적으로 하나의 HDFS block을 대상으로 수행

   -모든 Map task가 종료되면, MapReduce 시스템은 intermediate 데이터를 Reduce phase를 수행할 노드로 분산하여      전송한다.

Distributed File System 이다.

 

 

 

MapReduce-jobtracker

MapReduce job들은 jobtracker에 의해 제어된다.

jobtracker는 master node에 있다.

   클라이언트가 MapReduce job을 jobtracker에게 보낸다.

    jobtracker는 클러스터의 다른 노드들에게 Map과 Reduce task를 할당한다.

   이 노드들은 tasktracker에 의해 각각 실행된다.

   tasktracker는 실제로 Map 또는 Reduce task를 인스턴스화하고, 진행 상황을 jobtracker에게 보고해야한다.

 

 

한 노드에서 Map이 먼저 끝났다고 그 노드 먼저 Reduce를 실행하는 것이 아니다. 모든 노드의 Map이 끝나고 HDFS에 write한 다음 다같이 Reduce하는 것이다.

 

 

job은 full program이다.(전체 프로그램) 데이터 집합을 통해 Mapper와 Reducer를 전체 실행한다.

task는 데이터 조각을 통해 하나의 Mapper 또는 Reducer를 실행한다.

task attempt 는 task를 실행하기 위한 특정 인스턴스이다.(유동적임. 100개 쓰면 100개만 쓰고 50개면 50개)

   적어도 task가 있기 때문에 많은 task attempt가 있을 것이다.

   만약 task attempt가 실패하면, jobtracker에 의해서 다른 task attempt가 시작될 것이다.

   speculatice execution은 또한 완료된 task들 보다 더 많은 task를 시도할 수 있다.

 

 

 

 

MapReduce : Mapper

hadoop은 네트워크 트래픽을 방지하기 위해, 메타 데이터의 일부분을 가지고 노드에서 처리한다.

   -동시에 실행되는 여러 Mapper는 각각 입력 데이터의 일부를 처리하는 단계를 포함한다.

Mapper는 Key/Value 쌍의 형태로 데이터를 읽는다.

Mapper의 0개 또는 그 이상의 Key/Value 쌍을 출력한다. (pseudo-code):

map(in_key, in_value)->

                                    (inter_key, inter_value)list

 

 

Text 파일을 예로 들겠다. Input 값으로 Key는 몇 번째 줄인지, Value는 Key 값에 해당하는 줄에 어떤 데이터가 있는지를 넣는다. 그러면 Output 값으로 Key 값은 Ln 에 어떤 단어가 있는지가 담겨 있고, Value값으로는 그 특정 단어가 몇 번이나 포함되어 있는지가 담겨있다.

 

 

위 사진에서 map을 할 때 컴퓨터 두 대를 이용하고 있다. map이 끝난 데이터(중간결과)는 shuffling(묶어서 적당한 reducer로 보냄)을 해서 다시 HDFS로 들어가고, 이후에 HDFS에서 꺼내 다시 reduce한다.

Mapper, Reducer 의 input은 항상 key, value pair 다. output은 key,value pair의 리스트 이다.

이렇게 해야 sorting, grouping 등이 쉽기 때문에.

 

Mapper는 입력값의 Key를 사용하기도 하지만, 완전히 무시하기도 한다.

    -예를 들어, 표준 패턴은 한 번에 파일의 라인을 읽는다.

    -Key는 라인이 시작되는 파일에  Byte offset이다.

    -Value는 라인 자체의 내용이다.

    -일반적으로 Key는 관련이 없는 것으로 간주한다.

만약 Mapper가 무엇을 출력하는 경우, 출력 형태는 Key/Value 쌍 이어야 한다.

 

 

Mapper의 예제 몇 가지를 보자.

대문자로 바꾸는 예제

철자를 분리하여 출력하는 예제

 

소수인 경우에 출력하는 예제

 

단어의 길이를 출력하는 예제

 

 

 

 

MapReduce : Reducer

 

Mapper와 Reducer 는 모두 메모리에서 일어나기 때문에 시간이 별로 걸리지 않는데, 그 사이에 shuffling이 오래 걸린다. 

 

지금까지 한 것을 정리해보자면, 

<Key, Value> -> map -> [<Key,Value>] -> shuffle -> [<Key,Value>] -> reduce -> <Key,Value>

라고 할 수 있다.

HDFS에 File1을 넣어서 위 과정을 거치면 File2가 생성되어 다시 HDFS로 들어가게 된다.

 

 

 

Reducer

map단계가 끝나면, 중간 단계의 키 값을 기반으로 중간 값(intermediate values)을 리스트 형태로 조합

리스트를 reducer로 전달

   - 하나의 reducer나 여러 개의 reducer가 존재할 것이다.(이 부분은 job 설정에 정의돼 있다.)

   - 중간 키와 연관되어 있는 모든 값은 같은 reducer로 보내진다.

   - 중간 키와 그 값들의 리스트들은 키 순서대로 정렬되어 reducer로 보내진다.

   - 이 단계는 '셔플(shuffle)과 정렬(sort)' 이라고 알려져 있다.

reducer의 output 은 0이거나 key/value의 쌍이다. 

   - 이 결과들은 HDFS에 저장된다.

   - 실제로 reducer는 보통 input 키에 대해서 하나의 key/value 쌍으로 배출되어 쓰여진다.

 

 

 

 

Reducer의 예제를 몇 가지 알아보자.