MapReduce - map, reduce qua ví dụ Donald Duck

Giới thiệu

Bài này học MapReduce chia việc lớn cho nhiều máy. Mô hình này giúp đếm triệu phiếu bầu siêu nhanh.

Kiến thức cần nhớ

Song song và phân tán

• Song song: nhiều luồng chung một bộ nhớ một máy.
• Phân tán: nhiều máy riêng bộ nhớ, nói nhau qua mạng.
• Phân tán lo thêm máy chết giữa chừng và mạng chậm.
• Ví dụ đời thường: một bếp nhiều tay so với nhiều bếp nhiều quán.

Chuyện vịt Donald

• Donald một mình đếm triệu phiếu tới già không xong.
• Thuê đàn vịt con mỗi con đếm một thùng riêng.
• Mỗi con báo cáo số phiếu từng ứng viên thùng mình.
• Ví dụ đời thường: chia lớp chấm thi rồi cộng bảng điểm lại.

Map rồi reduce

• Map: nhận một mảnh, nhả ra cặp khóa-giá trị trung gian.
• Shuffle: gom mọi giá trị cùng khóa về cùng một máy.
• Reduce: gộp danh sách giá trị thành kết quả cuối.
• Ví dụ đời thường: đếm từ thì map nhả (từ,1), reduce cộng lại.

# Đếm từ bằng map-reduce thu nhỏ
def map_dong(dong):
    return [(tu, 1) for tu in dong.split()]  # mỗi từ một phiếu
def reduce_tu(tu, ds):
    return (tu, sum(ds))  # cộng hết phiếu cùng từ

Ví dụ

• Input: 3 dòng văn bản đếm từ -> Output: tổng đếm bằng tổng số từ vào.
• Câu này kiểm tra không mất không thừa một từ.
• Input: đầu vào rỗng -> Output: đầu ra rỗng, không treo.
• Câu này kiểm tra biên rỗng xử lý sạch.

💻 Bài tập

Ngôn ngữ: Python 3 với multiprocessing. Nộp vào day-050/.

Bài 1: Khung MapReduce tí hon

def run_mapreduce(inputs: list, mapper, reducer, n_workers: int = 4, combiner=None) -> dict:
    """mapper(item) -> iterable[(key, value)]
       reducer(key, values: list) -> value
       Map song song bằng multiprocessing.Pool, shuffle gom theo key, reduce song song."""

Đếm từ 3 dòng "a b a", "b c", "a" -> {a: 3, b: 2, c: 1}
inputs = []                        -> {}

Bài 2: Đếm phiếu của Donald

Sinh 10 file, mỗi file $10^6$ dòng, mỗi dòng là tên 1 ứng viên (5 ứng viên, phân bố không đều).

1. Đếm phiếu bằng khung Bài 1, mapper đọc 1 file.
2. Đo thời gian với n_workers = 1, 2, 4, 8. Vẽ tăng tốc.
3. So số cặp đi qua Shuffle khi có và không có combiner.

Kiểm tra: tổng phiếu = 10.000.000

Bài 3: Thêm các job khác (nâng cao)

1. Chỉ mục ngược: từ nhiều file văn bản, trả dict[từ, sorted list[tên file]].
2. Nhiệt độ lớn nhất theo năm: từ file năm,nhiệt_độ, trả max mỗi năm.
3. Mô phỏng lỗi: mapper ném lỗi ngẫu nhiên 10% số lần. Thêm cơ chế chạy lại task lỗi tối đa 3 lần. Kết quả cuối vẫn đúng.

✅ Tiêu chí hoàn thành

• Test mẫu pass, kết quả giống bản chạy tuần tự.
• Bảng/biểu đồ tăng tốc có số thật và giải thích vì sao không tăng tuyến tính.
• Combiner giảm số cặp Shuffle, có số liệu.
• Bài 3 chạy lại task lỗi mà kết quả vẫn đúng.

❓ Câu hỏi ôn tập

• Song song khác phân tán ở đâu?
• Chuyện vịt Donald ánh xạ map reduce sao?
• Shuffle gom dữ liệu thế nào?
• Bài nào không hợp với MapReduce?

🌕 Bạn đã hoàn thành ngày 50. Làm hết bài tập phía trên rồi sang ngày tiếp theo.