Giải quyết bài toán lập lịch phức tạp với OR-Tools CP-SAT

Giải quyết bài toán lập lịch phức tạp với OR-Tools CP-SAT

Trong quá trình cải thiện cách thức lập lịch bảo trì cho hạ tầng đám mây của Akamai, đặc biệt là các tác vụ bảo trì gây gián đoạn trên các máy chủ hypervisor phục vụ hàng trăm nghìn máy ảo (VM), tôi đã đối mặt với một bài toán tối ưu hóa khá phức tạp. Bài toán này đặt ra nhiều ràng buộc cạnh tranh như dung lượng, cam kết mức độ dịch vụ (SLA) về sự gián đoạn của khách hàng, và giới hạn tính đồng thời trên các máy chủ, rack và trung tâm dữ liệu.

Sau khi thử nghiệm nhiều công cụ tối ưu hóa khác nhau, bao gồm cả các bộ giải quyết MIP (Mixed Integer Programming) thương mại và mã nguồn mở, tôi nhận thấy thư viện OR-Tools của Google, cụ thể là bộ giải quyết CP-SAT, là lựa chọn phù hợp nhất cho loại bài toán lập lịch này. Bài viết dưới đây sẽ đi sâu vào lý do tại sao CP-SAT lại hiệu quả đến vậy.

Thách thức trong bảo trì hạ tầng đám mây

Các nhà cung cấp đám mây quản lý các máy chủ vật lý gọi là "hypervisor hosts", nơi chạy các máy ảo của khách hàng. Các máy chủ này cần được bảo trì định kỳ để đảm bảo tính bảo mật và độ tin cậy. Một số tác vụ bảo trì có thể thực hiện thông qua vá lỗi trực tiếp (live patches) mà không cần khởi động lại, nhưng những tác vụ khác yêu cầu khởi động lại máy chủ.

Trước khi khởi động lại, tất cả các máy ảo trên máy chủ đó phải được di chuyển sang các máy chủ khác. Quá trình này gây gián đoạn cho khách hàng, do đó đòi hỏi lập lịch cẩn thận để giảm thiểu tác động trong khi vẫn đảm bảo hoàn thành bảo trì kịp thời.

Quá trình di chuyển máy ảo được tóm tắt qua quy tắc "3C":

• Capacity (Dung lượng): Việc di chuyển máy ảo đòi hỏi dung lượng dự phòng trong trung tâm dữ liệu để chứa các máy ảo được chuyển đi.
• Concurrency (Tính đồng thời): Các thao tác di chuyển tiêu tốn tài nguyên như CPU, I/O đĩa và băng thông mạng. Chỉ có thể thực hiện một số lượng giới hạn các thao tác di chuyển cùng một lúc mà không gây quá tải.
• Conflict (Xung đột): Khách hàng có thể chấp nhận một mức độ gián đoạn nhất định, nhưng bảo trì kế hoạch không được gây quá nhiều phiền toái. Điều này có nghĩa là chỉ một phần nhỏ các máy ảo của bất kỳ khách hàng nào được di chuyển cùng lúc.

Mục tiêu là tìm một lịch trình bảo trì giảm thiểu tổng thời gian hoàn thành trong khi vẫn tuân thủ các ràng buộc trên.

Mô hình hóa bài toán với OR-Tools CP-SAT

OR-Tools là bộ công cụ mã nguồn mở của Google dùng để giải quyết các bài toán tối ưu hóa tổ hợp. CP-SAT là một bộ giải quyết đa năng, đặc biệt phù hợp với các bài toán lập lịch nhờ các biến và ràng buộc chuyên biệt để mô hình hóa thời gian.

Điểm mạnh của CP-SAT nằm ở các biến khoảng thời gian (interval variables), đại diện cho các tác vụ có thời gian bắt đầu, kết thúc và thời lượng. Điều này giúp việc biểu diễn các ràng buộc trở nên trực quan và hiệu quả hơn nhiều so với các phương pháp truyền thống.

Ví dụ, để mô hình hóa việc di chuyển các máy ảo, chúng ta tạo các biến khoảng cho mỗi VM:

vm_interval_vars = {}
for host in hosts:
    vm_interval_vars[host] = {}
    for vm in vms[host]:
        start_var = model.new_int_var(0, planning_horizon, f"{vm}_start")
        end_var = model.new_int_var(0, planning_horizon, f"{vm}_end")
        migration_duration = 10
        vm_interval_var = model.new_interval_var(
            start=start_var, size=migration_duration, end=end_var, name=f"{vm}_interval"
        )
        vm_interval_vars[host][vm] = vm_interval_var

Các biến khoảng này giúp dễ dàng áp dụng các ràng buộc. Ví dụ, AddNoOverlap đảm bảo các tác vụ không chồng chéo lên nhau, hoặc AddCumulative giới hạn tổng mức sử dụng tài nguyên tại bất kỳ thời điểm nào.

# Giới hạn số lượng di chuyển đồng thời tối đa là 1
maximum_migrations_per_host = 1
model.AddCumulative(
    vm_intervals, 
    [1] * len(vm_intervals), 
    maximum_migrations_per_host
)

Hoặc phức tạp hơn là giới hạn tổng thông lượng (throughput):

migration_throughput = {"vm_1": 5, "vm_2": 3, "vm_3": 2}
host_maximum_throughput = 5
# ... mã thiết lập mô hình ...
model.AddCumulative(vm_intervals, vm_throughputs, host_maximum_throughput)

So sánh với Lập trình nguyên hỗn hợp (MIP)

Để hiểu rõ sức mạnh của CP-SAT, ta cần so sánh nó với kỹ thuật phổ biến khác là MIP. Có hai cách chính để giải bài toán lập lịch bằng MIP: công thức theo chỉ số thời gian (time-indexed) và công thức liên tục thời gian (time-continuous).

Phương pháp Time-Indexed: Cách tiếp cận này tạo các biến nhị phân để chỉ thị xem một tác vụ có đang hoạt động tại một thời điểm cụ thể hay không. Mặc dù dễ hiểu, phương pháp này không mở rộng tốt (scale poorly). Khi số lượng tác vụ và khoảng thời gian lập kế hoạch tăng lên, số lượng biến và ràng buộc tăng theo cấp số nhân, khiến bài toán không thể giải quyết trong thời gian hợp lý.

So sánh thời gian giải quyết bài toán

Phương pháp Time-Continuous: Cách tiếp cận này bỏ qua chỉ số thời gian và sử dụng các biến thứ tự nhị phân giữa các cặp tác vụ. Nó hiệu quả hơn cho các bài toán có khoảng thời gian dài nhưng khó xây dựng mô hình và ít trực quan hơn CP-SAT. Đặc biệt, việc biểu diễn ràng buộc AddCumulative trong MIP cực kỳ phức tạp, đòi hỏi nhiều biến bổ sung và ràng buộc "Big-M", khiến mô hình trở nên cồng kềnh và khó hiểu.

Kết luận

Việc lựa chọn công cụ phù hợp là rất quan trọng. Các bài toán lập lịch có những ràng buộc độc đáo khiến chúng khó mô hình hóa bằng MIP. OR-Tools CP-SAT cung cấp các trừu tượng hóa mạnh mẽ, cho phép mô hình hóa các bài toán lập lịch một cách trực quan và hiệu quả.

Với các ràng buộc như AddNoOverlap và AddCumulative sử dụng biến khoảng thời gian, việc biểu diễn các giới hạn về tính đồng thời và tài nguyên trở nên dễ dàng hơn rất nhiều so với việc viết cùng một mô hình bằng MIP. Nếu bạn đang đối mặt với một bài toán lập lịch phức tạp, tôi khuyên bạn nên thử nghiệm CP-SAT.