Home > Programming > Các Scheduler trong Hadoop

Các Scheduler trong Hadoop

Mấy tháng trước tôi có vọc Hadoop, cũng viết được một bài báo cùi bắp. Thầy tự dưng bảo nhảy qua làm Openstack, Hadoop để nhóm khác làm, nay lại muốn mình tiếp tục xem Hadoop. Thật ra tôi thích làm phần này vì còn nhiều khía cạnh mà mình có thể nhúng tay vào.

Mô hình mapreduce đã cố định như vậy, khó có thể cải tiến hơn nữa. Do đó nhiều nghiên cứu tập trung vào scheduler. Scheduler hiệu quả không những giúp tận dụng được tài nguyên của hệ thống mà còn có thể giảm thiểu số lượng task cần backup (do chạy quá chậm), do đó rút ngắn thời gian tính toán. Với xu thế sử dụng cluster ngày càng phổ biến, và các node trong cluster có tài nguyên (cpu, gpu, ram, network…)không đồng nhất , việc có một scheduler hiệu quả càng trở nên quan trọng. Một scheduler tốt chắc chắn biết căn cứ vào tài nguyên hiện có của từng node để phân phát các nhiệm vụ phù hợp.

Bản thân Hadoop được kèm theo 3 loại scheduler: FIFO, Fair scheduler và Capacity scheduler. Trong đó, FIFO là loại được mặc định, không cần phải thiết lập gì thêm cả, cứ xong job này làm đến job khác. Còn với Fair scheduler[1], các job sẽ chia nhau lượng tài nguyên, do đó CPU time là xấp xỉ nhau. Job nào tính ít thì hoàn thành trước, thay vì phải đợi job khác xong mới đến lượt mình như cách mà FIFO làm. Trong cách này, mỗi user được phân cho một bể (pool) tài nguyên, các job mà user submit sẽ dùng chung lượng tài nguyên này. Capacity scheduler[2] khác với Fair scheduler ở chỗ nó không phân phát tài nguyên theo user mà theo queue. Khi có một TaskTracker trống, capacity scheduler sẽ chọn ra một queue có tỉ lệ tài nguyên trống nhiều nhất để lấy nhiệm vụ từ một job trong queue đó mà thực hiện, tất nhiên scheduler cũng phải đảm bảo  TaskTracker đó có đủ memory.

Một điều dễ thấy là 3 loại scheduler trên đều nhắm vào việc schedule các job. Thực tế là việc tính toán nhanh hay chậm còn dựa vào tốc độ thực thi của các task, việc backup các task cũng ảnh hưởng không nhỏ đến thời gian tính toán chung. Hadoop mặc định, một task nào đó (map task hoặc reduce task) nếu chậm hơn 20% tiến độ trung bình của các task cùng loại thì sẽ được backup. Điều này nghe có vẻ hợp lí trong các cluster đồng nhất (cấu hình các node tương đối đồng đều), tuy nhiên trong các cluster không đồng nhất, mà trong đó khả năng tính toán của các node rất khác nhau, điều này sẽ dẫn đến backup một lượng lớn task.

LATE[3](Longest Approximate Time to End)phần nào giải quyết vấn đề trên. Cách schedule này ước lượng thời gian mà mỗi task cần thêm để hoàn thành, task nào cần nhiều thời gian nhất (hoàn thành sau nhất) sẽ được xem xét backup. Tuy nhiên, tài liệu [4] chỉ ra rằng LATE đôi lúc không tìm đúng task cần backup, đồng thời nêu ra phương pháp mới SAMR hiệu quả hơn. SAMR (Self-adaptive MapReduce) dựa vào việc phân tích các thông tin của quá trình chạy được lưu trong các node để tìm ra đúng task nào cần phải backup. Phương pháp này có xét đến tốc độ  khác nhau của các giai đoạn trong mapreduce nên phần nào chính xác hơn LATE.

Tài liệu [5], [6] lại đề cập đến một khía cạnh khác của schedule: ứng dụng mapreduce trong các cluster không đồng nhất có chứa GPU. Ước gì có trong tay code của các vị này, tôi sẽ không phải làm công việc đau đầu mà thầy giao nữa. :D

Tham khảo

[1] http://hadoop.apache.org/common/docs/r0.20.2/fair_scheduler.html

[2] http://hadoop.apache.org/common/docs/r0.20.2/capacity_scheduler.html

[3] Zahafia M, Konwinski A, Joseph A. Improving MapReduce Performance in Heterogeneous Environments [C]. Proc of the 8th Usenix Symp on Operating Systems Design and Implementation, 2008: 29-42

[4] Quan Chen, Daqiang Zhang, Minyi Guo, Qianni Deng, Song Guo. SAMR: A Self-adaptive MapReduce Scheduling Algorithm In Heterogeneous Environment. 10th IEEE International Conference on Computer and Information Technology, 2010: 2736-2743

[5] Koichi Shirahata, Hitoshi Sato, Satoshi Matsuoka. Hybrid Map Task Scheduling for GPU-based Heterogeneous Clusters. 2nd IEEE International Conference on Cloud Computing Technology and Science, 2010: 733-740

[6] B. He, W. Fang, Q. Luo, N. K.Govindaraju, and T. Wang. Mars: A mapreduce framework on graphics processors.  Parallel Architectures and Compilation Techniques, 2008: 260–269

Categories: Programming Tags: ,
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: