메타 인프라의 핵심 자원 배정 엔진, 오픈소스로 전환
메타 플랫폼스가 자사 하이퍼스케일 데이터센터 전반에서 9년 넘게 활용해 온 배정 문제(Assignment Problem) 해결 라이브러리 '리밸런서(Rebalancer)'를 오픈소스로 공개했다. 리밸런서는 아파치(Apache) 2.0 라이선스로 깃허브(GitHub)에 공개되었으며, 독립 실행이 가능한 파이썬(Python) 패키지 형태로도 배포를 시작했다.
자원 배정 문제는 주어진 객체(Objects)를 특정 제약 조건(Constraints)과 목적 함수(Objectives)에 맞춰 컨테이너 또는 슬롯(Bins)에 효율적으로 분배하는 최적화 영역이다. 메타 엔지니어링 발표에 따르면, 리밸런서는 데이터센터 내 랙 배치, 서버에 대한 서비스 할당, 개별 서버 대상 태스크 스케줄링, 수십억 사용자의 글로벌 트래픽 분산 라우팅 등 인프라 전 계층에서 매일 약 4,000만 건의 배정 연산을 처리해 왔다.
모델링과 풀이 엔진을 분리한 3계층 아키텍처
기존 최적화 기법의 난제는 실무 운영 규칙을 수학 공식으로 치환하기 어렵다는 사용성 문제와, 문제가 대규모화될수록 풀이 시간이 기하급수적으로 폭증하는 계산 복잡도 문제였다. 메타는 이러한 한계를 극복하기 위해 문제 명세, 메모리 표현, 풀이 알고리즘을 완전히 분리하는 관심사 분리(Separation of Concerns) 방식을 도입했다.
리밸런서의 문제 정의 언어는 차원(Dimensions, 자원 속성), 파티션(Partitions, 객체 그룹), 스코프(Scopes, 슬롯 그룹) 같은 기본 개념을 바탕으로 집계 및 변환을 수행하는 '표현식(Expression) API'를 거쳐, '사양(Spec) API'로 고도화된다. CapacitySpec, BalanceSpec, GroupCountSpec과 같은 사전 정의 템플릿을 통해 복잡한 수식 구성 없이도 실무 제약 조건을 선언할 수 있도록 구성되었다.
수식 그래프와 이원화된 솔버 체계
리밸런서의 아키텍처 핵심은 선언된 문제를 방향성 비순환 그래프(DAG) 형태의 수식 그래프(Expression Graph)로 컴파일한다는 점이다. 리프 노드에서 자원 사용량을 계산하고, 상위 노드로 가면서 합계(Sum), 최댓값(Max), 제곱(Square) 등의 연산으로 결합된다. 배정 상태가 바뀔 때마다 그래프 전역을 재계산하지 않고 영향받는 노드만 갱신하므로 메모리와 연산 오버헤드를 대폭 줄인다.
풀이 방식은 문제 규모에 따라 혼합 정수 계획법(MIP) 엔진과 지역 탐색(Local Search) 엔진으로 이원화된다. MIP 엔진은 오픈소스 솔버인 HiGHS나 상용 솔버인 Gurobi, FICO Xpress를 호출하여 정밀한 최적해를 도출한다. 반면 초당 수천 건 이상이거나 수십만 단위의 객체를 다루는 대규모 문제에서는 수식 그래프 상에서 직접 상태 전이를 평가하는 지역 탐색 휴리스틱을 가동해 수초 내에 준최적해를 확보하도록 설계되었다.
성능 성과와 수학적 트레이드오프
메타가 OSDI '24 논문에서 제시한 실증 데이터에 따르면, 리밸런서는 26만 5천 개 객체와 3,200개 슬롯을 다루는 환경에서 99백분위수(P99) 지연 시간 12초를 기록했다. 100만 개 이상의 객체와 5,000개 슬롯으로 확장된 초거대 배치 문제에서도 평균 171초 수준의 처리 시간을 보였다. 이는 일반 상용 MIP 솔버로는 단시간 내 탐색 자체가 불가능한 규모다.
그러나 지역 탐색 엔진의 고속 성능 뒤에는 최적성 포기라는 명확한 한계가 존재한다. 이 휴리스틱 방식은 실무적으로 용인 가능한 국소 해(Local Optima)를 찾을 뿐, 수학적 전역 최적해(Global Optimum)를 증명하지 못한다. 반대로 전역 최적해를 도출하는 MIP 엔진은 객체와 슬롯 수가 증가하면 탐색 공간이 급격히 팽창하는 NP-hard 특성상 초대형 인프라 문제에는 적용이 제한적이다. 시스템 설계자는 속도와 정밀도 사이의 우선순위를 명확히 규정해야 한다.
실무 도입 요건 및 공개 초기 단계의 고려사항
외부 엔지니어링 팀이 리밸런서를 즉각 도입하기 전에 점검해야 할 기술적 제약도 분명하다. 리밸런서는 파이썬 3.12 이상 환경과 Linux x86-64, macOS ARM64 휠(Wheel)을 제공하지만, 현재 PyPI 분류상 '알파(Alpha)' 개발 단계(v1.0.4)로 지정되어 있어 향후 외부 공개 인터페이스의 변경 가능성을 염두에 두어야 한다.
또한 C++ 코어 자체를 커스텀 빌드할 경우 메타의 내부 의존 라이브러리(Folly 등)와 결합되어 있어 빌드 파이프라인 구성이 까다롭다. 아울러 기본 오픈소스 풀이 엔진인 HiGHS 대신 Gurobi나 Xpress 수준의 풀이 성능을 얻으려면 별도의 상용 라이선스를 확보해야 한다. 내부 검증 데이터 역시 메타 특유의 분산 아키텍처에 최적화된 결과인 만큼, 온프레미스나 타 퍼블릭 클라우드 인프라에 배포할 때는 자체 벤치마크 평가를 선행할 필요가 있다.
출처
Meta Engineering의 원출처와 본문에 표시한 참고자료를 바탕으로 한국어로 재구성했습니다. ‘ARCH.B 분석’은 자료를 읽고 덧붙인 편집 해석입니다.
Open-Sourcing Rebalancer: A Generic, High-Performance Library for Solving Assignment Problems (새 창)
