메타가 9년간 쓰던 리소스 할당 솔버 Rebalancer, 드디어 오픈소스로 풀렸습니다

들어가며: '할당 문제'는 왜 항상 지옥인가

개발하다 보면 이런 질문을 마주하게 됩니다.

"서버 N대가 있고, 태스크 M개가 있는데, 장애 도메인은 최대한 분산시키면서 자원 낭비는 최소화하려면 어떻게 배치해야 하지?"

이걸 머리로 풀면 그냥 '감'입니다. 정식으로 풀려고 하면 NP-hard 문제가 튀어나오고, 상용 솔버에 넣으면 모델 크기가 O(|objects| × |bins|)로 폭발해요. 메타는 이 문제를 9년 동안 내부 라이브러리 하나로 해결해왔고, 최근에 이걸 Apache 2.0으로 오픈소스화했습니다. 이름은 Rebalancer입니다.

이 글에서는 Rebalancer가 어떤 문제를 어떻게 분리해서 푸는지, 그리고 왜 이게 단순한 '솔버 하나 더'가 아니라 아키텍처 설계 교본인지 정리해볼게요. 근거자료는 Meta Engineering 원문을 참고하시면 됩니다.

핵심 구조: 문제 정의와 해법을 분리한다

Rebalancer의 설계 철학은 한 줄로 요약됩니다. "문제를 어떻게 기술할지(Spec)와 어떻게 풀지(Solve)를 분리한다."

3단계 추상화 스펙 언어

예를 들어 '태스크를 서버에 배치하되, 랙마다 하나의 잡만 허용하고 CPU/스토리지 균형을 맞춘다'는 요구사항은 이렇게 표현됩니다.

# 태스크=object, 서버=bin, 랙=scope, CPU/스토리지=dimension
spec = AssignmentSpec(
    objects=tasks,
    bins=servers,
    scopes=racks,
    dimensions=["cpu", "storage"],
    partitions=[job_partition],
)

spec.add(CapacitySpec(dimension="cpu", limit=server_cpu_limit))
spec.add(CapacitySpec(dimension="storage", limit=server_storage_limit))
spec.add(GroupCountSpec(partition=job_partition, scope=racks, max_count=1))
spec.add(BalanceSpec(dimensions=["cpu", "storage"]))

이 스펙은 내부적으로 표현 그래프(Expression Graph) 라는 DAG로 변환됩니다. 리프 노드는 "서버 A의 메모리 사용률", 상위 노드는 Max/Sum/Square 같은 연산이에요. 여기서 중요한 포인트는 모든 노드 값이 현재 할당 상태에 의존한다는 겁니다. 배치가 바뀌면 그래프 전체를 다시 평가해야 하죠.

두 개의 해법: Local Search vs Optimal Solver

Rebalancer는 완전히 다른 두 가지 해법을 제공합니다. 상황에 따라 골라 쓰는 게 실무 감각입니다.

Optimal Solver (MIP 기반)

표현 그래프를 혼합 정수 계획법(MIP) 으로 변환해서 FICO Xpress, Gurobi, HiGHS 같은 상용/오픈소스 솔버에 던집니다. 문제는 이 변환 과정에서 각 bin의 사용률을 바이너리 결정 변수의 가중합으로 표현해야 한다는 점이에요. 최악의 경우 모델 크기가 O(|objects| × |bins|)로 폭발합니다.

Rebalancer는 이를 완화하기 위해 다음 기법을 자동 적용합니다.

• Variable aggregation: 유사 객체를 하나의 정수 변수로 압축
• Interchangeability: 교환 가능한 객체 그룹화
• Symmetry breaking: 대칭 해 제거

그래도 1M 객체 × 5k 빈 규모는 MIP로 못 풉니다.

Local Search Solver

표현 그래프 위에서 직접 동작합니다. 현재 할당 주변의 이웃(neighborhood)을 탐색하면서 객체를 다른 bin으로 옮겨보는 방식이에요. 이웃 크기가 O(|objects| + |bins|)라서 메모리 폭발 없이 초대규모 문제를 다룰 수 있습니다.

# 개념적 의사 코드: Local Search 루프
while not stopping_condition_met():
    candidates = generate_moves(current_assignment)  # 이웃 생성
    best = None
    for move in candidates:  # 병렬 평가, 초당 수백만 건 가능
        new_assignment = apply(move)
        if violates_constraint(new_assignment):
            continue
        if best is None or objective(new_assignment) < objective(best):
            best = new_assignment
    if best is None:
        break  # 더 이상 개선 불가
    current_assignment = best

메타 내부에서는 대규모 문제는 거의 전부 Local Search로 풀고, 중소 규모면서 시간 여유가 있을 때만 Optimal Solver를 씁니다. 흔한 패턴은 Optimal로 프로토타이핑 → Local Search로 프로덕션 이관이에요.

실전 수치 (메타 공개 기준)

• 하루 약 4,000만 건의 할당 문제를 30개 이상의 서로 다른 문제 정의로 해결
• 265k objects / 3.2k bins 문제에서 P99 해결 시간 12초
• 1M+ objects / 5k bins 문제 평균 해결 시간 171초, 하루 3.4k건 이상 수행

이 기술의 한계와 주의사항

솔직히 말하면 Rebalancer가 만능은 아닙니다.

1. 문제 정의 자체의 난이도는 그대로 남습니다. 스펙 언어가 편해졌을 뿐, 현실 정책을 수식으로 번역하는 건 여전히 사람의 몫이에요. 오히려 '스펙을 잘못 짜면' 디버깅 지옥이 열립니다.
2. Local Search는 전역 최적해를 보장하지 않습니다. 초기 할당(initial assignment)에 성능이 크게 좌우됩니다. 초기값을 어떻게 주느냐가 실무 성패를 가릅니다.
3. MIP 경로는 확장성 한계가 명확합니다. 객체 수가 수십만 단위를 넘으면 사실상 Local Search로 가야 합니다.
4. 디버깅 도구(Explorer)에 대한 의존. 저자들도 명시했듯이, 모델러의 시간 대부분이 '솔버 동작 디버깅'에 소모됩니다. UI 없이 쓰면 생산성이 급락합니다.

한국 개발 생태계에서의 적용 맥락

국내 환경에서 Rebalancer를 그대로 쓸 수 있는 곳은 사실 많지 않습니다. 하이퍼스케일 데이터센터를 운영하는 곳은 손에 꼽죠. 하지만 설계 교본으로서의 가치는 국내 SI/플랫폼 조직에서 오히려 더 큽니다.

• 쿠버네티스 스케줄러 커스터마이징을 하는 팀이라면, Rebalancer의 'Spec → Expression Graph → Solver' 3단 분리는 좋은 참고 모델입니다. 스케줄링 정책을 코드에 하드코딩하는 대신 선언적으로 분리하는 감각을 배울 수 있어요.
• 배치 작업 스케줄러(예: 야간 배치를 어느 워커에 몰아줄지)를 자체 구현하는 팀이라면, Local Search 접근이 MIP보다 훨씬 현실적입니다.
• 물류/배차 최적화를 다루는 스타트업이라면, Rebalancer의 Spec API가 제공하는 추상화 수준을 그대로 벤치마킹할 만합니다.

다음 단계 학습 방향

1. 논문 먼저: OSDI'24에 실린 "Optimizing Resource Allocation in Hyperscale Datacenters" 를 읽어보세요. 스펙 언어의 형식 정의가 나옵니다.
2. PyPI 패키지 체험: pip install rebalancer 로 설치 후, 문서의 튜토리얼 문제를 로컬에서 돌려보세요.
3. Explorer 실행: Docker로 뜨는 웹 UI를 켜고, 제약 조건을 하나씩 relax 해보면서 해가 어떻게 바뀌는지 관찰하는 게 가장 빠른 학습법입니다.
4. 비교 대상: Google OR-Tools, OptaPlanner와 비교해보면 '선언적 스펙 + 이중 솔버'라는 Rebalancer만의 포지션이 명확해집니다.

마무리

Rebalancer의 진짜 가치는 '빠른 솔버'가 아니라 "문제 정의와 해법을 분리한다" 는 아키텍처 원칙을 9년간 프로덕션에서 검증했다는 점입니다. 사내 라이브러리 하나가 하루 4천만 건을 처리한다는 건, 그 설계가 이론이 아니라 실전에서 살아남았다는 뜻이에요. 국내에서도 스케줄링/배치/할당 문제를 다루는 팀이라면, 이 구조를 한 번쯤 뜯어볼 가치가 충분합니다.

함께 보면 좋은 글

• Cloudflare가 DNS 캐시 메모리 100TB를 아낀 비결, Rust 최적화 5단계
• 110,000개 논문 검색 시스템, 하이브리드 아키텍처로 구축하기 (Hugging Face 인프라 활용)