-
MapReduce là gì?
MapReduce được thiết kế bởi Google như 1 mô hình lập trình xử lý tập dữ liệu lớn song song, thuật toán được phân tán trên 1 cụm. Mặc dù, MapReduce ban đầu là công nghệ độc quyền của Google, nó đã trở thành thuật ngữ tổng quát hóa trong thời gian gần đây.
MapReduce gồm các thủ tục: 1 Map() và 1 Reduce(). Thủ tục Map() lọc (filter) và phân loại (sort) trên dữ liệu trong khi thủ tục Reduce() thực hiện tổng hợp dữ liệu. Mô hình này dựa tre7m các khái niệm biến đổi của bản đồ và reduce các chức năng trong lập trình hướng chức năng. Thư viện thủ tục Map() và Reduce() được viết bằng nhiều ngôn ngữ. Cài đặt miễn phí, phổ biến nhất của MapReduce là Apache Hadoop.
Các thuận lợi của các thủ tục MapReduce
Nền tảng MapReduce thường gồm các máy chủ phân tán và nó chạy nhiều tác vụ khác nhau song song. Có nhiều thành phần quản lý việc giao tiếp giữa các nodes khác nhau của dữ liệu và cung cấp tính sẵn sàng cao và mức độ chịu lỗi. Chương trình được viết theo chức năng MapReduce đợc tự động được phân tán và thực thi song song trên các máy chủ. Nền tảng MapReduce quan tâm cả chi tiết của phân vùng dữ liệu và thực thi quá trình xử lý trên máy chủ phân tán lúc chạy. Trong khi xử lý nếu có lỗi, nền tảng cung cấp tính sẵn sàng cao và các node khác thực hiện thay thế nhiệm vụ của node bị lỗi.
Như bạn đã thấy toàn bộ nền tảng MapReduce cung cấp nhiều hơn là chỉ các thủ tục Map() và Reduce(); nó cũng cung cấp khả năng mở rộng và chịu lỗi. Cài đặt điển hình của nền tảng MapReduce xử lý nhiều petabytes dữ liệu và hàng ngàn máy chủ.
Nền tảng MapReduce hoạt động như thế nào?
Đây là giải thích cơ bản quy trình MapReduce dùng nhiều máy chủ.
Thủ tục Map()
Luôn có 1 master node trong hạ tầng để nhận đầu vào. Ngay sau master node là các sub-inputs / sub-problems. Các sub-problems được phân phối đến các worker nodes. Một worker node sau đó xử lý chúng. Một khi worker node hoàn thành xử lý với sub-problem, nó trả kết quả trở về master node.
Thủ tục Reduce()
Tất cả worker nodes trả kết quả của sub-problem đã gán cho chúng về master node. Master node thu thập kết quả và tổng hợp thành kết quả của vấn đề lớn (big problem) ban đầu đã được gán cho master node.
Nền tảng MapReduce thực hiện các thủ tục Map() và Reduce() ở trên song song và độc lập nhau. Tất cả thủ tục Map() có thể chạy song song và khi mỗi worker node hoàn thành tác vụ thì chúng gửi trở về master node. Thủ tục cụ thể này có thể rất hiệu quả khi nó được thực hiện trên một số lượng rất lớn dữ liệu (big data).
Nền tảng MapReduce có 5 bước khác nhau:
- Chuẩn bị dữ liệu đầu vào cho Map()
- Thực thi mã Map() được cung cấp bởi người dùng
- Trộn dữ liệu xuất của Map vào Reduce Processor
- Thực thi mã Reduce() được cung cấp bởi người dùng
- Tạo dữ liệu xuất cuối cùng
- Input Reader
- Map Function
- Partition Function
- Compare Function
- Reduce Function
- Output Writer
MapReduce tương đương với SELECT và GROUP BY của 1 cơ sở dữ liệu quan hệ cho 1 cơ sở dữ liệu rất lớn. -
Quy trình giúp xử lý tập hợp dữ liệu siêu lớn, đặt tại các máy tính phân tán; giúp tiết kiệm chi phí xây dựng máy chủ lưu trữ dữ liệu; phát triển điện toán mây...
Bài toán đặt ra
Chúng ta có khối lượng lớn dữ liệu (terabytes) phân bố trên hàng ngàn máy tính biệt lập, và có rất nhiều dự án khác nhau cần dùng cũng như phân tích trên khối dữ liệu này. Làm thế nào để việc thao tác, xử lý dữ liệu hiệu quả, tiết kiệm nhất?
Đây là bài toán đặt ra khi mà mạng xã hội, dịch vụ trực tuyến… ngày càng phát triển mạnh mẽ.
Các khó khăn khi phải xử lý một tập hợp lớn dữ liệu phân tán:
- Quản lý, sắp xếp lịch trình truy xuất I/O
- Quản lý tiến trình song song và phân tán
- Theo dõi trạng thái dữ liệu
- Xử lý lỗi
- Quản lý số lượng lớn dữ liệu có quan hệ phụ thuộc nhau
- ….
MapReduce (MR) là quy trình giúp xử lý tập hợp dữ liệu siêu lớn đặt tại các máy tính phân tán, có thể xử lý được dữ liệu không cấu trúc (dữ liệu lưu trữ dạng tệp tin hệ thống) và dữ liệu cấu trúc (dữ liệu quan hệ 2 chiều). Trong MR, các máy tính chứa dữ liệu đơn lẻ được gọi là các nút (node)
MR định nghĩa dữ liệu (cấu trúc và không cấu trúc) dưới dạng cặp khóa/giá trị (key/value). Ví dụ, key có thể là tên của tập tin (file) và value nội dung của tập tin, hoặc key là địa chỉ URL và value là nội dung của URL,… Việc định nghĩa dữ liệu thành cặp key/value này linh hoạt hơn các bảng dữ liệu quan hệ 2 chiều truyền thống (quan hệ cha – con hay còn gọi là khóa chính – khóa phụ).
Quy trình xử lý
MapReduce được xây dựng từ mô hình lập trình hàm và lập trình song song. Tăng tốc độ thực thi xử lý dữ liệu là mục đích quan trọng nhất của MR. Quy trình này gồm 2 phần:
- Map: Đầu vào là nút chủ (master node) và sau đó chia nhỏ nó ra thành các vấn đề bé hơn. Gọi là các split 0, split 1, split 2, …
- Reduce: Từ các đầu ra trung gian sẽ tổng hợp lại để đưa ra các kết quả cuối cùng cho vấn đề master.
Một ví dụ về hàm Map:
def map (key, value):
list = []
for x in value:
if test:
list.append( (key, x) )
return list
Một ví dụ về hàm Reduce:
def reduce (key, listOgValues):
result = 0
for x in listOgValues:
result += x
return (key, result)
Để xử lý khối dữ liệu bao gồm rất nhiều cặp (key, value), lập trình viên viết hai hàm map và reduce. Hàm map có đầu vào là một cặp (k1, v1) và đầu ra là một danh sách các cặp (k2, v2). Như vập hàm Map có thể được viết theo dạng: map(k1,v1) => list(k2,v2). Và hàm reduce có dạng reduce(k2, list (v2)) => list(v3).
(1): Thư viện MR mà chương trình người dùng (User Program) sử dụng chia các tập tin đầu vào (dữ liệu cần xử lý) thành các phần nhỏ. Dung lượng mỗi phần từ 16 megabytes đến 64 megabytes (MB). Và sau đó sao chép chương trình thành các tiến trình song song chạy trên các máy tính phân tán chứa dữ liệu.
(2): Chương trình điều khiển Master sẽ gán mỗi phần dữ liệu cho một hàm Map và một hàm Reduce.
(3) – (4): worker là phần được gán một hàm Map và Reduce để xử lý, nó sẽ đọc dữ liệu, phân tích cặp key/value ở đầu vào và phân tích thành các cặp trung gian khác được lưu tại vùng nhớ đệm.
(5): Định kỳ, các cặp dữ liệu trung gian sẽ được đẩy đến các worker tương ứng (do master điều khiển) để hàm reduce xử lý. Các thuật toán sắp xếp, so sánh, phân vùng dữ liệu sẽ được sử dụng tại giai đoạn này. Các tập dữ liệu trung gian có cùng key sẽ được sắp xếp cùng một nhóm.
(6): Khi tất cả các tác vụ Map và Reduce đã hoàn tất thì sẽ cho ra kết quả cuối cùng của quy trình MR.
Với MR, rất nhiều máy tính trung gian có thể sử dụng để xử lý dữ liệu mà trước kia không thể.
MR cho phép lập trình viên dễ dàng sử dụng thư viện định tuyến MR để lập trình song song chính xác và hiệu quả, không phải bận tâm đến việc trao đổi dữ liệu giữa các cluster khác nhau vì sự độc lập dữ liệu khá cao; không phải theo dõi xử lý lỗi, các tác vụ…
Hiện nay đã có một số mô hình MR trên các ngôn ngữ Java, C++, Python, Perl, Ruby và C. Lập trình viên có thể lựa chọn ngôn ngữ và thư viện MR để xây dựng ứng dụng của mình. Thường các cài đặt MR đòi hỏi phải chạy trên một hệ thống tệp tin phân tán thích hợp, ví dụ như Google File System (GFS), Amazon S3,…
Ứng dụng thực tế
Năm 2009 dự án mã nguồn mở Hadoop của Apache đã lập kỷ lục thế giới về sắp xếp khối dữ liệu siêu lớn (sắp xếp một petabyte dữ liệu trong 16,25 giờ và một terabyte trong 62 giây). Mỗi ngày có đến vài nghìn hay vài chục nghìn chương trình MR được chạy ở Google, và rất nhiều công ty khác trên thế giới.
MR là giải pháp tốt cho các dạng bài toán xử lý khối lượng dữ liệu phát sinh khổng lồ với các tác vụ phân tích và tính toán phức tạp và không lường trước được, trong các lĩnh vực như khai khác dữ liệu (data mining), phân tích tài chính, mô phỏng, … Một số ví dụ:
- Sắp xếp dữ liệu phân tán: một khối lượng dữ liệu lớn được đặt tại nhiều máy khác nhau và cần phải sắp xếp chúng một cách đồng bộ để các ứng dụng truy xuất đạt hiệu quả cao.
- Đếm tần số truy cập một địa chỉ URL: hàm Map sẽ xử lý nhật ký (log) các yêu cầu truy xuất đến trang web có địa chỉ URL cần đếm và đầu ra là cặp giá trị. Hàm Reduce tiếp tục xử lý và kết quả là cặp giá trị (total count: là tổng số truy cập vào URL đó).
- Dùng trong trí tuệ nhân tạo khi phân tích thống kê.
- Xử lý dữ liệu bản đồ (đường, địa điểm…).
- Bài toán xếp thứ hạng (ranking) một trang web theo mức độ quan tâm của người dùng.
Bằng cách tập trung vào cốt lõi của thuật toán, sử dụng MR tiết kiệm được khá nhiều chi phí xây dựng các máy chủ lưu trữ dữ liệu. Ngoài Google, các hãng Yahoo, Facebook, Rackspace, …cũng đều đã sử dụng MR để xử lý dữ liệu.
Hiện nay người ta bắt đầu sử dụng MR cho việc phát triển các đám mây điện toán, thuật ngữ Cloud MapReduce hứa hẹn mở ra một hướng mới.
Theo PC World
| Similar Threads | Forum | Date |
|---|---|---|
| Analyze Cloud Business Data with Tableau's New NetSuite Integration | Tableau | Nov 7, 2015 |
| At Wheaton, Access to Data Makes People 'Want to Do Better' | Tableau | Nov 7, 2015 |
| In-Memory or Live Data: Which Is Better? | Tableau | Oct 24, 2015 |
| GOOGLE ANALYTICS DATA IS NOT MATCHING WITH TABLEAU REPORT WHEN CONNECTED WITH GOOGLE ANALYTICS | Tableau | Aug 21, 2015 |
| Tableau Kết hợp nhiều Datasource trong một View | Tableau | Aug 19, 2015 |
Bài đăng
0 nhận xét:
Đăng nhận xét