深度解析Kubernetes核心原理之Scheduler
深度解析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