MapReduce 정렬 알고리즘은 어떻게 작동하나요?

Question

MapReduce의 성능을 입증하는 데 사용되는 주요 예 중 하나는 테라소트 벤치마크.MapReduce 환경에서 사용되는 정렬 알고리즘의 기본을 이해하는 데 어려움을 겪고 있습니다.

나에게 정렬이란 단순히 다른 모든 요소와 관련된 요소의 상대적 위치를 결정하는 것을 의미합니다.따라서 정렬에는 "모든 것"과 "모든 것"을 비교하는 작업이 포함됩니다.평균 정렬 알고리즘(quick, bubble, ...)은 이를 스마트한 방식으로 수행합니다.

내 생각에는 데이터 세트를 여러 조각으로 분할한다는 것은 단일 조각을 정렬할 수 있다는 것을 의미하며 여전히 이러한 조각을 완전히 정렬된 '완전한' 데이터 세트에 통합해야 함을 의미합니다.수천 개의 시스템에 분산된 테라바이트 규모의 데이터 세트를 고려하면 이것이 엄청난 작업이 될 것으로 예상됩니다.

그렇다면 이것이 실제로 어떻게 이루어 집니까?이 MapReduce 정렬 알고리즘은 어떻게 작동하나요?

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

Answer 1

다음은 몇 가지 세부 사항입니다 Hadoop의 Terasort 구현:

Terasort는 각 감소에 대한 키 범위를 정의하는 정렬 된 N -1 샘플링 키 목록을 사용하는 사용자 정의 파티더를 제외하고는 표준 맵/감소 정렬입니다. 특히, 샘플 [i - 1] <= key <샘플 [i]가 i를 감소시키기 위해 전송되도록 모든 키. 이를 통해 감소 I의 출력은 모두 감소 I+1의 출력보다 적습니다. "

따라서 그들의 속임수는지도 단계에서 키를 결정하는 방식입니다. 본질적으로 그들은 단일 감속기의 모든 값이 다른 모든 감속기에 대해 '사전 분류'되도록 보장합니다.

나는 논문을 발견했다 제임스 해밀턴의 블로그 게시물.

Answer 2

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

에 나타났다:
OSDI'04 : 운영 체제 설계 및 구현에 관한 여섯 번째 심포지엄,
샌프란시스코, 캘리포니아, 2004 년 12 월.

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

또 한있다 설명이있는 Wikipedia 페이지 구현 참조와 함께.

또한 비판,

병렬 데이터베이스의 전문가를 개척하고 아키텍처를 공유하지 않은 David DeWitt와 Michael Stonebraker는 MapReduce가 사용할 수있는 폭 넓은 문제에 대해 논란의 여지가있는 주장을했습니다. 그들은 인터페이스를 너무 낮은 수준으로 불렀으며, 그것이 지지자들이 주장한 패러다임의 변화를 실제로 나타내는 지 의문을 제기했다. 그들은 Teradata를 20 년 이상 존재했던 선행 예술의 예로 인용하면서 Mapreduce 지지자들의 참신 주장에 도전한다. 그들은 MapReduce 프로그래머를 코다 실 프로그래머와 비교했으며, 두 가지 모두 "저수준 레벨 레코드 조작을 수행하는 저수준 언어로 쓰여진다"고 지적했다. Piglatin 및 Sawzall과 같은 프로젝트는 이러한 문제를 해결하기 시작했지만 Mapreduce의 입력 파일 사용 및 스키마 지원 부족은 B- 트리 및 해시 파티셔닝과 같은 공통 데이터베이스 시스템 기능으로 가능성을 방지합니다.

Answer 3

Google의 MapReduce 논문을 읽는 동안 같은 질문이있었습니다. @yuval f '에스 대답 내 퍼즐을 거의 해결했습니다.

종이를 읽는 동안 내가 알아 차린 한 가지는 마법이 파티셔닝에서 발생한다는 것입니다 (지도 후, 감소하기 전에).

논문은 사용합니다 hash(key) mod R 파티션 예제로서, 이것은 중간 데이터를 다른 작업을 줄이기 위해 중간 데이터를 분할하는 유일한 방법은 아닙니다.

경계 조건을 추가하십시오 @yuval f '에스 대답 완료하기 위해 : 최소와 최대 (들)가 샘플링 된 키 중 최소 키와 최대 키라고 가정합니다. 모든 키 <min (들)은 하나의 감소 작업으로 분할됩니다. 그 반대의 경우, 모든 키> = max (들)는 하나의 감소 작업으로 분할됩니다.

Min 또는 Max와 같은 샘플링 키에는 단단한 제한이 없습니다. 더, 더 고르게이 R 키는 모든 키에 분포되어 있습니다. 더 "병렬"이 분산 시스템은 감소하는 연산자가 메모리 오버 플로우 문제를 가질 가능성이 적습니다.

Answer 4

추측만 해보면...

거대한 데이터 세트가 주어지면 데이터를 병렬로 처리할 일부 청크로 분할할 수 있습니다(예: 레코드 번호 기준).레코드 1 - 1000 = 파티션 1 등).

각 파티션을 클러스터의 특정 노드에 할당/예약합니다.

각 클러스터 노드는 키 알파벳 순서에 따라 파티션을 자체 미니 파티션으로 추가로 분할(매핑)합니다.따라서 파티션 1에서 A로 시작하는 모든 항목을 가져와 x의 미니 파티션 A로 출력합니다.현재 A(x)가 이미 있는 경우 새 A(x)를 만듭니다.x를 순차 번호로 바꿉니다(아마도 이를 수행하는 스케줄러 작업일 것입니다).즉.다음 A(x) 고유 ID를 알려주세요.

매퍼(이전 단계)가 완료한 작업을 "축소" 클러스터 노드에 넘겨(예약) 합니다.그런 다음 노드 클러스터를 줄이면 모든 매퍼 작업이 완료될 때만 발생하는 각 A(x) 부분의 종류를 더욱 구체화합니다(여전히 가능성이 있을 때 A로 시작하는 모든 단어를 실제로 정렬할 수는 없습니다). 또 다른 A 미니 파티션을 만들 예정입니다).최종 정렬된 부분으로 결과를 출력합니다(예:정렬-A, 정렬-B 등)

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

그 사이에 중간 단계가 있을 수도 있습니다.잘 모르겠습니다 :).즉.추가 매핑 및 초기 축소 단계 이후 축소.