Thuật toán sắp xếp MapReduce hoạt động như thế nào?

Question

Một trong những ví dụ chính được sử dụng để chứng minh sức mạnh của MapReduce là Terasort benchmark. Tôi gặp sự cố khi hiểu các khái niệm cơ bản về thuật toán sắp xếp được sử dụng trong môi trường MapReduce.

Để tôi phân loại đơn giản liên quan đến việc xác định vị trí tương đối của một phần tử trong mối quan hệ với tất cả các phần tử khác. Vì vậy, phân loại liên quan đến việc so sánh "mọi thứ" với "mọi thứ". Thuật toán sắp xếp trung bình của bạn (nhanh, bong bóng, ...) đơn giản thực hiện điều này một cách thông minh.

Trong tâm trí của tôi chia tập dữ liệu thành nhiều phần có nghĩa là bạn có thể sắp xếp một phần duy nhất và sau đó bạn vẫn phải tích hợp các phần này vào bộ dữ liệu được phân loại đầy đủ. Với bộ dữ liệu terabyte phân phối trên hàng nghìn hệ thống, tôi mong đợi đây là một nhiệm vụ rất lớn.

Vậy điều này thực sự được thực hiện như thế nào? Thuật toán sắp xếp MapReduce này hoạt động như thế nào?

Cảm ơn bạn đã giúp tôi hiểu.

Answer 1

Dưới đây là một số chi tiết trên Hadoop's implementation for Terasort:

TeraSort là một bản đồ tiêu chuẩn/giảm loại, ngoại trừ một phân vùng tùy chỉnh mà sử dụng một danh sách sắp xếp của N - 1 phím được lấy mẫu để xác định phạm vi then chốt cho mỗi giảm . Đặc biệt, tất cả các phím sao cho mẫu [i - 1] < = khóa < mẫu [i] được gửi để giảm i. Điều này đảm bảo rằng đầu ra của giảm i đều nhỏ hơn đầu ra của việc giảm i + 1. "

Vì vậy, mẹo của chúng là xác định các khóa trong giai đoạn bản đồ. một giảm duy nhất là đảm bảo để được 'trước sắp xếp' chống lại tất cả gia giảm khác.

tôi tìm thấy tài liệu tham khảo giấy qua James Hamilton's Blog Post.

Answer 2

Google tham khảo: MapReduce: Simplified Data Processing on Large Clusters

Xuất hiện trong:
OSDI'04: Thứ sáu Hội nghị chuyên đề về Hệ điều hành Thiết kế và thực hiện,
San Francisco, CA, tháng Mười Hai, 2004.

Liên kết đó có tham chiếu PDF và HTML-Slide.

Ngoài ra còn có Wikipedia page with description với các tham chiếu triển khai.

Cũng chỉ trích,

David DeWitt và Michael Stonebraker, các chuyên gia tiên phong trong cơ sở dữ liệu song song và kiến ​​trúc không có gì chia sẻ, đã thực hiện một số khẳng định gây nhiều tranh cãi về bề rộng của vấn đề mà MapReduce có thể được sử dụng cho. Họ gọi giao diện của nó quá thấp, và đặt câu hỏi liệu nó thực sự đại diện cho sự thay đổi mô hình những người ủng hộ nó đã tuyên bố nó là như thế nào. Họ thách thức những tuyên bố của những người ủng hộ MapReduce về tính mới, trích dẫn Teradata như một ví dụ về nghệ thuật trước đó đã tồn tại trong hơn hai thập kỷ; họ đã so sánh các lập trình viên MapReduce với các lập trình viên Codasyl, lưu ý cả hai đều "viết bằng một ngôn ngữ cấp thấp thực hiện thao tác ghi mức thấp". Việc sử dụng các tệp đầu vào của MapReduce và thiếu hỗ trợ lược đồ ngăn các cải tiến hiệu suất được bật bởi các tính năng hệ thống cơ sở dữ liệu phổ biến như B-tree và phân vùng băm, mặc dù các dự án như PigLatin và Sawzall đang bắt đầu giải quyết những vấn đề này.

Answer 3

Chỉ cần đoán ...

Cho một tập lớn các dữ liệu, bạn sẽ phân vùng dữ liệu vào một số khối được xử lý song song (có lẽ bởi con số kỷ lục tức là kỷ lục 1-1000 = phân vùng 1, và Sớm).

Chỉ định/lập lịch mỗi phân vùng cho một nút cụ thể trong cụm.

Mỗi nút cụm sẽ tiếp tục ngắt (ánh xạ) phân vùng đó thành phân vùng nhỏ của riêng nó, có thể theo thứ tự bảng chữ cái chính. Vì vậy, trong phân vùng 1, hãy cho tôi tất cả những thứ bắt đầu với A và xuất nó vào phân vùng mini A của x. Tạo A (x) mới nếu hiện tại đã có A (x). Thay thế x bằng số tuần tự (có lẽ đây là công việc lên lịch để làm như vậy). I E.Cung cấp cho tôi id duy nhất A (x) tiếp theo.

Các công việc bàn giao (lịch biểu) đã hoàn thành bởi người lập bản đồ (bước trước) cho các nút cụm "giảm". Giảm cluster cluster sau đó sẽ tinh chỉnh thêm các loại A (x) phần mà wil cô đơn xảy ra khi các nhiệm vụ của al lthe mapper được thực hiện (Không thể bắt đầu phân loại tất cả các từ bắt đầu w/A khi vẫn còn khả năng vẫn còn sẽ là một phân vùng nhỏ khác trong quá trình tạo). Xuất kết quả trong phần được sắp xếp cuối cùng (ví dụ: Sắp xếp-A, Sắp xếp-B, v.v.)

Sau khi hoàn tất, hãy kết hợp phân đoạn đã sắp xếp thành một tập dữ liệu duy nhất một lần nữa. Tại thời điểm này, nó chỉ là một kết nối đơn giản của các tệp n (trong đó n có thể là 26 nếu bạn chỉ làm A - Z), v.v.

Có thể có các bước trung gian ở giữa ... Tôi không chắc chắn:). I E. tiếp tục lập bản đồ và giảm sau bước giảm ban đầu.

Answer 4

tôi có cùng một câu hỏi khi đọc giấy MapReduce của Google. @Yuval F 's answer giải quyết khá nhiều câu đố của tôi.

Một điều tôi nhận thấy khi đọc bài báo là phép thuật xảy ra trong phân vùng (sau bản đồ, trước khi giảm).

Giấy sử dụng hash(key) mod R làm ví dụ phân vùng, nhưng đây không phải là cách duy nhất để phân đoạn dữ liệu trung gian thành các tác vụ giảm khác nhau.

Chỉ cần thêm điều kiện biên để @Yuval F 's answer để làm cho nó hoàn chỉnh: giả sử min (S) và max (S) là chìa khóa tối thiểu và quan trọng nhất trong những chìa khóa lấy mẫu; tất cả các phím < phút (S) được phân chia thành một tác vụ giảm; ngược lại, tất cả các phím> = max (S) được phân chia thành một tác vụ giảm.

Không có giới hạn cứng trên các khóa được lấy mẫu, chẳng hạn như min hoặc max. Chỉ cần, đồng đều hơn các phím R được phân phối trong tất cả các khóa, nhiều hơn "song song" hệ thống phân tán này và ít có khả năng một toán tử giảm có vấn đề tràn bộ nhớ.