Giải thích đơn giản về MapReduce?

Question

Liên quan đến câu hỏi CouchDB của tôi.

Bất cứ ai có thể giải thích về MapReduce trong điều kiện một con tê có thể hiểu không?

Answer 1

1. Đi một loạt các dữ liệu
2. Thực hiện một số loại chuyển đổi có thể chuyển đổi tất cả các dữ kiện để một loại dữ kiện
3. Kết hợp những dữ liệu mới vào dữ liệu nào đơn giản hơn

Bước 2 là Map. Bước 3 là Giảm.

Ví dụ, thời gian

1. Nhận giữa hai xung trên một cặp mét áp lực trên đường
2. Bản đồ những lần vào tốc độ dựa trên khoảng cách của mét
3. Giảm những tốc độ để một tốc độ trung bình

Lý do MapReduce được chia giữa Bản đồ và Giảm là vì các phần khác nhau có thể dễ dàng được thực hiện song song. (Đặc biệt nếu Reduce có các thuộc tính toán học nhất định.)

Để có mô tả phức tạp nhưng tốt về MapReduce, hãy xem: Google's MapReduce Programming Model -- Revisited (PDF).

Answer 2

Hãy lấy ví dụ từ Google paper. Mục tiêu của MapReduce là có thể sử dụng hiệu quả một tải các đơn vị xử lý hoạt động song song với một số loại thuật toán. Ví dụ như sau: bạn muốn trích xuất tất cả các từ và số đếm của chúng trong một tập hợp các tài liệu.

tiêu biểu thực hiện: thực hiện

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 

Khoảng đó, bạn sẽ có một chương trình tổng thể mà sẽ phân vùng bộ chứng từ trong "chia rẽ" sẽ bị xử lý song song cho giai đoạn Bản đồ. Các giá trị phát ra được viết bởi người lao động trong bộ đệm cụ thể cho người lao động. Chương trình tổng thể sau đó giao cho các công nhân khác thực hiện pha Giảm ngay khi được thông báo rằng bộ đệm đã sẵn sàng để xử lý.

Mọi đầu ra của nhân viên (là bản đồ hoặc nhân viên Giảm) thực tế là một tệp được lưu trữ trên hệ thống tệp phân tán (GFS cho Google) hoặc trong cơ sở dữ liệu được phân phối cho CouchDB.

Answer 3

MapReduce là một phương thức xử lý một lượng lớn dữ liệu song song mà không yêu cầu nhà phát triển viết bất kỳ mã nào khác ngoài các hàm bản đồ và giảm.

Chức năng Bản đồ sẽ lấy dữ liệu và hủy kết quả, được giữ trong hàng rào. Hàm này có thể chạy song song với một số lượng lớn cùng một tác vụ bản đồ. Tập dữ liệu sau đó có thể được giảm thành giá trị vô hướng.

Vì vậy, nếu bạn nghĩ về nó như một câu lệnh SQL

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

Chúng ta có thể sử dụng bản đồ để có được tập hợp con của chúng ta về người lao động với mức lương> 1000 mà bản đồ phát ra đến hàng rào vào xô kích thước nhóm.

Giảm sẽ tổng hợp từng nhóm đó. Cung cấp cho bạn tập hợp kết quả của bạn.

chỉ gảy này từ university ghi chú nghiên cứu của tôi về giấy google

Answer 4

Đi tất cả các con đường xuống những điều cơ bản cho Bản đồ và giảm.

---

Bản đồ là một chức năng mà "biến" các mục trong một số loại danh sách khác loại mặt hàng và đặt chúng trở lại trong cùng một loại danh sách.

giả sử tôi có một danh sách các số: [1,2,3] và tôi muốn nhân đôi số, trong trường hợp này, hàm "double every number" là hàm x = x * 2. Và không có ánh xạ , tôi có thể viết một vòng lặp đơn giản, nói

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

và tôi muốn có A = [2, 4, 6] nhưng thay vì viết các vòng, nếu tôi có một chức năng bản đồ tôi có thể viết

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

x => x * 2 là một hàm được thực hiện đối với các phần tử trong [1,2,3]. Điều xảy ra là chương trình mất mỗi mục, thực hiện (x => x * 2) dựa vào nó bằng cách làm x bằng với mỗi mục và tạo ra một danh sách các kết quả.

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

vì vậy sau khi thực hiện chức năng bản đồ với (x => x * 2), bạn có [2, 4, 6].

---

Giảm là một chức năng mà "thu thập" các mục trong danh sách và thực hiện một số tính toán trên tất cả trong số họ, do đó làm giảm chúng đến một giá trị duy nhất.

Tìm tổng hoặc tìm điểm trung bình là tất cả các trường hợp của hàm reduce. Chẳng hạn như nếu bạn có một danh sách các số, nói [7, 8, 9] và bạn muốn họ tóm tắt, bạn muốn viết một vòng lặp như thế này

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

Nhưng, nếu bạn có quyền truy cập vào một chức năng giảm , bạn có thể viết nó như thế này

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

Bây giờ có một chút khó hiểu tại sao có 2 đối số (0 và hàm với x và y) đã trôi qua. Đối với một hàm reduce hữu ích, nó phải có khả năng lấy 2 mục, tính toán một cái gì đó và "giảm" 2 mục thành một giá trị duy nhất, do đó chương trình có thể giảm từng cặp cho đến khi chúng ta có một giá trị duy nhất.

việc thực hiện sẽ sau:

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

Nhưng bạn không muốn bắt đầu với zero tất cả các thời gian, do đó số đầu tiên là có để cho bạn chỉ định một giá trị hạt giống đặc biệt là giá trị trong lần đầu tiên result = hàng.

nói rằng bạn muốn tổng hợp 2 danh sách, nó có thể trông như thế này:

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) 

hoặc một phiên bản bạn muốn nhiều khả năng tìm thấy trong thế giới thực:

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

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

---

Đó là một điều tốt trong phần mềm DB vì, với sự hỗ trợ Map \ Reduce, bạn có thể làm việc với cơ sở dữ liệu mà không cần biết dữ liệu được lưu trữ trong DB để sử dụng nó như thế nào. Bạn chỉ cần có thể "nói" động cơ những gì bạn muốn bằng cách cung cấp cho họ chức năng Bản đồ hoặc Giảm và sau đó công cụ DB có thể tìm đường xung quanh dữ liệu, áp dụng chức năng của bạn và xuất hiện với các kết quả mà bạn muốn tất cả mà không cần biết làm thế nào nó lặp lại trên tất cả các bản ghi.

Có các chỉ mục và khóa, kết nối và chế độ xem và nhiều nội dung mà một cơ sở dữ liệu có thể giữ, do đó, bằng cách che chắn cho bạn cách dữ liệu được lưu trữ thực sự, mã của bạn được viết và bảo trì dễ dàng hơn.

Cùng với lập trình song song, nếu bạn chỉ định những gì bạn muốn thực hiện với dữ liệu thay vì thực sự triển khai mã lặp, thì cơ sở hạ tầng cơ sở có thể "song song" và thực hiện chức năng của bạn trong một vòng lặp song song đồng thời cho bạn.

Answer 5

MAP và REDUCE là các hàm Lisp cũ từ thời điểm người đàn ông giết chết những con khủng long cuối cùng.

Hãy tưởng tượng bạn có một danh sách các thành phố có thông tin về tên, số người sống ở đó và kích thước của thành phố:

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

Bây giờ bạn có thể muốn tìm ra thành phố với mật độ dân số cao nhất .

Đầu tiên chúng ta tạo ra một danh sách các tên thành phố và mật độ dân số sử dụng 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)) 

Sử dụng REDUCE bây giờ chúng ta có thể tìm thấy thành phố với mật độ dân số lớn nhất.

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

=> (C 5000/7) 

Kết hợp cả hai phần chúng tôi nhận được đoạn mã sau:

(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*)) 

Hãy giới thiệu chức năng:

(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)) 

Sau đó, chúng ta có thể viết MAP của chúng tôi GIẢM mã như:

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

=> (C 5000/7) 

Nó gọi MAP và REDUCE (đánh giá là trong ra ngoài), do đó, nó được gọi là bản đồ giảm.

Answer 6

Tôi không muốn tỏ ra nhàm chán, nhưng điều này đã giúp tôi rất nhiều, và nó khá đơn giản:

cat input | map | reduce > output 

Answer 7

Một thực sự dễ, nhanh và "cho núm vú cao su" giới thiệu về MapReduce có sẵn tại địa chỉ: http://www.marcolotz.com/?p=67

đăng một số nội dung của nó:

Trước hết, tại sao MapReduce được tạo ra ban đầu?

Về cơ bản Google cần một giải pháp để thực hiện các công việc tính toán lớn dễ dàng song song, cho phép dữ liệu được phân phối trong một số máy được kết nối qua mạng. Bên cạnh đó, nó đã phải xử lý sự thất bại máy một cách minh bạch và quản lý các vấn đề cân bằng tải.

MapReduce có điểm mạnh thực sự là gì?

Người ta có thể nói rằng phép thuật MapReduce dựa trên ứng dụng chức năng Bản đồ và Giảm. Tôi phải thú nhận người bạn đời, rằng tôi mạnh mẽ không đồng ý. Tính năng chính khiến MapReduce trở nên phổ biến là khả năng tự động song song và phân phối của nó, kết hợp với giao diện đơn giản. Những yếu tố này được tổng hợp với việc xử lý lỗi trong suốt đối với hầu hết các lỗi khiến khung công tác này trở nên phổ biến.

Một chút sâu hơn trên giấy:

MapReduce ban đầu được đề cập trong một bài báo của Google (Dean & Ghemawat, 2004 - liên kết ở đây) như một giải pháp để thực hiện tính toán trong Big dữ liệu sử dụng một cách tiếp cận song song và cụm máy tính-hàng hóa. Ngược lại với Hadoop, được viết bằng Java, khung của Google được viết bằng C++. Tài liệu mô tả cách một khung công tác song song sẽ hoạt động bằng cách sử dụng các hàm Map và Reduce từ lập trình hàm trên các tập dữ liệu lớn.

Trong giải pháp này sẽ có hai bước chính - được gọi là Bản đồ và Giảm - với bước tùy chọn giữa đầu tiên và bước thứ hai - được gọi là Kết hợp. Bước Bản đồ sẽ chạy trước, thực hiện các phép tính trong cặp khóa-giá trị đầu vào và tạo khóa-giá trị đầu ra mới. Người ta phải nhớ rằng định dạng của các cặp khóa-giá trị đầu vào không nhất thiết phải khớp với cặp định dạng đầu ra. Bước Giảm sẽ tập hợp tất cả các giá trị của cùng một khóa, thực hiện các tính toán khác trên nó. Kết quả là bước cuối cùng này sẽ tạo ra cặp khóa-giá trị. Một trong những ứng dụng tầm thường nhất của MapReduce là thực hiện đếm từ.

Các pseudo-code cho ứng dụng này, được đưa ra dưới đây:

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)); 

Như người ta có thể nhận thấy, bản đồ đọc tất cả các từ trong một bản ghi (trong trường hợp này là một kỷ lục có thể là một dòng) và phát ra từ đó làm khóa và số 1 làm giá trị. Sau đó, mức giảm sẽ nhóm tất cả các giá trị của cùng một khóa. Hãy đưa ra một ví dụ: hãy tưởng tượng rằng từ 'nhà' xuất hiện ba lần trong hồ sơ. Đầu vào của bộ giảm tốc sẽ là [house, [1,1,1]]. Trong bộ giảm tốc, nó sẽ tổng hợp tất cả các giá trị cho ngôi nhà quan trọng và cung cấp cho đầu ra giá trị khóa sau: [house, [3]].

Dưới đây là một hình ảnh như thế nào điều này sẽ trông giống như trong một khuôn khổ MapReduce:

Như một vài ví dụ cổ điển khác của các ứng dụng MapReduce, người ta có thể nói:

• Tính của truy cập URL tần số

• Biểu đồ liên kết ngược web

• Phân phối Grep

• Thuật ngữ Vector cho mỗi máy chủ

Để tránh quá nhiều lưu lượng truy cập mạng, bài viết mô tả cách khung nên cố gắng duy trì vị trí dữ liệu. Điều này có nghĩa rằng nó luôn luôn nên cố gắng để đảm bảo rằng một máy chạy công việc bản đồ có dữ liệu trong bộ nhớ của nó/lưu trữ địa phương, tránh để lấy nó từ mạng. Nhằm giảm mạng thông qua đặt một người lập bản đồ, bước kết hợp tùy chọn, được mô tả trước đây, được sử dụng. Combiner thực hiện các tính toán trên đầu ra của các người vẽ bản đồ trong một máy đã cho trước khi gửi nó đến các Hộp số - có thể nằm trong một máy khác.

Tài liệu này cũng mô tả cách các thành phần của khung nên hoạt động trong trường hợp lỗi. Những yếu tố này, trong bài báo, được gọi là công nhân và chủ nhân. Chúng sẽ được chia thành các phần tử cụ thể hơn trong các triển khai nguồn mở. Vì Google chỉ mô tả cách tiếp cận trong bài báo và không phát hành phần mềm độc quyền của nó, nên nhiều khung công tác nguồn mở đã được tạo ra để thực hiện mô hình. Như ví dụ, người ta có thể nói Hadoop hoặc tính năng MapReduce hạn chế trong MongoDB.

Thời gian chạy phải quản lý các chi tiết lập trình không chuyên gia, như phân vùng dữ liệu đầu vào, lập lịch thực thi chương trình trên nhiều máy móc, xử lý lỗi máy (theo cách minh bạch) và quản lý liên lạc giữa các máy. Một người dùng có kinh nghiệm có thể điều chỉnh các thông số này, như cách dữ liệu đầu vào sẽ được phân đoạn giữa các công nhân.

Các khái niệm chính:

• Fault Tolerance: Nó phải chịu đựng thất bại máy một cách duyên dáng. Để thực hiện điều này, các bậc thầy ping công nhân định kỳ. Nếu master không nhận được phản hồi từ một nhân viên cụ thể trong một khoảng thời gian nhất định, master sẽ xác định công việc là không thành công trong công nhân đó. Trong trường hợp này, tất cả các nhiệm vụ bản đồ được hoàn thành bởi công nhân bị lỗi sẽ bị vứt bỏ và được trao cho một công nhân có sẵn khác. Tương tự xảy ra nếu công nhân vẫn đang xử lý một bản đồ hoặc một nhiệm vụ giảm. Lưu ý rằng nếu công nhân đã hoàn thành phần giảm của nó, tất cả các tính toán đã được hoàn thành vào thời điểm nó không thành công và không cần phải được đặt lại. Là một điểm chính của thất bại, nếu thầy thất bại, tất cả công việc thất bại.Vì lý do này, người ta có thể xác định các điểm kiểm tra định kỳ cho tổng thể, để lưu cấu trúc dữ liệu của nó. Tất cả các tính toán xảy ra giữa điểm kiểm tra cuối cùng và lỗi chính bị mất.

• Địa phương: Để tránh lưu lượng mạng, khuôn khổ cố gắng đảm bảo rằng tất cả dữ liệu đầu vào có sẵn cục bộ cho các máy sẽ thực hiện tính toán trên chúng. Trong mô tả ban đầu, nó sử dụng Hệ thống tệp Google (GFS) với hệ số nhân rộng được đặt thành 3 và kích thước khối là 64 MB. Điều này có nghĩa rằng cùng một khối 64 MB (mà soạn một tập tin trong hệ thống tập tin) sẽ có bản sao giống hệt nhau trong ba máy khác nhau. Thầy biết đâu là các khối và cố gắng sắp xếp các công việc bản đồ trong máy đó. Nếu điều đó không thành công, chủ sẽ cố gắng cấp phát một máy gần bản sao của dữ liệu đầu vào nhiệm vụ (nghĩa là máy công nhân trong cùng một giá của máy dữ liệu).

• Nhiệm vụ chi tiết: Giả sử mỗi giai đoạn bản đồ được chia thành các phần M và mỗi giai đoạn Giảm được chia thành các phần R, lý tưởng sẽ là M và R lớn hơn rất nhiều so với số lượng máy công nhân. Điều này là do thực tế là một công nhân thực hiện nhiều nhiệm vụ khác nhau giúp cải thiện cân bằng tải động. Bên cạnh đó, nó làm tăng tốc độ phục hồi trong trường hợp công nhân thất bại (vì nhiều nhiệm vụ bản đồ đã hoàn thành có thể được trải ra trên tất cả các máy khác).

• Tác vụ sao lưu: Đôi khi, một nhân viên Bản đồ hoặc Giảm có thể hoạt động chậm hơn rất nhiều so với những người khác trong cụm. Điều này có thể giữ tổng thời gian xử lý và làm cho nó bằng với thời gian xử lý của máy chậm duy nhất đó. Bài báo gốc mô tả một thay thế được gọi là tác vụ sao lưu, được lập lịch bởi chủ khi một hoạt động MapReduce gần hoàn thành. Đây là những nhiệm vụ được lên lịch bởi Master of the in-progress tasks. Do đó, thao tác MapReduce hoàn thành khi bản sao lưu chính hoặc bản sao lưu kết thúc.

• Bộ đếm: Đôi khi, người ta có thể muốn đếm sự kiện xảy ra. Vì lý do này, đếm được tạo ra ở đâu. Các giá trị bộ đếm trong mỗi công nhân được truyền theo định kỳ cho tổng thể. Sau đó, tổng thể tổng hợp (Yep. Có vẻ như bộ tổng hợp Pregel đến từ nơi này) các giá trị bộ đếm của tác vụ thành công và giảm và trả lại chúng cho mã người dùng khi thao tác MapReduce hoàn tất. Ngoài ra còn có một giá trị truy cập hiện tại có sẵn trong trạng thái chính, do đó, một người xem quá trình có thể theo dõi nó hoạt động như thế nào.

Vâng, tôi đoán với tất cả các khái niệm ở trên, Hadoop sẽ là một miếng bánh cho bạn. Nếu bạn có bất kỳ câu hỏi nào về bài viết MapReduce gốc hoặc bất kỳ điều gì có liên quan, vui lòng cho tôi biết.

Answer 8

Nếu bạn đã quen thuộc với Python, sau đây là lời giải thích có thể đơn giản nhất của 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 

Xem cách mỗi đoạn dữ liệu thô được xử lý riêng, trong trường hợp này, nhân với 2 (đồ một phần của MapReduce). Dựa trên số mapped_result, chúng tôi kết luận rằng kết quả sẽ là 42 (số giảm một phần của MapReduce).

Một kết luận quan trọng từ ví dụ này là thực tế là mỗi đoạn xử lý không phụ thuộc vào đoạn khác. Ví dụ: nếu thread_1 bản đồ [1, 2, 3] và thread_2 bản đồ [4, 5, 6], kết quả cuối cùng của cả hai chủ đề sẽ vẫn là [2, 4, 6, 8, 10, 12] nhưng chúng tôi có được giảm một nửa thời gian xử lý cho điều này. Điều tương tự cũng có thể nói về hoạt động giảm và là bản chất của cách mà MapReduce hoạt động trong tính toán song song.

Answer 9

Đây là giải thích đơn giản nhất về MapReduce mà tôi đã tìm thấy.

Tôi càng giải thích ảnh càng đơn giản.