所属技术领域：
云原生
| 名词定义 |
调度器Scheduler是Kubernetes的重要组件之一。其作用是要将待调度的Pod依据某调度策略调度到最适合它运行的节点上运行。这里就涉及到三个对象：待调度的Pod、调度策略、待部署的节点队列。
Scheduler及相关联组件框架图： 
| 发展历程 |
极简Docker和Kubernetes发展史
2013年
Docker项目开源
2013年，以AWS及OpenStack，以Cloud Foundry为代表的开源Pass项目，成了云计算领域的一股清流，pass提供了一种“应用托管”的能力。
当时的虚假机虚拟机和云计算已经是比较普遍的技术了，主流用法就是租一批AWS或者OpenStack的虚拟机，然后用脚本或者手工的方式在机器上部署应用
Cloud FoudryFoundry这样的Pass项目，核心组件就是一套打包和分发机制，会调用操作系统的Cgroups和Namespace机制 为每个应用单独创建“沙盒”的隔离环境，然后在“沙盒”中运行这些进程，实现了多用户、批量、隔离运行的目的。
这个“沙盒”，就是所谓的容器。
这一年还叫dotCloud的Docker公司，也是Pass热潮中的一员。只不过，比起Heroku、Pivotal、Red Hat等大佬，dotCloud公司显得太微不足道，主打产品跟主流的CloudFoundry社区脱节，眼看就要阵亡的时候，dotCloud公司决定开源自己的容器项目Docker
“容器”其实不是什么新鲜的东西，不是Docker发明的，当时最热的Pass项目Cloud Foundry中，容器也只是最底层、最不受关注的一部分。
短短几个月，Docker就迅速崛起了，然后Cloud Foundry等所有Pass社区还没来得及成为对手，就已经被淘汰了。
Docker项目大部分和Cloud Foundry容器大部分功能和实现原理是一样的，但是不一样的“Docker镜像”，解决了环境打包的问题，直接打包了应用运行所需要的整个操作系统，赋予了本地环境和云端环境调度一致的能力，避免了用户通过“试错”来匹配不同环境之间差异的痛苦过程， 这也是Docker的精髓。
Pass的定义变成了一套以Docker容器为技术核心，以Docker镜像为打包标准的“容器化”思路
2013年年底，dotClound公司正式改名为Docker公司
2014年
Docker发布Docker Swarm
Docker发布Docker SwarnSwarm，以一个完整的整体来对外提供集群管理功能，最大的亮点就是完全使用Docker项目原来的容器管理API来完成集群管理。
docker run"容器"
只需要变成
docker run -H "swarm集群API地址""容器"
用户只需要使用原先的docker指令创建一个容器，这个请求就会被swarm拦截处理，通过具体的调度算法找到一个适合的Docker Daemon。
这种方式对已经熟悉docker命令行的开发者们非常的友好。
Docker收购Fig，并改名Compose
Docker公司收购了Fig项目，后改名为（Compose）。
Fig项目在开发者面前第一次提出了“容器编排”（Container Orchestration）
在云计算领域，“编排”主要指用户如何通过某些工具或者配置来完成一组虚拟机以及关联资源的定义、配置、创建、删除等工作，然后由云计算平台按照这些指定的逻辑来完成的过程
而容器时代，“编排”就是对Docker容器的一系列定义、配置和创建动作的管理。
Docker和Mesosphere公司的竞争
除了Docker生态外，Mesos和背后的创建公司Mesosphere也是一个非常大的热力，Mesos是大数据最受欢迎的资源管理项目，跟Yarn项目竞争的实力派对手。
大数据关注的计算密集型离线业务，其实不像Web服务那样适合用容器进行托管和扩容，也没有应用打包的强烈需要，所以Hadoop、Spark等项目现在也没在容器技术投入很大的精力，但是Mesos作为大数据套件之一，天生的两层调度机制让它非常容易从大数据领域独立出来去支持更广泛的Pass业务，所以Mesos公司发布了Marathon项目，成为了Docker Swarm的一个强有力的竞争对手。
虽然不能提供像Swarm那样的Docker API，但是Mesos社区拥有一个非常大的竞争力：超大规模集群管理经验
Mesos+Marathon组合进化成了一个调度成熟的Pass项目，同时能支持大数据业务，
Docker和CoreOS
CoreOS是一个基础设施领域创业公司，核心产品是一个定制化的操作系统，用户可以按照分布式集群的方式，管理所有安装了这个系统的节点，使用用户在集群里部署应用像使用单机一样方便
Docker项目发布后，Corecd很快认识到可以把容器的概念无逢集成到自己的这套方案中，从而为用户提供更高层次的Pass能力，所以CoreOS很早就成了Docker项目的贡献者，然而在2014年结束了合作，推出了自己的容器Rocket（rkt），然而这个rkt容器完全被Docker公司压制了。
OCI标准制定
由CoreOS、Google、RatHat等公司共同宣布，Docker公司将Libcontainer（容器运行时库）捐出，并改名为RunC项目，交由一个完全中立的基金会管理，以RunC为依据共同制定一套容器和镜像的标准规范
，叫OCI（Open Container Initiative），意在将容器运行时和镜像的实现从Docker项目中完全剥离出来，以此来压制Docker公司一家独大的现状，同时也为不依赖Docker项目构建平台层能力提供了可能。
不过并没有改变Docker在容器领域一家独大的现状
Kubernetes诞生
2014年6月，基础设施领域的领先者Google发，正式宣告了Kubernetes项目的诞生（Borg的开源版本），如同Docker横空出世一样，再一次改变了容器市场的格局。
微软、RedHat、IBM、Docker加入Kubernetes社区
2015年
CNCF基金会成立
为了在容器编排地位取得绝对的优势，同Swarm和Mesos竞争，Google、RedHat等开源基础设施公司，共同发起了一个名为CNCF的基金会：希望以Kubernetes为基础，建立一个由开源基础设施领域厂商主导、按照独立基金础会方式运营的平台社区，来对抗以Docker公司为核心的容器商业生态。简单的说就是打造一个围绕Kubernetes项目的“护城河”。
Docker擅长Docker生态的无缝集成，Mesos擅长大规模集群的调度与管理，Kubernetest选择了Pod、Sidecar等功能和模式作为切入点（大多来自Borg和Omega系统的内部特性）。
Kubernetes的团队规模很少，投入的工程能力有限，RedHat在这时候和Google联盟，正式开启户了容器编排“三国鼎立”的局书面。
Kubernetes来自Google公司在容器化基础设施领域多年来实践经验的沉淀和升华，在Github上的各项指标一路飙升，将Swarm项目远远地甩在了后边。
同年，Kubernetes发布Helm软件包管理系统、kubeam安装工具、发布Mikibube等一列更新操作
CNCF社区迅速增加了Prometheus、Fluentd、OpenTracing、CNI等一系列容器生态的知名工具和项目
大量的公司和创建团队将注意力投向CNCF社区而不再是Docker公司
2016年
Docker公司放弃现有的Swarm项目，将容器编排和集群管理功能内置到Docker中
面对CNCF的竞争优势，Docker公司宣布放弃现有的Swarm项目，将容器编排和集群管理功能内转到Docker项目当中。
然而这种改变带来的技术复杂度和维护难度，给Docker项目造成了非常不利的局书面
Kuberntes支持OpenApi，给开发人员定制化提供更大的灵活性
不同于Docker公司，Kubernetes推进“民主化”架构：从API到容器运行的每一层，都给开发者暴露出了可扩展的插件机制，鼓励用户通过代码的方式介入每一个阶段。
Kubernetes项目的这个变革非常有效，很快在整个容器社区中催生出了大量的、基于Kubernetes API和扩展接口的二次创新产品：
- 热度极高的Istio微服务治理工具
- 应用部署框架Operator
- Rook开源创业项目，把Ceph重量级产品封装成了简单易用的容器存储插件
Docker公司在Kubernetes社区的崛起和壮大后，败下阵来。
2017年
Docker将Containerd捐献给CNCF社区
Docker公司将容器运行时部分Containerd捐献给CNCF社区，标志着Docker项目你下面升级成为了一个Pass平台，Docker公司宣布将Docker项目改名为Moby，交给社区自行维护，而Docker公司的商业产品还占有Docker这个注册商标。
同年10月，Docker宣布将在自己主打产品Docker企业版中内置Kubernetes项目，持续了两年的容器编排之争终于落下帷幕
2018年
RatHat宣布2.5亿美元收购CoreOS
Docker公司CTO Solomon Hykes宣布辞职，容器技术圈子从此尘埃落定
| 技术特点 |
常用调度算法
调度的实质就是一种资源分配。不同的系统和系统目标，通常采用不同的调度算法——适合自己的才是最好的。
1、先来先服务调度算法FCFS
一种最简单的调度算法，按先后顺序进行调度。既可用于作业调度，也可用于进程调度。
按照作业提交，或进程变为就绪状态的先后次序分派CPU；
新作业只有当当前作业或进程执行完或阻塞才获得CPU运行
被唤醒的作业或进程不立即恢复执行，通常等到当前作业或进程出让CPU。（所以，默认即是非抢占方式）
不利于短作业
- 短作业（进程）优先调度算法SJF/SPF
以作业长短来计算优先级，作业越短其优先级越高。
通过上表可见采用SJF/SPF算法，平均周转时间、平均带权周转时间都有明显改善。
SJF/SPF调度算法能有效的降低作业的平均等待时间，提高系统吞吐量。
SJF/SPF的不足：
- 对短作业有利，但同时造成了对长作业的不利。
2.由于作业（进程）的长短含主观因素，不一定能真正做到短作业优先。
3.未考虑作业的紧迫程度，因而不能保证紧迫性作业（进程）的及时处理。
- 高优先权优先调度算法HPF
照顾紧迫性作业，使其获得优先处理而引入调度算法。常用于批处理系统中的作业调度算法，以及多种操作系统中的进程调度算法
分两种方式：
非抢占式优先权算法
抢占式优先权算法 关键点：新作业产生时
优先权的类型
静态优先权：创建进程时确定，整个运行期间保持不变。一般利用某一范围的一个整数来表示，又称为优先数。
动态优先权：创建进程时赋予的优先权可随进程的推进或随其等待时间的增加而改变。
v关于进程优先权的确定？依据如下：
1)进程类型：一般来，系统进程高于用户进程。
2)进程对资源的需求：如进程的估计时间及内存需要量的多少，对要求少的进程赋予较高优先权。
3)用户要求：由用户进程的紧迫程度及用户所付费用的多少来确定优先权的。
4.高响应比优先调度算法HRRNHighes Response Raito Next
短作业优先算法是一种比较好的算法（相当于根据作业长度设定的静态优先权算法），适用于短作业较多的批处理系统中，其主要不足是长作业的运行得不到保证。
HRRN为每个作业引入动态优先权，使作业的优先级随着等待时间的增加而以速率a提高：
优先权 =（等待时间+要求服务时间)/要求服务时间 = 响应时间 / 要求服务时间
1.同时到达的作业优先权相同。
初始t=0，随着时间增长，如果等待时间 t
相同，执行时间愈短的优先权愈高，利于短作业。
对于长作业，作业的优先级可以随等待时间的增加而提高，当其等待时间足够长也可获得处理机。长作业有照顾。
2.当执行时间相同的作业，优先权的高低决定于其等待时间的长短，也就是先来先服务。
- 基于时间片的轮转调度算法RR
分时系统新需求：及时响应用户的请求；采用基于时间片的轮转式进程调度算法。
早期分时系统采用的是简单的时间片轮转法，进入90年代后广泛采用多级反馈队列调度算法。
下面分开介绍这两种方法并比较性能。
（1）时间片轮转算法
1.将系统中所有的就绪进程按照FCFS原则，排成一个队列。
2.每次调度时将CPU分派给队首进程，让其执行一个时间片。时间片的长度从几个ms到几百ms。
3.在一个时间片结束时，发生时钟中断。
4.调度程序据此暂停当前进程的执行，将其送到就绪队列的末尾，并通过上下文切换执行当前就绪的队首进程。
进程阻塞情况发生时，未用完时间片也要出让CPU
多级反馈队列算法FB
特点：多个就绪队列，循环反馈动态优先级、时间片轮转
设置多个就绪队列，各队列有不同的优先级,优先级从第一个队列依次降低。
赋予各队列进程执行时间片大小不同, 优先权越高，时间片越短。
3）当一个新进程进入内存，引发的调度过程
1.准备调度：先将它放入第一个队列的末尾，按FCFS原则排队等待调度。
2.IF时间片内完成，便可准备撤离系统；
3.IF时间片内未能完成，调度程序便将该进程转入第二队列的末尾等待再次被调度执行。
4.当第一队列中的进程都执行完，系统再按FCFS原则调度第二队列。在第二队列的稍放长些的时间片内仍未完成，再依次将它放入第三队列。
5.依次降到第n队列后，在第n队列中便采取按时间片轮转的方式运行。
多级反馈队列调度算法的性能
多级反馈队列调度算法具有较好的性能，能较好的满足各种类型用户的需要。
终端型作业用户。大多属于较小的交互性作业，只要能使作业在第一队列的时间片内完成，便可令用户满意。
短批处理作业用户。周转时间仍然较短，至多在第二到三队列即可完成。
长批处理作业用户。将依次在1~n级队列中轮转执行，不必担心作业长期得不到处理。
| 相关词 |
1 调度策略
Kubernetes的调度策略分为Predicates（预选策略）和Priorites（优选策略），整个调度过程分为两步：
1.预选策略，Predicates是强制性规则，遍历所有的Node节点，按照具体的预选策略筛选出符合要求的Node列表，如没有Node符合Predicates策略规则，那该Pod就会被挂起，直到有Node能够满足。
2.优选策略，在第一步筛选的基础上，按照优选策略为待选Node打分排序，获取最优者。
1.1 预选策略
随着版本的演进Kubernetes支持的Predicates策略逐渐丰富，v1.0版本仅支持4个策略，v1.7支持15个策略，Kubernetes（v1.7）中可用的Predicates策略有：
MatchNodeSelector：
检查Node节点的label定义是否满足Pod的NodeSelector属性需求
PodFitsResources：
检查主机的资源是否满足Pod的需求，根据实际已经分配（Limit）的资源量做调度，而不是使用已实际使用的资源量做调度
PodFitsHostPorts：
检查Pod内每一个容器所需的HostPort是否已被其它容器占用，如果有所需的HostPort不满足需求，那么Pod不能调度到这个主机上
HostName：
检查主机名称是不是Pod指定的NodeName
NoDiskConflict：
检查在此主机上是否存在卷冲突。如果这个主机已经挂载了卷，其它同样使用这个卷的Pod不能调度到这个主机上，不同的存储后端具体规则不同
NoVolumeZoneConflict：
检查给定的zone限制前提下，检查如果在此主机上部署Pod是否存在卷冲突
PodToleratesNodeTaints：
确保pod定义的tolerates能接纳node定义的taints
CheckNodeMemoryPressure：
检查pod是否可以调度到已经报告了主机内存压力过大的节点
CheckNodeDiskPressure：
检查pod是否可以调度到已经报告了主机的存储压力过大的节点
MaxEBSVolumeCount：
确保已挂载的EBS存储卷不超过设置的最大值，默认39
MaxGCEPDVolumeCount：
确保已挂载的GCE存储卷不超过设置的最大值，默认16
MaxAzureDiskVolumeCount：
确保已挂载的Azure存储卷不超过设置的最大值，默认16
MatchInterPodAffinity：
检查pod和其他pod是否符合亲和性规则
GeneralPredicates：
检查pod与主机上kubernetes相关组件是否匹配
NoVolumeNodeConflict：
检查给定的Node限制前提下，检查如果在此主机上部署Pod是否存在卷冲突
已注册但默认不加载的Predicates策略有：
PodFitsHostPorts
PodFitsResources
HostName
MatchNodeSelector
PS：此外还有个PodFitsPorts策略（计划停用），由PodFitsHostPorts替代
1.2 优选策略
同样，Priorites策略也在随着版本演进而丰富，v1.0版本仅支持3个策略，v1.7支持10个策略，每项策略都有对应权重，最终根据权重计算节点总分，Kubernetes（v1.7）中可用的Priorites策略有：
EqualPriority：
所有节点同样优先级，无实际效果
ImageLocalityPriority：
根据主机上是否已具备Pod运行的环境来打分，得分计算：不存在所需镜像，返回0分，存在镜像，镜像越大得分越高
LeastRequestedPriority：
计算Pods需要的CPU和内存在当前节点可用资源的百分比，具有最小百分比的节点就是最优，得分计算公式：cpu((capacity – sum(requested)) 10 / capacity) + memory((capacity – sum(requested)) 10 / capacity) / 2
BalancedResourceAllocation：
节点上各项资源（CPU、内存）使用率最均衡的为最优，得分计算公式：10 – abs(totalCpu/cpuNodeCapacity-totalMemory/memoryNodeCapacity)*10
SelectorSpreadPriority：
按Service和Replicaset归属计算Node上分布最少的同类Pod数量，得分计算：数量越少得分越高
NodePreferAvoidPodsPriority：
判断alpha.kubernetes.io/preferAvoidPods属性，设置权重为10000，覆盖其他策略
NodeAffinityPriority：
节点亲和性选择策略，提供两种选择器支持：requiredDuringSchedulingIgnoredDuringExecution（保证所选的主机必须满足所有Pod对主机的规则要求）、preferresDuringSchedulingIgnoredDuringExecution（调度器会尽量但不保证满足NodeSelector的所有要求）
TaintTolerationPriority：
类似于Predicates策略中的PodToleratesNodeTaints，优先调度到标记了Taint的节点
InterPodAffinityPriority：
pod亲和性选择策略，类似NodeAffinityPriority，提供两种选择器支持：requiredDuringSchedulingIgnoredDuringExecution（保证所选的主机必须满足所有Pod对主机的规则要求）、preferresDuringSchedulingIgnoredDuringExecution（调度器会尽量但不保证满足NodeSelector的所有要求），两个子策略：podAffinity和podAntiAffinity，后边会专门详解该策略
MostRequestedPriority：
动态伸缩集群环境比较适用，会优先调度pod到使用率最高的主机节点，这样在伸缩集群时，就会腾出空闲机器，从而进行停机处理。
已注册但默认不加载的Priorites策略有：
EqualPriority
ImageLocalityPriority
MostRequestedPriority
PS：此外还有个ServiceSpreadingPriority策略（计划停用），由SelectorSpreadPriority替代
资料来源：
