CHƯƠNG 1 MÔ HÌNH MapReduce 1. Tổng quan về MapReduce 1. Sự quan trọng của MapReduce Về tính thiết thực, MapReduce cung cấp một công cụ rất hiệu quả để giải quyết các bài toán dữ liệu lớn. Ngoài ra, MapReduce còn quan trọng trong cách nó đã thay đổi việc sắp xếp tính toán trên quy mô lớn.
Nói một cách công bằng thì MapReduce không phải là mô hình tính toán song song đầu tiên được đưa ra. Mô hình phổ biến nhất trong lý thuyết khoa học máy tính có từ mấy thập kỷ trước là PRAM1 (Parallel Random Access Machine). Trong mô hình này, một lượng lớn các vi xử lý chia sẻ một bộ nhớ lớn không giới hạn, hoạt động đồng thời trên một lượng dữ liệu chia sẻ để tạo ra kết quả. Các mô hình khác như LogP2 và BSP3 (Bulk Synchronous Parallel), tuy nhiên không có mô hình nào có được sự thành công như MapReduce.
MapReduce là mức trừu tượng thành công nhất trên các tài nguyên tính toán mở rộng cho đến nay. Tuy nhiên, mức trừu tượng giải quyết sự phức tạp bằng cách che dấu sự chi tiết và đưa ra các hành vi được thiết kế tốt cho ngƣời sử dụng ứng với mức trừu tượng đó. Chính vì thế, mức trừu tượng không thể hoàn hảo, nó làm cho một số công việc dễ hơn, nhưng cũng làm một số công việc khác khó hơn hoặc có khi là không thể thực hiện được. Vấn đề này làm cho việc ứng dụng MapReduce trong một số bài toán cũng có mặt hạn chế.
Điều đó có nghĩa MapReduce không phải là mô hình cuối cùng trong lớp mô hình lập trình mới cho phép xử lý tính toán trên quy mô lớn một cách hiệu quả.org/wiki/Parallel_Random_Access_Machine 2 http://en.org/wiki/LogP_machine 3 http://en.org/wiki/Bulk_Synchronous_Parallel 12 LUAN VAN CHAT LUONG download : add luanvanchat@agmail. Các ý tưởng của MapReduce Giải quyết các bài toán dữ liệu lớn đòi hỏi cách tiếp cận riêng biệt mà nhiều khi đối lập với mô hình tính toán truyền thống. Dưới đây là các ý tƣởng chính của MapReduce: Scale “out” not “up” (mở rộng chứ không nâng cấp): Để tăng sức mạnh xử lý thay vì nâng cấp bộ vi xử lý cũng như khả năng lưu trữ của máy tính (mua các server có khả năng xử lý cao – high-end server) giải pháp đưa ra là tăng số lượng các server thông dụng (low-end server). Giải pháp này kinh tế hơn nhiều so vì nó chỉ bổ sung một số máy tính và tận dụng được các server sẵn có trong khi giải pháp nâng cấp có thể dẫn đến việc mua sắm mới lại toàn bộ các server.
Hơn nữa giá thành của một server chuyên dụng đắt hơn nhiều so với một cụm máy tính thông thường với khả năng xử lý tương đương. Assume failures are common (chấp nhận việc xảy ra lỗi là thường xuyên): Với sự gia tăng về số lượng của các server trong một cluster, lỗi xảy ra là điều bình thường. Do đó các dịch vụ phân tán trên nhiều server phải tính toán đến các lỗi về phần cứng cũng như phần mềm thường xuyên xảy ra. Mô hình lập trình MapReduce có khả năng xử lý các lỗi thông qua một số cơ chế như tự động khởi động lại các task trên cluster node khác nhau.
Move processing to the data (đưa xử lý đến dữ liệu): Trong các ứng dụng tính toán hiệu năng cao truyền thống (High – Prefomance Computing - HPC). Thông thường, một siêu máy tính có các nút xử lý (processing node) và các nút lưu trữ (storage node) được kết nối với nhau qua một kết nối tốc độ cao. Nhiều công việc nặng nề về dữ liệu không phải là những đòi hỏi xử lý cao. Do đó việc tách rời việc lưu trữ dữ liệu và tính toán tạo ra sự thắt cổ chai trong mạng.
Do đó sẽ hiệu quả hơn nếu chuyển sự thực thi xử lý đến dữ liệu thay vì chuyển dữ liệu đến nơi xử lý chúng. MapReduce sử dụng một kiến trúc trong đó các bộ xử lý và đĩa lưu trữ được đặt cùng với nhau. Trong sự thiết lập như vậy, chúng ta có thể tận dụng lợi thế của dữ liệu cục bộ bằng cách chạy đoạn mã trên bộ xử lý một cách trực tiếp trên khối dữ liệu cần xử lý. Hệ thống tập tin phân tán có nhiệm vụ quản lý dữ liệu mà MapReduce xử lý.
Process data sequentially and avoid random access (xử lý dữ liệu tuần tự và tránh truy cập ngẫu nhiên): Trong trường hợp xử lý một lượng lớn dữ liệu, dung lượng bộ nhớ thường không đủ cho toàn bộ dữ liệu xử lý. Do đó dữ liệu phải được lưu trữ trên đĩa. Thời gian cho việc truy cập ngẫu nhiên thường hạn chế bởi sự di chuyển của đầu đọc cũng như tốc độ đĩa do đó làm chậm công việc xử lý. Để tránh hạn chế này, MapReduce được thiết kế để xử lý các 13 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com khối dữ liệu của một tập dữ liệu lớn.
Hide system-level details from the application developer (che giấu mức chi tiết hệ thống đối với nhà phát triển): Để dễ dàng cho các lập trình viên khi viết ứng dụng xử lý phân tán, MapReduce che giấu sự thực thi phức tạp bên dưới. Thay vào đó, MapReduce cung cấp một mô hình lập trình trừu tượng với các interface đơn giản được định nghĩa sẵn. Phương pháp thường được sử dụng để giải quyết các bài toán dữ liệu lớn hiện nay là chia để trị. Ý tưởng là phân mảnh một bài toán lớn thành các bài toán con nhỏ.
Các bài toán nhỏ độc lập với nhau để có thể được giải quyết song song bởi các workers khác nhau – workers có thể là các tiến trình trong bộ vi xử lý hoặc các bộ vi xử lý trong trong bộ vi xử lý đa nhân, các bộ xử lý trên một máy, các máy trên một cụm máy tính. Các kết quả trung gian từ các worker cụ thể sẽ được gộp lại để tạo thành kết quả cuối cùng. Mô hình chia để trị MapReduce có nguồn gốc từ lập trình hàm (Functional Programming). Ví dụ điển hình như các ngôn ngữ lập trình Lisp và ML.
Tính năng chính của lập trình hàm là khái niệm về các hàm bậc cao (higher-order functions), hoặc các hàm chấp nhận tham số của nó là một hàm. Hai hàm bậc cao thường được xây dựng sẵn là Map và Fold. Như hình dưới, cho một danh sách, Map lấy tham số là một hàm f (có 1 tham số) và áp dụng cho toàn bộ phần tử trong danh sách. Cho một danh sách, Fold lấy tham số là một hàm g (có 2 tham số) và một giá trị khởi tạo: g đầu tiên được áp dụng cho giá trị khởi tạo và phần tử đầu tiên trong danh sách, kết quả 14 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com được lưu trong biến trung gian, tiếp tục dùng biến trung gian này để phần tử thứ 2 trong danh sách để làm tham số cho hàm g, công việc tiếp lặp đi lặp lại đến khi hết toàn bộ danh sách.
Fold trả về kết quả cuối cùng là giá trị cuối cùng của biến trung gian. Hàm Map và Fold trong Functional Programming Hàm Map trong MapReduce tương ứng với hàm Map, hàm Reduce tương ứng với hàm Fold trong lập trình hàm. Cấu trúc dữ liệu trong MapReduce Các cặp key-value là cấu trúc dữ liệu cơ bản trong MapReduce. Key và value có thể nhận các giá trị có kiểu cơ bản như số nguyên, số thực, chuỗi hay có thể nhận các kiểu giá trị có cấu trúc do người dùng định nghĩa.
Một phần quan trọng của giải thuật MapReduce là việc xác định cấu trúc key-value trên các tập dữ liệu cần xử lý. Ví dụ, đối với một tập các trang web, các key có thể là các URL và các value có thể là nội dung của các trang HTML, đối với một đồ thị, key có thể là node id và value có thể là danh sách kề của node đó. Trong một số thuật toán key được sử dụng để phân biệt các bộ dữ liệu (giống như khái niệm khóa trong cơ sở dữ liệu), trong khi ở một số thuật toán, các input key không quan trọng và thường được bỏ qua. Mapper và Reducer Trong MapReduce, lập trình viên định nghĩa một lớp Mapper và một lớp Reducer với hai hàm cơ bản sau: map (k1, v1) → [ (k2, v2)] reduce (k2, [v2]) → [ (k3, v3)] Ký hiệu […] để chỉ một danh sách các giá trị.
Đầu vào của một công việc MapReduce (MapReduce job) là dữ liệu được lưu trữ trên hệ thống file phân tán (Distributed File System). Hàm map và reduce lần lượt được cài đặt trong hai lớp 15 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Mapper và Reducer. Mapper được áp dụng cho mọi cặp key-value để tạo ra các cặp key-value trung gian. Reducer được áp dụng cho tất cả các giá trị (value) ứng với cùng một key trung gian để tạo các cặp key-value ở đầu ra.
Giữa 2 pha map và reduce là một phép xử lý nhóm phân tán các cặp key-value trung gian dựa trên các key. Dữ liệu trung gian được gởi đến mỗi reducer theo thứ tự được sắp xếp bởi các key. Tuy nhiên không có một quan hệ thứ thự nào được thiết lập cho các key giữa các reducer với nhau. Các cặp key-value ở đầu ra của các reducer được ghi vào hệ thống file phân tán (các cặp key-value trung gian được bỏ qua).
Đầu ra cuối cùng là r file trên hệ thống file phân tán, trong đó r là số các reducer. Trong phần lớn các trường hợp, việc tổng hợp các đầu ra của các reducer là không cần thiết bởi vì r files thường lại là đầu vào cho một MapReduce job khác. Hình 5 mô tả 2 giai đoạn của một MapReduce job. Hai pha Map và Reduce của một MapReduce job Ví dụ minh họa MapReduce: Ứng dụng đếm từ (Word count) trong một tập văn bản.
Input: Tập văn bản Outut: Danh sách các từ cùng số lần xuất hiện của chúng trong tập văn bản. class Mapper method Map (docId a, doc d) 16 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com for all term t ϵ doc d do Emit (term t, count 1) class Reducer method Reduce (term t, counts[c1, c2,…]) sum ← 0 for all count c ϵ counts[c1, c2,…] do sum ← sum + c Emit (term t, count sum) Hàm Map duyệt qua từng từ trong tập văn bản ứng với mỗi từ sẽ tạo ra một cặp key-value với key chính là từ vừa gặp và value = 1. Hàm Reduce nhận đầu vào là một từ (term) và và danh sách tần số ci bắt gặp của term đó (các giá trị thực là các số 1), Reduce chỉ đơn giản cộng tất cả các giá trị ci trong danh sách counts.