MapReduce에 대한 간단한 설명?

MapReduce에 대한 간단한 설명?

---

내 CouchDB 질문과 관련이 있습니다.

누구나 Numbnuts가 이해할 수있는 용어로 MapReduce를 설명 할 수 있습니까?

---

지도 및 축소에 대한 기본 사항으로 넘어갑니다.

---

맵 은 어떤 종류의 목록에있는 항목을 다른 종류의 항목으로 "변환"하여 같은 종류의 목록에 다시 넣는 기능입니다.

숫자 목록이 [1,2,3]이고 모든 숫자를 두 배로 늘리려 고한다고 가정합니다.이 경우 "모든 숫자를 두 배로"하는 함수는 함수 x = x * 2입니다. 그리고 매핑없이 간단한 루프

A = [1, 2, 3]
foreach (item in A) A[item] = A[item] * 2

A = [2, 4, 6]이지만 루프를 작성하는 대신 맵 함수가 있으면 작성할 수 있습니다.

A = [1, 2, 3].Map(x => x * 2)

x => x * 2는 [1,2,3]의 요소에 대해 실행될 함수입니다. 프로그램은 각 항목을 가져 와서 x를 각 항목과 동일하게하여 (x => x * 2) 실행하고 결과 목록을 생성합니다.

1 : 1 => 1 * 2 : 2  
2 : 2 => 2 * 2 : 4  
3 : 3 => 3 * 2 : 6  

따라서 (x => x * 2)로 맵 기능을 실행하면 [2, 4, 6]이됩니다.

---

감소 "를 수집"리스트에서 항목이 일부 계산을 수행하는 기능이다 모든 따라서 단일 값들을 감소는 그들.

합계를 찾거나 평균을 찾는 것은 모두 축소 함수의 예입니다. 예를 들어 [7, 8, 9]와 같은 숫자 목록이 있고 합계를 원하면 다음과 같은 루프를 작성합니다.

A = [7, 8, 9]
sum = 0
foreach (item in A) sum = sum + A[item]

그러나 reduce 함수에 액세스 할 수 있다면 다음과 같이 작성할 수 있습니다

A = [7, 8, 9]
sum = A.reduce( 0, (x, y) => x + y )

이제 왜 두 개의 인수 (0과 x와 y의 함수)가 전달되었는지 약간 혼란 스럽습니다. reduce 함수가 유용하려면 2 개의 항목을 가져 와서 무언가를 계산하고 2 개의 항목을 하나의 단일 값으로 "감소"할 수 있어야하므로 프로그램은 단일 값을 가질 때까지 각 쌍을 줄일 수 있습니다.

실행은 다음과 같습니다.

result = 0
7 : result = result + 7 = 0 + 7 = 7
8 : result = result + 8 = 7 + 8 = 15
9 : result = result + 9 = 15 + 9 = 24

그러나 항상 0으로 시작하고 싶지 않기 때문에 첫 번째 인수는 첫 번째 result =줄 의 시드 값을 구체적으로 지정하도록합니다 .

두 목록을 합산한다고 가정하면 다음과 같습니다.

A = [7, 8, 9]
B = [1, 2, 3]
sum = 0
sum = A.reduce( sum, (x, y) => x + y )
sum = B.reduce( sum, (x, y) => x + y )

또는 실제 환경에서 더 쉽게 찾을 수있는 버전 :

A = [7, 8, 9]
B = [1, 2, 3]

sum_func = (x, y) => x + y
sum = A.reduce( B.reduce( 0, sum_func ), sum_func )

---

Map \ Reduce 지원을 통해 DB에 데이터를 저장하는 방법을 알 필요없이 데이터베이스 작업을 수행 할 수 있기 때문에 DB 소프트웨어의 장점은 바로 DB 엔진입니다.

Map 또는 Reduce 함수를 제공하여 원하는 엔진을 "알릴"수 있어야합니다. 그러면 DB 엔진이 데이터를 탐색하고 함수를 적용하고 결과를 얻을 수 있습니다. 모든 레코드를 반복하는 방법을 모른 채 모든 것을 원합니다.

단일 데이터베이스가 보유 할 수있는 인덱스, 키, 조인 및 뷰 및 많은 것들이 있으므로 데이터가 실제로 저장되는 방식으로부터 사용자를 보호함으로써 코드를보다 쉽게 ​​작성하고 유지 관리 할 수 ​​있습니다.

루핑 코드를 실제로 구현하는 대신 데이터로 수행하려는 작업 만 지정하면 병렬 프로그래밍도 마찬가지입니다. 그러면 기반 인프라가 "병렬화"되어 병렬 병렬 루프에서 함수를 실행할 수 있습니다.

---

MapReduce는 개발자가 매퍼 이외의 다른 코드를 작성하고 함수를 줄일 필요없이 방대한 양의 데이터를 병렬로 처리하는 방법입니다.

지도 기능 배리어에 유지되는 결과, 데이터 아웃 및 괴로워 걸린다. 이 기능은 다수의 동일한 맵 작업 과 동시에 실행할 수 있습니다 . 그런 다음 데이터 세트를 스칼라 값 으로 줄일 수 있습니다 .

따라서 SQL 문처럼 생각하면

SELECT SUM(salary)
FROM employees
WHERE salary > 1000
GROUP by deptname

map 을 사용 하여 급여가 1000보다 큰 직원의 하위 집합을 가져와 그룹 크기 버킷의 장벽으로 만들 수 있습니다.

Reduce 는 각 그룹을 합산합니다. 결과 세트를 제공합니다.

Google 논문의 대학 연구 노트 에서 이것을 뽑았습니다.

---

1. 많은 데이터를 가져옵니다
2. 모든 데이텀을 다른 데이텀으로 변환하는 변환을 수행하십시오.
3. 새로운 데이터를 더 간단한 데이터로 결합

2 단계는지도입니다. 3 단계는 축소입니다.

예를 들어

1. 도로의 한 쌍의 압력계에서 두 개의 임펄스 사이의 시간을 확보하십시오.
2. 미터의 거리를 기준으로 해당 시간을 속도로 매핑
3. 그 속도를 평균 속도로 줄이십시오

MapReduce가 Map과 Reduce간에 분리되는 이유는 서로 다른 부분을 쉽게 병렬로 수행 할 수 있기 때문입니다. (특히 Reduce에 특정 수학 속성이있는 경우)

MapReduce에 대한 복잡하지만 좋은 설명은 Google의 MapReduce 프로그래밍 모델-재 방문 (PDF)을 참조하십시오 .

---

MAP 및 REDUCE는 사람이 마지막 공룡을 죽인 때부터 오래된 Lisp 기능입니다.

이름, 거주 인원 및 도시 크기에 대한 정보가있는 도시 목록이 있다고 가정합니다.

(defparameter *cities*
  '((a :people 100000 :size 200)
    (b :people 200000 :size 300)
    (c :people 150000 :size 210)))

이제 인구 밀도가 가장 높은 도시를 찾고 싶을 것입니다.

먼저 MAP을 사용하여 도시 이름 및 인구 밀도 목록을 만듭니다.

(map 'list
     (lambda (city)
         (list (first city)
               (/ (getf (rest city) :people)
                  (getf (rest city) :size))))
     *cities*)

=>   ((A 500) (B 2000/3) (C 5000/7))

REDUCE를 사용하여 인구 밀도가 가장 높은 도시를 찾을 수 있습니다.

(reduce (lambda (a b)
          (if (> (second a) (second b))
             a
             b))
        '((A 500) (B 2000/3) (C 5000/7)))

 =>   (C 5000/7)

두 부분을 결합하여 다음 코드를 얻습니다.

(reduce (lambda (a b)
          (if (> (second a) (second b))
             a
             b))
        (map 'list
             (lambda (city)
                (list (first city)
                   (/ (getf (rest city) :people)
                      (getf (rest city) :size))))
             *cities*))

함수를 소개하자 :

(defun density (city)
   (list (first city)
         (/ (getf (rest city) :people)
            (getf (rest city) :size))))

(defun max-density (a b)
   (if (> (second a) (second b))
          a
          b))

그런 다음 MAP REDUCE 코드를 다음과 같이 작성할 수 있습니다.

(reduce 'max-density
        (map 'list 'density *cities*))

 =>   (C 5000/7)

호출 MAP하고 REDUCE(평가는 내부에 있음), map reduce 라고 합니다 .

---

Google 논문 에서 예제를 보자 . MapReduce의 목표는 어떤 종류의 알고리즘에 대해 병렬로 작업하는 많은 처리 단위를 효율적으로 사용할 수 있도록하는 것입니다. 예는 다음과 같습니다. 모든 단어와 단어 수를 문서 세트에서 추출하려고합니다.

일반적인 구현 :

for each document
    for each word in the document
        get the counter associated to the word for the document
        increment that counter 
    end for
end for

MapReduce 구현 :

Map phase (input: document key, document)
for each word in the document
    emit an event with the word as the key and the value "1"
end for

Reduce phase (input: key (a word), an iterator going through the emitted values)
for each value in the iterator
    sum up the value in a counter
end for

그 주위에, 당신은 Map 단계를 위해 병렬로 처리 될 "분할"로 문서 세트를 분할하는 마스터 프로그램을 갖게 될 것입니다. 방출 된 값은 작업자에 의해 특정 버퍼에 작성됩니다. 마스터 프로그램은 버퍼 처리 준비가 완료되었음을 알리는 즉시 다른 작업자에게 Reduce 단계를 수행하도록 위임합니다.

Every worker output (being a Map or a Reduce worker) is in fact a file stored on the distributed file system (GFS for Google) or in the distributed database for CouchDB.

---

A really easy, quick and "for dummies" introduction to MapReduce is available at: http://www.marcolotz.com/?p=67

Posting some of it's content:

First of all, why was MapReduce originally created?

Basically Google needed a solution for making large computation jobs easily parallelizable, allowing data to be distributed in a number of machines connected through a network. Aside from that, it had to handle the machine failure in a transparent way and manage load balancing issues.

What are MapReduce true strengths?

One may say that MapReduce magic is based on the Map and Reduce functions application. I must confess mate, that I strongly disagree. The main feature that made MapReduce so popular is its capability of automatic parallelization and distribution, combined with the simple interface. These factor summed with transparent failure handling for most of the errors made this framework so popular.

A little more depth on the paper:

MapReduce was originally mentioned in a Google paper (Dean & Ghemawat, 2004 – link here) as a solution to make computations in Big Data using a parallel approach and commodity-computer clusters. In contrast to Hadoop, that is written in Java, the Google’s framework is written in C++. The document describes how a parallel framework would behave using the Map and Reduce functions from functional programming over large data sets.

In this solution there would be two main steps – called Map and Reduce –, with an optional step between the first and the second – called Combine. The Map step would run first, do computations in the input key-value pair and generate a new output key-value. One must keep in mind that the format of the input key-value pairs does not need to necessarily match the output format pair. The Reduce step would assemble all values of the same key, performing other computations over it. As a result, this last step would output key-value pairs. One of the most trivial applications of MapReduce is to implement word counts.

The pseudo-code for this application, is given bellow:

map(String key, String value):

// key: document name
// value: document contents
for each word w in value:
EmitIntermediate(w, “1”);

reduce(String key, Iterator values):

// key: a word
// values: a list of counts
int result = 0;
for each v in values:
    result += ParseInt(v);
Emit(AsString(result));

As one can notice, the map reads all the words in a record (in this case a record can be a line) and emits the word as a key and the number 1 as a value. Later on, the reduce will group all values of the same key. Let’s give an example: imagine that the word ‘house’ appears three times in the record. The input of the reducer would be [house,[1,1,1]]. In the reducer, it will sum all the values for the key house and give as an output the following key value: [house,[3]].

Here’s an image of how this would look like in a MapReduce framework:

As a few other classical examples of MapReduce applications, one can say:

•Count of URL access frequency

•Reverse Web-link Graph

•Distributed Grep

•Term Vector per host

In order to avoid too much network traffic, the paper describes how the framework should try to maintain the data locality. This means that it should always try to make sure that a machine running Map jobs has the data in its memory/local storage, avoiding to fetch it from the network. Aiming to reduce the network through put of a mapper, the optional combiner step, described before, is used. The Combiner performs computations on the output of the mappers in a given machine before sending it to the Reducers – that may be in another machine.

The document also describes how the elements of the framework should behave in case of faults. These elements, in the paper, are called as worker and master. They will be divided into more specific elements in open-source implementations. Since the Google has only described the approach in the paper and not released its proprietary software, many open-source frameworks were created in order to implement the model. As examples one may say Hadoop or the limited MapReduce feature in MongoDB.

The run-time should take care of non-expert programmers details, like partitioning the input data, scheduling the program execution across the large set of machines, handling machines failures (in a transparent way, of course) and managing the inter-machine communication. An experienced user may tune these parameters, as how the input data will be partitioned between workers.

Key Concepts:

•Fault Tolerance: It must tolerate machine failure gracefully. In order to perform this, the master pings the workers periodically. If the master does not receive responses from a given worker in a definite time lapse, the master will define the work as failed in that worker. In this case, all map tasks completed by the faulty worker are thrown away and are given to another available worker. Similar happens if the worker was still processing a map or a reduce task. Note that if the worker already completed its reduce part, all computation was already finished by the time it failed and does not need to be reset. As a primary point of failure, if the master fails, all the job fails. For this reason, one may define periodical checkpoints for the master, in order to save its data structure. All computations that happen between the last checkpoint and the master failure are lost.

•Locality: In order to avoid network traffic, the framework tries to make sure that all the input data is locally available to the machines that are going to perform computations on them. In the original description, it uses Google File System (GFS) with replication factor set to 3 and block sizes of 64 MB. This means that the same block of 64 MB (that compose a file in the file system) will have identical copies in three different machines. The master knows where are the blocks and try to schedule map jobs in that machine. If that fails, the master tries to allocate a machine near a replica of the tasks input data (i.e. a worker machine in the same rack of the data machine).

•Task Granularity: Assuming that each map phase is divided into M pieces and that each Reduce phase is divided into R pieces, the ideal would be that M and R are a lot larger than the number of worker machines. This is due the fact that a worker performing many different tasks improves dynamic load balancing. Aside from that, it increases the recovery speed in the case of worker fail (since the many map tasks it has completed can be spread out across all the other machines).

•Backup Tasks: Sometimes, a Map or Reducer worker may behave a lot more slow than the others in the cluster. This may hold the total processing time and make it equal to the processing time of that single slow machine. The original paper describes an alternative called Backup Tasks, that are scheduled by the master when a MapReduce operation is close to completion. These are tasks that are scheduled by the Master of the in-progress tasks. Thus, the MapReduce operation completes when the primary or the backup finishes.

•Counters: Sometimes one may desire to count events occurrences. For this reason, counts where created. The counter values in each workers are periodically propagated to the master. The master then aggregates (Yep. Looks like Pregel aggregators came from this place ) the counter values of a successful map and reduce task and return them to the user code when the MapReduce operation is complete. There is also a current counter value available in the master status, so a human watching the process can keep track of how it is behaving.

Well, I guess with all the concepts above, Hadoop will be a piece of cake for you. If you have any question about the original MapReduce article or anything related, please let me know.

---

I don't want to sound trite, but this helped me so much, and it's pretty simple:

cat input | map | reduce > output

---

If you are familiar with Python, following is the simplest possible explanation of MapReduce:

In [2]: data = [1, 2, 3, 4, 5, 6]
In [3]: mapped_result = map(lambda x: x*2, data)

In [4]: mapped_result
Out[4]: [2, 4, 6, 8, 10, 12]

In [10]: final_result = reduce(lambda x, y: x+y, mapped_result)

In [11]: final_result
Out[11]: 42

See how each segment of raw data was processed individually, in this case, multiplied by 2 (the map part of MapReduce). Based on the mapped_result, we concluded that the result would be 42 (the reduce part of MapReduce).

An important conclusion from this example is the fact that each chunk of processing doesn't depend on another chunk. For instance, if thread_1 maps [1, 2, 3], and thread_2 maps [4, 5, 6], the eventual result of both the threads would still be [2, 4, 6, 8, 10, 12] but we have halved the processing time for this. The same can be said for the reduce operation and is the essence of how MapReduce works in parallel computing.

참고URL : https://stackoverflow.com/questions/28982/simple-explanation-of-mapreduce