[옛 글] [BigData] MapReduce - master data structure와 고장 허용 범위

최초 작성일 : 2013/02/14 14:49 

==================================================================

내용이 어려워짐에 따라 번역은 점점 발번역으로 치닫고 있습니다...ㅠ.ㅠ

첫 글에 링크해드린 원문 문서를 참조해서 보세요...

==================================================================

Master Data Structure

master 프로그램은 몇가지 데이터 구조를 유지한다. 각각의 map task와 reduce task에 대해

master는 그 상태(비가동, 프로세스 진행 중 또는 완료)와 그 작업자 머신의 식별자를  저장한다.

(유휴 작업이 없도록 하기 위해)

master는 map task로부터 reduce task로 중간 파일 영역의 저장 위치를 전달해주는 전달자이다.

그러므로 각각의 완료된 map task에 대해 master는 map task가 생산해낸 R개의 중간 파일 영역의

위치와 크기를 저장한다. 이러한 위치와 크기 정보는 map task가 완료될 때마다 업데이트된다.

이 정보는 프로세스가 진행 중인 reduce task를 가진 작업자에게 점차 부하를 주게 된다

Fault Tolerance (고장 허용 범위)

MapReduce 라이브러리가 수백, 수천대의 머신에서 매우 커다란 양의 데이터를 처리하기 위해 디자인된

이후 머신의 고장에 대해 훌륭하게 대처해왔다.

Worker Failure

master는 주기적으로 모든 작업자들에게 ping을 날린다.

일정 시간 동안 작업자로부터 응답이 없는 경우 master는 이 작업자가 고장이라고 판단한다.

작업자에 의해 완료된 map task들은 다시 초기 유휴상태로 재설정되며 다른 작업자에게

스케쥴링 될 수 있는 상태가 된다. 이와 유사하게 고장이 발생한 작업자상에 있는 프로세스 진행 중인

map task 또는 reduce task들은 역시 유휴 상태로 재설정되어 스케쥴링 가능한 상태가 된다.

완료된 map task들은 고장난 머신상에 출력 파일을 저장하고 고장난 머신 상의 파일은

접근을 할 수 없기 때문에 재실행 되도록 한다. 하지만 완료된 reduce task는 파일을 전역적인

파일 시스템에 저장하기 때문제 재실행 할 필요가 없다.

map task가 A 작업자에게서 실행되다가 A가 고장이 나서 다시 B 작업자에게 실행되는 경우

reduce task를 수행 중인 모든 작업자들은 재실행에 대한 통지를 받는다.

이 중 아직 A 작업자로부터 데이터를 읽지 않은 reduce task들은 B 작업자로부터 데이터를 읽게 된다.

MapReduce는 대규모 작업자들의 고장에 탄력적이다.

일례로 어떤 MapReduce 작업은 수행되는 동안 실행중인 클러스터상의 네트워크 유지보수 작업이 원인이 되어

80대로 구성된 그룹들이 동시에 몇 분 동안 unreachable 상태가된 상황이 발생한 적이 있는데, 이 MapReduce의

master는 간단하게 unreachable 상태인 작업자들에 의해 수행되던 작업들을 완료하고 작업을 계속 수행해서

결국 MapReduce 작업을 완료하였다.

Master Failure

master가 위에 기술한 것과같이 주기적으로 master 데이터 구조의 체크포인트를 작성하도록 하는 것은 쉽다.

만일 master가 죽는다면 마지막에 확인된 상태로부터 새로운 복사이 시작 될 수 있다. 그러나 단지 하나의

master만 작동하는 상태에서 이 master의 고장은 예상 밖의 문제를 가져온다.

그러므로 현재 우리가 구현한 방식에서는 만일 master가 고장이 나면 MapReduce 연산을 취소시킨다.

사용자들은 이 상태를 감지할 수 있고 언제든지 그들이 원하는 때에 MapReduce 업무를 다시 시작할 수 있다.

Semantics in the Presence of Failures

사용자가 제공한 map과 reduce 작업 프로그램이 입력값에 대한 동일한 출력을 보장 할 때(*deterministic)

우리의 분산 구현 역시 전체 프로그램의 오류 없는 순차적인 실행을 통해 같은 결과물을 생산해 낼 수 있다.

우리는 이런 속성을 만족시키기 위해 map과 reduce task 출력의 개별적인 수행에 의존해야 한다.

각각의 실행 중인 task는 그 결과물을 자신만의 임시 파일에 쓴다.

하나의 reduce task는 이런 파일을 하나만 생성하고 map task는 이런 파일을  (하나의 reduce task에 대해)R개

생성한다.

map task가 완료되었을 때 작업자는 R개의 임시 파일의 이름들을 포함한 메시지를 master에게 보내게 된다.

master가 이미 업무가 종료된 map task로부터 종료 메시지를 받게되면 master는 그 메시지를 무시한다.

만약 그렇지 않으면 master는 master 데이터 구조에 R개의 파일의 이름들을 기록하게 된다.

reduce task가 완료되었을 때 reduce 작업자는 임시파일을 개별적으로 이름을 붙여 최종 출력 파일로 만든다.

만일 동일한 reduce task가 여러대의 머신에서 수행되고 있는 경우 동일한 최종 출력 파일을 위해

이름 변경 작업이 여러 곳에서 실행되는데 기본적인 파일 시스템이 하나의 reduce task로부터 생성된 데이터만을

최종 파일 시스템 상태에 저장하도록 보장해준다.

map과 reduce 작업 프로그램의 대다수는 동일 입력에 대해 동일 출력을 보장하며(deterministic)

순차적인 실행과도 동일한 이러한 의미는 프로그래머들이 자신들이 개발한 프로그램의 행위를 예측하는 것을

매우 쉽게 해준다.

map과(또는) reduce 업무가 입력에 대한 출력을 보장하지 못하는 경우에라도(**non-deterministics)

우리의 시스템은 보다 약하지만 여전히 합리적인 의미체계를 제공해 줄 수 있다.

비결정적인 업무의 존재하에서 특정 reduce R1에 대한 출력은 비결정적 프로그램의 순차적인 실행을 통해

생산된 출력 R1과 동일하다. 그러나 다른 reduce task  R2 을 위한 출력은 또 다른 비결정적인 프로그램의

순차적인  실행에 의해 생산된  R2 를 위한 출력과 부합할 것이다.

map task M과 reduce task R1 그리고  R2 를 생각해보자.
e(Ri)이 commit된  Ri 을 실행하도록 하면.(정확히 한 번만 실행을 한다)  e(R1)은 M의 실행 중 하나로부터
생성된 출력을 읽게될 것이고 e(R2)는 M의 다른 실행으로부터 생성된 출력을 읽게 되는 약한 의미체계가
발생하게 된다.

==========================================================

*deterministic algorithm

예측한 그대로 동작하는 알고리즘이다. 어떤 특정한 입력이 들어오면 언제나 똑같은 과정을 거쳐서 언제나 똑같은 결과를 내놓는다. 결정론적 알고리즘은 실제 기계에서 돌릴 수 있는 효율적인 알고리즘일 뿐 아니라, 가장 오랫동안 연구되었으며 가장 친숙한 알고리즘이다.

**non-deterministic algorithm

결과가 한 가지로 정의되지 않고 명시된 집합에 속한 하나의 값이 선택되는 연산을 포함하는 알고리즘.