MAPREDUCE

I. Thực trạng Big Data và nhu cầu xử lý dữ liệu quy mô lớn

1. Bối cảnh lịch sử tại Google

• Do sự bùng nổ dữ liệu tại Google: Vào những năm đầu thập niên 2000, khối lượng dữ liệu cần xử lý tại Google tăng nhanh một cách chóng mặt. Hệ thống cần phải xử lý hàng Terabyte đến hàng chục Terabyte dữ liệu thô được thu thập từ những trang web hay nhật ký người dùng.

• Nhu cầu tính toán thực tế: Từ các dữ liệu thô, các kỹ sư phải liên tục tính toán để tạo ra các dữ liệu phái sinh để vận hành công cụ tìm kiếm.

• Giới hạn của một máy đơn lẻ: Dù cho phép tính có đơn giản nhưng đối với một lượng dữ liệu khổng lồ đã vượt qua giới hạn xử lý hay lưu trữ thì cũng phải tốn một khoảng thời gian để hoàn thành, nên buộc phải được phân phối và xử lý song song trên hàng trăm hay hàng ngàn máy tính khác.

2. Thách thức của phân tán truyền thống

• Phân tán dữ liệu: Phân nhỏ dữ liệu khổng lồ và phân phối tới các Node máy tính mà không khiến hệ thống bị nghẽn.

• Đồng bộ và truyền thông: Việc giao tiếp và đồng bộ hóa luồng dữ liệu giữa các tiến trình chạy song song đòi hỏi mã nguồn cực phức tạp và dễ phát sinh lỗi.

• Cân bằng tải & Stragglers: Hệ thống phải được phân bổ công việc đồng đều, phải xử lý được hiện tượng máy chạy chậm. Những Node bị lỗi phần cứng hoặc xung đột tài nguyên sẽ khiến tốc độ của toàn bộ tiến trình tính toán chung bị trì trệ.

• Khả năng chịu lỗi: Vì cụm máy được xây dựng dựa trên hàng ngàn thiết bị, sẽ không xác định được thiết bị có bị lỗi hay không, nên hệ thống phân tán bắt buộc phải tự động phát hiện ra lỗi và phân công lại tác vụ để không làm ảnh hưởng đến kết quả chung.

3. Giải pháp MapReduce

• Hàm Map chịu trách nhiệm xử lý các bản ghi thô đầu vào để tạo ra các cặp Key/Value trị trung gian.

• Hàm Reduce thực hiện gộp và thu giảm toàn bộ các giá trị trung gian có chung khóa để cho ra kết quả cuối cùng.

II. Mô hình MapReduce

1. Key/Value trong phân tán dữ liệu

Tư tưởng của mô hình bắt nguồn từ hai hàm nguyên bản Map và Reduce trong ngôn ngữ lập trình Lisp. Triết lý sử dụng cặp Key/Value là nền tảng thiết yếu để đơn giản hóa và chuẩn hóa việc xử lý dữ liệu lớn trên các hệ thống phân tán nhờ vào các yếu tố quyết định sau.

• Tính vạn năng của mô hình dữ liệu cấu trúc hóa: Mọi dữ liệu thô đều có thể được quy nạp dưới dạng Key/Value.

• Cơ chế định tuyến và phân phối dữ liệu tự động: Key đóng vai trò là nhãn định tuyến, thư viện MapReduce dựa trên Value của Key để thực hiện phân vùng dữ liệu trung gian.

• Hỗ trợ song song hóa và độc lập tính toán: Do mỗi ban ghi được cấu trúc độc lập dưới dạng Key/Value, nên hệ thống có thể chi tập dữ liệu lớn thành nhiều tập nhỏ để xử lý song song mà không cần máy chủ phải liên tục đồng bộ trạng thái.

• Khả năng chịu lỗi tự nhiên: Nhờ tính độc lập của các cặp Key/Value và tính phi trạng thái (stateless) của hàm Map/Reduce thì khi một máy chủ gặp sự cố thì hệ thống sẽ cấp phát lại tác vụ cho một máy chủ khác mà không làm gián đoạn tiến trình.

2. Định nghĩa hàm Map/Reduce và các thành phần bổ trợ

2.1. Hàm Map

Tiếp nhận và xử lý bản ghi từ dữ liệu đầu vào để tạo ra một tập hợp các cặp Key/Value trung gian mới.

• Đầu vào: Nhận một cặp Key/Value gốc (k1,v1) trích xuất từ dữ liệu nguồn.

• Đầu ra: Phát ra một danh sách các cặp Key/Value trung gian list(k2, v2).

2.2. Hàm Reduce

Tiếp nhận các khóa trung gian cùng toàn bộ tập hợp giá trị tương ứng để tiến hành gộp nhóm, liên kết hoặc thực hiện các phép toán tổng hợp nhằm tạo ra tập kết quả cuối cùng nhỏ gọn hơn.

• Đầu vào: Nhận một khóa trung gian k2 và một tập hợp các giá trị trung gian list(v2) được truyền qua bộ lặp (iterator) liên kết với khóa đó.

• Đầu ra: Danh sách chứa các giá trị đầu ra, thường là rỗng hoặc chỉ có 0 hoặc 1 giá trị đầu ra được tạo ra cho mỗi lần gọi hàm Reduce.

2.3. Hàm Combiner

• Hoạt động như một Mini-Reduce chạy ngay trên các node thực thi hàm Map.

• Tổng hợp trước các cặp Key/Value trung gian có cùng khóa ngay tại bộ nhớ cục bộ trước khi truyền qua mạng, giúp giảm thiểu đáng kể băng thông mạng trong pha Shuffle & Sort.

2.4. Hàm Partitioner

• Quyết định cặp dữ liệu trung gian nào sẽ được gửi đến Reduce Task nào.

• Sử dụng hàm băm để đảm bảo khối lượng công việc được phân tán đều trên toàn mạng.

3. Sự biến đổi qua các giai đoạn

Quy trình biến đổi gồm 6 bước

Bước 1. Đầu vào (Input Split)

• Dữ liệu thô từ hệ thống tệp phân tán được chia tách và ánh xạ thành các cặp Key/Value đầu tiên có dạng (k1, v1).

Bước 2. Ánh xạ (Map Phase)

• Hàm Map xử lý (k1, v1) để chuyển đổi sang các cặp trung gian (k2, v2).

Bước 3. Tổng hợp cục bộ (Combiner Phase)

• Gom nhóm và xử lý trước các cặp trung gian trùng khóa (k2, v2) cục bộ bằng logic tương tự Reducer, giúp giảm bớt lượng dữ liệu trung gian trước khi truyền qua mạng trên nút Map.

Bước 4. Xáo trộn & Sắp xếp (Shuffle & Sort)

• Hàm Partitioner quyết định phân vùng, sau đó thư viện MapReduce tự động gom các cặp trung gian từ tất cả các máy trạm, sắp xếp theo khóa trung gian k2, để chuyển đổi từ cấu trúc phẳng sang cấu trúc gom nhóm (k2, list(v2)).

Bước 5. Tổng hợp (Reduce Phase)

• Hàm Reduce xử lý (k2, list(v2)) để tạo ra danh sách kết quả cuối cùng list(v2).

Bước 6. Đầu ra (Output Phase)

• Kết quả cuối cùng được ghi xuống đĩa, trả về định dạng lưu trữ tệp đầu ra phù hợp.