Kubernetes Custom Scheduler

Scheduler를 개선 방법 5가지

Source code modification

그냥 코드단위로 스케줄러 변경

Extender mechanism

HTTP로 추가적인 프로세스를 실행시켜 filtering과 scoring을 진행한다.

Custom Scheduler

여러개의 custom scheduler를 만들어서 pod마다 다른 scheduler를 실행시킬 수 있다.

Scheduling framework

scheduling 과정에 있는 여러 개의 plugin들을 추가/제거해 filtering과 scoring 방식을 바꿀 뿐만 아니라 pod queue에 정렬되는 기준들을 변경할 수도 있다.

Input to the scheduler from another component

Custom logic을 만들어서 affinity label등을 추가할 수 있다.

Custom Scheduler의 트렌드

초기의 custom scheduler들은 2017년에 나왔다. 걑은 종류의 자원을 두고 경쟁하는 pod들에 대해 QoS(Quality of Service) class를 제공해서 자원 할당 정도를 조정하는 것 등이 나왔다.

2019년에 나온 custom scheduler는 GPU sharing을 구현하고 utilization 정도를 올리기 위해 scheduler를 제작하였다.

2019년 이후부터는 크게 두 분류의 custom scheduler가 개발됐다. 첫 번째는 fog/edge computing을 지원해주는 custom scheduler를 개발했다. 기존의 K8s scheduler는 fog/edge의 노드들에 대한 topology를 신경쓰지 않았기 때문에 이것을 지원하기 위한 scheduler를 개발했다.
두 번째는 GPT-2나 GPT-3등의 NLP 기반 작업에서 효율성을 높이는 방향으로 custom scheduler를 개발하였다.

Classification methodology

workload 속도 최적화

• Interference and colocation : 같은 resource를 사용하는 multiple workload를 한 노드에 넣으면 resource conflict가 일어난다.

• QoS support 부족 : CPU, memory, local storage등의 resource는 scheduling시 고려되지만, network bandwidth에 대한 고려는 이루어지지 않고 있다.

• Topology-awareness : edge/fog 상에서 node들 간의 topology가 고려되지 않는 scheduling은 latency를 증가시킨다. 예를 들어 연결되는 작업을 하는 두 pod이 먼 node상에 있을 경우 통신시간이 증가한다.

• No support for co-scheduling : 연결된 작업을 하는 여러 pod의 그룹들을 scheduling할 때 동시에 하지 못하고 하나하나씩 차례로 scheduling해야 한다. 따라서 마지막 pod이 스케줄링되지 전까지 작업을 시작하지 못한다.

• No support for batch scheduling : batch scheduling이 없기 때문에 multi-priority queuing, fairness, and advanced preemption, multiple schedulers 등으로 대신하고 있다.

• No support for data locality awareness : data locality를 인식하도록 개선이 필요하다.

resource의 사용효율 증가

• Lack of real load awareness : pod이 스케줄링될 때 request만큼의 여유 resource를 가진 node로 할당되는데, 이 때 실행중인 pod의 resource 소비량은 실제 소비량이 아닌 해당 pod들의 request를 기준으로 계산된다. 따라서 실제 사용량을 기준으로 계산하면 더 효율적인 resource 사용이 가능해진다.

• GPU sharing : GPU의 할당량은 정수로밖에 지원되지 않으므로, custom scheduler를 만들어서 여러 pod들이 한 GPU를 사용할 수 있도록 custom scheduler를 개발할 수 있다.

Negative environmental impact 감소

환경을 보존하자!

Scheduler 심화

scheduler의 특징은 다음으로 나눌 수 있다.

• Objective : 앞에서 본 3개

• Target environment : cloud 환경인지, 아니면 edge/fog 환경인지 나누고, cloud라면 ML/DL 위주인지 체크한다.

• Target workloads
  (1) AI/ML 환경에서 training or inference
  (2) Serverless 환경
  (3) Big data Analytics
  (4) Stateful apps (ex. DB)
  (5) Virtual network functions
  (6) Network intensive
  (7) Delay sensitive
  (8) Heterogeneous

• 어떤 operation을 건들지
  (1) Sorting
  (2) Filtering
  (3) Scoring

• custom 방식
  (1) 앞에서 본 5개

• 성능 평가 방식
  (1) Real Cluster
  (2) Simulator
  (3) None

Custom Scheduler 예제

Interference & Colocation

workload들이 같은 자원을 두고 경쟁하지 못하도록 scheduling하는 것을 목표로 한다.

1. 어떤 제안자는 자원 분산을 위해 딥러닝의 강화학습을 기반으로 한 Harmony라는 모델을 제안한다. Harmony 모델은 클러스터 상태와 request resource를 입력으로 받고 pod을 알맞은 노드에 배치한다. 그 후 log로 interference 정도를 추출해 보상의 정도를 정하고 자원을 효율적으로 이용할 수 있다.

출처 - Deep Learning-based Job Placement in Distributed
Machine Learning Clusters

2. 어떤 제안자는 기존처럼 딥러닝 워크로드의 GPU 사용량을 실시간으로 평가하는 대신 딥러닝 모델을 통해 정보를 추출하고 GPU의 활용률을 예측해서 보여준다.

출처 - Towards GPU Utilization Prediction for Cloud Deep Learning

Lack of support for Network QoS

1. Kubernetes에서는 network를 자원의 단위로 간주하지 않으므로 NBW guard라는 network bandwidth 관리 system를 추가한다. NBW guard는 Linux 기반의 network management tool을 사용해서 traffic을 제한한다. 즉 network bandwidth를 할당해줌으로써 pod의 traffic이 특정 수치를 넘지 않도록 조절한다.

2. Remote DMA(네트워크 상에서 사용되는 DMA)를 관여한다. pod에서 RDMA bandwidth에 대한 request와 limit을 설정하도록 한다. 그리고 한 pod에서 multiple RDMA interface가 할당될 수 있도록 한다. 이를 통해 data transfer의 bandwidth를 조절할 수 있다.

3. latency-sensitive하고 data-intensive한 edge/fog 환경에서 실시간의 network status 정보를 확인하기 위해서 network-aware-scheduler(NAS)를 개발한다. NAS 상에서 fog에 해당하는 노드는 RTT(round trip time, 패킷 왕복 시간)으로 labeling된다. 또한 available bandwidth를 설정해서 노드에서 할당 가능한 대역폭을 넘기면 filtering시키는 과정을 거친다.

Topology-awareness

edge/fog에 제한되는 내용이므로 넘어가자.

No Support for Co-scheduling

1. Serverless workload상에서는 여러 개의 pod이 스케줄링될 때 각 부분의 이미지를 가지는 pod들에 대해서(ex. replicaset등을 말하는것 같다) 노드 탐색을 반복적으로 수행하므로 overhead가 발생한다. 따라서 동일한 이미지를 가지는 pod들을 한번에 스케줄링하는 방식을 사용하면 시간이 절약된다.

2. Kubernetes의 베타 기능으로 SIG(Special Interest Group)이 있다. pod spec에서 pod이 속한 group을 지정하고 pod 그룹의 우선순위를 비교해서 ready queue에서 정렬작업을 한다.

No Support for Batch Scheduling

1. multi-tenant 클라우드 환경에서 tenant간의 fairness를 보장해야 한다. Kube-batch에서는 fairness 보장 수단이 DRF(Domain Resource Fariness)밖에 존재하지 않으므로, 저자는 Kube-sphere라는 demand-aware와 demand-DRF-aware 2개를 추가로 고려하는 custom scheduler를 제작한다. demand-aware의 경우 많은 resource를 요구하는 유저를 우선하고, demand-DRF-aware는 starvation을 막기 위해 유저의 demand와 dominant resource share를 둘다 고려한다.

2. 두가지의 scheduler를 제안한다. 첫번째는 busy hour에 사용하는, resource requirements를 기반으로 한 queue sorting을 사용해서 fragmentation 문제를 완화한다. 두번째는 GPU-intensive 작업을 위해 사용하는데, 그들의 waiting time과 estimated running time을 잘 고려해서 priority를 동적으로 조절한다.

3. Kube-batch는 AL/ML 등의 데이터와 CPU 작업이 많이 필요한 작업들을 위해 batch 스케줄링을 목료로 한다. Kube-batch는 다양한 우선순위 class들과 gang scheduling을 지원하며, Kubeflow나 Volcano등에서 사용한다. Apache Yunikorn는 YARN을 같이 사용해서 batch-scheduling을 지원하는 tool이다. stateless workload + statedful service같은 혼합된 workload를 사용가능하게 할 수 있다. hierarchical resource queues, multi-policy job queuing를 사용해서 fairness를 개선하는 한편 scheduling throughput을 향상시킬 수 있다.

gang scheduling이란? 한 process의 여러 thread들을 따로따로 CPU에 실행시킴. pararell programming에서 사용 가능하다.

No support for Data locality Awareness

Lack of Real load awareness

pod을 scheduling할 때 reqeust값이 아닌 실제 사용량을 기반으로 scheduling plan을 만든다.

1. edge-computing 환경에서 실시간의 resource consumption을 기반으로 scheduling한다. 실시간의 scheduling 정보(ex. load, temperature, liveness)등을 node로부터 모은 후 node score를 계산해서 schdeuling한다.

2. modified PSO(particle swarm optimization) 알고리즘을 사용해 scheduling한다. node의 사용량을 CPU와 memory 뿐만 아니라 affinity를 가지고 계산한다.

3. IBM에서 개발된 Trimaran이라는 load-aware scheduler plugin이 있다. 이 plugin은 pod resource의 request와 실제 사용량 사이의 불일치를 탐지하는데, 이것에 TargetLoadPacking와 LoadVariationRiskBalancing라는 두 가지 plugin을 사용한다. TargetLoadPacking는 각 node에서 실제 resource 사용량을 기준으로 점수를 매긴다.
   LoadVariationRiskBalancing는 자원 사용의 평균과 표준편차를 구해서 점수를 매긴다.

4. Intel에서는 실시간의 telemetry 정보를 이용하는 TAS(Telemetry-aware scheduler)를 사용한다. 이 scheduler에서는 extender mechanism을 사용해 node의 power, CPU, memory등의 사용량을 체크한다.

GPU Sharing

1. GAIA는 GPU sharing을 제안한 scheduler이다. GPU cluster를 communication cost를 기반으로 tree 구조로 설계하고 얼마나 사용중인지의 상태를 표시한다. GAIA에서는 이 tree 구조에서 얼마나 GPU를 할당해줄 것인지 확인한다. 그리고 GAIA에서는 device plugin을 사용해서 GPU를 fractional한 virtual GPU들로 나눌 수 있다.

2. pod이 필요한 GPU 사용량보다 적은 GPU를 가진 node은 filtering한다. GPU 할당을 CPU와 memory처럼 하기 위해 두 개의 Custom Resource를 개발하는데, RESOURCE-MEM은 사용 가능한 VRAM의 크기이고 RESOURCE-COUNT는 사용 가능한 GPU의 수이다. 그리고 NVIDIA device plugin을 사용해서 GPU를 kubelet에서 인지하도록 한다.

3. KubeShare라는 프레임워크로 GPU sharing을 제안한다. SharePod이라는 Custom Resource를 제안하고, vGPU라는 custom shared device를 붙인다. 그리고 vGPU를 적절하게 continaer에 붙여주는 KubeShare-Sched와 vGPU pool을 관리하는 KubeShare-DevMgr라는 Custom controller를 만든다.

4. 어떤 작업이 CPU나 GPU에서 둘 다 수행 가능할 경우, CPU를 할당받을 때와 GPU를 할당받을 때의 예상 완료 시간을 비교해 더 나은 쪽으로 자원을 할당해준다.

Specific Contributions - etc

새로운 알고리즘 사용하기

1. SpeCon이라는 scheduler는 DL training의 application specefic의 효율성을 높이기 위해 제안되었다. DL 작업의 여러 단계들은 각각 자원의 필요량이 차이가 난다. 따라서 DL 작업을 progressing, watching, converge 3분류로 나눈다. 작업 속도가 느린 단계에서 리소스를 빼와서 작업 속도가 빠른 단계에 집중시킨다. 이로부터 DL 수행시간을 줄일 수 있다.

2. Prediction을 사용해서 CPU노드와 GPU노드 모두에 대한 작업 소요시간을 예상한다. Prediction은 instrcution수, floating point 계산수, 사용하는 resource량 등으로 예측하고, workload들의 우선순위를 조절하고 더 적절한 노드에 할당한다.

Summary

Annotation, Label, Extended Resource, CRD, Device Plugin을 추가해서 스케줄러를 확장할 수 있다.