Introduction to Big Data, Summer, 2013

Presentation on theme: "Introduction to Big Data, Summer, 2013"— Presentation transcript:

1 Introduction to Big Data, Summer, 2013
Map/Reduce Mincheol Shin

2 Index 맵리듀스 기본 하둡 맵리듀스 맵리듀스 예제: Word Count 하둡 맵리듀스 구성 요소 맵퍼 (Mapper)
리듀서 (Reducer)

3 1.1 맵리듀스 개념 맵리듀스 (Google에서 제안) 맵 리듀스
큰 데이터를 나누어서 여러 개의 Machine에서 처리하는 프로그래밍 모델 맵 입력 데이터를 key-value pair로 변경 “key1 – value1”, “key2 – value2”, “key1 – value3” “key3 – value4” 동일한 key를 갖는 key-value pair를 모아 key/value-list로 저장 key1 – value1. value3. … key2 – value2. value5, … key3 – valuen+1. valuen+2, … , valuen+m 리듀스 사용자가 작성한 Reduce 함수에 따라 KV List를 가공

4 1.1 맵리듀스 개념 Worker Worker Mapper Reducer Mapper Worker Reducer Mapper
Key1, value 1, … , value n1 Key2, value 1, … , value n2 Reducer Mapper Key1, value 1, … , value n3 Key2, value 1, … , value n4 Worker Reducer Mapper Key1, value 1, … , value n5 Key2, value 1, … , value n6 Mapper Key1, value 1, … , value n7 Key2, value 1, … , value n8 Hadoop Distributed File System File G File O

5 1.2 Word Count Example Word Count Map Function Reduce Function
문서에서 각 단어가 몇 번 나타나는지를 계산하는 프로그램 Map Function Input K: 문서의 이름, V: 문서의 내용 Output K: word (중복제거 X), V: list of 1 Process 문서를 단어 단위로 읽으며 읽은 단어를 key로, value는 1로 설정 Reduce Function K: word, V: list of “1” K: word, V: word가 나타난 개수 각 key 의 value를 모두 더함

6 1.2 Word Count Example: Map
Key/Value List Intermediate key/set of values Document Map, written by the user, takes an input pair. The reduce, written by the user, takes an intermediate key and a set of values for that key. Map 1 user 1 Map 1 intermediate 1 written 1 takes 1 written 1 1 key 1 1 by 1 an 1 by 1 1 and 1 the 1 the 1 1 1 intermediate a 1 user 1 1 user 1 1 set 1 takes 1 key 1 takes 1 1 of 1 an 1 and 1 an 1 1 values 1 input 1 a 1 input 1 for 1 pair 1 set 1 pair 1 1 the 1 of 1 that reduce 1 reduce 1 values 1 Machine 1 written 1 for 1 Machine 2 by 1 that 1 the 1 key 1

7 1.2 Word Count Example: Reduce
Intermediate key/set of values Reducer Map 1 a 1 Map 1 intermediate 1 written 2 set 1 written 1 1 key 1 1 by 2 of 1 by 1 1 and 1 the 3 values 1 the 1 1 1 a 1 user 2 for 1 user 1 1 set 1 takes 2 that 1 takes 1 1 of 1 an 2 an 1 1 values 1 input 1 input 1 for 1 pair 1 pair 1 that 1 reduce 1 reduce 1 intermediate 1 key 2 and 1

8 2. 하둡 맵리듀스 맵리듀스 기본 하둡 맵리듀스 맵리듀스 예제: Word Count 하둡 맵리듀스 구성 요소
맵퍼 (Mapper) 리듀서 (Reducer)

9 2.1 하둡 맵리듀스의 구성요소 태스크 (Task) 맵퍼 (Mapper) 리듀서 (Reducer)
맵퍼나 리듀서가 수행하는 단위 작업 (맵 태스크, 리듀스 태스크) 맵 혹은 리듀스를 수행하기 위한 정보를 가지고 있음 맵퍼 (Mapper) 3 단계: 맵 (Map), 컴바인 (Combine), 파티션 (Partition) 리듀서 (Reducer) 셔플/정렬 (Shuffle/Sort), 리듀스(Reduce)

10 2.1 하둡 맵리듀스의 구성요소 잡 트래커 (Job Tracker) 태스크 트래커(Task Tracker)
마스터(Master)라고도 불림 클러스터에 1개 역할 각 슬레이브(slave)에 태스크(Task)를 할당 슬레이브 모니터링 실패한 태스크의 재실행 태스크 트래커(Task Tracker) 각 노드에 1개씩 존재 노드의 태스크를 실행

11 2.1 하둡 맵리듀스의 구성요소: Data Flow
Reduce Task Reducer Reduce Task Mapper Output File {k1, v1, … vn} Shuffle Partition Sort Combine Mapper Reduce Map Partition Reduce Task Reduce Task Reducer Combine Output File {k1, v1, … vn} Shuffle Map Sort Map Task Map Task FileSplit FileSplit Reduce Hadoop Distributed File System File G File O

12 2.2 매핑 프로세스 입력 파일 맵(Map) 컴바인(Combine) 파티션(Partition)
HDFS에 있는 입력 파일을 분할하여 FileSplit을 생성 FileSplit 하나 당 맵 태스크(Map Task) 하나씩을 생성 맵(Map) 데이터를 읽어와서 KV 페어(Key-value pair)를 생성 컴바인(Combine) 목적: I/O 와 네트워크 트래픽 감소 디스크에 쓰기 전에 KV 리스트(Key-value list)에 대한 전처리를 수행 e.g. aggregation: Sum, count and etc 파티션(Partition) 키를 기준으로 디스크에 분할 저장. 해시 파티셔닝 (Hash Partioning)이 기본 각 파티션은 키를 기준으로 정렬이 됨 HDFS가 아닌 맵퍼의 Local File System에 저장 분할된 각 파일은 각각 다른 리듀스 태스크(Reduce Task)에 저장됨

13 Split file G into 4 file splits
2.2 매핑 프로세스 예제: Word Count Mapper Doc Data Map Combine Partition Local File System Map Hash (key) Output File 1 KV List Aggregated KV List Buffers KV List Output File 2 Map Map 1 1 1 Map 3 Output File 3 written written 1 written 1 Output File 4 user user 1 1 … … user … 2 Output File 5 … Split file G into 4 file splits Map Task FileSplit 1 Map Task FileSplit 2 Map Task FileSplit 3 Map Task FileSplit 4 Hadoop Distributed File System File G File G

14 2.3 리듀싱 프로세스 셔플 (Shuffle) 정렬 (Sort) 리듀스 (Reduce)
여러 맵퍼에 있는 결과 파일을 각 리듀서에 할당 리듀서에 할당된 결과 파일을 리듀서의 로컬 파일 시스템으로 복사 정렬 (Sort) 병합 정렬(Merge sort)를 이용하여 맵퍼 결과 파일을 정렬/병합 Key로 정렬된 하나의 커다란 파일이 생성됨 리듀스 (Reduce) 정렬 단계에서 생성된 파일을 처음부터 순차적으로 읽으면서 리듀스 함수를 수행

15 2.3 리듀싱 프로세스 예제: Word Count Mapper 1 Reducer 1 … … … Mapper 2
Reduce Task 1 Shuffle/Copy Sort (Merge sort) Reduce Local File System Reduce Task 2 Output File 1 Reduce Task 3 Output File 2 Output File 3 Local File System Reduce Task 4 Reduce Task 1 Seq File Result Output File 4 Reduce Task 2 Map 1 Map 5 Output File 5 Reduce Task 5 Reduce Task 3 Map … 2 written 8 … Reduce Task 6 written 1 Reduce Task 7 written … 4 Reduce Task 8 Mapper 2 Reduce Task 6 Local File System Reduce Task 7 Reducer 2 Output File 1 Reduce Task 8 Output File 2 Result Shuffle Output File 3 Reduce 3 Reduce Task 9 Sort User 7 … Output File 4 Output File 5 Reduce Task 10 Reduce

16 3. 요약 맵리듀스는 맵 리듀스 큰 데이터를 손쉽게 처리하기 위해 데이터를 분산 처리하는 프로그래밍 모델
인풋 데이터를 가공하여 사용자가 원하는 정보를 Key/Value 쌍으로 변환 리듀스 가공된 Key/Value를 Key를 기준으로 각 리듀서로 분배 사용자가 정의한 방법으로 각 Key와 관련된 정보를 추출