[mapreduce] 좋은 MapReduce 예제 [닫기]

“MapReduce로 긴 텍스트로 단어를 계산하는 방법”태스크 이외의 다른 좋은 예는 생각할 수 없었습니다. 나는 이것이 다른 사람들 에게이 도구가 얼마나 강력한 지에 대한 인상을주는 최고의 예가 아니라는 것을 알았습니다.

코드 스 니펫을 찾지 않고 실제로 “텍스트”예제 만 찾고 있습니다.



답변

맵 축소는 대량의 데이터를 효율적으로 처리하기 위해 개발 된 프레임 워크입니다. 예를 들어, 데이터 세트에 백만 개의 레코드가 있고 관계형 표현으로 저장되는 경우 값을 도출하고 이에 대한 변환을 수행하는 데 비용이 많이 듭니다.

예를 들어, 생년월일을 감안할 때 SQL에서 백만 개의 레코드에 대해 30 세 이상인 사람이 몇 명인지 알아내는 데 다소 시간이 걸리며 이는 쿼리의 복잡성이 증가 할 때만 질산염의 순서로만 증가합니다. Map Reduce는 데이터가 분산 방식으로 처리되는 클러스터 기반 구현을 제공합니다

여기 에 관한 모든 것을 설명하는 Wikipedia 기사 map-reduce가 있습니다.

또 다른 좋은 예는 map reduce를 통해 친구를 찾는 것입니다.이 개념을 이해하는 강력한 예가 될 수 있으며 잘 사용되는 유스 케이스입니다.

개인적 으로이 링크 는 개념을 이해하는 데 매우 유용합니다.

블로그에 제공된 설명 복사 (링크가 오래되었을 경우)

친구 찾기

MapReduce는 원래 Google에서 개발 한 프레임 워크로 여러 도메인에서 대규모 분산 컴퓨팅을 쉽게 할 수 있습니다. Apache Hadoop은 오픈 소스 구현입니다.

세부 사항에 대해 설명하지만 맵 기능과 축소 기능의 두 가지 기능을 정의합니다. map 함수는 값을 가져 와서 key : value 쌍을 출력합니다. 예를 들어 문자열을 가져와 단어의 길이를 키로, 단어 자체를 값으로 출력하는 map 함수를 정의하면 map (steve)는 5 : steve를 반환하고 map (savannah)는 8 : savannah를 반환 . map 함수는 stateless이며 출력 값을 계산하기 위해 입력 값만 필요하다는 것을 알 수 있습니다. 이를 통해 값에 대해 맵 기능을 병렬로 실행할 수 있으며 큰 이점을 제공합니다. reduce 함수에 도달하기 전에 mapreduce 프레임 워크는 키를 기준으로 모든 값을 그룹화하므로 map 함수가 다음 키 : 값 쌍을 출력하는 경우 :

3 : the
3 : and
3 : you
4 : then
4 : what
4 : when
5 : steve
5 : where
8 : savannah
8 : research

그들은 다음과 같이 그룹화됩니다.

3 : [the, and, you]
4 : [then, what, when]
5 : [steve, where]
8 : [savannah, research]

이러한 각 행은 키와 값 목록을 허용하는 reduce 함수의 인수로 전달됩니다. 이 경우, 우리는 특정 길이의 단어가 몇 개나 있는지 알아 내려고 노력할 것이므로 reduce 함수는 목록의 항목 수를 세고 다음과 같이 목록의 크기로 키를 출력합니다.

3 : 3
4 : 3
5 : 2
8 : 2

축소도 병렬로 수행 할 수있어 다시 큰 이점을 제공합니다. 그런 다음이 최종 결과를보고 우리 말뭉치 등에 길이가 5 인 단어가 두 개 밖에 없다는 것을 알 수 있습니다.

mapreduce의 가장 일반적인 예는 단어가 말뭉치에서 발생하는 횟수를 세는 것입니다. 인터넷 사본을 가지고 있다고 가정하고 (이런 상황에서 일할만큼 운이 좋았습니다) 인터넷의 모든 단어 목록과 발생 횟수를 원한다고 가정하십시오.

당신이 이것에 접근하는 방법은 당신이 가진 문서를 토큰 화하고 (단어들로 나누고) 각 단어를 매퍼에게 전달하는 것입니다. 그런 다음 매퍼는 값과 함께 단어를 다시 뱉어냅니다 1. 그룹화 단계는 모든 키 (이 경우 단어)를 가져 와서 1의 목록을 만듭니다. 그런 다음 축소 단계는 키 (단어)와 목록 (키가 인터넷에 나타날 때마다 1의 목록)을 가져 와서 목록을 합칩니다. 그런 다음 감속기는 단어 수와 함께 단어를 출력합니다. 모든 것이 말되고 완료되면 인터넷에있는 모든 단어의 목록과 그 단어가 몇 번이나 나타납니다.

쉬운가요? mapreduce에 대해 읽은 적이 있다면 위 시나리오는 새로운 것이 아닙니다. mapreduce의 “Hello, World”입니다. 실제 사용 사례는 다음과 같습니다 (Facebook은 실제로 다음을 수행 할 수도 있고 수행하지 않을 수도 있습니다).

Facebook에는 친구 목록이 있습니다 (친구는 Facebook에서 양방향입니다. 친구 인 경우 내 친구입니다). 또한 디스크 공간이 많으며 매일 수억 건의 요청을 처리합니다. 요청 처리 시간을 줄일 수있을 때 계산을 미리 계산하기로 결정했습니다. 일반적인 처리 요청 중 하나는 “You와 Joe의 친구가 230 명입니다”기능입니다. 다른 사람의 프로필을 방문하면 공통된 친구 목록이 표시됩니다. 이 목록은 자주 변경되지 않으므로 프로파일을 방문 할 때마다 다시 계산하는 것이 낭비 적입니다 (적절한 캐싱 전략을 사용할 수 있지만이 문제에 대한 mapreduce에 대해서는 계속 쓸 수 없습니다). 우리는 mapreduce를 사용하여 모든 사람을 계산할 수 있습니다. 친구는 하루에 한 번 공통된 결과를 저장합니다. 나중에 그것은 단지 빠른 검색입니다. 우리는 디스크가 많고 싸다.

친구가 Person-> [List of Friends]로 저장되어 있다고 가정하면 친구 목록은

A -> B C D
B -> A C D E
C -> A B D E
D -> A B C E
E -> B C D

각 줄은 매퍼에 대한 논쟁이 될 것입니다. 친구 목록의 모든 친구에 대해 매퍼는 키-값 쌍을 출력합니다. 열쇠는 그 사람과 친구가 될 것입니다. 이 값은 친구 목록이됩니다. 키는 친구가 순서대로 정렬되어 모든 친구 쌍이 동일한 감속기로 이동합니다. 이것은 텍스트로 설명하기 어렵 기 때문에 그냥 해보고 패턴을 볼 수 있는지 확인하십시오. 모든 매퍼가 실행되면 다음과 같은 목록이 표시됩니다.

For map(A -> B C D) :

(A B) -> B C D
(A C) -> B C D
(A D) -> B C D

For map(B -> A C D E) : (Note that A comes before B in the key)

(A B) -> A C D E
(B C) -> A C D E
(B D) -> A C D E
(B E) -> A C D E
For map(C -> A B D E) :

(A C) -> A B D E
(B C) -> A B D E
(C D) -> A B D E
(C E) -> A B D E
For map(D -> A B C E) :

(A D) -> A B C E
(B D) -> A B C E
(C D) -> A B C E
(D E) -> A B C E
And finally for map(E -> B C D):

(B E) -> B C D
(C E) -> B C D
(D E) -> B C D
Before we send these key-value pairs to the reducers, we group them by their keys and get:

(A B) -> (A C D E) (B C D)
(A C) -> (A B D E) (B C D)
(A D) -> (A B C E) (B C D)
(B C) -> (A B D E) (A C D E)
(B D) -> (A B C E) (A C D E)
(B E) -> (A C D E) (B C D)
(C D) -> (A B C E) (A B D E)
(C E) -> (A B D E) (B C D)
(D E) -> (A B C E) (B C D)

각 줄은 감속기에 인수로 전달됩니다. 감소 기능은 단순히 값 목록을 교차시키고 교차 결과와 동일한 키를 출력합니다. 예를 들어 reduce ((AB)-> (ACDE) (BCD))는 (AB) : (CD)를 출력하며 친구 A와 B는 공통 친구로 C와 D를 갖습니다.

축소 후 결과는 다음과 같습니다.

(A B) -> (C D)
(A C) -> (B D)
(A D) -> (B C)
(B C) -> (A D E)
(B D) -> (A C E)
(B E) -> (C D)
(C D) -> (A B E)
(C E) -> (B D)
(D E) -> (B C)

이제 D가 B의 프로필을 방문하면 빠르게 조회하여 (B D)공통의 친구가 세 명 있음을 알 수 있습니다 (A C E).


답변

Hadoop과 유사한 MapReduce 구현의 가장 좋은 예 중 하나입니다 .

그것들은 MapReduce 아이디어의 키-값 기반 구현으로 제한된다는 점을 명심하십시오 (따라서 적용 가능성이 제한적입니다).


답변

MapReduce에서 수행 할 수있는 친숙한 작업 중 하나는 일반적인 SQL 작업 인 SELECT, SELECT WHERE, GROUP BY 등입니다.

또 다른 좋은 예는 행렬 곱셈입니다. 여기서 한 행의 M과 전체 벡터 x를 전달하고 M * x의 한 요소를 계산합니다.


답변

때때로 저는 사람들에게 MR 개념을 제시합니다. 사람들에게 익숙한 처리 작업을 찾은 다음 MR 패러다임에 매핑합니다.

보통 나는 두 가지를 취합니다.

  1. 그룹 별 / 집계. 셔플 링 스테이지의 장점은 분명합니다. 셔플 링도 분산 정렬이라는 설명과 분산 정렬 알고리즘에 대한 설명도 도움이됩니다.

  2. 두 테이블의 조인 DB를 사용하는 사람들은 개념과 확장 성 문제에 익숙합니다. MR에서 어떻게 할 수 있는지 보여줍니다.


답변