所屬技術領域：
雲原生
| 名詞定義 |
排程器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替代
資料來源：