Cook: A Fair Preemptive Resource Scheduler for Compute Clusters

Two Sigma · 2016 · 3. Quy mô lớn · Độ khó: Trung bình — bài gốc

Bối cảnh

Phần lớn tài nguyên compute của Two Sigma được cấp động cho ứng dụng theo nhu cầu, vì chia sẻ hiệu quả hơn cấp tĩnh. Có hai loại job, giống tiến trình foreground/background của OS: interactive (task nhỏ, người dùng chờ kết quả ngay; cần latency thấp) và batch (chạy qua đêm hoặc nhiều ngày trên dải dữ liệu lớn; cần throughput).
Theo Two Sigma, latency thấp cho interactive thường quan trọng hơn throughput cho batch, vì thời gian của con người đắt.
Nguyên tắc công bằng (ai đang dùng ít thì được trước) tự nhiên ưu tiên interactive. Nhưng nếu chỉ có batch: cho batch dùng hết thì interactive tới sau không có chỗ; giữ chỗ cho interactive thì phí nếu nó không tới.

Preemption: cho batch dùng hết tài nguyên rảnh, khi interactive tới thì huỷ một số task batch để lấy lại tài nguyên. Cái giá là mất phần tính toán đã làm, vì đa số job không hỗ trợ checkpoint.
Cumulative Resource Share (CRS): khó nói task của user A quan trọng hơn của user B, nhưng dễ biết thứ tự quan trọng giữa các task của một user. CRS của một task là tổng tài nguyên của các task cùng user quan trọng bằng hoặc hơn nó, chia cho tổng tài nguyên cụm. Preempt khi chênh lệch CRS vượt một hằng số dung sai δ. Cook mở rộng cho trọng số theo user và nhiều loại tài nguyên (CPU, bộ nhớ).
Kiểm chứng trước khi lên production: viết simulator, chạy lại trace production 7 ngày, so có và không có preemption.

Kết quả mô phỏng: 30% job nhanh lên (đều là interactive), 10% chậm đi (đều là batch). Mức sử dụng hiệu dụng (chỉ tính task không bị preempt) giảm dưới 2% trung bình; giảm nhiều nhất vào buổi sáng, khi batch chạy đêm chưa xong mà người dùng đã tới văn phòng chạy interactive.
2016: Cook đã chạy production khoảng 1,5 năm; mở mã nguồn.

Nhiều người dùng chung một cụm: công bằng + preemption giải được mâu thuẫn "cho batch dùng hết" và "giữ chỗ cho interactive" mà không cần đoán tải.
Ưu tiên giữa tenant khó định nghĩa; ưu tiên trong một tenant thì dễ. Dựng thứ tự toàn cục từ thứ tự cục bộ.
Kiểm chứng thuật toán lập lịch bằng replay trace production trong simulator trước khi bật.