[HADOOP] MapReduce / Hadoop을 사용하여 큰 데이터 정렬하기

MapReduce / Hadoop을 사용하여 큰 데이터 정렬하기

MapReduce에 대해 읽고 있는데 다음과 같은 점이 나를 혼란스럽게합니다.

1 백만 개의 항목 (정수)을 가진 파일이 있고이를 MapReduce를 사용하여 정렬하려고한다고 가정합니다. 내가 그것에 대해 이해하는 방법은 다음과 같습니다 :

정수를 정렬하는 매퍼 함수를 ​​작성하십시오. 따라서 프레임 워크는 입력 파일을 여러 개의 청크로 나누어 다른 매퍼에게 제공합니다. 각 매퍼는 서로 독립적 인 데이터 덩어리를 정렬합니다. 모든 매퍼가 완료되면 결과의 각각을 감속기에 전달하고 결과를 결합하여 최종 출력을 제공합니다.

내 생각에 우리가 하나의 감속기를 가지고 있다면 분산 된 프레임 워크를 어떻게 활용할 것인가? 결국 결과를 한 곳에서 결합해야 하는가? 문제는 한 곳에서 100 만 개의 항목을 병합하는 데 도움이됩니다. 그게 아니면 뭔가 빠졌나요?

감사, 챈더

해결법

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

   1.병합 정렬을 확인하십시오.

   병합 정렬을 확인하십시오.

   부분적으로 정렬 된 목록을 정렬하는 것이 전체 목록을 정렬하는 것보다 작업 및 메모리 소비면에서 훨씬 효율적이라는 것이 드러났습니다.

   감속기가 4 개의 정렬 된 목록을 얻는 경우에는 4 개의 목록 중 가장 작은 요소를 찾아서 선택하면됩니다. 리스트 수가 일정하면이 감소는 O (N) 연산입니다.

   또한 일반적으로 감속기는 나무와 같이 무언가에 "분포"되어 있으므로 작업 또한 평행 정렬 될 수 있습니다.

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

   2.다른 사람들이 언급했듯이, 병합은 정렬보다 훨씬 간단하므로 거기에서 큰 승리가 있습니다.

   다른 사람들이 언급했듯이, 병합은 정렬보다 훨씬 간단하므로 거기에서 큰 승리가 있습니다.

   그러나 거대한 데이터 세트에서 O (N) 직렬 연산을 수행하는 것도 금지 될 수 있습니다. 정확히 지적했듯이 병합을 병렬로 수행하는 방법을 찾는 것이 좋습니다.

   이를 수행하는 한 가지 방법은 랜덤 파티셔너 (일반적으로 사용되는 것)에서 조금 더 똑똑한 것으로 파티션 기능을 대체하는 것입니다. 예를 들어, Pig가이 작업을 수행 할 때 데이터 집합을 샘플링하여 값 분포의 대략적인 근사값을 구한 다음 값 범위를 다른 감속기에 할당합니다. 감속재 0은 모든 요소가 <1000, 감속기 1이 모든 요소> = 1000 및 <5000 등을 가져옵니다. 그런 다음 병렬로 병합을 수행 할 수 있으며 최종 결과는 각 감속기 작업의 수를 아는대로 정렬됩니다.

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

   3.따라서 map-reduce를 사용하여 정렬하는 가장 간단한 방법은 다음 중 하나를 수행하는 것입니다.

   따라서 map-reduce를 사용하여 정렬하는 가장 간단한 방법은 다음 중 하나를 수행하는 것입니다.

   지도 단계 중  (Input_Key, Input_Value) 출력 (Input_Value, 입력 키)

   감속기는 정체 감속기입니다.

   예를 들어 우리의 데이터가 학생이라면 나이 데이터베이스, 그리고 매퍼 입력은 다음과 같습니다. ( 'A', 1) ( 'B', 2) ( 'C', 10) ... 출력은 (1, A) (2, B) (10, C)

   이 논리를 밖으로 시도하지 않은 그러나 그것은 내가하고있는 숙제 문제의 단계입니다. 업데이트 소스 코드 / 로직 링크를 올립니다.

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

   4.늦어서 미안하지만 미래의 독자를 위해, 예, 챈 더, 당신은 뭔가를 놓치고 있습니다.

   늦어서 미안하지만 미래의 독자를 위해, 예, 챈 더, 당신은 뭔가를 놓치고 있습니다.

   논리는 Reducer가 실행중인 노드의 데이터 만 셔플 한 다음 정렬 할 수 있다는 것입니다. 하나의 노드에서 실행되는 다른 노드의 데이터를 볼 수없는 감속기를 말하며, 데이터의 축소 알고리즘을 적용합니다. 따라서 병합 정렬 절차는 적용 할 수 없습니다.

   따라서 큰 데이터의 경우 우리는 TeraSort를 사용합니다. TeraSort는 사용자 정의 파 티셔 터가있는 ID 매퍼 및 감속기입니다. TeraSort에 대한 Hadoop 구현에 대해서는 여기에서 더 자세히 읽을 수 있습니다. 그것은 진술한다 :

   "TeraSort는 각 축소에 대한 키 범위를 정의하는 N - 1 샘플링 된 키의 정렬 된 목록을 사용하는 사용자 정의 분할자를 제외하고 표준 map / reduce 정렬입니다. 특히 sample [i - 1] <= key

5. ==============================

   5.여러 개의 정렬 된 항목을 결합하는 것이 여러 개의 정렬되지 않은 항목을 결합하는 것보다 효율적이라고 생각합니다. 따라서 매퍼는 청크 정렬 작업을 수행하고 감속기는 이들을 병합합니다. 매퍼가 정렬을 완료하지 않았다면 감속기가 정렬을 수행하는 데 어려움을 겪습니다.

   여러 개의 정렬 된 항목을 결합하는 것이 여러 개의 정렬되지 않은 항목을 결합하는 것보다 효율적이라고 생각합니다. 따라서 매퍼는 청크 정렬 작업을 수행하고 감속기는 이들을 병합합니다. 매퍼가 정렬을 완료하지 않았다면 감속기가 정렬을 수행하는 데 어려움을 겪습니다.

6. ==============================

   6.정렬은 MapReduce를 사용하여 효율적으로 구현할 수 있습니다. 하지만이 목적을 달성하기 위해 mapreduce를 사용하여 병합 정렬을 구현하는 방법을 생각하는 것 같습니다. 그것은 이상적인 후보가 아닐 수도 있습니다.

   정렬은 MapReduce를 사용하여 효율적으로 구현할 수 있습니다. 하지만이 목적을 달성하기 위해 mapreduce를 사용하여 병합 정렬을 구현하는 방법을 생각하는 것 같습니다. 그것은 이상적인 후보가 아닐 수도 있습니다.

   당신이 암시 한 것처럼, mergesort (map-reduce 사용)는 다음 단계를 포함합니다 :

   여기에서 언급 한 문제는 감축 단계에서 병렬 처리를 배제하는 하나의 감속기 만있을 수 있다는 것입니다. 다른 응답에서 언급했듯이, terasort와 같은 mapreduce 특정 구현이이 목적으로 고려 될 수 있습니다.

   http://www.chinacloud.cn/upload/2014-01/14010410467139.pdf에서 설명을 찾았습니다.

   병합 정렬로 돌아 가면, 하나의 레벨의 감속기 출력이 다음 레벨의 감속기로 이동하거나 동일한 감속기 세트로 되돌아가는 감속기의 계층 구조를 제공하는 도구 (또는 동등한 도구)가있는 경우 실현 가능합니다.

from https://stackoverflow.com/questions/3624384/sorting-large-data-using-mapreduce-hadoop by cc-by-sa and MIT license