Sắp xếp dữ liệu lớn bằng cách sử dụng MapReduce/Hadoop

Question

Tôi đang đọc về MapReduce và điều sau đây gây nhầm lẫn cho tôi.

Giả sử chúng tôi có một tệp với 1 triệu mục (số nguyên) và chúng tôi muốn sắp xếp chúng bằng cách sử dụng MapReduce. Cách tôi hiểu để đi về nó là như sau:

Viết hàm bản đồ sắp xếp số nguyên. Vì vậy, khung công tác sẽ chia tệp đầu vào thành nhiều phần và sẽ cung cấp cho họ những người lập bản đồ khác nhau. Mỗi người vẽ bản đồ sẽ sắp xếp dữ liệu của họ độc lập với nhau. Khi tất cả các bản đồ được thực hiện, chúng tôi sẽ chuyển từng kết quả của họ tới Reducer và nó sẽ kết hợp kết quả và cho tôi kết quả cuối cùng.

Nghi ngờ của tôi là, nếu chúng ta có một trình giảm tốc, thì nó sẽ tận dụng khung phân phối như thế nào, nếu cuối cùng, chúng ta phải kết hợp kết quả ở một nơi ?. Vấn đề này sẽ giảm xuống để hợp nhất 1 triệu mục ở cùng một nơi. Có phải vậy hay tôi đang thiếu thứ gì đó?

Cảm ơn, Chander

Answer 1

Check-out merge-sort.

Nó chỉ ra rằng sắp xếp một phần danh sách được phân loại là hiệu quả hơn nhiều về hoạt động và mức tiêu thụ bộ nhớ hơn so với phân loại danh sách đầy đủ.

Nếu trình giảm tốc có 4 danh sách được sắp xếp, nó chỉ cần tìm phần tử nhỏ nhất trong 4 danh sách và chọn danh sách đó. Nếu số lượng danh sách là hằng số thì việc giảm này là một hoạt động O (N).

Cũng thường các bộ giảm cũng được "phân phối" trong một cái gì đó giống như một cái cây, vì vậy công việc có thể được song song quá.

Answer 2

Tôi cho rằng, việc kết hợp nhiều mục được sắp xếp hiệu quả hơn kết hợp nhiều các loại chưa phân loại. Vì vậy, người vẽ bản đồ thực hiện nhiệm vụ sắp xếp các khối và trình giảm hợp nhất chúng. Nếu những người lập bản đồ không thực hiện phân loại, trình giảm tốc sẽ có thời gian khó khăn khi phân loại.

Answer 3

Như những người khác đã đề cập, việc hợp nhất đơn giản hơn nhiều so với sắp xếp, vì vậy có một chiến thắng lớn ở đó.

Tuy nhiên, thực hiện thao tác nối tiếp O (N) trên tập dữ liệu khổng lồ cũng có thể bị cấm. Như bạn đã chỉ ra một cách chính xác, tốt hơn là nên tìm cách để thực hiện hợp nhất song song.

Một cách để thực hiện việc này là thay thế chức năng phân vùng từ trình phân vùng ngẫu nhiên (thông thường được sử dụng) thành một cái gì đó thông minh hơn một chút. Ví dụ, Pig làm ví dụ này là lấy mẫu tập dữ liệu của bạn để đưa ra một xấp xỉ gần đúng về phân phối giá trị của bạn và sau đó gán phạm vi giá trị cho các bộ giảm khác nhau. Giảm 0 được tất cả các phần tử < 1000, bộ giảm tốc 1 nhận tất cả các phần tử> = 1000 và < 5000, v.v. Sau đó, bạn có thể làm việc hợp nhất song song, và kết quả cuối cùng được sắp xếp như bạn biết số lượng của mỗi công việc giảm tốc.

Answer 4

Vì vậy, cách đơn giản nhất để sắp xếp sử dụng bản đồ-giảm (mặc dù không phải là người hiệu quả nhất) là làm theo ý

sau

Trong Map Giai đoạn (Input_Key, Input_Value) phát ra (Input_Value, Input Key)

Giảm là một Identity Reduceer

vì vậy, ví dụ nếu dữ liệu của chúng tôi là một sinh viên, cơ sở dữ liệu tuổi sau đó nhập mapper của bạn sẽ là ('A', 1) ('B', 2) ('C' , 10) ... và đầu ra sẽ là (1, A) (2, B) (10, C)

Đã không thử logic này ra nhưng nó là bước trong một bài tập về nhà tôi đang làm việc trên. Sẽ đặt một liên kết mã nguồn/logic cập nhật.

Answer 5

Xin lỗi vì đến trễ nhưng đối với độc giả trong tương lai, có Chandler, bạn đang nhận được nó sai

logic là giảm tốc có thể xử lý xáo trộn và sau đó sắp xếp dữ liệu của nút của nó chỉ mà nó đang chạy. Tôi có nghĩa là giảm tốc chạy ở một nút không thể nhìn vào dữ liệu của nút khác, nó sẽ làm giảm bớt algo trên dữ liệu của nó. Không thể áp dụng thủ tục sáp nhập SO của loại sáp nhập.

Vì vậy, đối với dữ liệu lớn, chúng tôi sử dụng loại Tera, không có gì ngoài trình ánh xạ bản đồ và bộ giảm tốc với trình phân vùng tùy chỉnh. Đọc thêm về nó từ đây Bạn nên đọc thêm về nó từ đây Hadoop's implementation for Terasort. Nó có nghĩa là:

"TeraSort là loại bản đồ/giảm tiêu chuẩn, ngoại trừ phân vùng tùy chỉnh sử dụng danh sách được sắp xếp các phím lấy mẫu N - 1 xác định phạm vi khóa cho mỗi lần giảm. [i - 1] < = phím < 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 giảm i + 1. "

Answer 6

Việc sắp xếp có thể được triển khai hiệu quả bằng cách sử dụng MapReduce. Nhưng bạn dường như đang suy nghĩ về việc thực hiện hợp nhất sắp xếp bằng cách sử dụng mapreduce để đạt được mục đích này. Nó có thể không phải là ứng cử viên lý tưởng.

Giống như bạn ám chỉ, các mergesort (với bản đồ giảm) sẽ liên quan đến các bước sau:

1. phân vùng các yếu tố thành các nhóm nhỏ và gán mỗi nhóm cho người vẽ bản đồ ở round robin cách
2. Mỗi mapper sẽ sắp xếp tập hợp con và trả về {K, {tập hợp con}}, trong đó K giống nhau cho tất cả các người lập bản đồ
3. Vì cùng K được sử dụng trên tất cả các người vẽ bản đồ, chỉ có một giảm và do đó chỉ có một bộ giảm tốc. Trình giảm tốc có thể hợp nhất dữ liệu và trả về kết quả được sắp xếp

Vấn đề ở đây là, như bạn đã đề cập, chỉ có thể có một bộ giảm trừ sự song song trong giai đoạn giảm. Giống như nó đã được đề cập trong các bài trả lời khác, mapreduce triển khai cụ thể như terasort có thể được xem xét cho mục đích này.

Tìm thấy lời giải thích tại http://www.chinacloud.cn/upload/2014-01/14010410467139.pdf

Coming back to merge-sort, đây sẽ là khả thi nếu hadoop (hoặc tương đương) công cụ cung cấp hệ thống các gia giảm mà đầu ra của một mức độ gia giảm đi đến cấp độ tiếp theo của gia giảm hoặc quay trở lại cùng một bộ giảm số