Rebalancer - 복잡한 제약 조건에 맞춰 작업과 자원을 배치하는 Meta의 최적화 도구

요약

Meta는 복잡한 제약 조건에 맞춰 작업과 자원을 효율적으로 배치하는 최적화 도구 'Rebalancer'를 공개했습니다.
이 도구는 서버 할당 및 ML 작업 배치 등 대규모 문제를 처리하며, 지역 탐색과 혼합 정수 계획법 등 다양한 알고리즘을 지원합니다.

서버에 작업을 배치하거나 샤드를 분산할 때, 용량 제한/부하 균형/장애 대비등의 조건을 고려해 배치안을 계산
복잡한 수학식 대신 25개 이상의 목표와 제약 조건을 조합해 문제를 정의
같은 문제에 여러 알고리듬을 적용해 처리 속도와 해결책의 품질을 비교 가능
지역 탐색은 대상을 옮기거나 교환하며 배치를 개선하고, 대규모 문제에 적합하지만 전체 최적해는 보장하지 않음
- Meta의 대규모 문제 대부분은 이 방식으로 처리함
최적해가 필요한 문제에는 혼합 정수 계획법을 사용할 수 있으며, 오픈소스 HiGHS 및 상용 Gurobi, FICO Xpress 지원
Rebalancer Explorer에서 배치 결과를 비교하고, 대상을 옮기거나 제약을 완화했을 때의 영향 확인 가능
Meta에서 9년 이상 활용된 도구로, 서버 할당과 ML 작업 배치, 트래픽 라우팅 등 하루 약 4,000만 건의 배치 문제 처리
Meta 운영 측정에서 대상 26만 5,000개와 배치 자원 3,200개인 문제의 P99 풀이 시간은 12초
- 공식 소개글 : Open-Sourcing Rebalancer: A Generic, High-Performance Library for Solving Assignment Problems
회의실과 좌석 배치, 지원 티켓의 엔지니어 배정 등 인프라 밖의 문제에도 활용
C++ 기반으로 C++와 Python API 제공, 단일 프로세스에서 여러 스레드로 계산
Python 패키지와 Linux/macOS 설치 경로 제공, Explorer는 Docker Compose로 실행 가능
Apache 2.0 라이선스