scheduling-algorithms

변화하는 세상에서의 스케 (새 탭에서 열림)

클라우드 인프라의 가용 자원이 끊임없이 변동하는 환경에서 중단 없이 실행되어야 하는 비선점형(Non-preemptive) 작업들을 효율적으로 배치하기 위한 새로운 알고리즘이 제시되었습니다. Google Research는 이번 연구를 통해 가용량이 시간에 따라 변하는 환경에서도 작업 처리량(Throughput)을 최대로 확보할 수 있는 최초의 상수 요인(Constant-factor) 근사 알고리즘을 개발했습니다. 이 알고리즘은 변동성이 큰 클라우드 환경에서 작업 손실을 최소화하고 스케줄러의 안정성을 이론적으로 보장하는 기틀을 마련했습니다. ### 동적 클라우드 환경과 스케줄링의 난제 * 현대 클라우드 환경은 하드웨어 장애, 유지보수, 고순위 작업의 자원 점유 등으로 인해 가용 자원이 실시간으로 변동하는 특성을 가집니다. * 특히 비선점형 작업은 한 번 시작하면 중간에 멈출 수 없으며, 자원 부족으로 중단될 경우 지금까지의 모든 작업 진행 내용이 소실되는 리스크가 있습니다. * 스케줄러는 각 작업의 방출 시간(Release time), 마감 기한(Deadline), 처리 시간, 가중치를 고려하여 전체 처리량의 합계(가중치 또는 작업 수)를 극대화해야 합니다. ### 오프라인 설정에서의 최적화 전략 * 미래의 작업 도착 정보와 자원 변동 추이를 미리 알고 있는 오프라인 환경에서는 단순한 그리디(Greedy) 전략이 효과적임이 입증되었습니다. * 가장 먼저 끝나는 작업을 우선 배치하는 그리디 알고리즘은 동일 가치 작업들을 스케줄링할 때 최적해의 최소 1/2 성능을 보장(1/2-approximation)합니다. * 작업마다 가치가 다른 가중치 모델의 경우, Primal-dual 프레임워크를 활용하여 최적해의 1/4 성능을 보장하는 알고리즘을 구현했습니다. ### 온라인 환경의 복잡성과 중단 모델 * 실시간으로 작업이 도착하는 온라인 환경에서는 단 하나의 잘못된 결정(긴 작업 배치)이 미래의 수많은 짧은 작업을 막을 수 있어 기존 방식의 효율성이 급격히 떨어집니다. * **재시작 허용 모델(Interruption with restarts):** 작업 중단 시 진행 데이터는 소실되지만 나중에 다시 시도할 수 있는 모델로, 오프라인과 동일하게 1/2 수준의 경쟁비(Competitive ratio)를 달성할 수 있습니다. * **재시작 불가 모델(Interruption without restarts):** 중단된 작업을 영구히 폐기해야 하는 엄격한 모델로, 일반적인 상황에서는 효율적인 스케줄링이 어렵지만 '공통 마감일'이 있는 실무적 시나리오에서는 해결책을 찾았습니다. ### 공통 마감일 시나리오를 위한 상수 경쟁 알고리즘 * 모든 작업이 동일한 마감 시한을 가지는 실제 배치 작업 환경을 위해 최초의 상수 경쟁 알고리즘(1/11 경쟁비)을 설계했습니다. * 이 알고리즘은 새로운 작업이 도착할 때마다 다음 네 가지 우선순위에 따라 잠정적 스케줄을 갱신합니다. 1. 빈 시간대에 작업 추가. 2. 기존에 예약된 미래 작업보다 현저히 작은 작업으로 교체. 3. 현재 실행 중인 작업의 남은 시간보다 도착한 작업이 더 짧을 경우 실행 중인 작업 중단 및 교체. 4. 위 조건에 해당하지 않을 경우 새 작업 폐기. 이 연구 결과는 자원 공급이 불규칙한 클라우드 시스템에서 이론적 보장을 갖춘 견고한 스케줄러를 구축할 수 있는 근거를 제공하며, 특히 저순위 배치 작업의 효율성을 극대화하는 데 실질적인 도움을 줄 수 있습니다.

가상 머신 퍼즐 해결: (새 탭에서 열림)

구글 리서치와 딥마인드가 개발한 LAVA는 클라우드 데이터 센터의 자원 효율성을 극대화하기 위해 가상 머신(VM)의 수명을 실시간으로 예측하고 적응하는 새로운 스케줄링 알고리즘입니다. 기존의 단발성 예측 방식에서 벗어나 VM이 실행되는 동안 지속적으로 남은 수명을 재예측하는 방식을 채택하여 자원 파편화와 낭비를 획기적으로 줄였습니다. 이 시스템은 실제 구글의 대규모 클러스터 관리 시스템인 Borg에 적용되어 빈 호스트 확보 및 자원 활용도 측면에서 유의미한 성능 향상을 입증했습니다. ## 수명 예측의 불확실성과 연속 재예측 기술 * 클라우드 VM의 수명은 매우 불확실하며, 대다수의 단기 VM(88%)이 아주 적은 자원(2%)만 사용하는 반면 극소수의 장기 VM이 대부분의 자원을 점유하는 롱테일(Long-tail) 분포를 보입니다. * LAVA는 생존 분석(Survival Analysis)에서 영감을 얻은 머신러닝 모델을 사용하여 VM 수명을 단일 값이 아닌 확률 분포로 예측함으로써 내재된 불확실성을 관리합니다. * "연속 재예측(Continuous Reprediction)" 기능을 통해 VM이 실행되는 동안 축적된 정보를 바탕으로 남은 수명을 실시간으로 업데이트하며, 이를 통해 초기 예측 오류를 스스로 수정하고 정확도를 높입니다. ## NILAS: 기존 시스템에 통합되는 비침습적 스케줄링 * NILAS(Non-Invasive Lifetime Aware Scheduling)는 기존 구글의 Borg 스케줄러 점수 함수에 수명 예측 데이터를 통합한 알고리즘입니다. * 새로운 VM을 배치할 때 해당 호스트에 이미 있는 VM들의 예상 종료 시간을 고려하여, 비슷한 시기에 종료될 VM들을 한곳에 모읍니다. * 이 방식은 특정 시점에 호스트 내의 모든 VM이 동시에 종료되도록 유도하여, 대규모 작업이나 유지보수에 필수적인 '빈 호스트'를 더 많이 확보하는 데 기여합니다. ## LAVA와 LARS를 통한 자원 배치 및 재배치 최적화 * **LAVA (Lifetime-Aware VM Allocation):** 장기 VM이 점유 중인 호스트의 남은 유휴 공간에 아주 짧은 수명의 VM들을 배치하는 전략입니다. 이는 자원 파편화(Resource Stranding)를 방지하며, 단기 VM이 빠르게 종료되므로 호스트의 전체 수명에 영향을 주지 않고 효율을 높입니다. * **LARS (Lifetime-Aware Rescheduling):** 데이터 센터 유지보수나 파편화 제거가 필요할 때, 예측된 수명이 긴 VM부터 우선적으로 다른 호스트로 이주시킵니다. 수명이 짧은 VM은 이주시키지 않고 자연스럽게 종료되도록 기다림으로써 불필요한 시스템 중단과 이동 비용을 최소화합니다. LAVA의 도입은 예측 불가능한 사용자 워크로드를 다루는 클라우드 인프라에서 단순한 정적 규칙보다 실시간 데이터 기반의 적응형 알고리즘이 훨씬 효과적임을 시사합니다. 이러한 접근법은 대규모 데이터 센터 운영에서 경제적 효율성을 높일 뿐만 아니라, 서버 가동률 최적화를 통해 에너지 소비를 줄이는 환경적 지속 가능성 측면에서도 중요한 솔루션이 될 수 있습니다.

무작위 작업 도착 (새 탭에서 열림)

구글 리서치(Google Research)의 Ravi Kumar와 Manish Purohit는 대규모 클러스터 관리 시스템에서 필수적인 부하 분산(Load balancing) 문제를 최신 온라인 알고리즘 이론으로 분석했습니다. 연구팀은 작업이 무작위 순서로 도착하는 환경을 가정하고, 결정적(deterministic) 온라인 알고리즘이 가질 수 있는 성능의 이론적 한계를 새롭게 정립했습니다. 이 연구는 기존의 최악 조건 분석을 넘어 현실적인 무작위 작업 흐름에서 알고리즘이 달성할 수 있는 최선의 성능이 $\sqrt{\log n}$ 수준임을 입증하며 이론적 간극을 메웠습니다. ### 트리 균형 게임을 통한 부하 분산 모델링 * **모델의 정의**: 부하 분산 문제를 기하학적인 '트리 균형 게임'으로 치환하여 설명합니다. 트리 내의 노드는 서버(머신)를, 노드를 연결하는 간선(edge)은 처리해야 할 작업(job)을 의미합니다. * **목표와 규칙**: 간선이 하나씩 제시될 때마다 알고리즘은 이를 두 끝점 중 하나로 방향을 정해야(orient) 합니다. 최종 목표는 특정 노드로 향하는 간선의 수(내차수, indegree)의 최댓값을 최소화하는 것입니다. * **경쟁 분석(Competitive Analysis)**: 미래의 모든 정보를 알고 있는 오프라인 최적 알고리즘의 결과와 온라인 알고리즘의 결과를 비교하여 알고리즘의 효율성을 측정합니다. ### 결정적 알고리즘의 전통적 한계 * **최악의 시나리오**: 1990년대부터 알려진 바에 따르면, 적대적인 공격자(adversary)가 작업 순서를 정할 경우 어떤 결정적 알고리즘도 최대 부하를 $\log n$($n$은 노드 수) 미만으로 유지할 수 없습니다. * **정보의 비대칭성**: 공격자는 알고리즘이 어떤 선택을 해도 부하가 높아질 수밖에 없는 순서로 간선을 배치하며, 이는 시스템 성능의 하한선을 결정하는 근거가 됩니다. * **그리디 알고리즘의 한계**: 단순히 부하가 적은 쪽으로 작업을 배정하는 탐욕적(Greedy) 방식은 작업 도착 순서에 따라 성능이 크게 좌우되는 취약점을 가집니다. ### 무작위 도착 순서에서의 새로운 이론적 하한선 * **무작위 순서 모델**: 모든 작업의 순열이 동일한 확률로 발생하는 환경을 가정합니다. 이는 실제 데이터 센터의 워크로드와 더 유사한 모델입니다. * **성능 격차의 발견**: 이전 연구에서는 무작위 순서일 때 그리디 알고리즘이 $\log n$보다 약간 나은 성능을 보인다는 점을 밝혔으나, 다른 정교한 알고리즘이 얼마나 더 잘할 수 있는지는 미지로 남아있었습니다. * **재귀적 구조를 통한 증명**: 본 연구는 재귀적으로 구성된 새로운 사례를 통해, 무작위 순서에서도 결정적 알고리즘이 $\sqrt{\log n}$보다 나은 경쟁비를 보장할 수 없음을 증명했습니다. 이는 기존 예측보다 하한선을 지수적으로 높인 결과입니다. 이 연구는 구글의 보그(Borg)와 같은 대규모 클러스터 관리 시스템에서 자원 할당 효율성을 높이기 위한 이론적 토대를 제공합니다. 작업이 무작위로 유입되는 실제 환경에서도 알고리즘이 극복할 수 없는 수학적 한계가 존재함을 이해함으로써, 더욱 견고하고 현실적인 스케줄링 전략을 설계하는 지침으로 활용될 수 있습니다.