최초 작성일 : 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:54 


먼저 관련 기사입니다.

http://www.zdnet.co.kr/news/news_view.asp?artice_id=20130319082909

2010년에 처음 iOS 개발을 해보겠다고 다니던 회사를 그만 두고 공부를 시작했습니다.

그리고 1년동안 허접한 앱 2개를 만들어 앱스토어에도 올려보고...

2011년 5월부터 10월까지는 iOS 개발 프리랜서로 프로젝트 2개를 뛰었네요.

그리고 2011년 11월 계속 프리를 할 것인지 다시 정규직으로 갈 것인지에 대해

고민을 많이 했더랬죠.

일단 정규직으로 가기로 한 후 구직을 시작했는데 그 때는 단지 iOS 개발에 국한시키지 않았습니다.

그런데 그 당시 눈에 들어온 기업이 있었는데 넥스알이라는 하둡 전문 업체였습니다.

솔직히 당시 구인 광고에 '입사자 전원 아이패드 지급'이라는 문구가 있어 밑도끝도 없이

이력서를 넣었지요. 하둡이 뭔지도 모르고 말입니다...^^

사용자 삽입 이미지

중요한 것은 지금부터인데...

만일 그 때

하둡이란 것이 이렇게 뜰 줄 알았다면 진로를 아예 바꾸진 못했겠지만 나름

하둡과 빅데이터 관련된 공부를 열심히 해뒀을텐데 말이죠...

그냥 무심결에 지나쳐버린 것이 조금 아쉽네요...^^;;;

하지만 지금도 늦지 않았다는 생각에 공부를 시작하긴 했습니다.

작년 말부터 생각해왔던 것이지만 이미 모바일에서도 예전 PC에서와 같은

변화가 생겨나고 있다고 보여집니다.

초창기 PC는 그 자체로 유용한 물건이었고 사람들은 주로 네이티브 프로그램을

사용하기 위해 PC를 이용했죠. 하지만 웹이 생겨나고 브라우저가 운영체제로 들어오면서

PC 사용의 많은 부분이 인터넷을 통한 컨텐츠의 소비와 서비스의 이용으로 옮겨지게 되었습니다.

현재의 모바일 또한 다르지 않을 것이라 생각합니다.

이미 스마트폰의 이용 통계에서도 드러난 사실들이지만

게임을 제외한다면 가장 많은 비중을 차지하고 있는 앱들 혹은 이용 행태는

기존에 이미 웹으로 서비스 되고 있는 것들이거나 아니면 모바일을 대상으로 하는

새로운 서비스들입니다.

조금 과장해서 말하자면 PC와 마찬가지로 (서버를 통해 제공되는) 서비스가 없는

스마트폰은 깡통으로 전락하게 될지도 모르는 일이죠...^^;;;

요점은 (게임 개발을 논외로 한다면) 안드로이드든 iOS든 단말쪽의 네이티브 앱 개발로는

미래가 그리 밝지 않다는 것이죠.

또 한편으로는 '개발자'라는 마인드가 단말 개발에만 머물지 않게 하기도 할겁니다.

마치 자바 개발자가 테스트를 위해 톰캣이나 오라클 정도는 설치해봐야 하는 것처럼...

썰이 좀 길었네요.

누군가에게 조언할 처지는 못되니 그냥 제 꿈을 말하자면

좀 더 넓은 시각을 가지고 큰 그림을 그릴 수 있는 개발자가 되고싶을 뿐입니다...^^

블로그 이미지

마즈다

이제 반백이 되었지만 아직도 꿈을 좇고 있습니다. 그래서 그 꿈에 다가가기 위한 단편들을 하나 둘 씩 모아가고 있지요. 이 곳에 그 단편들이 모일 겁니다...^^

댓글을 달아 주세요

최초 작성일 : 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 수행 동작이 정상적인지를
확인하는 데 유용하다는 것을 알 수 있을 것이다.

블로그 이미지

마즈다

이제 반백이 되었지만 아직도 꿈을 좇고 있습니다. 그래서 그 꿈에 다가가기 위한 단편들을 하나 둘 씩 모아가고 있지요. 이 곳에 그 단편들이 모일 겁니다...^^

댓글을 달아 주세요

최초 작성일 : 2013/03/07 13:07 


Input and Output type


MapReduce 라이브러리는 몇가지 서로 다른 형식의 입력 파일을 읽을 수 있다.

예를들면 "text"모드의 입력은 각각의 행이 key/value 쌍으로 취급된다. key는 파일상의

위치(행)가 되고 value는 그 행의 내용이 되는 것이다.

일반적으로 지원하는 또다른 형식은 일련의 key/value 쌍을 key로 정렬하여 저장한다.


각각의 입력 형식의 구현은 분산된 map task에서의 처리를 위해 어떤식으로 의미있는

단위로 분할해야 하는가를 알고있다 (예를들면 text 모드에서는 행 단위로 영역이 구분되므로

행 단위로 분할을 하게 되는 것이다).


대부분의 사용자들은 이미 정의된 소수의 입력 형식을 사용하겠지만 사용자들은 간단하게 reader 인터페이스를

구현함으로써 새로운 입력 형식을 추가로 제공할 수 있다.


reader 인터페이스는 파일로부터 데이터를 읽어들이는데만 필요한 것은 아니다.

예를들면  데이터베이스로부터 레코드를 읽어들인다거나 메모리에 매핑된 데이터 구조로부터 데이터를

읽어들이는 기능을 정의하기도 쉽다.


이와 비슷하게 우리는 서로 다른 형식으로부터 만들어진 데이터를 위한 출력 형식도 제공하고 있으면

이 역시 입력 형식과 마찬가지로 사용자가 새로운 출력 형식을 추가할 수 있다.


Side-effects (부작용)


때때로 MapReduce 사용자들은 사용하는 map이나 reduce 작업으로부터 추가적인 출력으로

보조 파일을 생성하는 것이 편리하다는 것을 알게된다. 우리는 이러한 부작용이 단편적이고 서버의

상태를 바꾸지 않도록(*idempotent) 하는데 애플리케이션 개발자들에게 의존할 수 밖에 없다.


일반적으로 애플리케이션은 임시 파일에 작성되며 이 파일이 완전하게 생성되었을 때 단 한 번 이름이 바뀌게 된다.


우리는 하나의 task로부터 생성된 여러개의 출력 파일들에 대해 2단계의 commit을 수행하는 것을 허용하지 않는다.

따라서 다수의 파일을 생성하고 그 파일들 간의 일관성이 요구되는 task들은 반드시 동일한 결과를 출력해야 한다.

이러한 제약은 실제 사용상에는 아무런 문제가 되지 않는다.


Skipping Bad Records


때때로 사용자들의 코드에는 버그가 있고 이는 확실해 보이는 레코드처리시 Map 또는 Reduce 함수가

죽는 원인이 된다. 이러한 버그는 MapReduce 수행이 완전하게 종료되는 것을 방해한다.

보통의 상황이라면 버그를 수정해야 한다. 그러나 때때로 수정이 불가능하거나 수정하지 않아도 되는 경우도 있다.

대체로 버그가 소스를 수정할 수 없는 외부 업체의 라이브러리내에 있는 경우가 그러할 것이다.

또 다른 경우에는 커다란 데이터 셋을 이용하여 통계적인 분석을 하는 경우처럼  몇몇 레코드를 무시하는 선에서

(버그가)용인될 수도 있다.


우리는 MapReduce 라이브러리에서 결정적인 문제를 일으킨 레코드를 감지하고 이를 걸러내어

다음 단계를 진행할 수 있도록  프로그램을 실행에 대한 몇가지 선택적인 설정을 제공하고 있다.


각각의 작업자 프로세스는 각각의 분할 영역에서의 오류나 전송 오류를 잡아내는 signal handler를 설치한다.

사용자의 Map이나 Reduce 수행을 호출하기 전에 MapReduce 라이브러리는 전역 변수에 전달 받은 인자의

순번을 저장한다. 사용자의 코드가 signal를 발생시키면 이 signal handler는 앞서 저장한 순번을 포함하고 있는

마지막 순간의 UDP 패킷을 MapReduce의 master에게 보낸다. master가 특정 레코드에 대해 1개 이상의

오류를 가지고 있을 경우 master는 해당 Map 또는 Reduce task가 재실행 될 때  그 레코드가 걸러져야 함을

알려주게 된다.


Local Execution


Map 또는 Reduce 함수 내의 디버깅 문제는 실제 연산이 분산 환경(때로는 수 천대에 이르는)에서 이루어지는데다가

작업 할당의 결정이 master에 의해 동적으로 이루어지기 때문에 다루기가 까다롭다.


쉬운 디버깅이나 profiling, 소규모 테스트를 돕기 위해 우리는 MapReduce 라이브러리에

로컬 머신에서 MapReduce 수행의 모든 작업을 순차적으로 진행할 수 있도록 대안을 마련해놓았다.


사용자들에게 제공된 컨트롤들은 특정 map task를 위한 연산에서는 제약적일 수 있다.

사용자들은 특정 플래그를 이용하여 자신들의 프로그램을 호출할 수 있고 자신에게 유용한 디버깅 툴이나

테스트 툴을 쉽게 사용할 수 있다.


* idempotent(멱등 :冪等) 메서드를 여러 번 호출하여 한 번만 호출한 것과 동일한 결과가 나오는 경우. 읽기 전용 메서드와 같이 서버 측의 어떠한 상태도 변화시키지 못하는 모든 메서드는 idempotent임

블로그 이미지

마즈다

이제 반백이 되었지만 아직도 꿈을 좇고 있습니다. 그래서 그 꿈에 다가가기 위한 단편들을 하나 둘 씩 모아가고 있지요. 이 곳에 그 단편들이 모일 겁니다...^^

댓글을 달아 주세요

최초 작성일 : 2013/02/26 12:58 


Map과 Reduce 함수를 작성하는 기본 기능이 대부분의 필요를 충족시켜주기는 하지만

여기서 보다 확장된 유용한 기능들을 설명하고자 한다.


Partitioning Function


MapReduce의 사용자는 그들이 원하는 reduce task들과 출력 파일의 수를 ( R )과 같이 명시한다.

Data들은 중간 key를 이용하는 partitioning 함수에 의해 이 task들 상호간에 분할된다.


기본적인 분할 함수는 해싱을 이용해 제공된다.(예를들면 "hash(key) mod R" 과 같은 형태다)

이러한 분할 함수는 꽤 균형이 잘 잡힌 분할을 만들어낸다. 그러나 몇몇 경우에는 다른 함수들이 데이터를

분할하는데 더 유용하다.


예를들면 때때로 출력된 key들은 URL들인 경우가 있고 우리는 단일 호스트에 대한 목록만을 동일한 출력 파일에

정리하고 싶을 때가 있다. 이런 상황을 지원하기 위해 MapReduce 라이브러리 사용자들은 특별한 분할 함수를

제공할 수 있다. 분할 함수를 "hash(Hostname(key)) mod R"과 같이 사용하여 동일한 최종 출력 파일에

동일한 host의 모든 URL을 이끌어낼 수 있다.



Ordering Guarantees


우리는 주어진 분할 영역 내에서 중간 key/value 쌍들이 증가하는 key 값으로 정렬된다는 것을 보장받을 수 있다.

이러한 정렬에 대한 보장은 각각의 분할 영영에서 정렬된 출력 파일을 쉽게 생성하도록 해준다.

이렇게 잘 정렬된 파일은 출력 파일 형태가 키를 이용하여 효율적인 랜덤 엑세스 검색을 지원해야 하거나 사용자가 출력파일이

정렬되어있을 때 편리한 경우에 유용하다.


Combiner Function


어떤 경우에는 각각의 map task가 중간 key들을 생성해 내거나 사용자가 정의한 Reduce 함수가 교환되거나

합쳐지는데 중요한 반복이 생기는 경우가 있다.


이에 대한 좋은 예는 2.1장에서 예시한 단어 세기 예제이다.


단어 발생의 빈도는 *Zipf의 빈도에 따른 경향이 있기 때문에 각각의 map task들은 <the, 1> 쌍으로부터 수백에서

수천의 결과를 만들어낼 수가 있다. 이렇게 생성된 결과의 모든 수는 네트워크를 통해 하나의 reduce task에게 보내지고

하나의 수를 도출하기 위해 Reduce 함수에 의해 서로 더해진다. 우리는 결과물이 네트워크를 통해 전송되기 전에

이 데이터들을 부분적으로 병합할 수 있는 사용자 정의 결합 함수를 사용할 수 있도록 허용하고 있다.


결합 함수는 map task가 수행되는 각각의 머신에서 실행된다. 일반적으로 결함 함수와 reduce 함수는

같은 코드를 이용하여 구현된다. 유일한 차이점이라면 MapReduce 라이브러리가 각각의 출력 결과물을

어떻게 처리하는가이다. reduce 함수의 결과물은 최종 출력 파일에 기록된다. 결합 함수의 결과물은

reduce task로 보내지는 중간 파일에 기록된다.


부분 결합은 MapReduce의 어떤 클래스에서는 상당히 빠르다.

예제는 Appendix A에 수록되어있다.




*Zipf의 법칙 : 어떤 단어들의 집합에서 가장 빈도 수가 높은 단어를 기준으로 했을 때 두 번째로 빈도수가 높은 단어는 첫번째 단어의

1/2, 세 번째로 빈도수가 높은 단어는 첫번째 단어의 1/3…k번째 단어는 1/k가 된다는 법칙

이 법칙은 단어들의 빈도 수 외에 도시들의 인구 순위, 소득 분포, 신문이나 웹사이트의 독자, 지진 등의 빈도에도 적용이 된다.

블로그 이미지

마즈다

이제 반백이 되었지만 아직도 꿈을 좇고 있습니다. 그래서 그 꿈에 다가가기 위한 단편들을 하나 둘 씩 모아가고 있지요. 이 곳에 그 단편들이 모일 겁니다...^^

댓글을 달아 주세요

최초 작성일 : 2013/02/25 12:56 


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

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

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

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


Locality(지역성)


네트워크 대역폭은 우리의 컴퓨팅 환경에서 비교적 부족한 자원이다.

우리는 클러스터를 구성하고 있는 머신들의 로컬 디스크에 GFS(Google File System)에 의해

관리되는 입력 데이터를 저장함으로써 네트워크 대역폭을 절약할 수있다.


GFS는 각각의 파일을 64Mb의 블럭으로 분할한 후 각각의 블럭에 대해 몇개의 복사본(보통 3개)을

서로 다른 머신들에 저장한다. MpaReduce의 master는 입력 파일들의 위치 정보를 고려하여

입력 데이터에 적합한 복사본이 있는 머신에서 map task의 스케쥴링을 시도한다.


만일 실패하는 경우 그 task의 입력 데이터의 복사본이 있는 가까운 머신(같은 네트워크 스위치에 물려있고

동일한 데이터를 가지고 있는 머신)에서 map task의 스케쥴링을 시도한다.


큰 규모의 MapReduce 작업이 클러스터 내의 중요한 부분에서 수행될 경우 대부분의 입력 데이터는

네트워크 대역폭을 사용하지 않고 로컬 디스크에서 읽혀지게 된다.



Task Granularity


우리는 위에 설명한 M개의 map 수행 단계와 R개의 reduce 수행 단계를 더 세분화 할 수 있다.


이상적으로 생각한다면 M과 R은 작업자 머신보다 더 많은 수여야 한다.

각각의 작업자가 서로 다른 많은 task들을 수행하는 것은 동적 로드밸런싱을 향상시키고

작업자가 실패했을 경우 복구시간을 빠르게 해준다. 전체 머신들에서 이렇게 완료된 map task들이

늘어나게 된다.


이 때문에 master가 O(M+R) 개의  스케쥴링 결정을 만들어야 하고 이전에 설명한 것과 같이 O(M*R)개의 상태가

메모리에 유지되어야 하기 때문에 우리의 구현에서는 M과 R의 크기가 얼마나 되어야 하는가 하는 실질적인 허용 범위가 있다.

(메모리 사용량에 대한 상수 인자들이 아무리 작아도 O(M*R) 개의 상태들은 하나의  map task / reduce task 쌍에 대하여

약 1byte의 데이터로 구성되어있다.)


 게다가 보통 R의 수는 사용자로부터 제약을 받는데 이는 각각의  reduce task의 출력들이 분할된 출력 파일들 내에서

처리되기 때문이다.


실제로 우리는 각각의 크기가 대체로 16Mb에서 64Mb정도인 입력 데이터를 가진 개별적인 task M개를 선택하고

(이러한 이유 때문에 위에 설명한 지역성의 최적화가 더욱 효과적인다.) 우리가 사용하고자 하는 다수의

작업자 머신에서 R을 약간 작게 만든다.


우리는 보통 M = 200,000 개, R = 5,000 개 2000의 작업자 머신에서 MapReduce 연산을 수행한다.



Backup tasks


MapReduce의 총 수행 시간이 길어지게 되는 일반적인 이유는 "straggler" 때문이다.

"straggler"는 전체 연산 중 가장 나중에 수행된 몇몇 map 또는 reduce task들의 완료가 매우 오래걸린

머신들을 말한다.


Straggler들은 전체 호스트에서 그 원인을 찾을 수 있다.

예를 들면, 결함있는 디스크를 가진 머신은 읽기 성능을 30MB/s에서 1MB/s까지 떨어뜨리는

수정 가능한 오류를 자주 발생시킨다. 클러스터 스케쥴링 시스템은 MapReduce 코드가 CPU, 메모리, 로컬디스크 또는

네트워크 등의 자원에 대한 경쟁에서 보다 느려지기 때문에 MapReduce가 아닌 다른 task를 이 머신에

할당하게 된다.


우리가 최근 겪었던 문제는 머신 초기화 코드에 있던 버그인데 이는 프로세서의 캐시를 사용할 수 없도록 했다.

이 문제에 영향을 받은 머신들에서 연산 속도가 1/100이상 감소했다.


우리는 stragglers의 문제를 완화시킬만한 일반적인 매커니즘을 가지고 있다.

MapReduce의 수행이 종료 시점에 다다를 쯤, master는 나머지 수행중인 task들을 실행하는

백업 스케쥴을 시행한다. task는 원본이든지 백업이든지 상관없이 실행이 완료되는 시점에 완료된 것으로 표시된다.


이 매커니즘을 조정하여 MapReduce 수행에 사용되는 컴퓨터상의 자원들을 전반적으로 증가시켰다.

우리는 이러한 작업이 큰 규모의 MapReduce의 수행에 있어 상당한 시간을 줄인다는 것을 발견하였다.


일례로, 이후에(원문상의 5.3절)에 설명하게되는 정렬 프로그램은 backup task 메커니즘을 사용하지 않을 경우

완료시간이 44%나 늘어나게 된다.

블로그 이미지

마즈다

이제 반백이 되었지만 아직도 꿈을 좇고 있습니다. 그래서 그 꿈에 다가가기 위한 단편들을 하나 둘 씩 모아가고 있지요. 이 곳에 그 단편들이 모일 겁니다...^^

댓글을 달아 주세요

최초 작성일 : 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 R그리고  R2 를 생각해보자.
e(Ri)이 commit된  Ri 을 실행하도록 하면.(정확히 한 번만 실행을 한다)  e(R1)은 M의 실행 중 하나로부터
생성된 출력을 읽게될 것이고 e(R2)는 M의 다른 실행으로부터 생성된 출력을 읽게 되는 약한 의미체계가
발생하게 된다.

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

*deterministic algorithm

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

**non-deterministic algorithm

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

블로그 이미지

마즈다

이제 반백이 되었지만 아직도 꿈을 좇고 있습니다. 그래서 그 꿈에 다가가기 위한 단편들을 하나 둘 씩 모아가고 있지요. 이 곳에 그 단편들이 모일 겁니다...^^

댓글을 달아 주세요

최초 작성일 : 2013/02/05 15:23 


==============================================
오늘은 MapReduce라이브러리와 이 라이브러리를 사용하는, 개발자가 작성한
Map / Reduce 함수의 전체적인 프로세스를 설명하는 부분이며 삽입된 그림을
기반으로 일련의 작업 순서를 설명하고 있습니다.

입력 데이터

사용자 프로그램 - master - map worker - reduce worker - 중간데이터

출력데이터

요러한 요소들의 관계를 집어가면서 보시면 될겁니다.

글이 긴 만큼 번역이 개판인데...그냥 그림 참조하셔서 보세요...^^;;;
==============================================

MapReduce 인터페이스는 다양한 형태로 구현할 수 있는데 어떤 구현을 사용할 것인가 하는 것은
운영 환경에 따라 달라진다.

예를 들면 적은 용량의 공유메모리를 가진 머신이나 큰 NUMA(메모리와 CPU가 한 셋을 이루는 프로세서)
다중 프로세서를 가진 머신, 혹은 대량의 네트워크 머신들의 집합 등과 같이 각각의 환경에 따라
다른 구현이 쓰이는 것이다.

이번 글에서는 구글에서 널리 쓰이는 switch 이더넷으로 연결된 상용 PC들의 커다란 클러스터 
환경 하에서의 구현에 초점을 두고 살펴보도록 하겠다.

일단 환경은 이렇다 :

1. 일반적으로 각각의 머신은 듀얼코어의 X86 프로세서에 2~4Gb의 시스템 메모리를 가지고 있으며 운영체제는 리눅스이다.

2. 네트워크 장비는 일반적으로 각 머신 수준에서 100Mb 랜이나 기가비트 랜을 사용하나
평균적인 속도는 전체 양 끝단의 대역폭에 비해 상당히 느리다.

3. 하나의 클러스터는 수 백 대에서 수 천 대로 구성되므로 머신의 오작동은 일반적인 일이다.

4. 저장 공간은 각각이 머신에 직접 장착된 저가의 IDE 하드 디스크이다. 구글에서 개발된
분산 파일 시스템은 이 디스크들에 저장된 데이터를 관리하게 된다. 이 분산 파일 시스템은
신뢰할 수 없는 머신 상에서 효용성과 신뢰성을 제공하기 위해 데이터의 '복제'를 이용한다.

5. 사용자들은 스케쥴링 시스템에 job을 제출한다. 각각의 job은 일련의 task로 구성되고
스케쥴러에 의해 클러스터 내의 사용 가능한 일련의 머신들에 매핑된다.


MapReduce의 실행 개요

Map 호출코드는 입력 데이터들을 M개로 나누어진 세트로 분할하면서 자동으로 다수의 머신들에 분산된다.
이렇게 입력된 분할체들은 가각의 서로 다른 머신에서 병렬로 처리될 수 있다.
Reduce 호출코드는 분할 함수(예를 들면 hash(keymod R)를 통해 중간형태의 key 영역을
R개의 조각에 분할하여 넣음으로써 역시 다수의 머신에 분산된다.





위 그림은 구글에서 구현한 MapReduce 운용에 대한 흐름을 보여준다.
사용자의 프로그램이 MapReduce 함수를 호출하면 아래와 같은 일련의 action이 발생한다.


1. 사용자 프로그램에 포함된 MapReduce 라이브러리가 우선 입력 파일을 분할하여

 M 조각들로 집어넣는다 조각들은  16~64Mb 정도의 크기를 가지며  크기는

사용자들이 옵션 인자를 통해 조절 가능하다그리고나서  프로그램의 복사본들이

클러스터 내의 머신들로 복사되기 시작한다.


2.  복사본들  하나는 master라고 하여 특별한 기능을 수행한다.

나머지의 것들은 master 의해 할당된 작업을 수행하는 작업자들이다.

M개의 map task R개의 reduce task 할당 되었다고 해보자. master 쉬고있는

작업자들을 찾아내  map task reduce task  하나를 할당한다.


3. map task 할당된 작업자는 입력 분할체에 해당하는 contents 읽는다.

 작업자는 읽어들인 contents로부터 key/value 쌍을 뽑아내고 각각의 쌍들을 사용자가

작성한 Map 함수로 전달한다이렇게 Map 함수로부터 생성된 중간형태의 key/value쌍은

메모리 버퍼에 저장된다.


4. 주기적으로 버퍼에 저장된 쌍들은 로컬 디스크에 저장되며 분할 함수에 의해 R개의

영역으로 분할된다버퍼에 저장된 쌍들이 로컬 디스크에 저장된 위치는 다시 master에게

전달되며 master 책임지고 전달받은  위치를 reduce 업무를 할당받은 작업자에게 할당해준다.


5. reduce 작업자가 master로부터  위치에 대해 알림을 받으면  작업자는

원격 프로시져 콜을 이용해 map 작업자의 로컬 디스크로부터 저장된 버퍼 데이터를 읽어들인다.

reduce 작업자가 모든 중간데이터를 읽어들이고난  reduce 작업자는 중간데이터의

key 중심으로 데이터를 정렬하게 되고 존재하는 모든 동일키는 그룹으로 묶인다.

보통 많은 서로 다른 맵의 키들이 같은 reduce task 전달되기 때문에 정렬이 필요하다.

만일 데이터가 너무 커서 메모리가 부족할 경우에는 외부(외부 저장장치를 사용한정렬이

사용되기도 한다.


6. reduce 작업자는 모든 정렬된 중간 데이터에 걸쳐서 유일한 중간 키가 도출될 때까지

 작업을 반복하며 이렇게 도출된 키와 키에 해당하는 중간 값들의 세트를 사용자가

작성한 Reduce 함수로 전달한다. Reduce 함수의 출력값은 최종 출력 파일에 추가된다.


7. 모든 map task reduce task 완료되면 master 사용자 프로그램을 호출하게 되고

 시점에서 MapReduce 호출은 사용자의 코드를 반환하게 된다.




이 일련이 과정들이 성공적으로 완료된 후 mapreduce 실행의 결과는 R개의 출력 파일 내에서

볼 수 있을 것이다.(한 개의 reduce task당 R개의 파일이 생성되면 파일명은 사용자가 정의한다)



이렇게 출력된 R개의 출력 파일을 하나로 묶을 필요는 없다.
보통은 이 파일들을 또다른 MapReduce 수행의 입력파일로 사용되거나
다수의 파일들에 분할된 입력값을 다룰 수 있는 다른 분산 어플리케이션에 사용되기 때문이다.

블로그 이미지

마즈다

이제 반백이 되었지만 아직도 꿈을 좇고 있습니다. 그래서 그 꿈에 다가가기 위한 단편들을 하나 둘 씩 모아가고 있지요. 이 곳에 그 단편들이 모일 겁니다...^^

댓글을 달아 주세요

최초 작성일 : 2013/01/31 14:58 


Big Data : 

기존 데이터베이스 관리도구의 데이터 수집·저장·관리·분석의 역량을 넘어서는 대량의 정형 또는 비정형 데이터 세트 및 이러한 데이터로부터 가치를 추출하고 결과를 분석하는 기술...

데이터 양(Volume),
데이터 속도(Velocity),
그리고 데이터 다양성(Variety) 등
세 가지 요소의 복합적인 변화를 그 특징으로 한다.

Big Data 분석 기법 :

  • Text Mining(Text mining) : 텍스트 마이닝은 비/반정형 텍스트 데이터에서 자연 언어 처리 기술에 기반하여 유용한 정보를 추출, 가공하는 것을 목적으로 하는 기술이다.
  • 평판 분석 (Opinion mining) : 오피니언 마이닝은 소셜미디어 등의 정형/비정형 텍스트의 긍정, 부정, 중립의 선호도를 판별하는 기술이다.
  • 소셜 네트워크 분석 (Social network analysis) : 소셜 네트워크 분석은 소셜 네트워크 연결구조 및 연결강도 등을 바탕으로 사용자의 명성 및 영향력을 측정하는 기술이다.
  • 군집 분석 (Cluster Analysis) : 군집 분석은 비슷한 특성을 가진 개체를 합쳐가면서 최종적으로 유사 특성의 군을 발굴하는데 사용된다.

  • R (프로그래밍 언어) : 

    통계 계산과 그래픽을 위한 프로그래밍 언어이자 소프트웨어 환경이다.
    ...
    R은 통계 소프트웨어 개발과 자료 분석에 널리 사용되고 있으며, 패키지 개발이 용이하여 통계학자들 사이에서 통계 소프트웨어 개발에 많이 쓰이고 있다.

    Hadoop (하둡) :

    대량의 자료를 처리할 수 있는 큰 컴퓨터 클러스터에서 동작하는 분산 응용 프로그램을 지원하는 자유 자바 소프트웨어 프레임워크이다. 원래 너치의 분산처리를 지원하기 위해 개발된 것으로, 아파치 루씬의 하부 프로젝트이다. 분산처리 시스템인 구글 파일 시스템을 대체할 수 있는 하둡 분산 파일 시스템(HDFS: Hadoop Distributed File System)과맵리듀스를 구현한 것이다.

    MapReduce :

    구글에서 분산 컴퓨팅을 지원하기 위한 목적으로 제작하여 2004년 발표한 소프트웨어 프레임워크다. 이 프레임워크는 페타바이트 이상의 대용량 데이터를 신뢰할 수 없는 컴퓨터로 구성된 클러스터 환경에서 병렬 처리를 지원하기 위해서 개발되었다. 이 프레임워크는 함수형 프로그래밍에서 일반적으로 사용되는 Map과 Reduce라는 함수 기반으로 주로 구성된다.

    현재 MapReduce는 Java와 C++, 그리고 기타 언어에서 적용이 가능하도록 작성되었다.






    YARN :

    MapReduce 2.0의 다른 이름

    Google file system (GFS) :

    Google 에서 개발 한 독점적인 분산 파일 시스템. 이것은 상품화된 하드웨어의 대형 클러스터를 사용하여 데이터에 효율적이고 안정적으로 액세스엑세스 할 수 있도록 설계되었다. 구글 파일 시스템의 새 버전의 코드명은 Colouss이다.

    분산 파일 시스템 (Distributed file system, DFS)
    네트워크 파일 시스템 (Network file system) :

    컴퓨터 네트워크를 통해 공유하는 여러 호스트 컴퓨터의 파일에 접근할 수 있게 하는 파일 시스템이다.

    NoSQL (Not only SQL) :

    NoSQL은 널리 사용되는 관계형 데이터베이스 관리 시스템(RDBMS) 모델을 따르지 않는 데이터베이스

    관리 시스템의 광범위한 클래스이다. NoSQL은 테이블을 생성하지 않으며 데이터 조작을 위해 SQL을 사용하지

    않는다.


    NoSQL 시스템은 대체로 데이터의 검색과 추가에 매우 최적화 되어 있으며 흔히 다음 세대의 저장 장치

    (예를 들면 key-value 저장)에 대한 몇가지 기능을 제공한다.


    full SQL 시스템에 비히 감소된 실행타임의 유연성은 특정 데이터 모델에 대한 확장성과 성능으로

    확실한 보상이 될 수 있다.


    요컨대 NoSQL 데이터베이스 시스템은 데이터의 성격상 데이터간의 관계를 필요로 하지 않는

    방대한 양의 데이터를 처리할 때 유용하다.


    데이터는 구조화 될 수 있겠지만 진짜 NoSQL이 필요한 경우는 요소들 사이에 관계가 없는 방대한

    양의 데이터를 저장하고 검색하는 능력이 요구되는 때이다. 예를 들면 수백만 건의 key-value 쌍을

    하나 혹은 연관된 여러개의 배열에 저장하거나 혹은  수백만 건의 데이터 레코드를 저장하는 경우를

    들 수 있겠다.


    최근의 기업들의 입장에서 보자면 특히 점점 증가하는 요소들의 통계핵적인 분석이나 혹은 실시간 분석에

    유용할 것이다.(예를 들면 커다란 그룹의 사용자들이 올리는 트위터의 글들이라든가 서버상의 로그들이 그런 것이다.)


    일반적으로 NoSQL 데이터베이스는 데이터를 저장하는 방식에 따라 Key-Value Store,

    BigTable 이행, 문서 저장 데이터베이스(Document store database), 그리고

    graph 데이터 베이스의 하위 영역으로 카테고리가 나누어진다.


    - (영문판 위키피디아 발번역...-.-)


    Graph :

    이 형태의 데이터베이스는 데이터들간의 관계를 그래프로 잘 표현 할 수 있도록
    디자인 되었다. (각 요소들은 상호간에 불확실한 수의 관계로 연결되어있다)

    이런 류의 데이터에는 사회적 관계(Social Relations), 대중 교통 시설의 연결,
    도로 지도나 네트워크 topology 등을 예로 들 수 있다.

    Key-Value Store :

    스키마없는 방식으로 데이터를 저장 할 수 있다.
    데이터는 프로그래밍 언어의 데이터 타입이나 객체 형태로 저장될 수 있다.
    이 때문에 고정 된 데이터 모델이 필요 없다.

    Key-Value Stoer의 종류

    Eventually‐consistent key‐value store

    Hierarchical key–value store

    Hosted services

    Key–value cache in RAM

    Key–value stores on solid state or rotating disk

    Ordered key–value stores

    Multivalue databases

    Object database

    RDF database

    Tabular

    Tuple store


     [출처 : 위키백과]

    블로그 이미지

    마즈다

    이제 반백이 되었지만 아직도 꿈을 좇고 있습니다. 그래서 그 꿈에 다가가기 위한 단편들을 하나 둘 씩 모아가고 있지요. 이 곳에 그 단편들이 모일 겁니다...^^

    댓글을 달아 주세요