왜 이 솔버가 실무에서 중요할까?
데이터센터 운영에서 "어떤 객체를 어떤 빈에 넣을 것인가"라는 질문은 생각보다 훨씬 자주 등장합니다. 랙을 데이터센터에 배치하거나, 서버를 서비스에 할당하거나, 태스크를 서버에 분배하거나, 트래픽을 지역별 데이터센터로 라우팅하는 모든 순간이 사실상 **할당 문제(Assignment Problem)**입니다.
문제는 이게 NP-hard라는 점이에요. 상용 솔버로도 하이퍼스케일 규모는 감당이 안 됩니다. 메타는 이 문제를 9년 넘게 내부 도구로 풀어왔고, 최근 Rebalancer를 오픈소스로 공개했습니다. 근거자료는 메타 엔지니어링 블로그에서 확인할 수 있어요.
핵심 철학은 단순합니다. 문제 정의(Specification)와 해결(Solving)을 분리한다. 이 분리가 사용성, 확장성, 유지보수성을 모두 잡는 열쇠입니다.
핵심 구조: Expression Graph와 Spec API
Rebalancer는 문제를 세 단계로 추상화합니다.
- 모델링 구성 요소: dimensions(객체/빈의 속성), partitions(객체 그룹), scopes(빈 그룹), utilization(빈에 할당된 객체의 기여도)
- Expression API: SUM, MAX, SQUARE 같은 연산으로 구성 요소를 재귀적으로 조합
- Spec API: 수십 가지 목표/제약을 미리 정의된 레시피로 제공
예를 들어 태스크를 서버에 배치하는 문제를 이렇게 표현할 수 있습니다.
from rebalancer import (
Problem, Dimension, Partition, Scope,
CapacitySpec, GroupCountSpec, BalanceSpec
)
# 서버(빈)와 태스크(객체) 정의
problem = Problem()
server = problem.add_bin_set("server")
task = problem.add_object_set("task")
# CPU/스토리지를 dimension으로 모델링
cpu = Dimension("cpu", objects=task, bins=server)
storage = Dimension("storage", objects=task, bins=server)
# 랙 단위 scope, job 단위 partition
rack = Scope("rack", bins=server)
job = Partition("job", objects=task)
# 제약: 서버 용량 한도
problem.add_spec(CapacitySpec(dimensions=[cpu, storage]))
# 제약: 랙당 하나의 job만 허용
problem.add_spec(GroupCountSpec(partition=job, scope=rack, max_count=1))
# 목표: CPU/스토리지 사용률 균형
problem.add_spec(BalanceSpec(dimensions=[cpu, storage]))
# 초기 할당과 종료 조건 설정 후 솔빙
solution = problem.solve(initial=current_assignment, time_limit_sec=30)
print(solution.objective_value)
이렇게 정의된 문제는 내부적으로 expression graph로 변환됩니다. 리프 노드가 utilization이고, 그 위에 Max/Sum/Square/Abs 같은 집계·변환 노드가 얹히는 구조예요. 할당이 바뀔 때마다 각 노드 값을 갱신해야 한다는 점이 성능상 핵심 포인트입니다.
두 가지 솔버, 언제 뭘 쓸까?
Rebalancer는 상황에 따라 두 가지 해법을 제공합니다.
| 구분 | Optimal Solver (MIP) | Local Search Solver |
|---|---|---|
| 방식 | Expression graph를 MIP로 변환 후 FICO Xpress/Gurobi/HiGHS로 풀이 | Expression graph 위에서 직접 이웃 탐색 |
| 최악 모델 크기 | O(|objects| × |bins|) (이차) | O(|objects| + |bins|) (선형) |
| 적합한 규모 | 중소규모, 짧은 풀이 시간 | 대규모, 하이퍼스케일 |
| 메타 실사용 | 프로토타이핑, 로컬 서치 튜닝 | 대부분의 대규모 프로덕션 문제 |
주의할 점은 MIP 변환 시 utilization을 이진 결정변수의 가중합으로 표현해야 해서 모델이 순식간에 커진다는 것입니다. Rebalancer는 variable aggregation, interchangeability, symmetry breaking으로 모델을 줄이지만, 최악의 경우 여전히 이차 복잡도입니다.
반면 로컬 서치는 현재 할당 주변 이웃만 탐색하기 때문에 메모리 한계를 회피할 수 있고, 초당 수백만 건의 평가가 가능할 정도로 최적화되어 있습니다. 실무 팁은 이렇습니다.
- 프로토타이핑: Optimal Solver로 빠르게 baseline 확보
- 프로덕션 대규모: Local Search로 전환
- 오프라인 튜닝: Optimal Solver로 Local Search 파라미터 조정
메타 실사용 데이터도 참고할 만합니다. 하루 약 4천만 건의 할당 문제를 30가지 이상의 문제 정형으로 풀고 있고, P99 풀이 시간은 26만 5천 객체/3,200 빈 기준 12초입니다. 100만 객체/5천 빈 규모는 평균 171초가 걸립니다.
실무 적용과 주의사항
한국 개발 생태계에서의 적용 맥락: 국내 SI/클라우드 환경에서는 쿠버네티스 스케줄러나 배치 작업 할당, 물류 최적화 등에 바로 응용할 수 있습니다. 다만 Rebalancer는 Python 패키지로 제공되므로, 기존 Java/Go 기반 인프라에 붙이려면 별도 마이크로서비스로 분리하는 편이 현실적입니다.
이 기술의 한계:
- MIP 솔버는 상용 라이선스(FICO Xpress, Gurobi) 없이는 HiGHS로 성능 제약이 있을 수 있습니다.
- 로컬 서치는 전역 최적해를 보장하지 않습니다. 초기 할당 품질이 결과에 큰 영향을 미칩니다.
- 디버깅 UI인 Rebalancer Explorer가 Docker 이미지로 제공되지만, 대규모 문제에서는 시각화 자체가 무거울 수 있습니다.
다음 단계 학습 방향:
- Rebalancer 공식 문서의 튜토리얼로 소규모 문제부터 재현
- OSDI'24 논문으로 이론적 배경 보강
- 쿠버네티스 스케줄러 플러그인과 비교하며 실무 적용 시나리오 설계
할당 문제는 물류, 헬스케어, 에너지 등 거의 모든 산업에 존재합니다. 메타가 인프라 문제로 만든 도구지만, 범용 라이브러리로 설계된 만큼 여러분의 도메인에도 충분히 적용해볼 만합니다.
함께 보면 좋은 글