K8S的调度算法在仿真实验的实现

K8S调度算法在仿真实验的实现

K8S算法逻辑

总体来说K8S的调度策略，分为了两个部分，一个是预选（Predicates）阶段，一个是优选（Priorities）阶段。第一个阶段得到的机器节点会作为第二阶段的输入

预选（Predicates）阶段

下面分别对Predicates的策略进行介绍：
NoDiskConflict：pod所需的卷是否和节点已存在的卷冲突。如果节点已经挂载了某个卷，其它同样使用这个卷的pod不能再调度到这个主机上。GCE、Amazon EBS与Ceph RBD的规则如下：

NoVolumeZoneConflict：检查给定的zone限制前提下，检查如果在此主机上部署Pod是否存在卷冲突。假定一些volumes可能有zone调度约束， VolumeZonePredicate根据volumes自身需求来评估pod是否满足条件。必要条件就是任何volumes的zone-labels必须与节点上的zone-labels完全匹配。节点上可以有多个zone-labels的约束（比如一个假设的复制卷可能会允许进行区域范围内的访问）。目前，这个只对PersistentVolumeClaims支持，而且只在PersistentVolume的范围内查找标签。处理在Pod的属性中定义的volumes（即不使用PersistentVolume）有可能会变得更加困难，因为要在调度的过程中确定volume的zone，这很有可能会需要调用云提供商。
PodFitsResources：检查节点是否有足够资源（例如 CPU、内存与GPU等）满足一个Pod的运行需求。调度器首先会确认节点是否有足够的资源运行Pod，如果资源不能满足Pod需求，会返回失败原因（例如，CPU/内存 不足等）。这里需要注意的是：根据实际已经分配的资源量做调度，而不是使用已实际使用的资源量做调度。
资料补充：《Kubernetes之服务质量保证（QoS）》（http://dockone.io/article/2592）。
PodFitsHostPorts：检查Pod容器所需的HostPort是否已被节点上其它容器或服务占用。如果所需的HostPort不满足需求，那么Pod不能调度到这个主机上。
注：1.0版本被称之为PodFitsPorts，1.0之后版本变更为PodFitsHostPorts，为了向前兼容PodFitsPorts名称仍然保留。
HostName：检查节点是否满足PodSpec的NodeName字段中指定节点主机名，不满足节点的全部会被过滤掉。
MatchNodeSelector：检查节点标签（label）是否匹配Pod的nodeSelector属性要求。
关于nodeSelector参考资料：《Kubernetes之Pod调度 》（http://dockone.io/article/2635）。
MaxEBSVolumeCount：确保已挂载的EBS存储卷不超过设置的最大值（默认值为39。Amazon推荐最大卷数量为40，其中一个卷为root卷，具体可以参考http://docs.aws.amazon.com/AWSEC2/latest/UserGuide/volumelimits.html#linux-specific-volume-limits）。调度器会检查直接使用以及间接使用这种类型存储的PVC。计算不同卷的总和，如果卷数目会超过设置的最大值，那么新Pod不能调度到这个节点上。 最大卷的数量可通过环境变量KUBEMAXPDVOLS设置。
MaxGCEPDVolumeCount：确保已挂载的GCE存储卷不超过预设的最大值（GCE默认值最大存储卷值为16，具体可参见https://cloud.google.com/compute/docs/disks/persistent-disks#limitsforpredefinedmachinetypes）。与MaxEBSVolumeCount类似，最大卷的数量同样可通过环境变量KUBEMAXPD_VOLS设置。
MaxAzureDiskVolumeCount : 确保已挂载的Azure存储卷不超过设置的最大值。默认值是16。规则同MaxEBSVolumeCount。
CheckNodeMemoryPressure : 判断节点是否已经进入到内存压力状态，如果是则只允许调度内存为0标记的Pod。检查Pod能否调度到内存有压力的节点上。如有节点存在内存压力， Guaranteed类型的Pod（例如，requests与limit均指定且值相等） 不能调度到节点上。QoS相关资料：《Kubernetes之服务质量保证（QoS）》（http://dockone.io/article/2592）。
CheckNodeDiskPressure : 判断节点是否已经进入到磁盘压力状态，如果是，则不调度新的Pod。
PodToleratesNodeTaints : 根据 taints 和 toleration 的关系判断Pod是否可以调度到节点上，Pod是否满足节点容忍的一些条件。
MatchInterPodAffinity : 节点亲和性筛选。
GeneralPredicates：包含一些基本的筛选规则，主要考虑 Kubernetes 资源是否充足，比如 CPU 和 内存 是否足够，端口是否冲突、selector 是否匹配等：
PodFitsResources：检查主机上的资源是否满足Pod的需求。资源的计算是根据主机上运行Pod请求的资源作为参考的，而不是以实际运行的资源数量
PodFitsHost：如果Pod指定了spec.NodeName，看节点的名字是否何它匹配，只有匹配的节点才能运行Pod
PodFitsHostPorts：检查Pod申请的主机端口是否已经被其他Pod占用，如果是，则不能调度
PodSelectorMatches：检查主机的标签是否满足Pod的 selector。包括NodeAffinity和nodeSelector中定义的标签。

优选（Priorities）阶段

经过预选策略（Predicates）对节点过滤后，获取节点列表，再对符合需求的节点列表进行打分，最终选择Pod调度到一个分值最高的节点。Kubernetes用一组优先级函数处理每一个通过预选的节点（kubernetes/plugin/pkg/scheduler/algorithm/priorities中实现）。每一个优先级函数会返回一个0-10的分数，分数越高表示节点越优， 同时每一个函数也会对应一个表示权重的值。最终主机的得分用以下公式计算得出：
finalScoreNode = (weight1 * priorityFunc1) + (weight2 * priorityFunc2) + … + (weightn * priorityFuncn)
目前支持优选的优先级函数包括以下几种：
LeastRequestedPriority：节点的优先级就由节点空闲资源与节点总容量的比值，即由（总容量-节点上Pod的容量总和-新Pod的容量）/总容量）来决定。CPU和内存具有相同权重，资源空闲比越高的节点得分越高。需要注意的是，这个优先级函数起到了按照资源消耗来跨节点分配Pod的作用。详细的计算规则如下：
cpu((capacity – sum(requested)) * 10 / capacity) + memory((capacity – sum(requested)) * 10 / capacity) / 2

注：10 表示非常合适，0 表示完全不合适。
LeastRequestedPriority举例说明：例如CPU的可用资源为100，运行容器申请的资源为15，则cpu分值为8.5分，内存可用资源为100，运行容器申请资源为20，则内存分支为8分。则此评价规则在此节点的分数为(8.5 +8) / 2 = 8.25分。
BalancedResourceAllocation：CPU和内存使用率越接近的节点权重越高，该策略不能单独使用，必须和LeastRequestedPriority组合使用，尽量选择在部署Pod后各项资源更均衡的机器。如果请求的资源（CPU或者内存）大于节点的capacity，那么该节点永远不会被调度到。
BalancedResourceAllocation举例说明：该调度策略是出于平衡度的考虑，避免出现CPU，内存消耗不均匀的事情。例如某节点的CPU剩余资源还比较充裕，假如为100，申请10，则cpuFraction为0.1，而内存剩余资源不多，假如为20，申请10，则memoryFraction为0.5，这样由于CPU和内存使用不均衡，此节点的得分为10-abs ( 0.1 - 0.5 ) * 10 = 6 分。假如CPU和内存资源比较均衡，例如两者都为0.5，那么代入公式，则得分为10分。
InterPodAffinityPriority：通过迭代 weightedPodAffinityTerm 的元素计算和，并且如果对该节点满足相应的PodAffinityTerm，则将 “weight” 加到和中，具有最高和的节点是最优选的。
SelectorSpreadPriority：为了更好的容灾，对同属于一个service、replication controller或者replica的多个Pod副本，尽量调度到多个不同的节点上。如果指定了区域，调度器则会尽量把Pod分散在不同区域的不同节点上。当一个Pod的被调度时，会先查找Pod对于的service或者replication controller，然后查找service或replication controller中已存在的Pod，运行Pod越少的节点的得分越高。
SelectorSpreadPriority举例说明：这里主要针对多实例的情况下使用。例如，某一个服务，可能存在5个实例，例如当前节点已经分配了2个实例了，则本节点的得分为10*（（5-2）/ 5）=6分，而没有分配实例的节点，则得分为10 * （（5-0） / 5）=10分。没有分配实例的节点得分越高。
注：1.0版本被称之为ServiceSpreadingPriority，1.0之后版本变更为SelectorSpreadPriority，为了向前兼容ServiceSpreadingPriority名称仍然保留。
NodeAffinityPriority：Kubernetes调度中的亲和性机制。Node Selectors（调度时将pod限定在指定节点上），支持多种操作符（In, NotIn, Exists, DoesNotExist, Gt, Lt），而不限于对节点labels的精确匹配。另外，Kubernetes支持两种类型的选择器，一种是“hard（requiredDuringSchedulingIgnoredDuringExecution）”选择器，它保证所选的主机必须满足所有Pod对主机的规则要求。这种选择器更像是之前的nodeselector，在nodeselector的基础上增加了更合适的表现语法。另一种是“soft（preferresDuringSchedulingIgnoredDuringExecution）”选择器，它作为对调度器的提示，调度器会尽量但不保证满足NodeSelector的所有要求。
NodePreferAvoidPodsPriority（权重1W）：如果 节点的 Anotation 没有设置 key-value:scheduler. alpha.kubernetes.io/ preferAvoidPods = “…”，则节点对该 policy 的得分就是10分，加上权重10000，那么该node对该policy的得分至少10W分。如果Node的Anotation设置了，scheduler.alpha.kubernetes.io/preferAvoidPods = “…” ，如果该 pod 对应的 Controller 是 ReplicationController 或 ReplicaSet，则该 node 对该 policy 的得分就是0分。
TaintTolerationPriority : 使用 Pod 中 tolerationList 与 节点 Taint 进行匹配，配对成功的项越多，则得分越低。
另外在优选的调度规则中，有几个未被默认使用的规则：
ImageLocalityPriority：根据Node上是否存在一个pod的容器运行所需镜像大小对优先级打分，分值为0-10。遍历全部Node，如果某个Node上pod容器所需的镜像一个都不存在，分值为0；如果Node上存在Pod容器部分所需镜像，则根据这些镜像的大小来决定分值，镜像越大，分值就越高；如果Node上存在pod所需全部镜像，分值为10。

注：10 表示非常合适，0 表示完全不合适。
EqualPriority : EqualPriority 是一个优先级函数，它给予所有节点相等权重。
MostRequestedPriority : 在 ClusterAutoscalerProvider 中，替换 LeastRequestedPriority，给使用多资源的节点，更高的优先级。计算公式为：(cpu(10 *sum(requested) / capacity) + memory(10 sum(requested) / capacity)) / 2
要想获得所有节点最终的权重分值，就要先计算每个优先级函数对应该节点的分值，然后计算总和。因此不管过程如何，如果有 N 个节点，M 个优先级函数，一定会计算 MN 个中间值，构成一个二维表格：

最后，会把表格中按照节点把优先级函数的权重列表相加，得到最终节点的分值。上面代码就是这个过程，中间过程可以并发计算（下文图中的workQueue），以加快速度。
代码如下，注意下面代码并不能直接使用，更多的是用来做一个例子使用，代码语言为python,因为我仿真实验是python实现的

# 第一阶段：选出所有满足要求的节点，作为第二阶段的输入，第二个阶段找出更加适合的节点
    # 如果在预选（Predicates）阶段过程中，所有的节点都不满足条件，Pod 会一直处在Pending
    # 状态，直到有节点满足条件，这期间调度器会不断的重试。
    def predicates(self, node_affinity, node_anti_affinity, machine_list, container_type, container):
        # 标签约束：节点亲和性约束 节点反亲和性约束  节点资源约束
        affinity_dict = {}
        for i in range(0,len(node_affinity)):
            affinity_dict[i] = node_affinity[i]
        # for i in range(0,len(node_anti_affinity)):
        #     anti_affinity_dict[i] = node_anti_affinity[i]
        affinity_dict_sorted = sorted(affinity_dict.items(), key=lambda x:x[1], reverse=True)
        machine_predicates = []
        for index_key,index_value in affinity_dict_sorted:
            if node_anti_affinity[index_key] == 0:
                machine = machine_list[index_key]
                if container_type == 1:
                    if machine.compare_req_container(container):
                        machine_predicates.append(machine)
                else:
                    if machine.compare_req_task(container):
                        machine_predicates.append(machine)
        if not machine_predicates:
            priority_dict = {}
            for index_key,index_value in affinity_dict_sorted:
                priority = index_value - node_anti_affinity[index_key]
                priority_dict[index_key] = priority
            priority_dict_sorted = sorted(priority_dict.items(), key=lambda x: x[1], reverse=True)
            for index_priority_key, index_priority_value in priority_dict_sorted:
                machine = machine_list[index_priority_key]
                if container_type == 1:
                    if machine.compare_req_container(container):
                        machine = machine_list[index_priority_key]
                        machine_predicates.append(machine)
                else:
                    if machine.compare_req_task(container):
                        machine = machine_list[index_priority_key]
                        machine_predicates.append(machine)
        return machine_predicates

    # 每一个优先级函数会返回一个0-10的分数，分数越高表示节点越优，
    # 同时每一个函数也会对应一个表示权重的值。最终主机的得分用以下公式计算得出：
    # finalScoreNode = (weight1 * priorityFunc1) +
    # (weight2 * priorityFunc2) + … + (weightn * priorityFuncn)
    def priorities(self, machine_predicates, container_type, container, node_affinity):
        machine_priorities = {}
        least_requested_priority = []
        # LeastRequestedPriority策略 cpu((capacity – sum(requested)) * 10 / capacity) + memory((capacity – sum(requested)) * 10 / capacity) / 2
        # 节点的优先级就由节点空闲资源与节点总容量的比值，
        # 即由（总容量-节点上Pod的容量总和-新Pod的容量）/总容量）来决定。
        for machine in machine_predicates:
            if container_type == 1:
                machine_least_requested_priority = ((machine.cpu - container.cpu_request) * 10 / machine.cpu_capacity + (machine.mem - container.mem_size) * 10 / machine.memory_capacity) / 2
                # BalancedResourceAllocation：CPU和内存使用率越接近的节点权重越高，该策略不能单独使用，必须和LeastRequestedPriority组合使用，尽量选择在部署Pod后各项资源更均衡的机器。
                balanced_resource_allocation = 10 - abs((machine.cpu - container.cpu_request) / machine.cpu_capacity - (machine.mem - container.mem_size) * 10 / machine.memory_capacity)
                least_requested_priority.append(machine_least_requested_priority + balanced_resource_allocation)
            else:
                machine_least_requested_priority = ((machine.cpu - container.cpu_request) * 10 / machine.cpu_capacity + (machine.mem - container.mem_request) * 10 / machine.memory_capacity) / 2
                # BalancedResourceAllocation：CPU和内存使用率越接近的节点权重越高，该策略不能单独使用，必须和LeastRequestedPriority组合使用，尽量选择在部署Pod后各项资源更均衡的机器。
                balanced_resource_allocation = 10 - abs((machine.cpu - container.cpu_request) / machine.cpu_capacity - (machine.mem - container.mem_request) * 10 / machine.memory_capacity)
                least_requested_priority.append(machine_least_requested_priority + balanced_resource_allocation)
        for i in range(0,len(machine_predicates)):
            machine = machine_predicates[i]
            new_id = machine.machine_id
            new_id = new_id[2:]
            new_id = int(new_id)
            machine_priorities[i] = node_affinity[new_id - 1] + least_requested_priority[i]
        machine_priorities_sorted = sorted(machine_priorities.items(), key=lambda x: x[1], reverse=True)
        for index_key, index_value in machine_priorities_sorted:
            machine = machine_predicates[index_key]
            break
        return machine
        ```
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72