메타, 대규모 자원 할당 최적화 라이브러리 '리밸런서' 오픈소스 공개

오픈소스 공개와 도입 배경

메타가 지난 9년 이상 사내 자원 할당 문제를 해결하는 데 사용해 온 라이브러리 리밸런서(Rebalancer)를 아파치 2.0 라이선스로 오픈소스 공개했다. 이 라이브러리는 자원 할당 문제의 정의와 메모리 저장, 최적화 연산, 디버깅 영역을 분리하여 대규모 환경에서의 확장성과 사용 편의성을 확보했다. 메타는 운영체제 설계 및 구현 심포지엄인 OSDI 2024에서 관련 논문을 발표한 바 있으며, 이번 공개와 함께 파이썬 패키지와 도커 기반 시각화 탐색 도구도 함께 배포했다.

대규모 데이터센터에서는 랙 배치, 서버와 서비스 연결, 작업 스케줄링, 전 세계 사용자 트래픽 라우팅 등 객체를 적절한 위치에 배분하는 문제가 인프라 전반에서 지속적으로 발생한다. 그러나 현업 엔지니어가 실제 운영 정책을 복잡한 수학 공식으로 변환하기 어렵고, 문제 규모가 커지면 상용 최적화 도구로 해결하기 힘든 NP-하드(NP-hard) 문제에 직면하는 한계가 존재했다. 메타는 이러한 모델링의 어려움과 연산 병목을 극복하고 다양한 제약 조건을 유연하게 다루기 위해 문제 명세와 풀이 알고리즘을 분리하는 프레임워크를 구축했다.

추상화 모델링과 연산 구조

리밸런서는 3단계 추상화 체계를 적용하여 엔지니어가 복잡한 수식 없이도 직관적으로 할당 제약과 목표를 정의하도록 지원한다. 우선 객체와 수용 공간의 물리적 속성을 나타내는 차원(Dimension), 객체 그룹인 분할(Partition), 공간 묶음인 범위(Scope), 자원 사용량(Utilization) 같은 기본 요소를 선언한다. 이어 사용량의 합산이나 최댓값, 제곱 등의 변환 연산을 표현식으로 구성하고, 이를 토대로 용량 한도를 지정하는 용량 규격(CapacitySpec), 그룹 분할을 제한하는 그룹 수 규격(GroupCountSpec), 자원 간 균형을 맞추는 균형 규격(BalanceSpec) 등을 조합해 복잡한 비즈니스 로직을 구축한다.

사용자가 작성한 명세는 방향성 비순환 그래프(DAG) 형태의 표현 그래프(Expression Graph)로 자동 변환되어 내부에서 관리된다. 이 그래프의 최하단 잎 노드는 서버 메모리 사용량과 같은 기초 계산식을 담으며, 상위 노드는 합산이나 절댓값 같은 연산을 재귀적으로 연결하여 전체 자원 상태를 반영한다. 모델링 담당자가 초기 할당 상태와 제한 시간 등의 종료 조건을 설정하면, 리밸런서는 기존 할당에서 발생한 제약 위반을 최우선으로 해소하면서 목표 함수를 최소화하는 방향으로 최적 배치를 산출한다.

두 가지 솔버와 탐색기 지원

리밸런서는 문제 규모와 연산 목표에 맞추어 최적해 솔버(Optimal Solver)와 지역 탐색 솔버(Local Search Solver)라는 두 가지 상이한 연산 기법을 제공한다. 최적해 솔버는 표현 그래프를 혼합 정수 프로그래밍(MIP) 수식으로 변환하여 하이고(HiGHS), 구로비(Gurobi), 피코 익스프레스(FICO Xpress) 엔진으로 엄밀한 해를 도출하며 변수 병합과 대칭성 제거 기법으로 모델 크기를 축소한다. 반면 메타 사내 대규모 시스템에서 주로 사용하는 지역 탐색 솔버는 그래프 상에서 객체 배치를 국소적으로 변경하며 탐색 공간 크기를 선형 수준으로 억제하고, 병렬화 최적화와 탐색 공간 가지치기를 통해 초당 수백만 회의 후보 평가를 수행한다.

현재 메타에서는 매일 30개 이상의 문제 유형에 걸쳐 약 4000만 건의 할당 문제가 리밸런서로 연산되고 있다. 객체 26만 5000개와 수용 공간 3200개 수준의 작업에서는 99백분위수 처리 시간이 12초를 기록했으며, 100만 개 이상의 객체와 5000개 공간을 다루는 초대형 작업 3400여 건에서도 평균 연산 시간 171초를 유지했다. 아울러 최적화 도중 발생하는 내부 동작을 분석할 수 있도록 도커 웹 환경으로 구동되는 리밸런서 탐색기(Rebalancer Explorer)를 제공하여, 제약 조건 완화 영향과 특정 배치가 선택된 사유를 직관적으로 추적할 수 있도록 지원한다.

개발자 영향과 적용 한계

이번 오픈소스 공개를 통해 개발자는 인프라 스케줄러뿐만 아니라 물류, 헬스케어, 전력망 등 다양한 산업 영역의 복잡한 최적화 과제에 검증된 프레임워크를 도입할 수 있게 되었다. 실무에서는 초기 프로토타입 단계에 최적해 솔버를 적용해 기준 품질을 측정한 뒤 대규모 서비스 전환 시 지역 탐색 솔버로 마이그레이션하거나 오프라인에서 탐색 알고리즘을 튜닝하는 실용적인 파이프라인 구성이 가능하다. 메타 내부에서도 샤드 매니저(Shard Manager)의 서버 샤드 할당, 타이지(Taiji)의 글로벌 트래픽 분산, 서버리스 함수 배치, 지역 간 머신러닝 학습 부하 균등화 등 광범위한 핵심 시스템에 이를 적용하고 있다.

다만 최적해 솔버 방식은 최악의 경우 객체 수와 수용 공간 수의 곱에 비례하는 2차 복잡도로 모델 크기가 팽창하므로 초대형 문제에서는 메모리 한계로 인해 적용할 수 없다. 또한 대규모 문제에 적용되는 지역 탐색 솔버는 연산 속도가 빠르지만 수학적 절대 최적해를 보장하지 않으므로 문제 설정과 종료 조건에 따라 탐색 품질이 달라질 수 있다. 따라서 엔지니어는 자신의 도메인 특성에 맞추어 적절한 제약 규격을 구성해야 하며, 리밸런서 탐색기를 병행하여 모델의 제약 완화 여부와 세부 배치 동작을 지속적으로 검증하고 조정해야 한다.