Map Reduce

Map Reduce

1. Map Reduce

• 대용량 데이터 처리를 위한 분산 프로그래밍 모델
• 구글에서 2004년 발표한 소프트웨어 프레임워크
• 타고난 병행성(병렬 처리 지원)을 내포
• 누구든지 임의로 활용할 수 있는 충분한 서버를 이용하여 대규모 데이터 분석 가능
• 여러 노드에 task를 분배하는 방법
• 노드 프로세스 데이터는 가능한 경우, 해당 노드에 저장
• 흩어져 있는 데이터를 수직화하여, 그 데이터를 각각의 종류 별로 모으고, filtering과 sorting을 거쳐 데이터를 뽑아냄

 

 

1-1. Map Reduce task

- Map (흩어져 있는 데이터를 Key-value 형태로 연관성 있는 데이터 분류로 묶는 작업)
- Reduce (Map화한 작업 중 중복 데이터를 제거하고 원하는 데이터를 추출하는 작업)

 

| Map Reduce task는 Map과 Reduce 총 두단계로 구성

• 간단한 예시 : fork-join
  ```

1. 큰 작업에 대해 fork로 분할하고 또다시 fork로 분할
2. 작은 작업을 다시 join
3. Hadoop에서는 큰 데이터가 들어왔을 때, 64MB 단위 블럭으로 분할
4. 각각 블럭에 대한 연산 진행

구글에는 많은 텍스트 파일이 존재
- 텍스트 안에 단어가 몇 번 나왔는지 계산하는 작업 수행
즉,  텍스트 파일을 64MB 단위로 잘라내어 각 블럭에 대해 특정 단어가 몇 번 출현했는지 계산
그 후, Map 작업을 수행한 각각의 블럭의 결과 정보를 합치는 작업(Reduce)를 수행

 

1-2. Hadoop에서는 계산 시, 큰 파일을 블럭단위로 나눔

모든 블럭은 같은 Map 작업을 수행 -> Reduce 작업 수행

 

---

2. Hadoop Components

• MapReduce는 Hadoop 클러스터의 데이터를 처리하기 위한 시스템
• 총 2개(Map, Reduce)의 phase로 구성
• Map과 Reduce 사이에는 shuffle과 sort라는 스테이지 존재
• 각 Map task는 전체 데이터 셋에 대해서 별개의 부분에 대한 작업을 수행하게 되는데, 기본적으로 하나의 HDFS block을 대상으로 수행
  • HDFS(Hadoop Distributed File System) : 분산시스템

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

Distributed File System에서 수행되는 MapReduce 작업이 끝나면 HDFS에 파일이 써지고, MapReduce 작업이 시작할 때는 HDFS로부터 파일을 가져오는 작업이 수행

---

3. MapReduce Job

• Client 수행 작업 단위
• client가 수행하려는 작업 단위로 입력 데이터, MapReduce 프로그램, 설정 정보로 구성
• Hadoop은 Job을 Map Task와 Reduce Task로 작업으 나눠서 실행
• Job 실행 과정을 "제어"해주는 노드

 

---

4. Tracker

Job Tracker : Task tracker가 수행할 Task 스케줄링, 시스템 전체 수행을 조절

• Job : Full Program
• Map Reduce Job들은 JobTracker라는 소프트웨어 데몬에 의해 제어
  • JobTracker들은 마스터 노드에 존재하면

    client는 map reduce job을 JobTracker에 보냄
    JobTracker는 클러스터의 다른 노드들에게 map과 reduce Task를 할당
    이 노드들은 TaskTracker라는 소프트웨어 데몬에 의해 각각 실행
    TaskTracker는 실제로 map 또는 reduce task를 인스턴스화하고, 진행상황을 JobTracker에게 보고할 책임이 있음

Task Tracker : Task 수행하고, Job tracker에게 전체 경과 보고

• 데이터 집합을 통해 Mapper와 Reducer를 전체 실행
• Task는 데이터 조각을 통해 하나의 mapper 또는 reducer를 실행
• Task attempt는 Task를 실행하기 위한 특정 인스턴스를 의미
• 적어도 Task가 존재하기 때문에 많은 Task attempt가 있을 것
• 만약 Task attempt가 실패하면, JobTracker에 의해 다른 Task attempt가 시작될 것
• Speculative execution은 완료된 Task들 보다 더 많은 Task를 시도할 수 있음

 

---

5. Mapper

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

• 동시에 실행되는 여러 mapper는 각각 입력 데이터의 일부를 처리하는 단계를 포함

• Mapper는 Key-Value 상의 형태로 데이터를 읽음

• Mapper는 0개 또는 그 이상의 Key-Value 상의 형태로 데이터를 읽음

  map(in_key, in_value) -> (inter_key, inter_value) list

  

• 각각의 map, reduce를 어떤 PC에서 수행할지는 JobTracker에서 결정

• Mapper에서 중간 결과가 나오면 다시 그 중간 결과를 Shuffling

• Shuffling한 결과를 Reducer로 전달

  • Reducer : Mapper가 수집한 결과를 Shuffling하여 우리가 원하는 결과를 얻어내는 과정

• Map 함수의 input은 key, value가 필요

• output은 key, value의 list가 나옴

• Reduce도 input, output으로 key-value 쌍을 가짐

key값을 이용한 sorting, grouping 작업이 용이하기 때문에 key-value 쌍을 선호

즉, 빅데이터를 구성하는 기본 데이터 구조가 key-value 쌍이 된 것

Spark에서도 기본적인 자료구조형은 key-value 형태

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

    표준 패턴은 한 번에 파일의 라인을 읽음
    - Key는 라인이 시작되는 파일에 Byte Offset
    - Value는 라인 자체의 내용
    - 일반적으로 Key는 관련이 없는 것으로 간주

  • 만약 Mapper가 무언가를 출력하는 경우, 출력 형태는 key-value 형태여야 함

 

---

6. Reducer

• Map 단계가 끝나면, 중간 단계의 키 값을 기반으로 중간 값을 리스트 형태로 조합

• 그 뒤 리스트는 Reducer로 전달

    1. 하나의 Reducer나 여러개의 Reducer가 존재할 것 (job 설정에서 이 부분은 정의되어 있음)
    2. 중간 키와 연관되어 있는 모든 값은 같은 Reducer로 보내짐
    3. 중간 키와 그 값들의 리스트들은 키 순서대로 정렬(hash값이 같은 건 같은 Reducer)되어 Reducer로 보내짐
    이 단계가 Shuffle과 Sort라고 알려져있음

• Reducer의 output은 0이거나 key-value의 쌍이며, 이 결과들은 HDFS에 저장

• 실제로 Reducer는 보통 input키에 대해 하나의 key-value쌍으로 배출되어 쓰여짐

 

---

참조 블로그_1

참조 블로그_2