Thiết kế bản đồ / Giảm thuật toán: Bộ kết hợp trong Mapper


Hoàng Gia Bảo
5 năm trước
Hữu ích 6 Chia sẻ Viết bình luận 0
Đã xem 4111

Bộ kết hợp trong Mapper

Gần đây tôi đọc một cuốn sách về thuật toán Map / Giảm của Lin và Dyer . Cuốn sách này cung cấp một cái nhìn sâu sắc trong việc thiết kế các thuật toán M / R hiệu quả. Hôm nay, trong bài đăng này, tôi sẽ đăng về thuật toán kết hợp trong ánh xạ và chương trình M / R mẫu sử dụng thuật toán này.

Ưu điểm của combiner in-mapper so với combiner truyền thống:

Khi một trình ánh xạ với bộ kết hợp truyền thống (bộ giảm tốc nhỏ) phát ra cặp giá trị khóa, chúng được thu thập trong bộ nhớ đệm và sau đó bộ kết hợp tổng hợp một loạt các cặp giá trị khóa này trước khi gửi chúng đến bộ giảm tốc. Hạn chế của phương pháp này là:

  1. Việc thực hiện combiner không được đảm bảo; vì vậy, các công việc MapReduce không thể phụ thuộc vào việc thực hiện kết hợp.
  2. Hadoop có thể lưu trữ các cặp khóa-giá trị trong hệ thống tệp cục bộ và chạy bộ kết hợp sau đó sẽ gây ra IO đĩa đắt tiền.
  3. Một bộ kết hợp chỉ kết hợp dữ liệu trong cùng một bộ đệm. Do đó, chúng tôi vẫn có thể tạo ra nhiều lưu lượng mạng trong giai đoạn xáo trộn ngay cả khi hầu hết các khóa từ một trình ánh xạ đều giống nhau. Để xem điều này, hãy xem xét ví dụ đếm từ, giả sử rằng kích thước bộ đệm là 3 và chúng ta có <key, value> = <Stanford, 3>, <Berkeley, 1>, <Stanford, 7>, <Berkeley, 7>, và <Stanford, 2> phát ra từ một người lập bản đồ. Ba mục đầu tiên sẽ nằm trong một bộ đệm và hai mục cuối sẽ nằm trong bộ đệm khác; kết quả là, bộ kết hợp sẽ phát ra <Stanford, 10>, <Berkeley, 1>, <Berkeley, 7>, <Stanford, 2>. Nếu chúng ta sử dụng bộ kết hợp trong bản đồ, chúng ta sẽ nhận được <Stanford, 12>, <Berkeley, 8>.

Hãy xem xét trường hợp tính điểm trung bình cho học sinh. Hãy để chúng tôi xem xét chúng tôi có dữ liệu dưới đây

s_id c_id đánh dấu
8001 101 78
8001 102 88
8002 101 56
8002 102 77

Mã giả cho thuật toán M / R cơ bản tính toán các điểm trung bình được đưa ra:

class Mapper
    method Map(integer s_id, integer m)
        Emit(integer s_id, integer m)

class Reducer
    method Reduce(integer s_id, integer [m1 , m2 , . . .])
        sum ← 0
        cnt ← 0
        for all integer m ∈ integer [m1 , m2 , . . .] do
            sum ← sum + m
            cnt ← cnt + 1
        avg_m ← sum/cnt
        Emit(integer s_id, float avg_m )

Nếu chúng ta có một số lượng lớn các bản ghi đầu vào thì cùng một số lượng các bản ghi được phát ra từ tác vụ bản đồ sẽ được xáo trộn và sắp xếp trước khi chuyển sang bộ giảm tốc. Lượng truyền dữ liệu lớn này có thể cản trở tốc độ thực hiện công việc M / R tổng thể.

Chúng ta có thể làm cho thuật toán này nhanh hơn bằng cách giảm số lượng bản ghi được phát ra bởi trình ánh xạ. Để đạt được điều này, chúng ta có thể sử dụng một mảng kết hợp để lưu trữ một phần các dấu và một mảng kết hợp khác để lưu trữ số lượng nhãn hiệu và cuối cùng phát ra các giá trị này theo phương pháp gần. Mã pseduo cho bộ kết hợp trong ánh xạ được hiển thị bên dưới:

class Mapper
    method Initialize
        S ← new AssociativeArray
        C ← new AssociativeArray
    method Map(integer s_id, integer m)
        S{s_id} ← S{s_id} + m
        C{s_id} ← C{s_id} + 1
    method Close
        for all integer s_id ∈ S do
            Emit(integer s_id, pair (S{s_id}, C{s_id}))

class Reducer
    method Reduce(integer s_id, pairs [(s1 , c1 ), (s2 , c2 ) . . .])
        sum ← 0
        cnt ← 0
    for all pair (s, c) ∈ pairs [(s1 , c1 ), (s2 , c2 ) . . .] do
            sum ← sum + s
            cnt ← cnt + c
    avg_m ← sum/cnt
    Emit(integer s_id, float avg_m )

Sử dụng thuật toán này, chúng tôi có thể cải thiện hiệu suất của công việc M / R bằng cách giảm số lượng cặp giá trị khóa trung gian được phát ra từ bộ ánh xạ xuống bộ giảm tốc.

Trong bài đăng tiếp theo của tôi, tôi sẽ đăng chương trình M / R bằng cách sử dụng bộ kết hợp trong ánh xạ và cũng so sánh hiệu suất của chương trình này với chương trình M / R mà không sử dụng bất kỳ tối ưu hóa nào.

Hữu ích 6 Chia sẻ Viết bình luận 0
Đã xem 4111