자바랑 코덕코덕

Inverted Index

먼저 예시를 보면

Doc1: apple banana coconut
Doc2: apple doughnut egg
Doc3: apple coconut melon

위와 같이 있다고 했을 때, Inverted Index는 아래와 같습니다.

apple -> Doc1:1, Doc2:1, Doc3:1
banana -> Doc1:7
coconut -> Doc1:14, Doc3:7
doughnut -> Doc2:7
egg -> Doc2:16
melon -> Doc3:15

위와 같이 각각의 단어가 어느 문서에서 어느 위치에 있는지 list로 가지고 있는것을 Inverted Index라고 합니다.

Partitioner Class

Map 함수의 출력인 (Key, Value) 쌍이 Key에 의해서 어느 Reducer (머신)로 보내질 것인지를 정해지는데
이러한 결정을 정의하는 class

하둡의 기본 타입은 Hash 함수가 Default로 제공되고 있어서 Key에 대한 해시 값에 따라 어느 Reducer(머신)으로 보낼지를 결정한다.

하둡의 기본타입
- Text
- IntWritable
- LongWritable
- FloatWritable
- DoubleWritable

Partitioner Class 예제 코드

소문자로 시작하면 0번 머신으로, 대문자로 시작하면 1번 머신으로 보내는 파티셔너 예제 코드

 public static class MyPartitioner extends Partitioner<Text, IntWritable> {
   @Override
   public int getPartition(Text key, IntWritable value, int numPartitions) {
     if(key.toString().charAt(0) < 'a') return 0;
     else return 1;
   }
 }

병렬 분산 알고리즘 구현이 가능한 맵리듀스 프레임워크에 대해서 이야기하기 전에
왜❓ 병렬 분산 알고리즘을 사용해야 하는지 먼저 이야기 하겠습니다.

💡 병렬 분산 알고리즘을 사용하는 이유

• Scale-out: 많은 수의 값싼 서버 이용
• Scale-up: 적은 수의 값비싼 서버 이용

데이터 중심(data-intensive) 어플리케이션 분야에서는 Scale-out을 선호합니다.
왜냐하면 가격과 성능의 관계가 선형적으로 증가하지 않기 때문입니다.
예를 들면, 두배 성능의 프로세서 하나를 가진 컴퓨터의 가격이 일반적인 컴퓨터 가격의 두배보다 훨씬 비쌉니다.
그래서 수 십에서 수 천대의 컴퓨터를 묶어서 처리하기 위해 병렬 분산 알고리즘이 필요합니다.
그럼 병렬 분산 알고리즘 구현이 가능한 맵리듀스 프레임워크에 대해 이야기 하겠습니다.

🤔 Why MapReduce...?

데이터 중심 프로세싱(Data-intensive processing)에서는 한대의 컴퓨터로 처리하는데는 한계가 있습니다.
여러 컴퓨터를 묶어서 처리를 해야하는데 그 역할을 하는 것이 바로 맵리듀스(MapReduce)입니다

맵리듀스는 빅데이터를 활용하여 효율적인 계산이 가능한 첫 번째 프로그래밍 모델입니다.
Scalable(사용자 수, 데이터가 급증해도 프로그램 성능이 크게 떨어지는 일이 없는) 병렬 소프트웨어의 구현을 쉽게 할 수있도록 도와주는 프로그래밍 모델입니다.

✔️ MapReduce Programming Model

구글에서 맵리듀스 프레임워크를 만들었고 외부에서 사용할 때는 오픈소스인 하둡(Hadoop)을 이용하여 맵리듀스 프레임워크를 구현하여 사용합니다.

함수형 프로그래밍(Functional programming) 언어의 형태로 사용자는 3가지 함수(main, map, reduce) 를 구현해서 제공해야 합니다.

• main 함수: 드라이브에 해당
• map 함수: (key1, val1) -> [(key2, val2)]
  • org.apache.hadoop.mapreduce 패키지에 있는 Mapper 클래스를 상속받아 수행합니다.
• reduce 함수: (key2, [val2] -> [(key3, val3)]
  • org.apache.hadoop.mapreduce 패키지에 있는 Reducer 클래스를 상속받아 수행합니다.

드라이브에 해당하는 main 함수는 map 함수와 reduce 함수를 차례대로 호출합니다.
map 함수와 reduce 함수는 key와 value가 쌍으로 구성된 형태로 입력을 받고 출력을 합니다.
[]로 표시된 것은 list로 여러개 받을 수 있다는 것을 의미합니다.
Reduce 함수의 [val2]은 list 형태이고, map 함수와 reduce 함수의 출력은 하나도 없을 수도 있고 1개일 수도 있고 여러개 일 수도 있습니다.

이 세가지 함수에 추가로 combine 함수가 있습니다.

• Combine 함수: reduce 함수와 유사
  • 각 머신에서 map phase에서 map 함수의 출력 크기를 줄여서 shuffling phase와 reduce phase의 비용을 줄여주는데 사용됩니다.

한번의 맵리듀스 페이즈는 map 함수를 먼저 호출하고 그 다음 reduce 함수가 호출됩니다.
필요하면 맵 함수가 끝난 후, combine 함수를 중간에 수행 할 수도 있습니다.

그럼 이 맵리듀스 프레임워크가 어떻게 동작하는지 더 자세하게 한번 알아보도록 하겠습니다.

🔍 MapReduce Framework

맵리듀스 프레임워크는 앞서 설명한데로 각각의 레코드(또는 튜플)이 (key, value)쌍으로 표현됩니다.
main 함수는 한개의 마스터 머신(master machine)에서 수행됩니다.
마스터 머신은 map 함수 수행 전 전처리를 하거나 reduce함수 결과를 후처리 하는데 사용될 수 있습니다.

맵리듀스는 3 단계로 아래 그림과 같이
map phase => shuffling phase => reduce phase 순서로 호출되어 수행됩니다.

MapReduce Phase

• Map phase
  • 제일 먼저 수행되며 여러 파티션에 병렬 분산으로 호출되어 수행됩니다.
  • 그러면 각 머신에서 수행되는 mapper를 통해 입력 데이터 한 줄씩 map 함수가 호출됩니다.
  • map 함수는 (key, value)쌍 형태로 여러 머신에 나누어 보내지고 같은 key를 갖으면 같은 머신으로 보내집니다.
• Shuffling phase
  • 모든 머신에서 map phase가 다 끝나면 시작됩니다.
  • map phase에서 각각의 머신으로 보내진 (key, value)쌍이 key를 기준으로 정렬됩니다.
  • 같은 key를 가진 (key, value)쌍을 모아서 value-list를 만듭니다. 그후 (key, value-list)쌍을 key에 따라 여러 머신에 분산해서 보냅니다.
• Reduce phase
  • 모든 머신에서 shuffling phase가 다 끝나면 시작됩니다.
  • 각각의 머신에서는 shuffling phase에서 보낸 (key, value-list)쌍 마다 reduce 함수가 호출됩니다.
  • 하나의 reduce 함수가 끝나면 다음 (key, value-list)쌍에 호출됩니다.
  • (key, value)쌍 형태로 출력할 수 있습니다.

🐘 Hadoop

하둡은 Apache 프로젝트에서 만든 MapReduce 프레임워크 오픈 소스입니다.
여기에는 하둡 분산 파일 시스템(Hadoop Distributed File System - HDFS) 이라는 게 있습니다.

빅데이터 파일을 여러대의 컴퓨터에 나누어 저장을 합니다. 이 각 파일은 여러 개의 순차적인 블록으로 저장이 됩니다.
그리고 그 하나의 파일의 각각의 블록은 폴트 톨러런스(fault tolerance)를 위해서 여러개로 복사되어 여러 머신에 저장됩니다.

폴트 톨러런스는 시스템을 구성하는 부품의 일부에서 결함 또는 고장이 발생하여도 정상적으로 혹은 부분적으로 기능을 수행할 수 있게 하는 것을 말합니다. 그래서 하나의 파일 조각에 문제가 생겨도 다른 머신에 저장된 조각을 가져다 사용 할 수 있습니다.

🛠 구성 요소로 소프트웨어의 수행을 분산하기 위한 MapReduce 와 데이터 분산을 위한 HDFS 이 있습니다.
🛠 한 개의 Namenode(master)와 여러대의 Datanode(slaves)로 이루어져 있습니다.

🧐 이 글은 공부한 내용을 정리하고 공유하기 위해 작성한 글입니다!
🛠 수정해야 하는 내용이 있다면 알려주세요! 감사합니다 🙇‍♀️