深度解析Kubernetes核心原理之Scheduler

Kubernetes是一个容器编排引擎，它被设计为在被称为集群的节点上运行容器化应用。通过系统建模的方法，本系列文章的目的是为了能够深入了解Kubernetes以及它的深层概念。

Kubernetes Scheduler是Kubernetes的一个核心组件：在用户或者控制器创建一个Pod后，Scheduler在对象存储数据里监控未被分配的Pod，并将Pod分配到某个节点。然后Kubelet在对象存储数据里监控已分配的Pod，并运行该Pod。

本文提供了一个Kubernetes Scheduler的更简洁、更详细的模型表述。该模型部分基于TLA+规范。

图 1. Pod处理流程

Kubernetes Scheduler的任务是选择一个placement(位置)。一个placement是一个部分的，非内射的Pod集合到节点集合的分配。

图 2. 调度示例

调度是一个最优化问题：首先，Scheduler确定feasible placements(可用的位置)，这些是满足给定约束的placement集合。然后，Scheduler确定viable placements(可行的位置)，这些是得分最高的feasible placements集合。

图 3. Possible(可能), Feasible(可用)和Viable(可行)的调度

Kubernetes Scheduler是一个保证局部最优解的多步调度器，而不是一个保证全局最优解的单步调度器。

图 4. 多步 vs. 单步

Kubernetes Scheduler

图 5. Kubernetes Pod对象和Node对象

图5描述了Kubernetes Scheduler所感兴趣的Kubernetes对象和属性。在Kubernetes里： * 一个Pod表示为一个Kubernetes Pod对象 * 一个Node表示为一个Kubernetes Node对象 * 一个Pod分配给一个Node表示为Pod的Spec.NodeName属性

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的Spec.NodeName等于一个Node的Name，则表示这个Pod对象绑定到了这个Node对象。

Kubernetes Scheduler的任务现在可以更规范地表述为：对于一个Pod p，Kubernetes Scheduler选择一个Node n，且更新(*)这个Pod的Spec.NodeName使得BoundTo(p, n)为true。

控制循环逻辑

Scheduler ≝

LETUnbound ≝ {Pod \in Objects : Pod.Kind = "Pod" ∧ ~ Bound(Pod,Objects)} IN

∃ Pod∈ { Pod ∈ Unbound : ∀ Other ∈ Unbound : Other.Spec.Priority ≤ Pod.Spec.Priority}:

CASE SchedulingEnabled(Pod) ⟶ Scheduling(Pod)

[] PreemptionEnabled(Pod) ⟶ Preemption(Pod)

[] OTHER ⟶ UNCHANGED(Objects)

Kubernetes Scheduler监控Kubernetes对象存储并且选择一个未绑定的最高优先级的Pod来执行调度流程或者抢占流程。

调度流程

SchedulingEnabled(Pod) ≝

∃ Node∈ {Node ∈ Objects : Node.Kind = "Node"}:

Feasibility(Pod, Node, Objects)

Scheduling(Pod) ≝

LETFeasibile ≝ {Node ∈ Objects : n.Kind = "Node" ∧ Feasibility(Pod, n,Objects)} IN

∃Node ∈ Feasibile :

∧ ∀Other ∈ Feasibile : Viability(Pod, Other, Objects) ≤ Viability(Pod, Node,Objects)

∧Objects' = {

IF Pod = Object THEN

[Pod EXCEPT !["Spec"] = [Pod.Spec EXCEPT!["NodeName"] = Node.Name]]

ELSE

Object : Object ∈ Objects}

对于一个给定的Pod，如果存在至少一个Node可以运行该Pod，则启用调度流程。

如果调度流程启用，Scheduler将绑定该Pod到一个可选的Node，使得绑定能达到最优的可行性。

如果调度流程未启用，则Sheduler将尝试执行抢占流程。

抢占流程

PreemptionEnabled(Pod) ≝

∃ Node∈ {Node \in Objects : Node.Kind = "Node"}:

∃Pods ∈ SUBSET(Jeopardy(Pod, Node, Objects)):

Feasibility(Pod, Node, Objects \ Pods)

Preemption(Pod) ==

LETPreemptable == {Node ∈ Objects : Node.Kind = "Node" ∧ ∃ Pods ∈SUBSET(Jeopardy(p, Node, Objects)): Feasibility(Pod, Node, Objects \ Pods)} IN

∃Node ∈ Preemptable:

∃Pods ∈ SUBSET(Jeopardy(Pod, Node, Objects)):

∀OtherNode ∈ qualified:

∀ OtherPods ∈ SUBSET(Jeopardy(Pod, OtherNode, Objects)):

∧ Casualty(Pods) ≤ Casualty(OtherPods)

∧ Objects' = (Objects \ Pods)

对于一个给定的Pod，如果存在至少一个Node，在删除绑定到该Node的较低优先级Pod子集后可以运行该Pod，则启用抢占流程。

如果抢占流程启用，Scheduler将触发绑定到Node的低优先级Pod子集的删除操作，使得抢占流程造成的损害最小。

(抢占损害是用Pod Disruption Budget来评估的，超出了本文的主题)

注意的是Scheduler不保证触发抢占流程的Pod在后续的调度流程中能绑定到Node。

1. 可用性(Feaisbility)

对于每一个Pod，Kubernetes Scheduler确定可用的Node集合，这些Node满足了该Pod的约束。

从概念上讲，KubernetesScheduler定义了一个过滤函数集合。给定一个Pod和一个Node，过滤函数决定该Node是否满足该Pod的约束。所有过滤函数都必须返回true才表示该Node可以运行该Pod。

Feasibility(Pod, Node,Snapshot) ==

(Filter_1(Pod, Node, Snapshot) ∧ Filter_2(Pod, Node, Snapshot) ∧ ...)

下面小节详细描述了目前一些可用的过滤函数：

1.1 可调度性和生命周期阶段（Schedulability and LifecyclePhase）

该过滤函数基于Node的可调度性和生命周期阶段来确定Node的可用。Nodeconditions通过taints和tolerations来说明(如下所示)。

图 1.1 可调度性和生命周期阶段

Filter(Pod, Node) ≝

\* Onlyconsider Nodes that accept new Pods

∧Node.Spec.Unschedulable = False

\* Onlyconsider Nodes that are ready to accept new Pods (Lifecycle Phase)

∧Node.Status.Phase = "Running"

1.2 资源需求和资源可用性

该过滤函数基于Pod的资源需求和Node的资源可用性来确定Node的可用。

图 1.2 资源需求和资源可用性

Resources(Pod, Node) ≝

∧ 1 ≤Node.Status.Allocatable["pods"]

\* Usethe 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"]

∧ ...

\* Usethe 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"]

∧ ...

1.3 Node Selector

该过滤函数基于Pod的node selector值和Node的label值来确定Node的可用。

图 1.3 Node Selector

Filter(Pod, Node) ==

∀ Label∈ DOMAIN(Pod.Spec.NodeSelector):

∧Label ∈ DOMAIN(Node.Labels)

∧Pod.Spec.NodeSelector[Label] = Node.Labels[Label]

1.4 Node Taints 和 Pod Tolerations

该过滤函数基于Pod的taints键值对和Node的tolerations键值对来确定Node的可用。

图 1.4 Node Taints 和 Pod Tolerations

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

如果某个Node的taints匹配Pod的tolerations, 一个Pod可能被绑定到该Node。如果某个Node的taints不匹配Pod的tolerations, 一个Pod不能被绑定该Node。

1.5 亲和性

该过滤函数基于Pod需要的Node亲和项，Pod亲和项和Pod反亲和项来确定Node的可用。

图 1.4 Node Taints和Pod Tolerations

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) ≝

CASENodeSelectorRequirement.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) ==

IFPodAffinityTerm.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))

Node亲和

一个Pod必须分配给label匹配Pod的Node亲和需求的Node。另外，一个Pod不能分配给label不匹配Pod的Node亲和需求的Node。

Pod亲和

一个Pod必须分配给匹配TopologyKey的Node, 且该Node上至少有一个Pod匹配Pod的亲和需求。

Pod反亲和

一个Pod必须分配给匹配TopologyKey的Node, 且该Node上没有Pod匹配Pod的反亲和需求。

2. 可行性(Viability)

对于每一个Pod，Kubernetes Scheduler确定可用的Node集合，这些Node满足了该Pod的约束。然后，Kubernetes Scheduler从可用Node集合中确定最高可行性的Node。

从概念上讲，Kubernetes Scheduler定义了一个评分函数集合。给定一个Pod和一个Node，评分函数确定Pod和Node配对的可行性。这些结果最后相加。

Viability(Pod, Node,Snapshot) ==

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

下面小节详细描述了目前一些可用的过滤函数：

2.1 亲和偏好

这些过滤函数基于Pod的偏好Node亲和项，Pod亲和项和Pod反亲和项，对Node的可行性进行评分。

图 1.4 Node Taints和Pod Tolerations

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 Selector项的权重的总和 * 对于每一个匹配的Pod亲和项的权重的总和 * 对于每一个匹配的Pod反亲和项的权重的总和

用例分析

图6描述了包含2个不同类型的节点和2个不同类型的Pod的例子： * 没有GPU资源的9个节点 * 有GPU资源的6个节点

这个用例的目标是保证： *不需要GPU的Pod被分配到没有GPU的节点 * 需要GPU的Pod被分配到有GPU的节点

图 1.4 Node Taints和Pod Tolerations

(*)Kuberntes绑定对象

本文提到Kubernete Scheduler通过设置Pod的.Spec.NodeName为节点的名称，将一个Pod绑定到一个节点。然而，Scheduler是间接地设置.Spec.NodeName而不是直接设置。

Kubernetes Scheduler不被允许更新Pod的Spec。因此，KubernetesScheduler创建了一个Kubernetes绑定对象, 而不是更新Pod。在创建绑定对象后，Kubernetes API将负责更新Pod的.Spec.NodeName。

∀ Binding ∈ { Binding ∈Objects: Binding.kind = "Binding" }:

∃ Pod ∈{Pod ∈: P.Kind = "Pod"}:

∧Pod.Name = Binding.Name

∧Pod.Namespace = Binding.Namespace

∧Pod.Spec.NodeName = Binding.Target.Name

关于本文：

本文是由谷歌和SAP举办的KubeCon 2018贡献者峰会的非会议专题中详述Kubernetes Scheduler的总结。

原文：

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