변화하는 세상에서의 스케 (새 탭에서 열림)
클라우드 인프라의 가용 자원이 끊임없이 변동하는 환경에서 중단 없이 실행되어야 하는 비선점형(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. 위 조건에 해당하지 않을 경우 새 작업 폐기. 이 연구 결과는 자원 공급이 불규칙한 클라우드 시스템에서 이론적 보장을 갖춘 견고한 스케줄러를 구축할 수 있는 근거를 제공하며, 특히 저순위 배치 작업의 효율성을 극대화하는 데 실질적인 도움을 줄 수 있습니다.