맵 리듀스

MapReduce

MapReduce는 클러스터에서 [1][2][3]병렬 분산 알고리즘을 사용하여 빅데이터 세트를 처리하고 생성하기 위한 프로그래밍 모델 및 관련 구현입니다.

MapReduce 프로그램은 필터링 및 정렬(예를 들어 이름별로 학생을 큐에 정렬, 각 이름에 대해 큐에 1개씩 정렬)을 실행하는 맵 프로시저와 요약 연산(예를 들어 각 큐의 학생 수를 카운트하여 이름 빈도를 산출)을 수행하는 축소 방법으로 구성됩니다.「MapReduce System」( 「인프라스트럭처」 또는 「프레임워크」라고도 불립니다)는, 분산 서버의 매시, 다양한 태스크의 병행 실행, 시스템의 다양한 부분간의 모든 통신과 데이터 전송의 관리, 용장성과 폴트 톨러런스 기능을 제공하는 것으로, 처리를 조정합니다.

이 모델은 데이터 [4]분석을 위한 분할 적용 결합 전략의 전문화입니다.MapReduce 프레임워크의 목적은 원래 [6]형태와 동일하지 않지만 맵에서 영감을 받아 함수 [5]프로그래밍에서 일반적으로 사용되는 함수를 축소합니다.MapReduce 프레임워크의 주요 기여는 실제 맵 및 축소 기능(예를 들어 1995년 Message Passing Interface 표준의[7][8] 축소 및 분산[9] 작업과 유사함)이 아니라[citation needed] 실행 엔진을 최적화함으로써 다양한 애플리케이션에 대해 달성되는 확장성과 내장해성입니다.따라서 MapReduce의 싱글 스레드 구현은 일반적으로 기존의 (비 MapReduce) 구현보다 빠르지 않습니다. 이러한 이점은 일반적으로 멀티 프로세서 [10]하드웨어의 멀티 스레드 구현에서만 볼 수 있습니다.이 모델을 사용하면 MapReduce 프레임워크의 최적화된 분산 셔플 조작(네트워크 통신 비용 절감) 및 폴트 톨러런스 기능이 실행될 때만 유용합니다.통신비 최적화는 좋은 MapReduce [11]알고리즘에 필수적입니다.

MapReduce 라이브러리는 여러 프로그래밍 언어로 작성되었으며 최적화 수준이 다릅니다.분산 셔플을 지원하는 일반적인 오픈 소스 구현은 Apache Hadoop의 일부입니다.MapReduce라는 이름은 원래 독점적인 구글 기술을 지칭했지만, 그 이후로 일반화되어 왔다.2014년이 되자 구글은 더 이상 MapReduce를 주요 빅데이터 [12]처리 모델로 사용하지 않게 되었고 Apache Mahout에 대한 개발은 풀맵을 [13]통합하고 기능을 줄이는 디스크 지향 메커니즘으로 옮겨갔습니다.

개요

MapReduce는 다수의 컴퓨터(노드)를 사용하여 대규모 데이터셋 간에 병렬 가능한 문제를 처리하기 위한 프레임워크입니다.클러스터(모든 노드가 같은 로컬 네트워크상에 있으며 유사한 하드웨어를 사용하는 경우) 또는 그리드(노드가 지리적으로 또는 관리적으로 분산된 시스템 간에 공유되고 있는 경우)라고 합니다.다른 종류의 하드웨어).처리는 파일 시스템(비구조화) 또는 데이터베이스(구조화)에 저장된 데이터에 대해 발생할 수 있습니다.MapReduce는 통신 오버헤드를 최소화하기 위해 데이터가 저장된 장소 근처에서 데이터를 처리함으로써 데이터의 인접성을 활용할 수 있습니다.

MapReduce 프레임워크(또는 시스템)는 보통 다음 3가지 조작(또는 단계)으로 구성됩니다.

  1. 맵: 각 워커노드는map로컬 데이터에 대한 기능을 수행하고 출력을 임시 저장소에 씁니다.마스터 노드는 다중 입력 데이터의 복사본을 하나만 처리하도록 보장합니다.
  2. Shuffle: 워커노드는 (에 의해 생성된) 출력 키를 기반으로 데이터를 재배포합니다.map하나의 키에 속하는 모든 데이터가 동일한 작업자 노드에 위치하도록 합니다.
  3. 절감: 작업자 노드가 각 출력 데이터 그룹을 키별로 병렬로 처리합니다.

MapReduce는 맵의 분산 처리와 축소 작업을 허용합니다.맵은 각 매핑 조작이 서로 독립적일 경우 병렬로 실행할 수 있습니다.실제로 이것은 독립된 데이터 소스 수 및/또는 각 소스 근처의 CPU 수에 의해 제한됩니다.마찬가지로 동일한 키를 공유하는 지도 동작의 모든 출력이 동시에 동일한 리덕터에 제시되거나 리덕션 함수가 관련성이 있는 경우 일련의 '리덕션'은 리덕션 단계를 수행할 수 있다.이 과정은 종종 있는 더 순차(때문에 제철 법의 여러 인스턴스 연결해야 하므로)알고리즘에 비해 비효율적인 보기보다 단일"상품"서버의 데이터만 몇시간에 1페타 바이트 정도로 해결하기 위한 MapReduce를 사용할 수 있는 대형 서버 농장 –를 감당할 수 있으면 맵 리듀스 훨씬 큰 데이터 집합에 적용될 수 있다.[14]병렬 처리를 통해 작업 중 서버 또는 스토리지의 부분적인 장애로부터 복구할 수도 있습니다.매퍼 또는 리듀서 중 하나에 장애가 발생했을 경우 입력 데이터를 사용할 수 있다고 가정하여 작업을 다시 예약할 수 있습니다.

MapReduce를 보는 또 다른 방법은 5단계 병렬 분산 계산입니다.

  1. Map() 입력을 준비합니다.MapReduce system은 Map 프로세서를 지정하고 각 프로세서가 동작하는 입력 키 K1을 할당하고 해당 프로세서에 해당 키와 관련된 모든 입력 데이터를 제공합니다.
  2. 사용자가 제공한 Map() 코드를 실행합니다.Map()은 각 K1 키에 대해 정확히 한 번 실행되며 키 K2에 의해 정리된 출력을 생성합니다.
  3. 프로세서에 대한 Map 출력의 "Shuffle" – MapReduce 시스템은 프로세서 감소를 지정하고 각 프로세서가 작업해야 할 K2 키를 할당하고 해당 키와 관련된 모든 Map 생성 데이터를 해당 프로세서에 제공합니다.
  4. 사용자가 제공한 Reduce() 코드를 실행합니다.Reduce()는 Map 스텝에 의해 생성된 각 K2 키에 대해 정확히 한 번 실행됩니다.
  5. 최종 출력 생성 – MapReduce 시스템은 모든 Reduce 출력을 수집하여 K2별로 정렬하여 최종 결과를 생성합니다.

이들 5개의 스텝은 논리적으로 순서대로 실행되는 것으로 생각할 수 있습니다.각 스텝은 이전 스텝이 완료된 후에만 시작됩니다.그러나 실제로는 최종 결과에 영향을 주지 않는 한 인터리빙할 수 있습니다.

대부분의 경우 입력 데이터는 이미 여러 서버 간에 분산되어 있을 수 있습니다.이 경우 로컬로 존재하는 입력 데이터를 처리하는 맵서버를 할당함으로써 스텝1을 대폭 간소화할 수 있습니다.마찬가지로 스텝 3은 처리할 필요가 있는 맵 생성 데이터에 가능한 한 가까운 Reduce 프로세서를 할당함으로써 고속화할 수 있습니다.

논리 뷰

MapReduce의 Map 및 Reduce 함수는 모두 (키, 값) 쌍으로 구성된 데이터와 관련하여 정의됩니다.맵은 한 데이터 도메인에 있는 유형을 가진 데이터 쌍을 가져와서 다른 도메인에 있는 쌍의 목록을 반환합니다.

Map(k1,v1)→list(k2,v2)

Map 기능은 모든 쌍에 병렬로 적용됩니다(키 입력).k1)을 클릭합니다.그러면 쌍 목록이 생성됩니다(키 입력).k2)를 참조해 주세요.그 후 MapReduce 프레임워크는 동일한 키를 사용하여 모든 쌍을 수집합니다(k2)는, 모든 리스트로부터 그룹화되어 각 키에 대해서 1개의 그룹을 작성합니다.

다음으로 Reduce 함수는 각 그룹에 병렬로 적용되어 같은 도메인 내의 값 컬렉션이 생성됩니다.

Reduce(k2, list (v2))→list((k3, v3))[15]

각 축소 콜은 보통 1개의 키 값 쌍 또는 빈 반환 중 하나를 생성합니다.단, 1개의 콜은 여러 개의 키 값 쌍을 반환할 수 있습니다.모든 콜의 반환은 원하는 결과 목록으로 수집됩니다.

따라서 MapReduce 프레임워크는 (키, 값) 쌍의 목록을 다른 (키, 값) [16]쌍의 목록으로 변환합니다.이 동작은 일반적인 기능 프로그래밍 맵과 다르며 축소 조합은 임의의 값 목록을 받아들여 맵에 의해 반환되는 모든 값을 조합한 단일 값을 반환합니다.

MapReduce를 구현하기 위해서는 맵의 구현과 추상화 축소는 필요하지만 충분하지 않습니다.MapReduce의 분산 구현에는 Map 및 Reduce 단계를 수행하는 프로세스를 연결하는 수단이 필요합니다.분산 파일 시스템일 수 있습니다.매퍼에서 리듀서로 직접 스트리밍하거나 매핑 프로세서가 결과를 쿼리하는 리듀서에 제공하는 등 다른 옵션을 사용할 수 있습니다.

예

표준 MapReduce 예제에서는 문서 [17]집합에서 각 단어의 모양을 카운트합니다.


함수 맵(문자열 이름, 문자열 문서): // 이름: 문서 이름 // 문서: 출력(w, 1) 함수 감소(문자열, 반복자 부분 카운트): // 단어: // 단어: // 부분 카운트: 부분 카운트: 집계된 부분 카운트 합계 = 0개 부분 카운트 수: + = 출력(워드, 합계)

여기서, 각 문서를 단어로 분할해, 그 단어를 결과 키로서 맵 기능에 의해서 각 단어를 카운트 한다.프레임워크는 모든 쌍을 동일한 키로 결합하여 동일한 호출에 공급하여 줄입니다.따라서 이 함수는 해당 단어의 전체 모양을 찾기 위해 모든 입력 값을 합하면 됩니다.

또 다른 예로, 11억 명의 인구가 있는 데이터베이스의 경우, 연령에 따라 개인이 가지고 있는 평균적인 사회적 접촉 수를 계산하고 싶다고 가정해 보자.SQL에서 이러한 쿼리는 다음과 같이 표현될 수 있습니다.

  선택한다. 나이, AVG(연락처)     부터 사회의.사람인 그룹. 타고 나이 주문 타고 나이

MapReduce를 사용하여K1 키 값은 각각 100만 레코드의 배치를 나타내는 1부터 1100까지의 정수일 수 있으며, K2 키 값은 개인의 나이(년)가 될 수 있으며, 이 계산은 다음 함수를 사용하여 달성할 수 있다.

함수 맵이 입력됩니다.1 ~ 1100 사이의 정수 K1은 100만 소셜 배지를 나타냅니다.각 사회별 개인 기록.K1배치에 인물 기록 Y가 사람의 나이 연락처의 사람에게 한가지 출력 레코드(Y(N,1))반복 끝 기능 기능을 줄이produce다 N순위가 되게 해 주니 입력:나이(년에)Y각 입력 레코드(Y(N,C))것을 하면 Accumulate S의 합이란 N*C Accumulate에 Cnew이 이 돈의 C반복 동작먹는다A가 하나의 출력 레코드new(Y,(A,Cnew)) 엔드 함수를 생성하도록 합니다.

Reduce 함수에서는 C는 총 N개의 연락처를 가진 사람의 수이므로 Map 함수에서는 모든 출력 쌍이 한 사람의 연락처를 참조하므로 {{1}}이라고 적는 것이 당연합니다.

MapReduce 시스템은 1100 Map 프로세서를 라인업하여 각각에 대응하는 100만 개의 입력 레코드를 제공합니다.Map 스텝에서는 11억(Y,(N,1)의 레코드가 생성되며, Y 값은 예를 들어 8에서 103 사이입니다.다음으로 MapReduce 시스템은 연령별 평균이 필요하기 때문에 키/값 쌍의 shuffling 작업을 수행하여 96 Reduce 프로세서를 라인업하고 각 프로세서에 대응하는 수백만 개의 입력 레코드를 제공합니다.Reduce 스텝에서는 96개의 출력 레코드(Y,A)만 대폭 축소되어 최종 결과 파일에 Y로 정렬됩니다.

처리가 두 번 이상 감소하는 경우 레코드의 카운트 정보가 중요합니다.레코드의 카운트를 추가하지 않으면 다음과 같이 계산된 평균이 잘못됩니다.

-- 지도 출력 #1: 연령, 접점 수 10, 9 10, 9 10, 9
-- 맵 출력 #2: 콘택트 10, 9, 10, 9의 경과시간, 수량
-- 지도 출력 #3: 연령, 콘택트 수 10, 10

파일 #1과 #2를 줄이면 평균 10세((9+9+9+9)/5)의 연락처가 9개인 새로운 파일이 생성됩니다.

-- 스텝 #1: 연령, 콘택트 10, 9의 평균

파일 #3으로 줄이면 이미 본 레코드 수를 셀 수 없게 되므로 10세((9+10)/2)의 경우 평균 9.5 연락처가 됩니다. 이는 잘못된 것입니다.정답은 9.120 = 55 / 6 = (9*3+9*2+10*1)/(3+2+1)입니다.

데이터 흐름

소프트웨어 프레임워크 아키텍처는 코드가 수정 불가능한 프리즈 스폿과 확장 가능한 핫 스팟으로 효과적으로 분할되는 오픈 클로즈드 원칙을 고수합니다.MapReduce 프레임워크의 프리즈 스팟은 대규모 분산 정렬입니다.애플리케이션에 의해 정의되는 핫스팟은 다음과 같습니다.

  • 입력 판독기
  • 지도 함수
  • 분할 함수
  • 비교 함수
  • a 축소 함수
  • 아웃풋 라이터

입력 리더

입력 리더는 입력을 적절한 크기의 '분할'(실제로는 64MB~128MB)로 나누고 프레임워크는 각 Map 함수에 1개의 분할을 할당합니다.입력 리더는 안정적인 스토리지(일반적으로 분산 파일 시스템)에서 데이터를 읽고 키/값 쌍을 생성합니다.

일반적인 예에서는 텍스트파일로 가득 찬 디렉토리를 읽고 각 행을 레코드로 반환합니다.

지도 기능

Map 함수는 일련의 키/값 쌍을 취하여 각각 처리하고 0개 이상의 출력 키/값 쌍을 생성합니다.맵의 입력과 출력 유형은 서로 다를 수 있습니다(대부분 다를 수 있습니다.

응용 프로그램이 워드 카운트를 수행하는 경우 맵 함수는 행을 워드로 분할하고 각 워드의 키/값 쌍을 출력합니다.각 출력 쌍에는 키로서 워드를, 값으로서 행내의 그 워드의 인스턴스 수가 포함됩니다.

파티션 함수

각 Map 함수 출력은 샤딩 목적으로 응용 프로그램의 파티션 함수에 의해 특정 리듀서에 할당됩니다.파티션 함수는 키와 리듀서의 수가 제공되며 원하는 리듀서의 인덱스를 반환합니다.

일반적인 기본값은 키를 해시하고 해시 값 모듈로를 사용하여 환원기 수를 줄이는 것입니다.로드 밸런싱을 위해 샤드당 데이터의 대략적인 균일한 분포를 제공하는 파티션 함수를 선택하는 것이 중요합니다.그렇지 않으면 MapReduce 운영은 느린 리듀서가 완료될 때까지 기다릴 수 있습니다(즉, 리듀서가 불균일하게 분할되지 않은 데이터의 큰 공유를 할당).

맵과 축소 단계 사이에 데이터를 생성한 맵 노드에서 축소되는 샤드로 데이터를 이동하기 위해 데이터를 혼합(노드 간에 병렬 정렬/교환)한다.네트워크 대역폭, CPU 속도, 생성되는 데이터 및 맵에 걸리는 시간에 따라 셔플이 계산 시간보다 오래 걸릴 수 있으며 계산 시간을 줄일 수 있습니다.

비교 함수

각 감소에 대한 입력은 Map이 실행된 기계에서 가져와 애플리케이션의 비교 기능을 사용하여 정렬됩니다.

기능 축소

프레임워크는 정렬된 순서대로 각 고유 키에 대해 애플리케이션의 축소 함수를 한 번 호출합니다.[ Reduce ]는 해당 키와 관련된 값을 반복하여 0 이상의 출력을 생성할 수 있습니다.

워드 카운트 예제에서 감소 함수는 입력 값을 취합하여 워드와 최종 합계의 단일 출력을 생성합니다.

출력 라이터

Output Writer는 Reduce의 출력을 안정적인 저장소에 씁니다.

퍼포먼스에 관한 고려사항

MapReduce 프로그램이 빠르다는 보장은 없습니다.이 프로그래밍 모델의 주요 장점은 플랫폼의 최적화된 셔플 동작을 이용할 수 있다는 것이며, 프로그램의 맵과 축소 부분만 작성하면 됩니다.그러나 실제로 MapReduce 프로그램의 작성자는 셔플 단계를 고려해야 합니다. 특히 파티션 함수와 Map 함수에 의해 쓰여진 데이터의 양은 성능과 확장성에 큰 영향을 미칠 수 있습니다.결합기 기능 등의 추가 모듈을 사용하면 디스크에 기록되거나 네트워크를 통해 전송되는 데이터 양을 줄일 수 있습니다.MapReduce 애플리케이션은 특정 상황에서 [18]하위 선형 속도 향상을 달성할 수 있습니다.

MapReduce 알고리즘을 설계할 때 저자는 계산과 통신 비용 사이에서 좋은 트레이드오프를[11] 선택할 필요가 있다.통신 비용이 계산 [11][18]비용을 좌우하는 경우가 많으며, 많은 MapReduce 구현은 크래시 복구를 위해 모든 통신을 분산 스토리지에 쓰도록 설계되어 있습니다.

MapReduce의 튜닝 퍼포먼스는 매핑, 셔플, 정렬(키에 의한 그룹화), 리덕션의 복잡성을 고려해야 한다.매퍼에 의해 생성되는 데이터의 양은 계산 비용의 대부분을 매핑과 축소 사이에서 전환하는 핵심 파라미터입니다.리덕션에는 비선형 복잡성이 있는 정렬(키 그룹화)이 포함됩니다.따라서 파티션 크기가 작으면 정렬 시간이 단축되지만, 많은 수의 환원제를 사용하는 것은 비현실적일 수 있기 때문에 단점이 있습니다.분할 유닛 사이즈의 영향은 미미합니다(특별히 나쁘게 선택되지 않는 한 <1MB> 등).일부 매퍼가 로컬 디스크에서 로드를 읽을 경우 얻는 이점은 평균적으로 [19]미미합니다.

프로세스가 빠르게 완료되고 데이터가 단일 머신 또는 소규모 클러스터의 메인 메모리에 들어가는 경우 MapReduce 프레임워크를 사용하는 것은 일반적으로 효과적이지 않습니다.이러한 프레임워크는 계산 중에 노드 전체가 손실된 상태에서 복구되도록 설계되었기 때문에 중간 결과를 분산 스토리지에 씁니다.이 크래시 복구는 비용이 많이 들고 계산에 많은 컴퓨터가 포함되어 있고 계산 실행 시간이 긴 경우에만 효과가 있습니다.오류 발생 시 몇 초 만에 완료되는 작업을 재시작할 수 있으며 클러스터 크기에 따라 하나 이상의 시스템에 장애가 발생할 가능성이 빠르게 증가합니다.이러한 문제에 대해서는, 모든 데이터를 메모리에 보관해, 노드 장해에 대한 계산을 재기동하는 것만으로, 또는 데이터가 충분히 작을 때에 분산되어 있지 않은 솔루션이 MapReduce 시스템보다 고속인 경우가 많습니다.

배포 및 신뢰성

MapReduce는 네트워크 내의 각 노드에 데이터 세트의 많은 작업을 분산시킴으로써 신뢰성을 실현합니다.각 노드는 완료된 작업 및 상태 업데이트와 함께 정기적으로 보고해야 합니다.노드가 이 간격보다 오랫동안 무음 상태가 되면 마스터 노드(Google 파일 시스템의 마스터 서버와 유사)는 해당 노드를 비활성 상태로 기록하고 노드의 할당된 작업을 다른 노드로 보냅니다.개별 작업에서는 파일 출력에 이름을 붙이는 원자 연산을 사용하여 병렬 충돌 스레드가 실행 중인지 확인합니다.파일 이름을 변경하면 작업 이름 외에 다른 이름으로 파일을 복사할 수도 있습니다(부작용을 감안).

축소 작업은 거의 동일한 방식으로 작동합니다.병렬 동작에 관한 특성이 열악하기 때문에 마스터 노드는 동작 중인 데이터를 보유하고 있는 노드 또는 같은 랙에서 동작을 줄이도록 스케줄링하려고 합니다.이 속성은 데이터 센터의 백본 네트워크 전체에서 대역폭을 절약하기 때문에 적합합니다.

구현의 신뢰성이 높다고는 할 수 없습니다.예를 들어 이전 버전의 Hadoop에서 NameNode는 분산 파일 시스템의 단일 장애 지점이었습니다.최신 버전의 Hadoop은 "NameNode"에 대한 액티브/패시브 페일오버를 통해 고가용성을 제공합니다.

사용하다

MapReduce는 분산 패턴 기반 검색, 분산 정렬, 웹 링크 그래프 반전, 특이값 분해,[20] 웹 액세스 로그 통계, 반전 인덱스 구성, 문서 클러스터링, 기계 학습,[21] 통계 기계 번역 등 다양한 애플리케이션에서 유용합니다.또한 MapReduce 모델은 멀티코어 및 멀티코어 시스템,[22][23][24] 데스크톱 그리드,[25] 멀티클러스터,[26] 자원봉사 컴퓨팅 환경,[27] 다이내믹 클라우드 환경,[28] 모바일 환경,[29] 고성능 컴퓨팅 [30]환경 등 여러 컴퓨팅 환경에 맞게 조정되었습니다.

구글에서 맵리듀스는 구글의 월드와이드웹 인덱스를 완전히 재생성하는 데 사용되었다.지수를 업데이트하고 다양한 [31]분석을 실행하는 오래된 임시 프로그램을 대체했다.구글의 개발은 배치 처리 대신 스트리밍 조작과 업데이트를 제공하는 Percolator, FlumeJava[32], MillWheel과 같은 기술로 진행되어 완전한 [33]인덱스를 재구축하지 않고도 "라이브" 검색 결과를 통합할 수 있게 되었다.

MapReduce의 안정적인 입출력은 보통 분산 파일 시스템에 저장됩니다.임시 데이터는 일반적으로 로컬 디스크에 저장되며 리듀서에 의해 원격으로 가져옵니다.

비판

신규성 결여

병렬 데이터베이스와 공유되지 않는 아키텍처를 전문으로 하는 컴퓨터 과학자인 David DeWitt와 Michael Stonebraker는 MapReduce를 [34]사용할 수 있는 광범위한 문제에 대해 비판해 왔습니다.그들은 그것의 인터페이스가 너무 낮다고 말했고 그것이 정말로 지지자들이 [35]주장해온 패러다임의 변화를 대변하는 것인지 의문을 제기했다.그들은 Teradata를 20년 이상 존재해 온 선행 기술의 예로 들며 MapReduce 지지자들의 참신성 주장에 이의를 제기했다.그들은 또한 MapReduce 프로그래머와 CODASYL 프로그래머를 비교하면서 둘 다 "낮은 수준의 레코드 [35]조작을 수행하는 낮은 수준의 언어로 쓰는 것"에 주목했다.MapReduce의 입력 파일 사용 및 스키마 지원 부족은 B-tree 및 해시 파티셔닝과 같은 일반적인 데이터베이스 시스템 기능에 의한 성능 향상을 방지하지만, Pig(또는 PigLatin), Sawzall, Apache [36]Hive[37], HBase 및[37][38] Bigtable과 같은 프로젝트는 이러한 문제의 일부에 대처하고 있습니다.

Greg Jorgensen은 이러한 [39]관점을 거부하는 기사를 썼다.Jorgensen은 DeWitt와 Stonebraker의 분석 전체가 근거가 없다고 단언한다.MapReduce는 데이터베이스로 사용되도록 설계되거나 의도된 것이 아니기 때문이다.

이후 DeWitt와 Stonebraker는 2009년에 여러 특정 문제에 [40]대한 Hadoop의 MapReduce 및 RDBMS 접근 방식의 성능을 비교한 상세한 벤치마크 연구를 발표했습니다.그들은 관계형 데이터베이스가 특히 복잡한 처리나 기업 전체에서 데이터가 사용되는 다양한 종류의 데이터 사용에 실질적인 이점을 제공하지만, MapReduce는 사용자가 단순하거나 일회성 처리 작업에 더 쉽게 채택할 수 있다고 결론지었다.

MapReduce 프로그래밍 패러다임은 Danny Hillis의 1985년 논문에도 기술되어 있으며, 당시 Connection Machine을 프로그래밍하는 데 널리 사용되었습니다. Connection Machine은 맵을 가속화하고 축소하는 특별한 하드웨어 지원을 가지고 있었습니다.

2010년 구글은 MapReduce에 대한 특허로 기술된 것을 승인받았다.2004년에 출원된 이 특허는 Hadoop, CouchDB 및 기타 오픈 소스 소프트웨어에 의한 MapReduce 사용을 포함할 수 있습니다.Ars Technica에서 편집자는 MapReduce 개념을 대중화한 구글의 역할을 인정하면서도 특허가 유효한지 새로운지에 의문을 [42][43]제기했다.2013년 구글은 "OPN(Open Patent Non-Assertion) 서약"의 일환으로 이 특허를 [44][45]방어적으로만 사용하겠다고 약속했다.특허는 2026년 [46]12월 23일에 만료될 예정입니다.

제한된 프로그래밍 프레임워크

MapReduce 태스크는 배치 작업 스케줄러에 의해 실행되는 비순환 데이터 흐름 프로그램, 즉 상태 비저장 매퍼와 상태 비저장 리듀서로 작성되어야 합니다.이 패러다임은 데이터셋의 반복적인 쿼리를 어렵게 하며, 단일 작업 세트를 여러 번 재방문하는 반복 알고리즘이 [47]표준인 머신러닝과 같은 분야에서 느끼는 제한을 가한다.

「 」를 참조해 주세요.

MapReduce 구현

레퍼런스

  1. ^ "MapReduce Tutorial". Apache Hadoop. Retrieved 3 July 2019.
  2. ^ "Google spotlights data center inner workings". cnet.com. 30 May 2008.
  3. ^ "MapReduce: Simplified Data Processing on Large Clusters" (PDF). googleusercontent.com.
  4. ^ Wickham, Hadley (2011). "The split-apply-combine strategy for data analysis". Journal of Statistical Software. 40: 1–29. doi:10.18637/jss.v040.i01.
  5. ^ "당사의 추상화는 지도에서 영감을 얻어 리스프와 다른 많은 기능적 언어로 존재하는 원형을 줄입니다." - "MapReduce: Google Research의 Jeffrey Dean과 Sanjay Ghemawat의 "대규모 클러스터에서의 데이터 처리 단순화"
  6. ^ Lämmel, R. (2008). "Google's Map Reduce programming model — Revisited". Science of Computer Programming. 70: 1–30. doi:10.1016/j.scico.2007.07.001.
  7. ^ http://www.mcs.anl.gov/research/projects/mpi/mpi-standard/mpi-report-2.0/mpi2-report.htm MPI 2 표준
  8. ^ "MPI Reduce and Allreduce · MPI Tutorial". mpitutorial.com.
  9. ^ "Performing Parallel Rank with MPI · MPI Tutorial". mpitutorial.com.
  10. ^ "MongoDB: Terrible MapReduce Performance". Stack Overflow. October 16, 2010. The MapReduce implementation in MongoDB has little to do with map reduce apparently. Because for all I read, it is single-threaded, while map-reduce is meant to be used highly parallel on a cluster. ... MongoDB MapReduce is single threaded on a single server...
  11. ^ a b c Ullman, J. D. (2012). "Designing good MapReduce algorithms". XRDS: Crossroads, the ACM Magazine for Students. 19: 30–34. doi:10.1145/2331042.2331053. S2CID 26498063.
  12. ^ Sverdlik, Yevgeniy (2014-06-25). "Google Dumps MapReduce in Favor of New Hyper-Scale Analytics System". Data Center Knowledge. Retrieved 2015-10-25. "We don't really use MapReduce anymore" [Urs Hölzle, senior vice president of technical infrastructure at Google]
  13. ^ Harris, Derrick (2014-03-27). "Apache Mahout, Hadoop's original machine learning project, is moving on from MapReduce". Gigaom. Retrieved 2015-09-24. Apache Mahout [...] is joining the exodus away from MapReduce.
  14. ^ Czajkowski, Grzegorz; Marián Dvorský; Jerry Zhao; Michael Conley. "Sorting Petabytes with MapReduce – The Next Episode". Retrieved 7 April 2014.
  15. ^ "MapReduce Tutorial".
  16. ^ "Apache/Hadoop-mapreduce". GitHub. 31 August 2021.
  17. ^ "Example: Count word occurrences". Google Research. Retrieved September 18, 2013.
  18. ^ a b Senger, Hermes; Gil-Costa, Veronica; Arantes, Luciana; Marcondes, Cesar A. C.; Marín, Mauricio; Sato, Liria M.; da Silva, Fabrício A.B. (2015-01-01). "BSP cost and scalability analysis for MapReduce operations". Concurrency and Computation: Practice and Experience. 28 (8): 2503–2527. doi:10.1002/cpe.3628. hdl:10533/147670. ISSN 1532-0634. S2CID 33645927.
  19. ^ Berlińska, Joanna; Drozdowski, Maciej (2010-12-01). "Scheduling divisible MapReduce computations". Journal of Parallel and Distributed Computing. 71 (3): 450–459. doi:10.1016/j.jpdc.2010.12.004.
  20. ^ Bosagh Zadeh, Reza; Carlsson, Gunnar (2013). "Dimension Independent Matrix Square Using MapReduce" (PDF). arXiv:1304.1467. Bibcode:2013arXiv1304.1467B. Retrieved 12 July 2014. {{cite journal}}:Cite 저널 요구 사항 journal=(도움말)
  21. ^ Ng, Andrew Y.; Bradski, Gary; Chu, Cheng-Tao; Olukotun, Kunle; Kim, Sang Kyun; Lin, Yi-An; Yu, YuanYuan (2006). "Map-Reduce for Machine Learning on Multicore". NIPS 2006.
  22. ^ Ranger, C.; Raghuraman, R.; Penmetsa, A.; Bradski, G.; Kozyrakis, C. (2007). "Evaluating MapReduce for Multi-core and Multiprocessor Systems". 2007 IEEE 13th International Symposium on High Performance Computer Architecture. p. 13. CiteSeerX 10.1.1.220.8210. doi:10.1109/HPCA.2007.346181. ISBN 978-1-4244-0804-7. S2CID 12563671.
  23. ^ He, B.; Fang, W.; Luo, Q.; Govindaraju, N. K.; Wang, T. (2008). "Mars: a MapReduce framework on graphics processors" (PDF). Proceedings of the 17th international conference on Parallel architectures and compilation techniques – PACT '08. p. 260. doi:10.1145/1454115.1454152. ISBN 9781605582825. S2CID 207169888.
  24. ^ Chen, R.; Chen, H.; Zang, B. (2010). "Tiled-MapReduce: optimizing resource usages of data-parallel applications on multicore with tiling". Proceedings of the 19th international conference on Parallel architectures and compilation techniques – PACT '10. p. 523. doi:10.1145/1854273.1854337. ISBN 9781450301787. S2CID 2082196.
  25. ^ Tang, B.; Moca, M.; Chevalier, S.; He, H.; Fedak, G. (2010). "Towards MapReduce for Desktop Grid Computing" (PDF). 2010 International Conference on P2P, Parallel, Grid, Cloud and Internet Computing. p. 193. CiteSeerX 10.1.1.671.2763. doi:10.1109/3PGCIC.2010.33. ISBN 978-1-4244-8538-3. S2CID 15044391.
  26. ^ Luo, Y.; Guo, Z.; Sun, Y.; Plale, B.; Qiu, J.; Li, W. (2011). "A Hierarchical Framework for Cross-Domain MapReduce Execution" (PDF). Proceedings of the second international workshop on Emerging computational methods for the life sciences (ECMLS '11). CiteSeerX 10.1.1.364.9898. doi:10.1145/1996023.1996026. ISBN 978-1-4503-0702-4. S2CID 15179363.
  27. ^ Lin, H.; Ma, X.; Archuleta, J.; Feng, W. C.; Gardner, M.; Zhang, Z. (2010). "MOON: MapReduce On Opportunistic eNvironments" (PDF). Proceedings of the 19th ACM International Symposium on High Performance Distributed Computing – HPDC '10. p. 95. doi:10.1145/1851476.1851489. ISBN 9781605589428. S2CID 2351790.
  28. ^ Marozzo, F.; Talia, D.; Trunfio, P. (2012). "P2P-MapReduce: Parallel data processing in dynamic Cloud environments". Journal of Computer and System Sciences. 78 (5): 1382–1402. doi:10.1016/j.jcss.2011.12.021.
  29. ^ Dou, A.; Kalogeraki, V.; Gunopulos, D.; Mielikainen, T.; Tuulos, V. H. (2010). "Misco: a MapReduce framework for mobile systems". Proceedings of the 3rd International Conference on PErvasive Technologies Related to Assistive Environments – PETRA '10. p. 1. doi:10.1145/1839294.1839332. ISBN 9781450300711. S2CID 14517696.
  30. ^ Wang, Yandong; Goldstone, Robin; Yu, Weikuan; Wang, Teng (May 2014). "Characterization and Optimization of Memory-Resident MapReduce on HPC Systems". 2014 IEEE 28th International Parallel and Distributed Processing Symposium. IEEE. pp. 799–808. doi:10.1109/IPDPS.2014.87. ISBN 978-1-4799-3800-1. S2CID 11157612.
  31. ^ "How Google Works". baselinemag.com. As of October, Google was running about 3,000 computing jobs per day through MapReduce, representing thousands of machine-days, according to a presentation by Dean. Among other things, these batch routines analyze the latest Web pages and update Google's indexes.
  32. ^ Chambers, Craig; Raniwala, Ashish; Perry, Frances; Adams, Stephen; Henry, Robert R.; Bradshaw, Robert; Weizenbaum, Nathan (1 January 2010). FlumeJava: Easy, Efficient Data-parallel Pipelines (PDF). Proceedings of the 31st ACM SIGPLAN Conference on Programming Language Design and Implementation. pp. 363–375. doi:10.1145/1806596.1806638. ISBN 9781450300193. S2CID 14888571. Archived from the original (PDF) on 23 September 2016. Retrieved 4 August 2016.
  33. ^ Peng, D., & Dabek, F. (2010년, 10월)분산 트랜잭션 및 알림을 사용한 대규모 증분 처리.OSDI에서 (Vol. 10, 페이지 1-15).
  34. ^ "Database Experts Jump the MapReduce Shark".
  35. ^ a b David DeWitt; Michael Stonebraker. "MapReduce: A major step backwards". craig-henderson.blogspot.com. Retrieved 2008-08-27.
  36. ^ "Apache Hive – Index of – Apache Software Foundation".
  37. ^ a b "HBase – HBase Home – Apache Software Foundation".
  38. ^ "Bigtable: A Distributed Storage System for Structured Data" (PDF).
  39. ^ Greg Jorgensen. "Relational Database Experts Jump The MapReduce Shark". typicalprogrammer.com. Retrieved 2009-11-11.
  40. ^ Pavlo, Andrew; Paulson, Erik; Rasin, Alexander; Abadi, Daniel J.; DeWitt, Deavid J.; Madden, Samuel; Stonebraker, Michael. "A Comparison of Approaches to Large-Scale Data Analysis". Brown University. Retrieved 2010-01-11.
  41. ^ Hillis, W. Danny (1986). The Connection Machine. MIT Press. ISBN 0262081571.
  42. ^ Paul, Ryan (20 January 2010). "Google's MapReduce patent: what does it mean for Hadoop?". Ars Technica. Retrieved 21 March 2021.
  43. ^ "United States Patent: 7650331 - System and method for efficient large-scale data processing". uspto.gov.
  44. ^ Nazer, Daniel (28 March 2013). "Google Makes Open Patent Non-assertion Pledge and Proposes New Licensing Models". Electronic Frontier Foundation. Retrieved 21 March 2021.
  45. ^ King, Rachel (2013). "Google expands open patent pledge to 79 more about data center management". ZDNet. Retrieved 21 March 2021.
  46. ^ "System and method for efficient large-scale data processing". Google Patents Search. 18 June 2004. Retrieved 21 March 2021.
  47. ^ Zaharia, Matei; Chowdhury, Mosharaf; Franklin, Michael; Shenker, Scott; Stoica, Ion (June 2010). Spark: Cluster Computing with Working Sets. HotCloud 2010.
Wikimedia Commons에는 MapReduce 관련 미디어가 있습니다.