Akamai перешла на Google OR-Tools для оптимизации миграции виртуальных машин

Команда Akamai работает над оптимизацией графиков обслуживания инфраструктуры, особенно сложных обновлений гипервизоров, где нужно безопасно перенести сотни тысяч виртуальных машин. Простая задача смены оборудования превращается в сложную проблему с ограничением по вместимости, параллельности операций и конфликтами. Главная цель — выполнить все задачи в кратчайшие сроки, не нарушая уровень обслуживания клиентов. Автор решил проверить разные инструменты, включая коммерческие решатели MIP, но в итоге остановился на библиотеке Google OR-Tools с её решателем CP-SAT. Этот инструмент подходит идеально, так как умеет работать со специальными переменными для моделирования времени. Чтобы понять разницу, автор создал простую модель для одной хостовой машины с тремя виртуальными машинами, каждая из которых должна переехать за 10 единиц времени. В коде используются интервальные переменные, которые фиксируют начало и конец миграции. С помощью ограничения AddNoOverlap можно запретить одновременные переезды на одном ресурсе, а функция AddCumulative позволяет задать лимит на количество параллельных операций или их общий трафик. Например, если трафик ограничен в пять единиц, решатель расставит задачи так, что две машины с низким потреблением поедут вместе, а одна «тяжелая» — отдельно. Если попробовать решить такую же задачу через классическую MIP-моделирование, возникнут серьезные проблемы. Простой вариант с индексацией по времени требует создания тысяч переменных для каждого момента времени, что приводит к экспоненциальному росту времени вычислений. Более сложная непрерывная модель использует бинарные переменные для упорядочивания задач, но формулирование ограничений наложения становится громоздким и трудно читаемым. В итоге CP-SAT выигрывает за счет понятных абстракций и высокой скорости работы с интервалами. Для задач планирования и расписания этот инструмент оказывается намного эффективнее и проще в реализации, чем традиционные методы.