논문 요약— Omega: flexible, scalable schedulers for large compute clusters
Schwarzkopf, Malte, Andy Konwinski, Michael Abd-El-Malek, and John Wilkes. “Omega: flexible, scalable schedulers for large compute clusters.” In Proceedings of the 8th ACM European Conference on Computer Systems, pp. 351–364. 2013.
여러 대의 서버로 하나의 클러스터를 구축하고 그 위에서 분산 시스템을 운영하게 되면 애플리케이션을 수동으로 일일이 띄우는 것이 아니라 어떤 서버에 배포, 실행할 지를 자동화해주는 오케스트레이션 시스템이 필요해진다. 자연히 오케스트레이션 시스템이 어떤 태스크, 애플리케이션을 어떤 서버에서 실행할 지를 결정하는 방식, 즉 스케줄링 알고리즘이 서버 비용에 큰 영향을 준다.
이 논문에서는 omega에서 여러 대의 스케줄러를 다루기 위해 선택한 아키텍쳐 디자인을 설명하고, 이에 따른 시뮬레이션을 통한 기존 구현과의 성능 비교를 다루고 있다. omega는 현재 오케스트레이션 솔루션 중 대세인 쿠버네티스의 전신이라고 할 수 있다. 이 논문에서도 나중에 쿠버네티스에 영향을 준 몇 가지 키워드를 엿볼 수 있다. 예를 들어 쿠버네티스에서 클러스터의 상태를 raft 알고리즘으로 동기화하는 것과 유사하게 논문의 핵심 아이디어 또한 여러 개의 스케줄러가 클러스터의 자원 상태 정보를 동기화하여 공유함으로서 lock이 필요한 연산을 되도록 피하는 것이다. (동기화 알고리즘은 논문에서는 직접적으로 제시하고 있지는 않으나 다른 출처에 의하면 paxos 알고리즘을 사용한다고 한다.[¹])
개인적인 감상으로는 사실 짧은 경험을 돌이켜봐도 스케줄러가 배포 등의 일상적인 작업에 병목이 될 수 있다는 것이 다소 낯설었다. kubernetes에서 복수의 스케줄러를 띄울 수 있다는 것도 새로 알게 된 사실이다.
그럼 논문의 내용을 알아보도록 하자.
앞서 설명했듯이 스케줄러는 외부로부터 주어진 태스크를 클러스터의 서버에 언제 어떻게 배치하여 그 태스크를 실행할 지 결정하는 일을 한다. 스케줄러는 다양한 요구사항을 만족시켜야 한다.
- 클러스터의 자원 이용률을 높게 유지할 것
- 스케줄링하는 태스크의 constraint를 지키도록 스케줄링할 것
- 빠른 결정을 내릴 것
- 비즈니스적인 중요도에 따른 다양한 범주의 공평함을 만족시킬 것
- 높은 가용성과 신뢰성
이러한 요구사항을 만족하는 좋은 스케줄러를 만들기 어려운 이유는 여러 다양한 요구사항을 갖고 있는 이질적인 워크로드에 모두 대응을 해야 하기 때문이다. 필자에 따르면 워크로드는 아래 두 가지 유형으로 분류할 수가 있다.
- batch — 실행 후 짧은 시간 안에 끝나는, 개수로는 대부분을 차지하지만 실제 리소스 사용량은 개수 대비 적은 유형
- service — 유저 대상 또는 내부 서비스등이 속해 있는, 오랜 시간 계속해서 실행되는 유형
[²]
이 중 스케줄링이 어려운 것은 단연 service 유형이다. 리소스를 더 많이 쓸 뿐 아니라 예를 들어 내장애성을 위해 서비스의 각 인스턴스들을 여러 available zone에 분산하여 배치한다든가 전원 계통이 다른 곳에 배치한다든가 하는 여러 constraint를 모두 만족시켜야 하기 때문이다. (여러 개의 constraint를 만족시키는 배치를 찾는 것은 NP-hard 알고리즘이다) 필자에 따르면 구글에서는 이러한 constraint 십 수 개가 있으며, 이 때문에 스케줄링에 수십 초 가량의 시간을 쓴다고 한다. 복잡한 워크로드의 입장에서는 스케줄링에 걸리는 시간이 어쩔 수 없는 것이지만, 단순하면서 interactive한 batch 유형의 워크로드를 실행시키는 입장에서는 head-of-line blocking이 된다. 예를 들어 본인이 10초짜리 태스크를 실행했는데 다른 복잡한 서비스를 스케줄링하느라 몇분씩 기다리게 된다면 매우 짜증날 것이다. 이러한 head-of-line blocking 문제의 해결책으로 필자는 batch와 service 워크로드의 스케줄러를 따로 마련해 병렬적으로 스케줄링을 돌릴 것을 제시하고 있다. 그리고 여러 유형의 job들을 유형에 따라 다른 방식으로 핸들링할 수 있는 기능이 스케줄러에 필요한 요구사항임을 밝혔다.
우선 omega의 디자인적 특성을 설명하기 전에 필자는 클러스터 스케줄러의 아키텍쳐 선택을 위한 분류 기준을 아래와 같이 제시했다.
- 워크로드의 성격에 따라서 다른 스케줄링 알고리즘을 지원할 것인가, 하나의 알고리즘만 지원할 것인가 (Partitioning the scheduling work)
- 클러스터 전체의 자원에 자유롭게 태스크를 배치할 수 있도록 허용할 것인가 (Resource choice)
- 스케줄러 여러 개가 클러스터의 자원을 두고 경쟁하게 된다면 클러스터 내 자원을 오직 하나의 스케줄러만 접근 가능하도록 할 것인가 (pessimisive) 아니면 여러 스케줄러가 접근 가능하게 하고 나중에 충돌을 잡아내는 식으로 할 것 인가 (optimistic) (interference)
- 하나의 job이 여러 task를 가질 수가 있다면 모든 태스크를 동시에 배치할 것인가 아니면 일부 태스크만 나중에 배치할 수 있도록 허용할 것인가 (Allocation granularity)
- 여러 스케줄러가 cluster-wide 한 정책에 따라야 한다면 어떻게 할 것인가 (Cluster-wide policies)
이러한 분류 기준에 따라 필자는 4가지 스케줄러 아키텍쳐를 제시하고 비교한다.
우선 첫번째로 베이스라인이 되는 구현은 단일 스케줄러 구현일 것이다. 클러스터에 스케줄러가 하나라면 어떨까? 워크로드에 따라 보다 정교한 스케줄링 알고리즘이 필요할 경우에도 구현을 고도화시키는 방식으로 해결할 수 있을 것이다. 예를 들어, 필자는 batch와 service 사이에 다른 알고리즘을 적용하는 multi-path 구현을 구글에서 이미 사용하고 있었다고 설명하고 있다. 그러나 필자에 따르면 monolithic scheduler는 여러 문제가 있을 수 있다.
- 하나의 스케줄러에 n개의 태스크가 들어온다면 스케줄링에 드는 시간은 O(n)이다. 따라서 클러스터와 워크로드가 커질 수록 스케줄러가 미치는 병목 또한 늘어난다.
- 다양한 스케줄링 알고리즘을 지원하게 되면 스케줄러 자체의 복잡성 또한 늘어난다.
위의 이유로 필자는 단일 스케줄러가 확장가능성이 없다고 보았다.
마찬가지로 두번째로 제시한 클러스터를 여러 개의 partition으로 쪼개고, 각 파티션마다 스케줄러를 두는 것 또한 태스크의 불균형으로 인해 클러스터의 자원 이용률을 최적화할 수 없어 확장할 수 없다고 보았다. (필자에 따르면 야후나 다른 회사에서는 당연히 “프론트엔드 프로덕트 클러스터” 따위를 따로 두겠지만 이는 매우 비효율적이며 구글은 다르다고 한다 😅 [³])
여러 스케줄러가 전체 클러스터에 접근하기 위해 Apache mesos에서는 two-level scheduling이라는 방법을 선택했다. 클러스터에 단일한 resource manager를 두고, 한 스케줄러가 resource manager에게 할당 가능한 자원을 요청하면 resource manager는 가용한 자원에 lock을 걸고 offer를 준다. 그럼 이 scheduler가 스케줄링을 마치기 전까지는 다른 스케줄러에게는 그 offer를 주지 않는다.
이 방식은 각 태스크가 짧은 시간 안에 끝나고 빠르게 자원을 반환할 때는 효과적인 방식이지만, 우선 스케줄러가 클러스터 전체의 상황을 알 수 없기 때문에 gang scheduling 등을 위해 한꺼번에 많은 자원을 필요로 하거나 복잡한 constraint를 가진 잡을 스케줄링할 때 성능이 저하되고 심지어 deadlock에 걸릴 위험까지 있다.
omega에서는 클러스터 단위의 resource managing을 없애버리고 모든 스케줄러가 클러스터 내 모든 정보를 공유하고 자유롭게 스케줄링할 수 있도록 하는 shared-state scheduling 방식을 선택했다.
모든 스케줄러는 클러스터의 현재 상태의 사본을 내부에 저장하고 있으며, 이를 cell state라고 한다. 스케줄링을 할 때는 이 local copy에 원자적 커밋을 트랜잭션한다. 스케줄러들은 낙관적 동시성 제어 (optimistic concurrency control)를 사용한다. 즉, 일단 쓰기를 시도한 뒤, 트랜잭션이 실패할 경우 다시 시도한다.
따라서 omega에서는 모든 스케줄러가 병렬적으로 동작하며, inter-scheduler 따위가 없기 때문에 head-of-line blocking 문제나 모든 스케줄러가 따라야 하는 제약사항의 소지가 없다.
위의 네 가지 스케줄러 아키텍쳐에 필자가 앞서 설명한 분류 기준을 적용해 본다면 아래 태이블처럼 표기할 수 있을 것이다.
| Approach | Resource choice | Interference | Alloc. granularity | Cluster-wide policies |
|-----------------------|-----------------|-----------------------|----------------------------|-------------------------------------|
| Monolithic | all available | none (serialized) | global policy | strict priority (preemption) |
| Statically partitioned| fixed subset | none (partitioned) | per-partition policy | scheduler-dependent |
| Two-level (Mesos) | dynamic subset | pessimistic | hoarding | strict fairness |
| Shared-state (Omega) | all available | optimistic | per-scheduler policy | free-for-all, priority preemption |필자는 위 아키텍쳐를 비교하기 위해 Lightweight, High-fidelity, 이렇게 두 가지 시뮬레이터에서의 실험을 진행했다. 둘 모두 실제 구글에서 사용된 클러스터의 태스크 기록을 기반으로 진행하였으며 결과는 거의 유사함을 확인하였다.
| | Lightweight | High-fidelity |
|--------------------|----------------------|------------------|
| Machines | homogeneous | actual data |
| Resource req. size | sampled | actual data |
| Initial cell state | sampled | actual data |
| Tasks per job | sampled | actual data |
| λjobs | sampled | actual data |
| Task duration | sampled | actual data |
| Sched. constraints | ignored | obeyed |
| Sched. algorithm | randomized first fit | Google algorithm |
| Runtime | fast (24h ≤ 5 min.) | slow (24h ≤ 2h) |스케줄러의 스케줄링 시간은 $t_{decision} = t_{job} \plus t_{task} \times \text{tasks per job}$으로 시뮬레이션하였고, $t_{job} = 0.1 \text{s}$, $t_{task} = 5 \text{ms}$를 사용하였다. 이 실험에서는 매개변수로서 service 타입 워크로드를 스케줄링하는데 걸리는 시간 $t_{decision}(service)$과 시간당 워크로드가 제출되는 비율인 $\lambda_{jobs}$를 사용하여 클러스터의 부하와 constraint의 복잡성을 시뮬레이션하였다.
스케줄러의 성능을 나타내는 지표로 작업이 제출된 후부터 첫번째 스케줄링이 시도 될 때까지의 시간인 job wait time과 평균적으로 스케줄링이 성공하기까지의 충돌 횟수인 conflict fraction을 사용하였다. 스케줄러는 한 번에 하나의 작업만을 수행하므로 job wait time이 길어진다는 것은 스케줄러의 큐가 적체되어 있음을 뜻한다.
실험 결과는 위와 같다. 가로 축은 $t_{job}$, 새로 축은 $t_{task}$, 수직 축은 scheduler의 busyness, 붉은 색은 scheduling되지 못한 job이 남아있음을 뜻한다.
보다 정교한 시뮬레이터에서 $t_{job}(service)$를 조절해가며 확인해 본 결과 $t_{job}(service) = 10\text{sec}$ 전후로 SLO인 30초를 맞추지 못하였고, 비슷한 시점에서 conflict fraction이 1.0을 넘겼음 (즉 평균적으로 모든 job이 스케줄링 될 때 한 번 이상 재시도했음)을 확인하였다.
번외로, 필자는 단일 스케줄러 구현에서 batch job의 스케줄링 시간이 성능에 매우 큰 영향을 미치는 것에 주목했다. omega에서는 여러 스케줄러가 병렬적으로 작동할 수 있기 때문에 batch job을 여러 스케줄러에 로드밸런싱하면서 성능 향상을 꾀할 수 있었다.
추가로 high fidelity simulator 환경에서 확인해 볼 수 있었던 omega에서 cell state 의 conflict fraction에 영향을 주는 디자인 선택 두 가지를 제시했다. commit하려는 머신 중 하나의 변경사항만 감지되어도 전체를 실패시키는 coarse-grained conflict detection이고, 두번째는 하나의 머신만 over-commit되어도 전체 트랜잭션을 실패시키는 all-or-nothing scheduling(i.e. gang scheduling)인데, 둘 다 conflict fraction에 악영향을 미치기 때문에 특별한 이유가 없다면 fine-grained conflict detection과 incremental scheduling을 사용할 것을 권하고 있다.
마지막으로 보다 특수한 scheduler 구현에도 omega가 잘 대응할 수 있음을 보이기 위해 병렬 실행에 최적화된 MapReduce 전용 스케줄러를 구현하여 성공적으로 적용하였다고 밝혔다.
[¹]: Burns, Brendan, Brian Grant, David Oppenheimer, Eric Brewer, and John Wilkes. “Borg, omega, and kubernetes.” Communications of the ACM 59, no. 5 (2016): 50–57.
[²]: https://people.csail.mit.edu/malte/pub/talks/2013-04-17_eurosys-omega.pdf
