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

• 서버에 작업을 배치하거나 샤드를 분산할 때,
  용량 제한/부하 균형/장애 대비등의 조건을 고려해 배치안을 계산

• 복잡한 수학식 대신
  25개 이상의 목표와 제약 조건을 조합해 문제를 정의

• 같은 문제에 여러 알고리듬을 적용해 처리 속도와 해결책의 품질을 비교 가능
  지역 탐색은 대상을 옮기거나 교환하며 배치를 개선하고, 대규모 문제에 적합하지만 전체 최적해는 보장하지 않음

• Meta의 대규모 문제 대부분은 이 방식으로 처리함

• 최적해가 필요한 문제에는 혼합 정수 계획법을 사용할 수 있으며, 오픈소스
  HiGHS 및 상용 Gurobi, FICO Xpress 지원

• Rebalancer Explorer에서 배치 결과를 비교하고, 대상을 옮기거나 제약을 완화했을 때의 영향 확인 가능
  Meta에서 9년 이상 활용된 도구로, 서버 할당과 ML 작업 배치, 트래픽 라우팅 등 하루 약 4,000만 건의 배치 문제 처리

• Meta 운영 측정에서 대상 26만 5,000개와 배치 자원 3,200개인 문제의
  P99 풀이 시간은 12초
  회의실과 좌석 배치, 지원 티켓의 엔지니어 배정 등 인프라 밖의 문제에도 활용
  C++ 기반으로 C++와 Python API 제공, 단일 프로세스에서 여러 스레드로 계산

• Python 패키지와 Linux/macOS 설치 경로 제공, Explorer는 Docker Compose로 실행 가능

• Apache 2.0 라이선스

댓글과 토론