병렬 분산 알고리즘 구현 ( 이론 )

병렬 분산 알고리즘 구현

• 맵리듀스 프레임워크 이해하기
• 맵리듀스 프레임워크를 사용할 수 있는 Hadoop 설치 및 알고리즘 코드 실행
• 하둡을 이용하여 빅데이터 분석 및 처리용 맵리듀스 알고리즘을 구현하는데 필요한 코딩능력 배양하기

왜 병렬분산 알고리즘을 사용해야할까?

• Scale-out
  • 아주 많은 값싼 서버를 이용
• Scale-up
  • 적은 수의 값비싼 서버를 이용
• 데이터 중심 어플리케이션 분야에서는 아주 많은 값싼 서버를 많이 이용한다.
• 고가의 서버들은 가격에 관점에서는 선형으로 성능이 증가하지 않는다.

맵리듀스 프레임워크

• 데이터 중심 프로세싱

  • 한대의 컴퓨터 능력으로 처리가 어렵다
  • 수십수백수천대의 컴퓨터를 묶어 처리해야한다
  • 맵리듀스 프레임워크가 하는 것이 이것

• 맵리듀스는 빅데이터를 이용한 효율적인 계산이 가능한 첫 번째 프로그래밍 모델

  • 기존에 존재하는 여러 가지 다른 병렬 컴퓨팅 방법에서는 프로그래머가 낮은 레벨의 시스템 세부 내용까지 아주 잘 알고 많은 시간을 쏟아야만 함

• 빅데이터를 이용하는 응용분야에서 최근 주목받음

• Scale-out으로 클러스터를 만들고 여기에 빅 데이터를 처리하기 위한 스케일러블 병렬 소프트웨어의 구현을 숩게 할수 있도록 도와주는 간단한 프로그래밍 모델

  • *스케일러블 - 사용자 수가 급증 or 데이터가 급증 해도 유연하게 처리해줌 (성능이 안느려짐)

• 구글의 맵리듀스 or 오픈소스인 하둡 은 맵리듀스 프레임워크의 우수한 구현의 형태

• 드라이버에 해당하는 메인 함수가 맵 함수와 리듀스 함수를 호출해서 처리

맵리듀스 프로그래밍 모델

• 함수형 프로그래밍 언어의 형태
• 유저는 아래 3가지 함수를 구현해서 제공해야 함
  • Main 함수
  • Map 함수 : (key1, val1) -> [(key2, val2)]
  • Reduce 함수 : (key2,[val2]) -> [(key3, val3)]

맵리듀스 프레임워크

• 각 레코드 or 튜플은 키-밸류 쌍으로 표현
• 메인 함수를 한 개의 마스터 머신에서 수행하는데 이 머신은 맵 함수를 수행하기 전에 전처리를 하거나 리듀스 함수의 결과를 후처리하는데 사용될 수 있다.
• 컴퓨팅은 맵과 리듀스라는 유저가 정의한 함수 한 쌍으로 이루어진 맵리듀스 페이즈를 한번 수행하거나 여러 번 반복해서 수행할 수 있다.
• 한번의 맵리듀스 페이즈는 맵 함수를 먼저 호출하고 그 다음에 리듀스 함수를 호출하는데 때에 따라서는 맵 함수가 끝난 후에 컴바인 함수를 중간에 수행할 수 있다.
• 드라이버에 해당하는 메인 프로그램에서 맵리듀스 페이즈를 수행시킨다.

맵리듀스 페이즈(3단계 구성)

• 맵 페이즈
  • 제일 먼저 수행됨, 데이터의 여러 파티션에 병렬 분산으로 호출되 수행
  • 각 머신마다 수행된 Mapper는 맵 함수가 입력 데이터의 한 줄 마다 맵 함수 호출
  • 맵 함수는 (키, 벨류)의 쌍 형태로 결과 출력, 여러 머신에 나누어 보내며 같은 키를 가진 쌍은 같은머신으로 보냄
• 셔플링 페이즈
  • 모든 머신에서 맵페이즈가 다 끝나면 시작된다.
  • 맵 페이즈에서 각각의 머신으로 보내진 쌍을 키를 이용해서 정렬 한 후, 각 키 마다 같은 키를 가진 쌍을 모아서 밸류-리스트(Value-list)를 만든 다음 (key, value-list) 형태로 key에 따라 여러 머신에 분산해 보냄
• 리듀스 페이즈
  • 모든 머신에서 셔플링 페이즈가 다 끝나면 각 머신마다 리듀스 페이즈가 시작
  • 각 머신에서 셔플링 페이즈에서 해당 머신으로 보내진 각각 (key,value-list) 쌍 마다 리듀스 함수가 호출, 하나의 리듀스 함수가 끝나면 다음 (key,value-list) 쌍에 리듀스 함수가 호출된다.
  • 출력이 있다면 (key, value) 쌍 형태로 출력

Hadoop

• Apache 프로젝트의 맵리듀스 프레임워크의 오픈 소스
• 하둡 분산 파일 시스템 (하둡 디스트리뷰트 파일 시스템 - HDFS)
  • 빅 데이터 파일을 여러 대의 컴퓨터에 나누어서 저장함
  • 각 파일은 여러 개의 순차적인 블록으로 저장함
  • 하나의 파일의 각각의 블록은 폴트 톨러런스를 위해서 여러 개로 복사 되어 여러 머신의 여기저기 저장됨
    • 폴트 톨러런스 : 시스템 구성 부품 일부에서 결함 or 고장이 발생해도 정상적 또는 부분적으로 기능을 수행할수 있는 것을 말ㄹ함
• 빅 데이터를 수천 대의 값싼 컴퓨터에 병렬 처리하기 위해 분산함
• 주요 구성 요소들
  • MapReduce(맵리듀스) - 소프트웨어의 수행을 분산함
  • Hadoop Distributed File System(HDFS) - 데이터를 분산함
• 한 개의 Namenode(master) 와 여러 개의 Datanode(slaves)
  • Namenode
    • 파일 시스템을 관리하고 클라이언트가 파일에 접근할 수 있게 함
  • Datanode
    • 컴퓨터에 들어있는 데이터를 접근 할수 있게 함
• 자바 프로그래밍 언어로 맵리듀스 알고리즘 구현

MapReduce의 함수

• 맵 함수
  • org.apache.jaddop.mapreduce라는 패키지에 있는 Mapper 클래스를 상속받아서 맵 메소드(method)를 수정한다.
  • 입력 텍스트 파일에서 라인 단위로 호출되고 입력은 키-밸류(Key,Value-List)의 형태
  • key는 입력 텍스트 파일에서 맨 앞 문자를 기준으로 맵 함수가 호출된 해당 라인의 첫 번쨰 문자까지의 오프셋
  • Value는 텍스트의 해당 라인 전체가 들어있다.
• 리듀스 함수
  • org.apache.hadoop.mapreduce라는 패키지에 있는 reducer 클래스를 상속받아 re4duce 메소드를 수정한다.
  • 셔플링 페이즈의 출력을 입력으로 받는데 키-벨류의 형태
  • Value-list는 맵 함수의 출력에서 키를 갖는 키,벨류 쌍들의 벨류들의 리스트
• 컴바인 함수
  • 리듀스 함수와 유사한 함수임, 각 머신에서 맵 페이즈에서 맵 함수의 출력 크기를 줄여서 셔플링 페이즈와 리듀스 페이즈의 비용을 줄여주는데 사용된다.

요약

MapPhase 에서 일단 쫘악 펼처준다

MapReduce 쫘악 펼쳐준 것을 각 머신들로 보내준다. ( 110 까지는 첫번쨰 머신, 1120까지는 두번쨰 머신)

Shuffling Phase 소팅해줌 ( 정렬, 같은얘뜰끼리 Key, Value-list 쌍으로 해준다.)

Reduce 함수 호출 : 마침내 (key, value) 로 나타내짐

Combine 함수

• 맵 함수의 결과 크기를 줄여준다.
• 각각의 머신에서 Reduce함수를 이용하는 것처럼 수행된다.
• 셔플링 비용을 줄여준다.
• 따라서 맵리듀스 알고리즘 디자인에 사용하는 것이 좋음

Overview of MapReduce

• Mapper and Reducer
  • 각 머신에서 독립적으로 수행된다.
  • Mapper는 Map 함수를 Reducer는 Reduce 함수를 각각 수행한다.
• Combine functions
  • 각 머신에서 Map 함수가 끝난 다음에 Reduce 함수가 하는 일을 부분적으로 수행한다.
  • 셔플링 비용과 네트웍 트래픽을 감소 시킨다
• Mapper와 Reducer 는 필요하다면 setup() and cleanup()를 수행할 수 있다.
  • setup() : 첫 Map 함수나 Reduce 함수가 호출되기 전에 맨 먼저 수행한다.
    • 모든 map 함수들에게 BroadCast 해서 전달해야 할 파라미터 들 정보를 Main 함수에서 받아오는데 사용
    • 모든 Map 함수들이 공유하는 자료구조를 초기화 하는데 사용
  • cleanup() : 마지막 Map 함수나 Reduce함수가 끝나고 나면 수행한다.
    • 모든 Map 함수들이 공유하는 자료구조의 결과를 출력하는데 사용
• 한 개의 MapReduce job을 수행할 때에 Map 페이즈만 수행하고 중단 할 수도 있다.