개별 문제를 독립적으로 해결할 수있을 때까지 문제를 작은 문제로 나누고 원래 질문에 대답하기 위해 문제를 결합하는 것을 나누기 및 정복 알고리즘 설계 기법이라고합니다. [참조 : CLR 알고리즘 소개]
최근에, 특히 매우 큰 데이터 세트의 영역에서 계산 문제를 해결하기위한 이러한 접근법 은 분할 및 정복이 아니라 맵리 듀스 (MapReduce) 라고 불린다 .
내 질문은 다음과 같습니다. MapReduce는 나누기 및 정복 접근 방식에 의존하는 독점 프레임 워크 이상입니까, 아니면 어떤 점에서 독특하게 만드는 세부 사항이 있습니까?
답변
MapReduce 아키텍처에 대해 묻는다면, 그것은 단지 분할 및 정복 기술입니다. 그러나 유용한 MapReduce 아키텍처에는 문제를 효율적으로 “분류”, “정복”및 “감소”할 수있는 다른 인프라의 산이 있습니다. 대규모 MapReduce 배포 (1000의 컴퓨팅 노드)를 사용하면 작업을 분할하고 무언가를 계산 한 다음 마지막으로 모든 결과를 수집하는 단계가 쉽지 않습니다. 로드 밸런싱, 데드 노드 감지, 중간 상태 저장 (오래 실행되는 문제의 경우) 등은 자체적으로 어려운 문제입니다.
답변
MapReduce는이 분할 정복 알고리즘을 구현하기위한 프레임 워크이다 매우 스케일 러블 방식으로 자동으로 컴퓨터의 임의의 큰 클러스터 노드 단위 수준의 작업을 분배함으로써, 및 작업 단위를 재분배하여 개개의 노드의 실패를 자동으로 처리 다른 노드로.
매우 정교한 개념은 아니지만 매우 유용한 인프라입니다.
답변
MapReduce는 대부분의 분할 및 정복 시스템에서 상당히 근본적인 방식으로 분기되지만 많은 사람들이 거의 그리워하지 않는 간단한 시스템입니다. 그것의 진짜 천재는 중간 결과에 태그를 붙이는 것입니다.
일반적인 (이전) 분할 및 정복 시스템에서는 작업을 직렬로 분할하고 작업 패킷을 병렬로 실행 한 다음 해당 작업의 결과를 다시 직렬로 병합합니다.
MapReduce에서는 작업을 직렬로 나누고, 작업 패킷을 병렬로 실행하고, 결과에 태그를 지정하여 어떤 결과가 다른 결과와 관련되는지 표시합니다. 그런 다음 병합은 태그가 동일한 모든 결과에 대해 직렬이지만 태그가 다른 결과에 대해 병렬로 실행될 수 있습니다.
대부분의 이전 시스템에서 병합 단계는 가장 사소한 작업을 제외하고 병목 현상이되었습니다. 맵리 듀스로 그것은 할 수 있는 작업의 성격이 모두 병합이 연속적으로 수행 할 것을 요구하는 경우 여전히. 그러나 작업이 어느 정도의 병렬 결과 병합을 허용하는 경우 MapReduce는 이러한 가능성을 활용할 수있는 간단한 방법을 제공합니다. 대부분의 다른 시스템은 두 가지 중 하나를 수행합니다. 일부 작업에 필요할 수 있기 때문에 모든 병합을 순차적으로 실행 하거나 특정 작업에 대한 병렬 병합을 정적으로 정의합니다. MapReduce는 병합 단계에서 일관성을 유지하면서 (매핑 단계에서 실수를하지 않았다고 가정하면서) 가능한 한 많은 병렬로 자동 예약 할 수있는 충분한 데이터를 제공합니다.
또한 MapReduce에서는 모든 단계가 재귀 적 일 수 있음을 암시하므로 큰 작업을 병렬로 실행할 수있는 5 개의 작은 작업으로 나눌 수있는 초기 매핑 단계가있을 수 있습니다. turn) 다른 여러 병렬 작업에 매핑됩니다.
이로 인해 매핑 작업과 축소 측면 모두에 트리 구조가 생겨서 많은 작업을 충분히 수행 할 수 있도록 큰 작업을 신속하게 분할 할 수 있습니다.
답변
MapReduce는 단순히 분할 및 정복 기법 이 아니라 많은 예에서 그렇게 보입니다.
맵핑 단계에서 일대 다 관계를 수행 할 수 있으며 자주 원합니다. 따라서 단순히 사례로 나누는 것이 아닙니다.
맵과 축소 사이에는 (구현에 따라) 정렬 또는 해싱 단계가 있습니다. 이 작업의 효율성은 전체 리소스 요구 사항에 매우 중요합니다. 세부 사항은 응용 프로그램 프로그래머에게는 보이지 않지만이 단계는 프레임 워크의 핵심입니다.
축소 작업은 병합 유형입니다. 정복으로 생각할 수 있지만 실제로는 “나중에 사용하기 위해 데이터를 방출”하거나 “데이터 저장소에 데이터를 저장”하는 경향이 있습니다. (대량의 데이터 세트가있는 경우 입력 및 최종 결과를 포함하여 모든 것이 실제로 분배되기를 원합니다. 따라서 분산 키 / 값 저장소는 입력을 받고 출력을 저장하는 장소로도 의미가 있습니다.)