MapReduce
명지대 클라우드 컴퓨팅 수업 내용 정리
Big Data & Hadoop
Hadoop은 사실상의 표준 빅 데이터입니다. 저장 및 처리 플랫폼!
분산 파일 시스템 및 프레임워크 제공 매우 큰 분석 및 변환을 위해 MapReduce paradigm을 사용하는 data set
- (수 천개의) 호스트들의 많은 데이터와 계산을 분할
- 응용 프로그램 계산을 그들의 데이터와 근접하게 병렬로 실행
Hadoop 클러스터는 commodity server를 추가해 컴퓨팅 용량을 확장하고, 스토리지 용량 및 IO 대역폭을 늘린다.
Introduction of MapReduce
- Google은 수백 가지의 특별한 목적을 가진 계산을 수행하였다.
- 크롤링된 문서, 웹 요청 로그와 같은 대량의 원시 데이터를 처리하여 다양한 종류의 파생 데이터를 계산하였다.
- 대부분의 이러한 계산은 개념적으로 간단하지만 입력 데이터는 일반적으로 크고 계산은 합리적인 시간 내에 완료하기 위해 수백 또는 수천 대의 기계에 분산되어야 합니다.
MapReduce
MapReduce는 대규모 데이터 세트를 처리하고 생성하기 위한 프로그래밍 모델입니다.
- 간단한 계산을 표현하는 새로운 abstraction
- 병렬화, 내결함성, 데이터 배포 및 로드 밸런싱의 지저분한 세부 정보를 숨깁니다.
- map에서 영감을 받아 Lisp 및 기타 여러 functional languages에 있는 primitives를 줄입니다.
- intermediate key/value pairs를 계산하기 위해 입력의 각 logical record에 map 작업 적용
- 파생 데이터를 적절하게 결합하기 위해 동일한 키를 공유하는 모든 값에 축소 연산을 적용합니다.(????)
MapReduce의 Programming Model
해당 계산은 input "key/value" pairs를 취하고 output "key/value" pairs를 생성합니다.
- user가 작성한 Map은 input pair를 취하고 intermediate key/value pairs를 생성합니다.
- MapReduce는 same intermediate key와 관련된 모든 intermediate values을 그룹화하고 이를 reduce 함수에 전달합니다.
- user가 작성한 Reduce 함수는 intermediate key와 set of values를 수락하고, 이러한 값을 병합하여 smaller set of values을 형성합니다.
Example: WordCount
많은 문서 모음에서 각 단어의 발생 횟수를 계산하는 문제
Implements
- Execution Overview (Google MapReduce)
- Map invocations은 input data를 set of M splits로 자동 분할하여 여러 시스템에 분산됩니다.
- input splits은 다른 머신에 의해 병렬로 처리될 수 있습니다.
- partitioning function을 사용하여 intermediate key space을 R 조각으로 분할하여 Reduce invocations
Fault Tolerance
- Handling Worker Failures
- master는 모든 worker들에게 주기적으로 pings를 보냄. 만약 일정 시간 이후에도 핑에 대한 응답을 받지 못하면, master는 work가 죽었다고 판단
- 실패한 worker가 완료한 모든 맵 작업이 재설정되고 다른 worker에 대한 일정을 잡을 수 있다.
- 완료된 map tasks은 실패 시 다시 실행됩니다. output은 실패한 시스템의 로컬 디스크에 저장됩니다.
- 완료된 reduce tasks은 다시 실행할 필요가 없습니다. output은 전역 파일 시스템에 저장됩니다.
- MapReduce는 대규모 worker failures에 탄력적입니다.
- worker가 고장난 경우에는 다른 worker에게 재실행하고 수행한 작업을 계속 전진하여 결국 MapReduce 작업을 완료했습니다.
Locality
- 네트워크 대역폭은 컴퓨팅 환경에서 상대적으로 부족한 자원입니다.
- input data가 머신의 로컬 디스크에 저장된다는 사실을 활용
- 계산이 데이터 가까운 곳에서 이루어지도록 해야한다.
- master는 해당 input의 복제본이 포함된 시스템에서 mapping 작업을 예약하려고 시도합니다.
- 실패하면 해당 작업의 input data 복제본 근처에서 mapping 작업을 예약하려고 시도합니다.
Experience in Google
- Large-Scale Indexing(대규모 인덱싱)
- MapReduce의 가장 중요한 용도 중 하나
- production indexing system의 완벽한 재정의
- Google 웹 검색에 사용되는 데이터 구조를 생성합니다.
- GFS 파일 세트로 저장된 크롤링 시스템에 의해 검색된 많은 문서 세트를 입력으로 사용
(몰라 어려워,,,)
- 인덱싱 시스템에 MapReduce를 사용할 때의 이점
- 인덱싱 코드는 더 간단하고 작으며 이해하기 쉽다.
- MapReduce의 성능은 충분하다.
- 인덱싱 프로세스가 훨씬 더 쉽게 작동할 수 있게 되었습니다.
Hadoop: MapReduse + HDFS
HDFS의 Master를 "JobTracker"로, Worker는 "TaskTracker"로
Hadoop MapReduce (ver. 1.2.1)
- JobTracker
- MapReduce 작업을 클러스터의 특정 노드, 이상적으로는 데이터가 있거나 최소한 동일한 rack에 있는 노드로 farms out(흙뿌려둔다.)
- Hadoop MapReduce 서비스의 실패 지점(하나가 다운되면 실행 중인 모든 작업이 중지된다)
- MapReduce job processing의 단계
1. 클라이언트 애플리케이션이 JobTracker에 Job 제출
2. JobTracker는 NameNode와 통신하여 데이터 위치를 결정합니다.
3. JobTracker는 입력 데이터 또는 그 근처에서 사용 가능한 슬롯이 있는 TaskTracker 노드를 찾습니다.
4. JobTracker는 선택한 TaskTracker 노드에 작업을 제출합니다.
5. TaskTracker 노드는 모니터링되며, heartbeat signal를 충분히 자주 제출하지 않으면 실패한 것으로 간주되고 다른 TaskTracker에서 작업이 예약됩니다. (TaskTracker는 지속적으로 heartbeat signal를 제출)
6. TaskTracker는 작업이 실패할 때 JobTracker에 알립니다. JobTracker는 그 다음 무엇을 할지 결정합니다. 다른 곳에서 작업을 다시 제출할 수 있고, 특정 record를 피해야 할 것으로 표시할 수 있으며, TaskTracker를 신뢰할 수 없는 것으로 블랙리스트에 올릴 수도 있습니다.
7. 작업이 완료되면 JobTracker가 상태를 업데이트합니다.
8. client application은 정보를 위해 JobTracker를 poll할 수 있습니다.
- TaskTracker
- task를 받는 일은 Map이 수행, Reduce와 Shuffle은 JobTracker가 수행한다.
- 모든 TaskTracker는 set of slot(static)로 구성됩니다.
- 실제 작업을 수행하기 위해 별도의 JVM 프로세스를 생성합니다.
- 프로세스 실패로 인해 TaskTracker가 중단되지 않도록 합니다.
- 생성된 프로세스를 모니터링하여 output 및 exit codes를 capture
- 프로세스가 완료되면 성공 여부에 관계없이 TaskTracker가 JobTracker에 알립니다.
- JobTracker가 아직 살아 있음을 확인하기 위해 일반적으로 몇 분마다 JobTracker에 heartbeat message를 보냅니다.
- 또한 JobTracker에 사용 가능한 slot number를 알려줍니다.