쿠버네티스 스케쥴러 스케쥴링 과정

모든 컨테이너에는 리소스 요구사항이 다르며 모든 파드들도 요구사항이 다르다. 따라서 기존 노드들은 특정 스케줄링 요구사항에 따라 스케쥴링 되어야 한다.

 

클러스터에서 파드에 대한 스케줄링 요구사항을 만족하는 노드를 실행 가능한 노드 즉, feasible 노드라고 한다. 만약 feasible 노드가 존재하지 않으면 스케줄러가 배치할 수 있을 때까지 파드가 스케줄 되지 않은 상태로 유지된다. feasible 노드를 찾은 후 모든 feasible 노드에 점수를 메기는 기능 셋을 실행하고, 가장 점수가 높게 측정된 feasible 노드를 선택해 파드를 실행한다.

 

이후 스케쥴러의 바인딩이라 하는 프로세스에서 이 결정에 대해 API 서버에 알린다. 리소스 요구사항 이외에도, 하드웨어/소프트웨어/정책 제한조건, 어피니티/안티 어피니티, 데이터 지역성, 워크로드 간 간섭 등이 스케쥴링을 결정하기 위해 고려해야 할 사항이다.

 

위 단계를 2개로 나누면

1. 필터링 ⇒ feasible 한 노드 집단을 찾는 과정
2. 스코어링 ⇒ feasible 노드 집단에 점수를 메기는 과정

스케줄러의 주 업무는 placement를 고르는 것이다. placement란 pod를 node에 partial 혹은 non-injective하게 할당하는 것이다.

partial : Some pods may not be assigned a Node

Non-injective : Some pods may be assigned the same Node

 

스케쥴러는 possible → feasible → viable 과정을 거치는 multi-step 스케쥴러이다. 이는 지역 최적화를 보장한다. 이와 반대로 single-step 스케쥴링은 global 최적화를 보장한다.

 

스케줄러가 주로 확인하는 오브젝트와 속성값에 대한 그림이다.

BoundTo(Pod, Node, Snapshot) ≝ 
  ∧ Pod ∈ Snapshot
  ∧ Pod.Kind = "Pod"
  ∧ Node ∈ Snapshot
  ∧ Node.Kind = "Node"
  ∧ Pod.Spec.NodeName = Node.Name

Bound(Pod, Snapshot) ≝ 
  ∃ Node ∈ Snapshot:
    BoundTo(Pod, Node, Snapshot)

pod의 podspec 내부의 nodename 값을 통해 pod가 node에 할당된다. nodename이 node의 Name과 동일하면 할당이 된다. (해당 노드가 없으면 안됨)

좀더 formal하게 스케줄러의 Task를 설명하자면, BoundTo 값이 True가 되게끔 pod에 select된 node 값을 update 하는 것이다.

Unbound시 스케쥴러는 다음의 과정을 Loop한다

1. Scheduling Step 만약 scheduling step이 활성화 되어 있고, 적어도 한 노드가 파드에 대해 feasible node일 경우 scheduling step은 사용 가능하다. 스케쥴러가 feasible 노드에 파드를 bind하고 이 binding은 가장 높은 viability를 만족할 것이다. (높은 score) 하지만 이것이 not enabled한 경우 스케쥴러는 Preemtion Step을 수행한다.
2. Preemtion Step 특정 노드에 바인딩된 우선순위가 낮은 파드의 집합이 삭제될 경우, 해당 노드가 feasible이 되는 노드가 존재한다면 Preemtion step을 사용할 수 있다. 스케쥴러는 최대한 낮은 우선순위의 파드 집합을 삭제해 피해를 최소화 한다. 이 파드는 추후의 스케쥴링에서 같은 노드에 다시 스케쥴링이 될거라 보장되지 않는다.

Feasibility

파드에 대해 노드가 Feasible 한지 알아내는 과정이다. 스케쥴러는 노드가 파드의 제약조건을 만족하는지 여부를 결정하는 필터 함수를 정의한다. 이때 노드가 파드에 feasible 하려면 모든 필터 기능이 참이어야 한다.

필터링 종류

1. Schedulability and Lifecycle phase ⇒ Running 상태여야 함

Filter(Pod, Node) ≝
  \\* Only consider Nodes that accept new Pods
  ∧ Node.Spec.Unschedulable = False
  \\* Only consider Nodes that are ready to accept new Pods (Lifecycle Phase)
  ∧ Node.Status.Phase = "Running"

  2. Resource Requirements and Resource Availability ⇒ 파드 자원 요구사항에 대해 노드 자원이 사용가능해야 함.

Resources(Pod, Node) ≝
  ∧ 1 ≤ Node.Status.Allocatable["pods"]
  \\* Use the maximum resource requirements of init containers
  ∧ Max({ i \\in DOMAIN p.Spec.InitContainer : p.Spec.InitContainer[i].Resources.Required["cpu"] }) ≤ Node.Status.Allocatable["cpu"]
  ∧ Max({ i \\in DOMAIN p.Spec.InitContainer : p.Spec.InitContainer[i].Resources.Required["mem"] }) ≤ Node.Status.Allocatable["mem"]
  ∧ ...
  \\* Use the sum of resource requirements of main containers
  ∧ Sum({ i \\in DOMAIN p.Spec.Container : p.Spec.Container[i].Resources.Required["cpu"] }) ≤ Node.Status.Allocatable["cpu"]
  ∧ Sum({ i \\in DOMAIN p.Spec.Container : p.Spec.Container[i].Resources.Required["mem"] }) ≤ Node.Status.Allocatable["mem"]

  3. Node Selector ⇒ 파드 스펙의 Node Selector value와 노드의 label에 기반한다.

Filter(Pod, Node) ==
  ∀ Label ∈ DOMAIN(Pod.Spec.NodeSelector): 
      ∧ Label ∈ DOMAIN(Node.Labels) 
      ∧ Pod.Spec.NodeSelector[Label] = Node.Labels[Label]

  4. Node Taints and Pod Toleration ⇒ 하단 참조

Filter(Pod, Node) == 
    ∀ Taint ∈ Node.Spec.Taints:
        ∃ Toleration ∈ Pod.Spec.Tolerations: Match(Toleration, Taint)

Match(Toleration, Taint) ==
    ∧ CASE Toleration.Operator = "Exists" 
           ⟶ Toleration.key = Taint.key 
        [] Toleration.Operator = "Equal" 
           ⟶ Toleration.key = Taint.key ∧ Toleration.value = Taint.value
        [] OTHER 
           ⟶ FALSE
    ∧ Toleration.Effect = Taint.Effect

파드는 노드의 Taints에 대해 본인의 Toleration이 일치하면 해당 노드에 bound 될 수 있다. 하지만 일치하지 않는다면 절대 bound 될 수 없다.

 

     5. Required Affinity ⇒ 파드에서 요구하는 Node Affinity Terms, Pod Affinity Terms, and Pod Anti Affinity Terms에 대한 부분을 확인한다.

 

- 코드

Filter(Pod, Node) ≝
    \* Node, Affinity
    ∧ ∃ NodeSelectorTerm ∈ Pod.Spec.Affinity.NodeAffinity.Required.NodeSelectorTerms : 
            Match_NS(NodeSelectorTerm, Node)
    \* Pod, Affinity
    ∧ ∀ PodAffinityTerm ∈ Pod.Spec.Affinity.PodAffinity.Required : 
            P_Affinity(PodAffinityTerm, Node)
    \* Pod, Anit-Affinity
    ∧ ∀ PodAffinityTerm ∈ Pod.Spec.Affinity.AntiPodAffinity.Required : 
          ¬ P_Affinity(PodAffinityTerm, Node)

\* Node, Affinity, Match Node Selector Term
Match_NS(NodeSelectorRequirement, Node) ≝
    CASE NodeSelectorRequirement.Operator = "In" 
         ⟶   (NodeSelectorRequirement.Key ∈ DOMAIN(Node.Labels) ∧ Node.Labels[NodeSelectorRequirement.Key] ∈ NodeSelectorRequirement.Value)
      [] NodeSelectorRequirement.Operator = "NotIn" 
         ⟶ ¬ (NodeSelectorRequirement.Key ∈ DOMAIN(Node.Labels) ∧ Node.Labels[NodeSelectorRequirement.Key] ∈ NodeSelectorRequirement.Value)
      [] NodeSelectorRequirement.Operator = "Exits" 
         ⟶   (NodeSelectorRequirement.Key ∈ DOMAIN(Node.Labels))
      [] NodeSelectorRequirement.Operator = "DoesNotExist" 
         ⟶ ¬ (NodeSelectorRequirement.Key ∈ DOMAIN(Node.Labels))
      [] _NodeSelectorRequirement.Operator = "Gt" ∧ ∀ Value ∈ NodeSelectorRequirement.Value: Value ∈ Int
         ⟶   (NodeSelectorRequirement.Key ∈ DOMAIN(Node.Labels) ∧ Node.Labels[NodeSelectorRequirement.Key] ∈ Int ∧ Node.Labels[NodeSelectorRequirement.Key] > Max(NodeSelectorRequirement.Value))
      [] _NodeSelectorRequirement.Operator = "Lt" ∧ ∀ Value ∈ NodeSelectorRequirement.Value: Value ∈ Int
         ⟶   (NodeSelectorRequirement.Key ∈ DOMAIN(Node.Labels) ∧ Node.Labels[NodeSelectorRequirement.Key] ∈ Int ∧ Node.Labels[NodeSelectorRequirement.Key] < Min(NodeSelectorRequirement.Value))
      [] OTHER 
         ⟶ FALSE

\* Pod, (Anti)Affinity, Match Pod Affinity Term
P_Affinity(PodAffinityTerm, Node) ==
    IF PodAffinityTerm.TopologyKey \in DOMAIN(Node.Labels) THEN
        ∃ Other ∈ {Other ∈ Objects : Other.Kind = "Node" ∧ PodAffinityTerm.TopologyKey ∈ DOMAIN(Other.Labels) ∧ Other.Labels[PodAffinityTerm.TopologyKey] = Node.Labels[PodAffinityTerm.TopologyKey]}: 
            ∃ Pod ∈ {Pod ∈ objects : Pod.kind = "Pod" ∧ BoundTo(Pod, Node) ∧ Pod.Namespace ∈ PodAffinityTerm.Namespaces}:
                Match_LS(PodAffinityTerm.LabelSelector, Pod.Labels)
    ELSE
        FALSE

\* Pod, (Anti)Affinity, Match Label Selector
Match_LS(LabelSelector, Labels) ≝
    ∧ ∀ Key ∈ DOMAIN(LabelSelector) : Key ∈ DOMAIN(Labels) ∧ LabelSelector[Key] = Labels[Key]
    ∧ ∀ LabelSelectorRequirement ∈ LabelSelector.MatchExpression:
          CASE LabelSelectorRequirement.Operator = "In"
               ⟶   (LabelSelectorRequirement.Key ∈ DOMAIN(Labels) ∧ Labels[LabelSelectorRequirement.Key] ∈ LabelSelectorRequirement.Values)
            [] _LabelSelectorRequirement.Operator = "NotIn"
               ⟶ ¬ (LabelSelectorRequirement.Key ∈ DOMAIN(Labels) ∧ Labels[LabelSelectorRequirement.key] ∈ LabelSelectorRequirement.Values)
            [] _LabelSelectorRequirement.Operator = "Exists"
               ⟶   (LabelSelectorRequirement.Key ∈ DOMAIN(Labels))
            [] _LabelSelectorRequirement.Operator = "DoesNotExist"
               ⟶ ¬ (LabelSelectorRequirement.Key ∈ DOMAIN(Labels))

Viability

pod에 feasible한 노드 집단을 위의 필터링 과정을 통해 정했으면, 이제 Viability를 통해 scoring을 해 점수를 메긴다.

점수는 pod-node 한 쌍에 대해 메겨진다. 그리고 각각의 Rating에 대해 sum 한 결과가 최종 점수가 된다.

Viability(Pod, Node, Snapshot) ==
  Sum(<<Rating_1(Pod, Node, Snapshot), Rating_2(Pod, Node, Snapshot), ...>>)

1. Preferred Affinity ⇒ Node Affinity Terms, Pod Affinity Terms, and Pod Anti Affinity Terms 에 대한 파드-노드 간의 weight 값을 본다.

Rating(Pod, Node) ≝
  Sum(<<
    Sum(LAMBDA Term: Term.Weight, {NodeSelectorTerm ∈ Pod.Spec.Affinity.NodeAffinity.Preferred.NodeSelectorTerms : Match_NS(NodeSelectorTerm, Node) }),
    Sum(LAMBDA Term: Term.Weight, {PodAffinityTerm ∈ Pod.Spec.Affinity.PodAffinity.Preferred : P_Affinity(PodAffinityTerm, Node) }),
    Sum(LAMBDA Term: Term.Weight, {PodAffinityTerm ∈ Pod.Spec.Affinity.AntiPodAffinity.Preferred : ~ P_Affinity(PodAffinityTerm, Node)})
  >>)

이 합산은 Node Affinity Terms, Pod Affinity Terms, and Pod Anti Affinity Terms의 weight를 더한 값으로 측정된다.

CASE Study

Taint & Tolerant를 이용해 특정 노드에 특정 Tolerant를 가진 파드만 할당 가능하게 한다. Node에 Label을 붙이고 Node Affinity를 적용해 GPU가 필요한 파드는 GPU가 존재하는 노드에만 할당 하게 한다.

 

 

 

참고: 

https://kubernetes.io/ko/docs/concepts/scheduling-eviction/kube-scheduler/

쿠버네티스 스케줄러

참고 : https://dominik-tornow.medium.com/the-kubernetes-scheduler-cd429abac02f

The Kubernetes Scheduler