Quá trình nào Map các cặp trung gian

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ụ).

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.