MapReduce
Định nghĩa
MapReduce là programming model xử lý batch trên nhiều machine bằng hai bước chính: map biến input record thành key-value pair, còn reduce tổng hợp mọi value có cùng key.
Cơ chế
Input records
-> map(record)
-> emit(key, value)
-> shuffle/group by key
-> reduce(key, values)
-> outputFramework chịu trách nhiệm phân phối task, gom key, sắp xếp execution và retry khi failure.
Invariant quan trọng
map và reduce phải là pure functions:
- output chỉ phụ thuộc input;
- không query thêm database;
- không tạo side effect.
Nhờ đó framework có thể chạy function ở machine bất kỳ, theo thứ tự bất kỳ hoặc chạy lại mà không thay đổi semantics.
Vị trí giữa declarative và imperative
MapReduce không hoàn toàn declarative vì developer viết logic bằng code. Nó cũng không hoàn toàn imperative vì framework quyết định placement, grouping, order và retry.
So với Declarative Query Language, arbitrary map/reduce code cho optimizer ít thông tin hơn để rewrite hoặc tối ưu query.
Ví dụ trực giác
Đếm số observation theo tháng:
map(observation) -> emit(month, count)
group(month) -> [count1, count2, ...]
reduce(month) -> sum(counts)Trade-off
- Phù hợp với distributed batch computation.
- Pure function làm failure recovery đơn giản hơn.
- Hai function phối hợp thường dài và khó dùng hơn một declarative query.
- MapReduce không độc quyền distributed processing; SQL cũng có thể chạy trên cluster.