Google OR-Tools CP‑SAT를 활용한 복잡한 스케줄링 문제 해결

클라우드 인프라의 유지보수 스케줄링은 높은 위험을 동반하는 균형 잡기 작업이다. 수십만 대의 게스트 VM을 서비스하는 하이퍼바이저 호스트를 관리할 때, 단순 재부팅은 서버 재시작에 그치지 않고 거대한 오케스트레이션 과제가 된다. 고객 중단을 최소화하기 위해 엔지니어는 "3C"를 고려해야 한다: 용량 (마이그레이션된 VM을 위한 가용 공간), 동시성 (네트워크 및 I/O 제한), 그리고 충돌 (단일 고객의 VM이 동시에 이동할 수 있는 수에 대한 SLA 제한).

이러한 조합 최적화 문제에서는 솔버 선택이 몇 초 안에 해결되는 모델과 지수적 복잡성으로 인해 충돌하는 모델 사이의 차이를 만들 수 있다. 혼합 정수 계획법(MIP)이 전통적인 선택지이지만, Google의 OR-Tools CP‑SAT 솔버는 스케줄링에 특화된 보다 직관적이고 성능이 뛰어난 프레임워크를 제공한다.

스케줄링 도전 과제: RCPSP

클라우드에서의 유지보수 스케줄링은 본질적으로 **자원제한 프로젝트 스케줄링 문제 (RCPSP)**의 변형이다. 표준 RCPSP에서는 특정 기간과 자원 요구량을 가진 작업들이 있으며, 목표는 자원 제한을 초과하지 않으면서 전체 프로젝트 기간(완료 시간)을 최소화하는 것이다.

클라우드 유지보수 상황에서 각 VM 마이그레이션은 하나의 작업이다. 자원은 사용 가능한 네트워크 대역폭과 호스트 CPU이다. 목표는 3C를 준수하면서 전체 플릿에 필요한 모든 유지보수를 가능한 가장 짧은 시간에 완료하는 것이다.

CP‑SAT를 활용한 모델링

CP‑SAT는 시간 개념에 직접 매핑되는 특수 변수와 제약조건을 도입하기 때문에 특히 강력하다. 시간을 일련의 이진 플래그로 다루는 대신, CP‑SAT는 구간 변수를 사용한다.

구간 변수

구간 변수는 시작 시간, 종료 시간, 그리고 지속 시간을 포함한다. 이를 통해 솔버는 작업을 개별적인 점들의 집합이 아니라 연속적인 시간 블록으로 취급할 수 있다.

# Example: Creating an interval variable for a VM migration
start_var = model.new_int_var(0, planning_horizon, f"{vm}_start")
end_var = model.new_int_var(0, planning_horizon, f"{vm}_end")

vm_interval_var = model.new_interval_var(
    start=start_var, size=migration_duration, end=end_var, name=f"{vm}_interval"
)

동시성 관리

구간이 정의되면, 두 가지 주요 제약조건을 사용하여 자원 제한을 적용하는 것이 간단해진다:

  1. AddNoOverlap: 리스트 내의 두 작업이 겹치지 않도록 보장한다. 이는 단일 스레드 자원(예: 호스트당 한 번에 하나의 마이그레이션)에 이상적이다.
  2. AddCumulative: 특정 용량을 가진 자원을 모델링한다. 예를 들어, 호스트의 총 네트워크 처리량이 5 단위이고, 서로 다른 VM이 그 처리량을 서로 다른 양으로 요구한다면, AddCumulative는 모든 활성 마이그레이션의 합이 5를 초과하지 않도록 보장한다.
# Limiting total throughput across concurrent migrations
model.AddCumulative(vm_intervals, vm_throughputs, host_maximum_throughput)

CP‑SAT vs. 혼합 정수 계획법 (MIP)

많은 개발자들이 처음에 MIP 솔버를 사용해 스케줄링 문제에 접근한다. 그러나 MIP는 일반적으로 두 가지 형태 중 하나를 필요로 하는데, 두 형태 모두 상당한 단점을 가지고 있다:

1. 시간 인덱스 방식

이 방식은 가능한 모든 시간 단계마다 이진 변수를 생성한다(예: active[task, time]). 직관적이지만 확장성이 떨어진다. 계획 기간이나 작업 수가 증가함에 따라 변수 수가 지수적으로 늘어나며, 실제 환경의 기간(예: 분 단위로 측정된 24시간 창)에서는 문제를 해결할 수 없게 되는 경우가 많다.

2. 연속 시간 방식

시간 인덱스 폭발을 피하기 위해 작업 A가 작업 B보다 먼저 끝나는지를 지정하는 이진 “순서” 변수를 사용할 수 있다. 큰 기간에 대해 더 효율적이지만 수학적으로 복잡하다. MIP에서 누적 자원 제약(예: 처리량)을 구현하려면 복잡한 “Big‑M” 제약과 모든 작업 쌍에 대한 추가 이진 변수가 필요해 모델을 작성·디버그·유지보수하기 어렵다.

실용적인 고려사항 및 트레이드오프

CP‑SAT는 표현력이 뛰어나지만 만능 해결책은 아니다. 커뮤니티 인사이트는 이 솔버들을 구현하는 사람들을 위한 몇 가지 핵심 고려사항을 강조한다:

확장성 한계

수백만 개의 샤드를 수만 개의 작업에 할당하는 등 극도로 대규모 문제의 경우에도 CP‑SAT는 너무 느려질 수 있다. 이런 경우 엔지니어는 최적은 아니지만 신속한 할당을 제공하는 “수제” 휴리스틱으로 전환해야 할 수도 있다.

메타휴리스틱 대안

특정 문제, 예를 들어 차량 라우팅 문제(VRP)와 같은 경우 메타휴리스틱 솔버(예: 시뮬레이션 어닐링 또는 타부 탐색)가 CP‑SAT보다 성능이 좋을 수 있다. 이러한 솔버는 문제의 공식적인 수학 모델을 필요로 하지 않으며, 두 솔루션을 비교할 비용 함수만 있으면 된다. Timefold와 같은 도구는 최적 해보다 빠르게 “충분히 좋은” 해가 필요할 때 대안으로 자주 언급된다.

“AI” 오해

흥미롭게도 이러한 솔버들을 “AI”라고 부르는 추세가 늘어나고 있다. OR‑Tools가 Google AI 산하에 있지만, CP‑SAT는 제약 프로그래밍과 SAT 해결에 기반을 두고 있으며, 이는 1960년대에 시작된 기술이다. LLM과 달리 이 솔버들은 결정론적 보장과 하드 제약에 기반한 최적 해를 제공하므로, “환상”이 허용되지 않는 인프라에 필수적이다.

요약

대부분의 스케줄링 문제에서 CP‑SAT의 구간 변수와 누적 제약이 제공하는 추상화는 MIP보다 우수한 선택이 된다. 이는 개발자의 인지 부하를 줄이고 일반적으로 시간 기반 제약에 대해 더 나은 성능을 제공한다. 더 깊이 탐구하고자 하는 사람들에게는 Dr. Dominik Krupke의 CP‑SAT Primer가 솔버의 미묘한 차이를 마스터하기 위한 강력히 추천되는 자료이다.

Sources