[HADOOP] MapReduce 정렬 알고리즘은 어떻게 작동합니까?

MapReduce 정렬 알고리즘은 어떻게 작동합니까?

MapReduce의 성능을 입증하는 데 사용되는 주요 사례 중 하나는 Terasort 벤치 마크입니다. MapReduce 환경에서 사용되는 정렬 알고리즘의 기본 사항을 이해하는 데 문제가 있습니다.

나에게 정렬은 단순히 다른 모든 요소와의 관계에서 요소의 상대적 위치를 결정하는 것을 포함한다. 따라서 정렬은 "모든 것"과 "모든 것"을 비교하는 것입니다. 귀하의 평균 정렬 알고리즘 (빠른, 거품, ...)은 똑똑한 방식으로 간단하게 이것을 수행합니다.

데이터 세트를 여러 조각으로 나눠서 마음에 드는 것은 하나의 조각을 정렬 할 수 있다는 것을 의미합니다. 그런 다음이 조각들을 여전히 '완전한'완전 정렬 된 데이터 집합으로 통합해야합니다. 수천 개의 시스템에 분산 된 테라 바이트 데이터 세트를 감안할 때 나는 이것이 거대한 작업이 될 것으로 기대합니다.

이것이 실제로 어떻게 이루어 졌습니까? 이 MapReduce 정렬 알고리즘은 어떻게 작동합니까?

이해를 도와 주셔서 감사합니다.

해결법

1. ==============================

   1.다음은 Terasort에 대한 Hadoop의 구현에 대한 세부 정보입니다.

   다음은 Terasort에 대한 Hadoop의 구현에 대한 세부 정보입니다.

   그래서 그들의 트릭은 맵 단계에서 키를 결정하는 방식에 있습니다. 기본적으로 단일 감속기의 모든 값이 다른 모든 감속기에 대해 '사전 정렬'되도록 보장합니다.

   제임스 해밀턴 (James Hamilton)의 블로그 포스트 (Blog Post)를 통해이 기사를 찾았습니다.

2. ==============================

   2.Google 참조 : MapReduce : 대형 클러스터에서의 단순화 된 데이터 처리

   Google 참조 : MapReduce : 대형 클러스터에서의 단순화 된 데이터 처리

   이 링크에는 PDF 및 HTML 슬라이드 참조가 있습니다.

   구현 참조에 대한 설명이있는 Wikipedia 페이지도 있습니다.

   또한 비판,

3. ==============================

   3.나는 구글의 MapReduce 논문을 읽는 동안 같은 질문을했다. @Yuval F의 대답은 내 퍼즐을 거의 해결했습니다.

   나는 구글의 MapReduce 논문을 읽는 동안 같은 질문을했다. @Yuval F의 대답은 내 퍼즐을 거의 해결했습니다.

   종이를 읽는 동안 눈치 채는 한가지는 마술이 파티셔닝 (맵 이후, 줄이기 전)에서 발생한다는 것입니다.

   이 논문은 파티셔닝 예제로 hash (key) mod R을 사용하지만, 이것은 중간 데이터를 여러 가지 축소 작업으로 분할하는 유일한 방법은 아닙니다.

   @Yuval F의 대답에 경계 조건을 추가하면됩니다. min (S)와 max (S)가 샘플링 된 키 중 최소 키와 최대 키라고 가정하십시오. 모든 키 = max (S)는 하나의 축소 작업으로 분할됩니다.

   샘플링 된 키에는 min 또는 max와 같은 엄격한 제한이 없습니다. 이 R 키가 모든 키에 분산되어 있기 때문에이 분산 시스템이 더 "병렬"되어 작업량이 줄어든 연산자에 메모리 오버 플로우 문제가 발생할 가능성이 적습니다.

4. ==============================

   4.그냥 추측 ...

   그냥 추측 ...

   거대한 데이터 세트가 주어지면 데이터를 여러 청크로 분할하여 병렬로 처리합니다 (레코드 번호 즉 레코드 1 - 1000 = 파티션 1 등).

   각 파티션을 클러스터의 특정 노드에 할당 / 예약하십시오.

   각 클러스터 노드는 파티션을 고유 한 미니 파티션으로 분할 (예 : 주요 알파벳 순서)합니다. 그래서, 파티션 1에서 A로 시작하는 모든 것들을 얻고 그것을 x의 미니 파티션 A로 출력하십시오. 현재 A (x)가 이미있는 경우 새 A (x)를 만듭니다. x를 순차 번호로 바꿉니다 (아마도 이렇게하는 스케줄러 작업 일 것입니다). 나. 다음 A (x) 고유 ID를주세요.

   매퍼가 완료 한 작업 (이전 단계)을 "축소"클러스터 노드로 이전합니다. 노드 클러스터를 줄이면 매퍼 작업이 완료 될 때마다 발생하는 각 A (x) 부분의 정렬이 더욱 정교 해집니다 (실제로 여전히있을 가능성이있을 때 실제로 w / A로 시작하는 모든 단어를 정렬 할 수는 없습니다. 다른 미니 파티션이 될 것입니다.) 결과를 최종 정렬 된 부분으로 출력합니다 (즉, 정렬 된 A, 정렬 된 B 등)

   완료되면 정렬 된 파티션을 단일 데이터 세트로 다시 결합하십시오. 이 시점에서 그것은 n 파일의 단순한 연결입니다 (n은 A - Z 만 수행하는 경우 26 일 수 있음).

   사이에 중간 단계가있을 수 있습니다 ... 잘 모르겠습니다. :) 나. 초기 감속 단계 후에지도를 작성하고 줄입니다.

from https://stackoverflow.com/questions/1152732/how-does-the-mapreduce-sort-algorithm-work by cc-by-sa and MIT license