최초 작성일 : 2013/05/30 15:24 


맵 리듀스 개요

맵 : 
- 원시 데이터를 key-value 쌍의 중간 파일로 만든다.
- 입력데이터가 있는 노드에서 맵 함수가 수행되는 것이 가장 좋다 (지역성 최적화)
- 맵 함수에 전달되는 입력 데이터는 라인 offset을 키로, 해당 라인 내용을 value로 하는 형태로 구성된다.
- 맵 함수는 이 입력값들로부터 필요로 하는 key와 value를 추출한다.
- 이 과정에서 잘못된 레코드를 제거하는 기능도 수행한다.
- 맵 task의 실행 결과는 HDFS가 아닌 로컬 디스크에 저장된다. (HDFS와 로컬 디스크의 개념을 명확히 구분하자)
  이유는 맵의 결과물은 단지 리듀스 함수로 전달하기 위한 중간 결과물일 뿐이며 모든 잡이 완료되면
  버려도 되는 데이터이기 때문이다.

리듀스 : 
- 각 맵 task들의 결과물들을 입력으로 받아 최종 결과물을 생성한다.
- 각 노드에 있는 맵 task의 결과물들을 입력으로 받으므로 지역성 최적화의 영향이 없다.
- 리듀스의 결과물은 안정성을 위하여 HDFS에 저장된다.


셔플 : 
- 맵 task의 결과물을 리듀스 task로 보내기 전의 중간 가공 단계
- key에 대한 정렬이나 그룹화 및 파티셔닝 작업이 이루어진다.
- 정렬은 말 그대로 정렬이며 그룹화는 같은 key로 묶는 것, 그리고 파티셔닝은 리듀스 task가 2개 이상인 경우
  결과물을 각각의 리듀스 task에 분배하기 위해 특정 기준으로 쪼개는 작업이다.
- 때때로 셔플 작업이 없을 수도 있으며 이런 경우에는 리듀스 task도 없는 맵 task만으로 이루어진
  job이 수행된다. 또한 이 상태에서는 맵 task의 결과가 HDFS에 저장된다.

컴바이너 : 
- 맵 task의 결과물을 네트워크를 통해 리듀스 task로 이동시키는 과정을 최적화하기 위한 방법 중 하나
- 같은 key를 가진 value들을 리스트로 묶어 새로운 key-value쌍을 만든다.
  즉 {key1, value1}, {key1, value2}를 {key1, list(value1, value2)}의 형태로 만드는 것이다.
- 주로 연합 연산(합계, 카운팅, 최대값 등)에 사용된다.
- 컴바이너를 사용하게 되면 맵 task 결과물의 사이즈를 줄일 수 있다. 즉 네트워크의 트래픽량을 줄일 수
  있게 되는 것이다.

블로그 이미지

마즈다

이미 마흔을 넘어섰지만 아직도 꿈을 좇고 있습니다. 그래서 그 꿈에 다가가기 위한 단편들을 하나 둘 씩 모아가고 있지요. 이 곳에 그 단편들이 모일 겁니다...^^

최초 작성일 : 2013/05/15 13:05 


드디어 마지막 결론입니다~~~!

그동안 발번역을 열심히 보아주신(분이 계시다면) 경의를 표합니다...^^;;;
이제 다음 주부터는 실무 연습으로 들어가야겠네요.
자세한 계획은 다음 글에...^^;;;

감사합니다.
=============================================

결론

MapReduce 프로그래밍 모델은 구글에서 여러가지 서로 다른 목적을 위해 성공적으로 사용되고 있다.
우리는 몇가지 이유로부터 이러한 성공의 결과를 찾고 있다.

첫 번째로 MapReduce의 프로그래밍 모델은 병렬화, 고장 방지, 지역 최적화, 로드 밸런싱 등의 세부적인
부분을 모두 라이브러리 내부에 감추고 있기 때문에 사용하기 쉽고 심지어 병렬이나 분산 시스템에 대한 경험이 없는
프로그래머도 사용 가능하다.

두 번째로 매우 다양한 문제들을 MapReduce 연산으로 쉽게 표현할 수 있다.
예를 들면 MapReduce는 구글의 검색 서비스, 정렬이나 데이터 마이닝, *machine learning(기계 학습),
그리고 많은 다른 시스템들을 위한 데이터를 생산해내고 있다.

세 번째로 우리는 수천대의 머신으로 구성된 대규모 클러스터를 대상으로 MapReduce 구현을 개발했다.
이러한 구현은 이러한 머신 리소스들을 보다 효과적으로 사용 가능하도록 해주며 그래서 구글에 닥친
컴퓨터와 관련된 다수의 커다란 문제점들을 다루는데 적합하다.

우리는 이 작업으로부터 몇가지를 배웠다.
첫 번째로 프로그래밍 모델을 제한하는 것이 연산을 병렬화 분산화 시키는데 쉽고
이러한 연산의 고장 관리를 하는데 쉽다는 것이다.

두 번째로 네트워크 대역폭은 부족한 자원이라는 것이다. 우리 시스템의 다수의 최적화는
데이터를 네트워크를 통해 전송하는 전송량의 감소에 초점이 맞춰져있다:로컬 최적화는 로컬 디스크로부터
데이터를 읽을 수 있도록 해주고 단일 복사본의 중간 형태의 데이터를 로컬 디스크에 기록함으로써
네트워크 대역폭을 절약하게 해준다.

세 번째로 남아도는 실행은 느린 머신들, 머신의 고장 관리, 데이터 손실 등에 의한 악영향을 감소시키는데
이용 가능하다.





machine learning
(1) 새로운 정보를 학습하고, 습득한 정보를 효율적으로 사용할 수 있는 능력과 결부시키는 지식 습득.
(2) 작업을 반복적으로 수행함으로써 결과를 얻어내는 기술의 개선 과정.
컴퓨터인터넷IT용어대사전

블로그 이미지

마즈다

이미 마흔을 넘어섰지만 아직도 꿈을 좇고 있습니다. 그래서 그 꿈에 다가가기 위한 단편들을 하나 둘 씩 모아가고 있지요. 이 곳에 그 단편들이 모일 겁니다...^^

최초 작성일 : 2013/05/09 12:26 


이제 마지막 여덟 번 째 섹션인 '결론'만 남았네요.
결론까지 다 번역하고 나면 드디어 기다리고 기다리는 실제 구축 연습니다.
빈약하지만 열심히 장비도 준비를 해놓았네요...^^;;;

오늘도 발번역 나갑니다.

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

Related Work 2

MapReduce 라이브러리의 일부인 정렬 장치는 *NOW-Sort 수행과 유사하다. 소스 머신들(map 작업자들)은
정렬을 위해 데이터를 분할하고 분할된 데이터를 R개의 reduce 작업자 중 하나에게 전달한다. 각각의 reduce
작업자들은 로컬상에서 그 데이터들을 정렬한다(가능하다면 메모리상에서 수행한다). 물론 NOW-Sort는
우리의 라이브러리에서는 광범위하게 적용 가능한 사용자 정의 Map, Reduce 함수는 가지고 있지 않다.

**River는 분산된 qeue들을 통해 데이터를 전송함으로써 프로세스들이 상호 통신하는 프로그래밍 모델을 제공한다.
River 시스템도 MapReduce처럼 이기종의 하드웨어로부터 생겨난 불균일성이나 시스템의 교란에도
훌륭한 평균 성능을 제공해준다. River는 균형잡힌 종료시간 유지를 위해 디스크와 네트워크 전송에 대한
주의 깊은 스케쥴링을 함으로써 이러한 성능을 이끌어내었다.

MapReduce는 다른 접근 방식을 취한다.
프로그래밍 모델을 제한함으로써 MapReduce 라이브러리는 문제들을 매끄럽게 수행되는 다수의 task들 사이에
분할해서 넣을 수 있다. 이러한 task들은 사용 가능한 작업자들 내에서 동적으로 스케쥴링 되고 따라서
빠른 작업자들은 더 많은 task들을 수행하게 된다.

또한 제한적인 프로그래밍 모델은 우리가 job 실행 종료 부근에서 발생하는 task들의 남아도는 실행을 스케쥴링
할 수 있도록 해줌으로써 불균일한 상황(작업자가 느려지거나 멈추는 것과 같이)이 발생하는 경우에도
훌륭하게 종료 시간을 단축시킬 수 있게 해준다.

***BAD-FS는 MapReduce와 매우 다른 프로그래밍 모델을 가지고 있다. 그리고 MapReduce와는 달리
광범위한 영역의 네트워크망 사이에서 job들을 실행시킬 목적으로 만들어졌다. 그러나 2가지 근본적인 유사성이 있다.
(1) 양 시스템은 고장으로 발생하는 데이터 손실을 복구하기 위해 남아도는 실행을 이용한다.
(2) 양 시스템은 혼잡한 네트워크간의 데이터 전송량을 줄이기 위해 지역 기반의 스케쥴링을 이용한다.

****TACC는 고가용성의 네트워크 서비스를 단순하게 구축하기 위해 고안되었다.
MapReduce처럼 내고장성을 구현하기 위해 재실행 매커니즘을 이용한다.



*NOW-Sort
Andrea C. Arpaci-Dusseau, Remzi H. Arpaci-Dusseau, David E. Culler, Joseph M.
Hellerstein, and David A. Pat- terson.
High-performance sorting on networks of work- stations.
In Proceedings of the 1997 ACM SIGMOD In- ternational Conference on Management of Data,
Tucson, Arizona, May 1997.

**River
Remzi H. Arpaci-Dusseau, Eric Anderson, Noah Treuhaft, David E. Culler, Joseph M.
Hellerstein, David Patterson, and Kathy Yelick.
Cluster I/O with River: Making the fast case common.
In Proceedings of the Sixth Workshop on Input/Output
in Parallel and Distributed Systems (IOPADS ’99), pages 10–22,
Atlanta, Georgia, May 1999.

***BAD-FS
John Bent, Douglas Thain, Andrea C.Arpaci-Dusseau, Remzi H.
Arpaci-Dusseau, and Miron Livny.
Explicit control in a batch-aware distributed file system.
In Pro- ceedings of the 1st USENIX Symposium on Networked Systems Design
and Implementation NSDI, March 2004.

****TACC
Armando Fox, Steven D. Gribble, Yatin Chawathe, Eric A. Brewer, and Paul Gauthier.
Cluster-based scal- able network services.
In Proceedings of the 16th ACM Symposium on Operating System Principles,
pages 78– 91, Saint-Malo, France, 1997.

블로그 이미지

마즈다

이미 마흔을 넘어섰지만 아직도 꿈을 좇고 있습니다. 그래서 그 꿈에 다가가기 위한 단편들을 하나 둘 씩 모아가고 있지요. 이 곳에 그 단편들이 모일 겁니다...^^

최초 작성일 : 2013/05/03 13:04 


=============================================
문서의 막바지에 다다르니 전문 용어 및 원서와 논문들의 인용구가 많아
독해에 어려움이 많네요...ㅠ.ㅠ

이미 앞서 올린 글을 통해 발번역인 거 다 아셨으니 그냥 그러려니 하고 보세요...ㅠ.ㅠ
=============================================

Related Work

많은 시스템들이 제한된 프로그래밍 모델들을 제공하고 자동으로 연산의 병렬화를 하는데 그 제약을 사용한다.
예를 들면 associative 함수는 parallel prefix computations[6, 9, 13]을 이용하여 N개의 프로세서 상에서
log N의 시간 동안 N개의 요소를 가진 배열의 모든 접두어에 대해 연산이 수행된다.

MapReduce는 거대한 실세계에서의 연산에 대한 우리들의 경험을 기반으로 이러한 프로그래밍 모델들의 일부에 대한
간소화와 정제가 고려되어있다.

보다 주목할 만한 것은 우리는 수천개의 프로세서에 대한 고장 방지 구현을 제공한다는 것이다.
반면에 대부분의 병렬 프로세싱 시스템들은 단지 작은 규모의 구현만을 제공하거나 머신의 고장에 대한 관리를
프로그래머에게 맡기고 있다.

*Bulk Synchronous Programming과 일부 **MPI primitives는 높은 수준의 추상화를 제공하고
이를 통해 개발자들이 병렬 프로그램을 작성하기 쉽도록 해준다. 이러한 시스템들과 MapReduce 간의 명확한 차이는
MapReduce가 사용자의 프로그램을 자동으로 병렬화 할 수 있는 제한적 프로그래밍 모델을 활용하고 있다는 점과
고장 방지 기능의 투명성을 제공하고 있다는 점이다.


우리의 지역 최적화는 ***active disks와 같은 기술로부터 영감을 얻어 구현하고 있다.
active disk에서는 I/O 서브시스템들간에 데이터를 주고 받는 전송량이나 네트워크 전송량을 줄이기 위해
연산 수행에 필요한 요소들이 있는 로컬 디스크에서 연산이 수행되도록 한다.

우리는 디스크 관리 프로세서상에서 직접 수행하는 대신 소수의 디스크가 직접 연결된 일반적인 상용 프로세서상에서
프로세스를 수행하며 그밖의 일반적인 접근은 active disk와 유사하다.

우리의 백업 task 매커니즘은 ****Charlotte System에 채택되어있는 eager scheduling과 유사하다.
간단한 eager scheduling의 단점 중 하나는 주어진 task가 반복적인 오류를 발생시킬 경우 전체 연산의
완료가 실패한다는 것이다. 우리는 잘못된 레코드를 무시하고 넘어가는 우리의 매커니즘을 통해 이러한 문제를 가진
몇몇 인스턴스를 수정하였다.

MapReduce의 구현은 내부 클러스터 관리 시스템에 의존한다.
내부 클러스터 관리 시스템은 대규모 공유 머신들의 집합체 상에서 분산과 사용자 task 수행을
책임지고 있다. 이 문서의 논점에서 벗어나지만 클러스터 관리 시스템은 *****Condor와 같은 다른 시스템들과
그 기본 사상이 유사하다.



-> 아래 내용은 원문에 등록된 참고 문헌들입니다.

*Bulk Synchronous Programming
L.G.Valiant.Abridgingmodelforparallelcomputation.
Communications of the ACM, 33(8):103–111, 1997.

**MPI primitives
William Gropp, Ewing Lusk, and Anthony Skjellum.
Using MPI: Portable Parallel Programming with the Message-Passing Interface.
MIT Press, Cambridge, MA, 1999.

***techniques such as active disks
L. Huston, R. Sukthankar, R. Wickremesinghe, M. Satya- narayanan, G. R. Ganger,
E. Riedel, and A. Ailamaki.
Di- amond: A storage architecture for early discard in inter- active search.
In Proceedings of the 2004 USENIX File and Storage Technologies FAST Conference,
April 2004.

Erik Riedel, Christos Faloutsos, Garth A. Gibson, and David Nagle.
Active disks for large-scale data process- ing.
IEEE Computer, pages 68–74, June 2001.

****Charlotte System
Arash Baratloo, Mehmet Karaul, Zvi Kedem, and Peter Wyckoff.
Charlotte: Metacomputing on the web.
In Pro- ceedings of the 9th International Conference on Parallel and
Distributed Computing Systems, 1996.

*****Condor
Douglas Thain, Todd Tannenbaum, and Miron Livny.
Distributed computing in practice: The Condor experi- ence.
Concurrency and Computation: Practice and Ex- perience, 2004.

블로그 이미지

마즈다

이미 마흔을 넘어섰지만 아직도 꿈을 좇고 있습니다. 그래서 그 꿈에 다가가기 위한 단편들을 하나 둘 씩 모아가고 있지요. 이 곳에 그 단편들이 모일 겁니다...^^

최초 작성일 : 2013/04/23 12:47 


지금까지의 MapReduce 사용에 있어 가장 주목할만한 점 한가지는 구글의 웹 검색 서비스에 사용되는
데이터 구조를 생성하는 production indexing 시스템을 완전히 다시 작성했다는 것이다.
indexing 시스템은 우리의 crawling 시스템이 검색해오는 대량의 문서 셋을 입력값으로 받아
GFS 파일 셋으로 저장한다. 이러한 문서 셋의 원본 내용들은 20 테라바이트 이상의 데이터들이다.
indexing 수행은 5개에서 10개 정도의 MapReduce 업무가 순차적으로 진행되면서 이루어진다.
(이전 버전의 indexing 시스템에서 ad-hoc distributed passes를 사용하는 대신에)MapReduce를
이용하는 것은 몇가지 이익을 준다.

• MapReduce 라이브러리 내에 오류(실패) 관리, 분산과 병렬 처리에 대한 코드들이 감춰져있기 때문에
  indexing 코드는 보다 단순하고 작고 이해하기 쉬워진다. 예를 들면 한 단위의 연산을 수행하는
  C++ 코드는 MapReduce로 구현할 겨웅 약 3800라인에서 700라인 정도로 감소한다.
 
• MapReduce 라이브러리는 개념적으로 관련이 없는 연산을 데이터에 대한 추가적인 전달을 회피하기 위해
  뒤섞어 놓는 대신에 서로 분리되도록 유지하는데 충분한 성능을 발휘한다.
  이 것은 indexing 프로세스을 변경하기 쉽게 하였다.
  일례로 예전의 indexing 시스템이 수개월 동안 걸려 처리한 변경작업을 새로운 시스템을 구현하여
  몇일만에 처리하였다.
 
• 머신의 고장, 느려진 머신, 네트워크의 일시적인 중단 등이 작업자의 개입 없이
  MapReduce에서 자동으로 관리되기 때문에 indexing 프로세스는 보다 운영하기 쉬워졌다.
  게다가 indexing 클러스터에 머신을 추가함으로써 indexing 프로세스의 성능을 개선하기도 쉬워졌다.

블로그 이미지

마즈다

이미 마흔을 넘어섰지만 아직도 꿈을 좇고 있습니다. 그래서 그 꿈에 다가가기 위한 단편들을 하나 둘 씩 모아가고 있지요. 이 곳에 그 단편들이 모일 겁니다...^^

최초 작성일 : 2013/04/19 12:57 


Experience

MapReduce 라이브러리의 최초 버전은 2003년 2웖에 만들어졌다.
그리고 locality 최적화, 작업자 머신들 간에 task 수행에 있어서의 동적인 로드 밸런싱 등  
괄목할만한 개선이 2003년 8월에 이루어졌다.

그 때부터 우리는 우리가 작업하는 곳에서 발생하는 다양한 문제점을 해결하는데 MapReduce 라이브러리가
얼마나 광범위하게 적용 가능한지를 알고 환호했다.

MapReduce는 Google 내의 광범위한 도메인에 사용되어 다음과 같은 역할을 하였다.

* 대규모 머신에서 배우는 문제들
* 구글 뉴스와 Froogle의 생산물에 대한 클러스링 문제들
* 인기있는 쿼리들(Google Zeitgeist같은)의 보고서에서 만들어지는 데이터의 추출
* 새로운 실험을 위한 웹페이지나 생산물들의 속성 추출 (예를들어 지역화된 검색을 위한 대규모
실험용 웹페이지로부터 지리적인 위치를 추출하는 것).
* 대규모 그래프 연산





Figure 4는 우리의 주요한 소스 코드 관리 시스템에 2003년 초 0개로부터 2004년 9월 말의
900개의 분산된 인스턴스에 이르기까지 등록된 분산 MapReduce 프로그램이 등록된 수의 주목할만한
성장을 보여준다.

MapReduce는 간단한 프로그램을 짜고 그 것을 수천대의 머신들에서 효과적으로 실행시키는데
30분 정도의 시간이면 가능하도록 하여 개발과 프로토타이핑의 속도를 매우 높였다는데 있어
꽤 성공적이다.

더 나아가서 분산이나 병렬처리 시스템경험이 없는 개발자들로 하여금 많은 양의 리소스를 쉽게
이용 가능하게 해준다.

MapReduce 라이브러리는 각각의 job 끝에 job이 연산에 사용한 자원들에 대한 통계를 로그로 남긴다.
Table 1은 2004년 8월 Google에서 실행된 MapReduce job들의 서브셋에 대한 통계를 보여준다.

블로그 이미지

마즈다

이미 마흔을 넘어섰지만 아직도 꿈을 좇고 있습니다. 그래서 그 꿈에 다가가기 위한 단편들을 하나 둘 씩 모아가고 있지요. 이 곳에 그 단편들이 모일 겁니다...^^

최초 작성일 : 2013/04/17 13:17 






Effect of Backup Task

Figure 3 (b)에서 우리는 backup task들이 비활성화된 정렬 프로그램의 실행을 볼 수있다.
프로그램 실행의 흐름은 과도한 쓰기 작업이 있는 경우에 완료 시점까지 long tail 현상이
나타난다는 것을 제외하면 Figure 3 (a)와 유사하다.

960초 이후 5개의 reduce task들을 제외한 모든 수행이 완료되었다. 그러나 이 마지막의
straggler들은 이후 300초가 지날 때까지 끝나지 않았다. 모든 연산은 1283초가 걸렸으며
소요시간이 44% 증가하였다.

Machine Failure

Figure 3 (c)에서는 연산 중에 1746개의 작업자를 제외한 200개의 작업자를 의도적으로
몇분간 중지시킨 상태의 실행을 보여준다.

x축 아래로 내려간 클러스터 스케쥴러는 즉시 머신들 상의 새 작업자로 재시작 되었다
(프로세스들이 죽었지만 머신들은 여전히 정상적으로 동작했다).

작업자가 죽는 것은 앞서 완료됐어야 할 몇몇 map 작업이 사라졌고(통신할 map 작업자가 죽었고)
그리고 이전 상태로 되돌려져야 하기 때문에 마이너스 입력 속도를 보여준다.

이러한 map 작업의 재실행은 비교적 신속하게 이루어진다.
전체 연산은 시작시의 부하를 포함해 933초만에 끝났다(일반적인 수행에 비해 단지 5%만 상승했다).

블로그 이미지

마즈다

이미 마흔을 넘어섰지만 아직도 꿈을 좇고 있습니다. 그래서 그 꿈에 다가가기 위한 단편들을 하나 둘 씩 모아가고 있지요. 이 곳에 그 단편들이 모일 겁니다...^^

최초 작성일 : 2013/04/11 12:22 


Sort

sort 프로그램은 10의 10승개의 100바이트 크기 레코드들을 정렬한다.(약 1테라바이트의 데이터이다.)
이 프로그램은 *TeraSort benchmark 이후에 모델링 되었다.

소팅 프로그램은 50 줄도 안되는 사용자 코드로 구성되어있다.
3줄의 Map 함수는 text문서의 라인으로부터 10바이트의 정렬 키를 추출하고
이 키와 원래 문서의 라인을 key/value 쌍으로 뽑아낸다.

우리는 라이브러리에 내장되어있는 Identity(항등)함수를 Reduce 연산자로 사용할 것이다.
이 함수는 중간형태의 key/value 쌍을 아무 변화 없이 출력 key/value 쌍으로 보낸다.
정렬된 최종 출력은 2방향으로 복제된 GFS 파일로 저장된다.
(프로그램의 출력 값으로 2테라바이트의 데이터가 작성된다.)

이전과 마찬가지로 입력 데이터는 64Mb 크기의 조각(M = 15000)으로 분할된다.
그리고 4000개(R = 4000)의 파일들에 정렬된 출력값들을 나누어 저장한다.
이 분할 함수는 데이터의 최초 바이트를 이용하여 분할된 R 중 하나에 출력값들을
나누어 넣게 된다.

이 벤치마크를 위한 분할 함수는 키 분산에 대한 지식 기반으로 만들어졌다.
우리가 MapReduce 수행의 전단계에 추가하려고 하는 일반적인 정렬 프로그램은
key들의 샘플을 모아서 마지막 정렬 단계를 위해 계산된 분할 포인트로 샘플 키들을
분산하는데 사용된다.





Figure 3의 (a)는 일반적인 정렬 프로그램의 실행을 보여준다.
좌측 상단이 그래프는 입력 값을 읽는 실행 속도를 보여준다.
실행 속도는 약 13 GB/s 정도에서 최고점에 이르렀다가 모든 map task가 종료 되기 전
200초 정도 지난 시점까지 상당히 빠르게 감소하다가 종료된다.

입력 값을 읽어들이는 실행 속도가 grep 함수 실행보다 짧다는 것에 주목하라.
이것은 정렬을 위한 map task들이 그들의 로컬 디스크에 중간 파일들을 저장하는데
절반 가량의 시간과 I/O 대역폭을 사용하기 때문이다.

grep을 위한 중간 형태의 출력 파일은 무시해되 될 정도의 크기이다.

좌측 중앙의 그래프는 데이터가 map task로부터 reduce task로 네트워크를 통해
전송되는 속도를 보여준다. 이 shuffling은 첫 번째 map task가 완료 되자마자 시작된다.
그래프에서 첫 번째로 높아진 부분은 약 1700여개의 reduce task들의 첫번째 배치 작업에 대한
값이다(전체 MapReduce는 약 1700여대의 머신들에 배치되어있고 각각의 머신은 한번에
최소한 1개의 reduce task를 실행한다).

연산이 진행되는 약 300초 동안 이 첫 번째 reduce task들의 배치 중 몇몇은 종료가 되고
남아있는 reduce task들을 위해 shuffling을 시작한다. 모든 shuffling은 약 600초 정도
연산을 수행한 후 완료된다.

좌측 하단의 그래프는 정렬된 데이터를 reduce task를 통해 최종 출력 파일에 저장하는 속도를 보여준다.
첫 shuffling이 끝나는 시점과 파일 기록 시점에는 지연이 발생하는데 이는 머신이 중간 데이터를
정렬하는데 부하가 걸리기 때문이다.

쓰기 작업은 잠시동안 약 2~4GB/s의 속도로 계속된다.
850초 무렵 정렬연산 내의 모든 쓰기 작업이 종료된다.

초기 기동시의 부하를 포함하여 전체 연산에는 891초가 소요되었다.
이 것은 현재까지 보고된 TeraSort 벤치마크의 가장 좋은 기록인 1057초와 근접한 값이다.

알아두어야 할 몇가지 사항은 우리의 로컬 최적화를 통해 대부분의 데이터가 비교적 제약이 있는
네트워크를 우회하여 로컬에서 읽혀지기 때문에 입력 속도는 shuffle 속도나 출력 속도보다 빠르다는
것이다. shuffle 속도는 출력 속도보다 빠른데 이는 출력 단계에서는 정렬된 데이터를 복사하여
2벌의 데이터를 기록하기 때문이다(우리는 신뢰성과 가용성을 높이기 위해 출력 데이터의 복제본을
만든다). 우리는 2개의 복제된 데이터를 기록하는데 이는 신뢰성과 가용성이 우리의 기반
파일시스템으로부터 제공받도록 만들어진 메커니즘 때문이다.

복제가 아닌 삭제 기능의 코드를 사용할 경우 데이터 기록을 위한 네트워크 대역폭에 대한 요구는
더욱 감소한다.
 


*TeraSort benchmark
Jim Gray. Sort benchmark home page.
http://research.microsoft.com/barc/SortBenchmark/.

블로그 이미지

마즈다

이미 마흔을 넘어섰지만 아직도 꿈을 좇고 있습니다. 그래서 그 꿈에 다가가기 위한 단편들을 하나 둘 씩 모아가고 있지요. 이 곳에 그 단편들이 모일 겁니다...^^

최초 작성일 : 2013/03/26 12:54


Performance

이번 장에서는 대규모 클러스터에서 돌아가는 2개의 연산에 대한 MapReduce의 성능을
측정해 볼 것이다.

연산 중 하나는 약 1테라바이트 크기의 데이터로부터 특정 패턴을 검색하는 연산이고
다른 하나는 약 1테라바이트 크기의 데이터를 정렬하는 연산이다.
이 두 프로그램은 MapReduce 사용자가 작성한 실제 프로그램으로부터 구현한 큰 규모의
서브셋이다. 프로그램들을 구성하는 클래스 하나는 어떤 위치로부터 다른 위치로 재구성을
수행하고 다른 클래스는 커다란 데이터 덩어리에서 관심있는 적은 양의 데이터를 추출한다.


Cluster Configuration

모든 프로그램들은 약 1800대의 머신으로 구성된 클러스터상에서 실행된다.
각가의 머신은 하이퍼스레딩이 가능한 2Ghz의 제온 프로세서 2개와 4Gb의 메모,
그리고 2개의 160Gb의 IDE 하드 디스크를 가지고 있으며 기가비트 이더넷으로
연결되어있다.

이 머신들은 총 100~200Gbps의 대역폭을 갖는 스위칭 네트워크 내에 2단계의
트리 구조로 배치가 되어있다. 모든 머신들은 동일한 호스팅 시설 내에 있기 때문에
한 쌍의 머신들 사이에서 데이터 왕복 시간은 1/1000초보다도 작다.
총 4Gb의 메모리 중 약 1~1.5Gb는 클러스터상의 다른 task 수행을 위해 예약되어있다.

프로그램들은 CPU와 디스크와 네트워크의 대부분이 idle 상태인 주말 오후에 실행이 되었다.


Grep
 
비교적 드물게 나타나는 3음절 패턴을 검색하기 위해 grep 프로그램은
100바이트의 레코드들을 10의 10승만큼 스캔한다(3음절 패턴은 92,337개의
레코드에서 발견되었다).
입력은 대략 64Mb의 조각(M = 15000)으로 나뉘고 전체 출력은 하나의 파일에
저장된다(R = 1).



Figure 2는 전체 시간동안의 연산 과정을 보여준다.
Y축은 입력 데이터의 스캔률을 보여준다.

더 많은 머신들에 이 MapReduce 연산이 할당될 수록 스캔률은 서서히 증가한다.
그리고나서 1764개의 작업자가 할당되었을 때 최고점은 30 GB/s를 넘어섰다.
map task가 끝나면서 스캔률은 떨어지기 시작하고 연산 수행 시간이 80초 정도 되었을 때 0이 되었다.

전체 연산 수행 시간은 시작에서 종료까지 약 150초가 걸렸다.
이 150초에는 약 1분 정도의 초기 구동에 대한 부하가 포함되어있다.
이 부하는 모든 작업자 머신에 프로그램을 전달하는 것과 1000개의 입력 파일을
열기 위해 GFS(Google File System)과 통신하는 데 발생하는 지연, 그리고
로컬 디스크의 최적화를 위해 필요한 정보를 수집하는데 발생한 것이다.

블로그 이미지

마즈다

이미 마흔을 넘어섰지만 아직도 꿈을 좇고 있습니다. 그래서 그 꿈에 다가가기 위한 단편들을 하나 둘 씩 모아가고 있지요. 이 곳에 그 단편들이 모일 겁니다...^^

최초 작성일 : 2013/03/20 12:16 


Status Information

master는 내부에 HTTP 서버를 실행시켜 사용자가 볼 수 있도록 일련의 상태 정보 페이지를
출력한다. 이 상태 페이지는 얼마나 많은 task가 완료 되었는지, 얼마나 많은 task가 수행 중인지,
입력 바이트 수, 중간 데이터의 바이트 수, 출력 바이트 수, 처리율 등의 연산 수행에 대한
진행 상태를 보여준다.

또한 이 페이지에는 표준 에러나 각각의 task에서 생성한 표준 출력 파일에 대한 링크도 제공한다.

사용자들은 이러한 데이터통해 연산이 얼마나 걸릴 지, 연산에 추가 리소스가 필요한지 예측할 수 있다.
이 페이지들은 또한 예상했던 것 보다 더 느려지는 지점을 밝혀내는 데도 사용할 수 있다.

추가적으로 상위의 상태 페이지는 어떤 작업자가 실패했는지, 그리고 그 실패 시점에 어떤 map과
reduce task들이 수행되고 있는지를 보여준다. 이 정보는 사용자 코드에서 버그 진단을 시도할 때
유용하다.

Counter

MapReduce 라이브러리는 현재 발생한 다양한 이벤트를 카운트하기 위해 카운터 장치를 제공하고 있다.
예를들면 사용자 코드가 작성된 모든 단어의 수를 알고자 할 경우도 있고 색인화 된 독일어 문서의 수를
찾고자 할 수도 있다.

이 카운터 장치를 이용하게 되면 사용자 코드는 이름이 붙은 카운터 객체를 생성하게 되고
Map과(또는) Reduce 함수 내에서 적절하게 카운터를 증가시키게 된다.

다음은 그 예이다.

Counter* uppercase;
  uppercase = GetCounter("uppercase");
map(String name, String contents): for each word w in contents:
      if (IsCapitalized(w)):
        uppercase->Increment();
      EmitIntermediate(w, "1");

개별적인 작업자 머신으로부터 생성된 카운터 값은 주기적으로 master에게 전송한다
(이 전송은 ping에 대한 응답에 같이 실려간다). master는 성곡적으로 수행된
map과 reduce task들로부터 전송된 카운터 값들의 총합을 계산하여 MapReduce 수행이
완료되면 사용자 코드에 그 값을 리턴해준다.

현재의 카운터 값들은 master의 상태 페이지에 표시되고 사용자는 그 것을 통해 현재 살아있는
프로세스들의 진행 상태를 볼 수 있다. 카운터 값들을 합산할 때 master는 중복해서 카운팅하는
것을 피하기 위해 같은 map 또는 reduce task에서의 중복된 수행들을 제거한다.
(중복 수행은 백업 task라든지 실패에 의한 재시작 등을 사용할 때 발생한다)

수행된 입력 key/value쌍들이나 생성된 출력 key/value쌍들의 수 처럼 어떤 카운터 값들은
MapReduce 라이브러리에 의해 자동으로 관리된다.

어떤 MapReduce 수행에서는 사용자의 코드가 입력쌍과 출력쌍의 수가 정확히 일치할 것을
보장받길 원하고, 혹은 독일어 문서의 일부분에 대한 처리가 전체 문서 처리의 허용된 범위 내에
있기를 원할 수도 있기 때문에 사용자들은 카운터 장치가 MapReduce 수행 동작이 정상적인지를
확인하는 데 유용하다는 것을 알 수 있을 것이다.

블로그 이미지

마즈다

이미 마흔을 넘어섰지만 아직도 꿈을 좇고 있습니다. 그래서 그 꿈에 다가가기 위한 단편들을 하나 둘 씩 모아가고 있지요. 이 곳에 그 단편들이 모일 겁니다...^^