최초 작성일 : 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/02/04 13:16 


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

나름 영문 문서를 해설 식으로 적어보고자 했으나...

가면 갈수록 그냥 문서의 직역이 되고 있네요...ㅠ.ㅠ

양해부탁드립니다.

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


지난 시간에 살펴본 바와 같이 간단하게 말하면 Map은 논리적 레코드를 key-value형태의 중간 데이터로 만드는 작업을 수행하고

reduce는 key-value를 가공하여 공통된 key를 가진 value들의 집합을 출력하는 작업을 수행한다.


요기에 대해 조금만(많이 하면 골치아픕니다…) 깊게 들어가보도록 하자.


아래와 같은 간단한 샘플코드가 있다.


map(String key, String value): // key: document name
// value: document contents for each word w in value:

      EmitIntermediate(w, "1");

reduce(String key, Iterator values): // key: a word
// values: a list of counts
int result = 0;

    for each v in values:

      result += ParseInt(v);

    Emit(AsString(result));


map함수는 각 단어와 그 단어가 나타나는 횟수를 리턴한다.(여기서는 그 횟수를 간단히 '1'로 하였다.)

reduce 함수는 특정 단어에 대해 리턴된 모든 횟수를 합산한다.


추가로, 개발자들은  input / output 파일 이름을 가진 mapreduce의 사양에 맞도록 객체에 코딩을 하게 되고

이러한 객체를 선택적 인자로 넘겨 줄 수 있다.

이후 개발자는 이 객체를 전달함으로써 MapReduce함수를 호출하게 되는 것이다.

이러한 사용자들의 코드는 MapReduce 라이브러리틀 통해 연결된다.


map과 reduce의 개념적인 input / output 타입은 다음과 같다


map (k1,v1)  list(k2,v2) 
reduce (k2,list(v2))  list(v2)

이런 단어 세기 외에 다음과 같은 예들이 있다.


Distributed Grep : map 함수에서 특정 패턴과 매칭되는 라인들을 리턴한다. reduce 함수는 중간 데이터를

복사해서 출력하는 것과 유사한 함수로 기능한다.


Count of URL Access Frequency : map 함수는 웹 페이지 요청 로그를 분석하여 <URL, 1>의 결과를 도출하고

reduce는 같은 URL에 대한 value들을 합산하여 <URL, total count>쌍의 결과를 출력한다.


Reverse Web-Link Graph : map 함수는 'source'라는 이름의 페이지 내에서 'target'으로 링크되는 URL을 분석하여

<target, source>라는 쌍을 리턴하고 reduce 함수에서는 target URL과 관련된 모든 source URL들을 모아

<target, list(source)> 쌍을 만들어낸다.


Term-Vector per Host : term vector는 특정 문서 혹은 문서들의 목록 속에서 가장 중요한 단어들을

<word, frequence> 쌍으로 요약하는 것이다.

map 함수는 입력된 문서로부터 <hostname, term vector>쌍을 리턴한다.(hostname은 문서의 URL로부터

추출한 것이다.) reduce 함수는 주어진 host로부터 모든 문서당 term vector를 전달받아 이 term vector들을

함께 모은 후 빈도수가 낮은 용어들을 제거한 후에 최종적으로 <hostname, term vector>의 쌍을 리턴한다.


Inverted Index : map 함수는 각각의 문서들을 분석하여 일련의 <word, document ID>쌍을 리턴한다.

reduce 함수는 주어진 단어에 대해 모든 쌍을 전달받아 그 단어에 상응하는 document ID들을 정렬한 후

<word, list(document ID)>쌍으로 리턴한다. 모든 출력 쌍들의 집합은 간단한 역색인(Inverted index)을 구성하며

단어의 위치 추적을 강화하기가 쉬워진다.


Distributed sort : map 함수는 각각의 레코드로부터 key를 추출하고 <key, record>쌍을 출력한다.

reduce 함수는 변경되지 않은 모든 쌍들을 출력한다. 이 연산은 분할된 설비들에 의존적이다.

블로그 이미지

마즈다

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

최초 작성일 : 2013/02/01 17:15


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

워낙에 영어 알레르기가 있는 놈이 영문 문서 보면서 발번역 하느라 토쏠립니다...ㅠ.ㅠ
이점 감안하고 보시기 바랍니다...
==============================================
우선 앞선 글(http://www.prapps.net/587)에서 위키백과에서 정의한 내용을 간단하게
적어보았다. 다음과 같은 내용이다.
구글에서 분산 컴퓨팅을 지원하기 위한 목적으로 제작하여 2004년 발표한 소프트웨어 프레임워크다. 이 프레임워크는 페타바이트 이상의 대용량 데이터를 신뢰할 수 없는 컴퓨터로 구성된 클러스터 환경에서 병렬 처리를 지원하기 위해서 개발되었다. 이 프레임워크는 함수형 프로그래밍에서 일반적으로 사용되는 Map과 Reduce라는 함수 기반으로 주로 구성된다.

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


오늘은 여기서 약간만 더 내용을 심화 시켜 보도록 하겠다.
오늘의 글은 다음 링크에 링크된 문서에서 발췌, 번역 한 것이다.

http://research.google.com/archive/mapreduce-osdi04-slides/index.html

우선 소개 글에서 맵리듀스가 생겨나게된 배경을 설명하고 있다.
쉽게 말해

' 5년간 구글 인간들이 엄청난 양의 미가공 데이터를 파생테이터로
만들기 위해 특별한 목적의 많은 프로그램을 구현하였는데 사실 이 작업 자체는
매우 쉬운 작업이지만 이 작업을 적절한 시간에 끝내기 위해서는 분산된 많은
서버들 상에서 이루어져야 했고 이 것은 엄청 골치 아픈 일이었다.

그래서 잡다하고 복잡한 기능들(병렬화, 내고장성, 데이터 분산처리, 로드 밸런싱 등)은
라이브러리에 다 숨기고 간단하 연산만을 수행하도록 개념을 잡았다.

이러한 개념은 Lisp 및 다른 언어에서의 기본형 데이터에 대한 표현인 Map과 Reduce에서
그 영감을 얻었다.

그래서 입력값인 각각의 논리적인 레코드들을 중간형태의 key/value 형태로 만들기 위해
map을 적용 시켰고. 다시 여기에서 같은 key들을 공유하는 value들을 적절한 파생 데이터로
조합하기 위해 reduce를 적용 시켰다.

그렇다!
도대체 map이 뭐고 reduce가 뭔지 무지 궁금했는데...
바로 이거였던 것이다.

Map : 논리적 레코드를 key/value형태의 중간 데이터로 만드는 작업
Reduce : key/value 형태의 중간 데이터를 key를 중심으로 재분류하여 분석하는 작업

간단히 말하면 이런 것이다.

그리고 이렇게 만들어진 맵리듀스는

대량의 연산을 자동으로 병렬처리 및 분산처리가 가능하게 해주고, 또 그 인터페이스들의 구현들을 조합하는 경우 대량의 상업용PC(비교적 저가의 PC) 클러스터에서
고성능을 발휘할 수 있는 간단하고도 강력한 인터페이스를 만들어 낸 데에 그 의의가 있다.

이상 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


     [출처 : 위키백과]

    블로그 이미지

    마즈다

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