文章目錄

• Kubernetes概述
  • k8s提供的功能
  • k8s的元件
    • 控制台元件
    • Node元件
    • 插件
  • k8s架構
  • Pods
    • pod内共享資源和通信
      • 存儲
      • 網絡
    • 靜态pod
  • pod的限制性拓撲政策
  • pod如何管理多個containers
  • 示例
• 工作負載類型
  • deploymnet
  • statefulset
  • DeamonSet
  • Jobs
• 服務
  • 暴露服務的方式
  • 拓撲感覺提示
    • EndpointSlice 控制器
  • 服務内部流量政策
  • 虛拟IP與Service代理
    • userspace 代理模式
    • iptable代理模式
    • ipvs代理模式
• 排程
  • 過濾
    • GeneralPredicates
    • Volume過濾規則
    • 檢查排程Pod是否滿足Node本身的條件
    • affinity and anti-affinity
  • 打分
  • 代碼邏輯
• Volcano 排程器
  • 排程工作流
    • Action作用
      • enqueue
      • allocate
      • preempt
      • reclaim
      • backfill
  • 一些排程插件
    • Gang Scheduling
    • DRF (dominant resource fairss)
    • binpack
    • proportion(隊列)
    • 最終優選
• kubelet工作原理
  • pod管理
  • 容器監控和健康檢查
  • 容器運作時
    • 工作模式
    • 架構
    • 互動
    • CRI接口定義源碼
    • CNI接口源碼
• k8s的可擴充性
• k8s的局限性
  • 叢集管理
    • 水準伸縮性
  • 多叢集管理
    • 現有的一些探索方案
      • kubefed
  • 應用場景
    • 應用分發
    • 批處理排程
    • 硬多租戶
• K8S的對比
• 排程算法的演進
  • 問題分類
    • 互相幹擾
  • 配置設定粒度
  • 叢集行為
  • 集中排程
  • 靜态分區排程
  • 兩層排程器
  • 共享狀态排程
• Borg

Kubernetes概述

docker和k8s是雲原生時代兩顆璀璨的明珠，分别對應了雲計算中的兩大核心功能：虛拟化和排程。資源的虛拟化為排程提供了前提，而排程則增加了系統了靈活性和資源的使用率。

kubernetes,簡稱k8s，至今已經已經成為容器編排的事實标準。本文則主要講述k8s相關的一概念，并對其餘的雲上排程算法進行比較。

k8s提供的功能

• 服務發現與負載均衡
  • 通過DNS名稱或者IP位址通路容器
  • 配置設定節點間的網絡流量
• 存儲編排
• 自動部署和復原
• 自動完成裝箱計算
• 自我修複
• 密鑰與配置管理

k8s的元件

[外鍊圖檔轉存失敗,源站可能有防盜鍊機制,建議将圖檔儲存下來直接上傳(img-pwXz3V7p-1622985228011)(https://gitee.com/weixiao619/pic/raw/master/components-of-kubernetes-20210605222057314.svg)]

控制台元件

• Kube-apiserver

  對外暴露k8s的服務

• etcd

  etcd是高可用的k-v資料庫，在k8s中作為叢集運作所需的持久化資料存儲元件

• Kube-scheduler

  排程元件，選擇将pod排程到哪個git當中

• Kube-controller-manager

  從邏輯上講，每個控制器都是一個單獨的程序， 但是為了降低複雜性，它們都被編譯到同一個可執行檔案，并在一個程序中運作。

  這些控制器包括:

  • 節點控制器（Node Controller）: 負責在節點出現故障時進行通知和響應
  • 任務控制器（Job controller）: 監測代表一次性任務的 Job 對象，然後建立 Pods 來運作這些任務直至完成
  • 端點控制器（Endpoints Controller）: 填充端點(Endpoints)對象(即加入 Service 與 Pod)
  • 服務帳戶和令牌控制器（Service Account & Token Controllers）: 為新的命名空間建立預設帳戶和 API 通路令牌

• Cloud-controller-manager

  雲控制器管理器是指嵌入特定雲的控制邏輯的 控制平面元件。 雲控制器管理器允許您連結聚合到雲提供商的應用程式設計接口中， 并分離出互相作用的元件與您的叢集互動的元件。

Node元件

• kubelet
  • 運作在叢集的每一個節點上，確定容器在pod上的運作
• kube-proxy
  • 運作在每一個節點上的網絡代理，負責節點和pod間通訊的網路規則
• Container Runtime
  • Docker,containerd,CRI-O等任何實作k8s CRI (容器運作環境接口)
  • 最新k8s已不支援docker

插件

• DNS
• Web界面
• 容器資源監控
• 叢集日志

k8s架構

如圖為k8s的架構，其中一個Node一般為一個實際的主控端，

Pods

pods是k8s管理的的最小計算單元

一個pod中包含一個或多個container,共享存儲和網絡資源

Pod也可以包含init container，同時也有ephemeral containers可以用于debug

Pod之間的上下文共享，依賴一系列linux的隔離技術實作，如 namespace、cgroups等

pod并不需要直接建立，而是通過deployment或statefulset等進行建立

pod的更新并不是更新已有的pod，而是建立一個新的pod去替換已有的pod

pod内共享資源和通信

存儲

一個pod中共享一系列存儲卷，pod中所有的containers都可以通路這些共享的卷，進而實作共享存儲。pod内部的

網絡

• 每個pod被指定一個唯一的ip位址,pod中的每個容器都共享ip位址和端口。
• pod内部的容器之間可以通過localhost進行通信，也可以通過linux标準的程序間通訊方式進行通訊

容器的特權模式：允許容器使用作業系統的管理者能力，例如操作網絡棧，通路硬體資源等

靜态pod

靜态pod是直接通過kubelet進行管理的特殊節點，不能通過APIServer暴露，

pod的限制性拓撲政策

pod的拓撲政策配置樣例，主要依賴四個參數：

#pod.spec.topologySpreadConstraints demo
apiVersion: v1
kind: Pod
metadata:
  name: mypod
spec:
  topologySpreadConstraints:
    - maxSkew: <integer>   #辨別節點的最大深度差
      topologyKey: <string>  # 辨別一組排程節點
      whenUnsatisfiable: <string> # 不滿足時的排程政策
      labelSelector: <object> # 用于尋找labels比對的的pods           

複制

pod如何管理多個containers

Pod 被設計成支援形成内聚服務單元的多個協作過程（形式為容器）。 Pod 中的容器被自動安排到叢集中的同一實體機或虛拟機上，并可以一起進行排程。 容器之間可以共享資源和依賴、彼此通信、協調何時以及何種方式終止自身。

例如，你可能有一個容器，為共享卷中的檔案提供 Web 伺服器支援，以及一個單獨的 “sidecar”容器負責從遠端更新這些檔案，如下圖所示：

[外鍊圖檔轉存失敗,源站可能有防盜鍊機制,建議将圖檔儲存下來直接上傳(img-TzaRnOkk-1622985228014)(https://gitee.com/weixiao619/pic/raw/master/pod.svg)]

你可以使用工作負載資源來建立和管理多個 Pod。 資源的控制器能夠處理副本的管理、上線，并在 Pod 失效時提供自愈能力。 例如，如果一個節點失敗，控制器注意到該節點上的 Pod 已經停止工作， 就可以建立替換性的 Pod。排程器會将替身 Pod 排程到一個健康的節點執行

示例

apiVersion: apps/v1
kind: Deployment
metadata:
  name: nginx-deployment
  labels:
    app: nginx
spec:
  replicas: 3
  selector:
    matchLabels:
      app: nginx
  template:
    metadata:
      labels:
        app: nginx
    spec:
      containers:
      - name: nginx
        image: nginx:1.14.2
        ports:
        - containerPort: 80           

複制

工作負載類型

deploymnet

statefulset

DeamonSet

Jobs

服務

Service 從邏輯上定義了運作在叢集中的一組 Pod，這些 Pod 提供了相同的功能。 當每個 Service 建立時，會被配置設定一個唯一的 IP 位址（也稱為 clusterIP）。 這個 IP 位址與一個 Service 的生命周期綁定在一起，當 Service 存在的時候它也不會改變。 可以配置 Pod 使它與 Service 進行通信，Pod 知道與 Service 通信将被自動地負載均衡到該 Service 中的某些 Pod 上。

暴露服務的方式

• NodePort
• LoadBalancer
• Ingress

拓撲感覺提示

EndpointSlice 控制器

此特性開啟後，EndpointSlice 控制器負責在 EndpointSlice 上設定提示資訊。 控制器按比例給每個區域配置設定一定比例數量的端點。 這個比例來源于此區域中運作節點的 可配置設定 CPU 核心數。 例如，如果一個區域擁有 2 CPU 核心，而另一個區域隻有 1 CPU 核心， 那控制器将給那個有 2 CPU 的區域配置設定兩倍數量的端點。

服務内部流量政策

在相同node中通路pod

虛拟IP與Service代理

userspace 代理模式

[外鍊圖檔轉存失敗,源站可能有防盜鍊機制,建議将圖檔儲存下來直接上傳(img-l4PUQnZ6-1622985228015)(https://gitee.com/weixiao619/pic/raw/master/services-userspace-overview.svg)]

iptable代理模式

[外鍊圖檔轉存失敗,源站可能有防盜鍊機制,建議将圖檔儲存下來直接上傳(img-BIh9V3QL-1622985228016)(https://gitee.com/weixiao619/pic/raw/master/services-iptables-overview.svg)]

ipvs代理模式

[外鍊圖檔轉存失敗,源站可能有防盜鍊機制,建議将圖檔儲存下來直接上傳(img-MsQtTLd6-1622985228017)(https://gitee.com/weixiao619/pic/raw/master/services-ipvs-overview.svg)]

排程

在 Kubernetes 中，排程 是指将 Pod 放置到合适的 Node 上，然後對應 Node 上的 Kubelet 才能夠運作這些 pod。

Kube-scheduler給一個pod做排程分為兩部分内容：

1.過濾

2.打分

過濾

過濾過程中，會過濾出可排程的Node節點，過濾政策有如下幾種：

GeneralPredicates

負責最基礎的排程政策，過濾主控端的CPU和記憶體等資源資訊

Volume過濾規則

負責與容器持久化Volume相關的排程政策。例如：

檢查多個 Pod 聲明挂載的持久化 Volume 是否有沖突；

檢查一個節點上某種類型的持久化 Volume 是不是已經超過了一定數目；

檢查Pod 對應的 PV 的 nodeAffinity 字段，是否跟某個節點的标簽相比對

檢查排程Pod是否滿足Node本身的條件

如PodToleratesNodeTaints負責檢查的就是我們前面經常用到的 Node 的“污點”機制。NodeMemoryPressurePredicate，檢查的是目前節點的記憶體是不是已經不夠充足。

affinity and anti-affinity

根據pod的node之間的親和性與反親和性進行過濾

打分

//篩選函數
// scheduleOne does the entire scheduling workflow for a single pod.
scheduleOne()

// 1. 逾時打日志




// 2. 預選政策選出滿足排程條件的Node節點
findNodesThatFit()
// Run "prefilter" plugins.
	s := fwk.RunPreFilterPlugins(ctx, state, pod)

// "NominatedNodeName" can potentially be set in a previous scheduling cycle as a result of preemption.
	// This node is likely the only candidate that will fit the pod, and hence we try it first before iterating over all nodes.
feasibleNodes, err := g.evaluateNominatedNode(ctx, pod, fwk, state, diagnosis)


// 用不同的過濾插件{NodePort, Volume, Label等}進行過濾
runFilterPlugin()

// 3. 對節點進行打分
prioritizeNodes()

// 運作預打分插件
// InterPodAffinity, NodeAffinity, PodTopologySpread, 
RunPreScorePlugins()

// 運作打分插件
RunScorePlugins()           

複制

代碼邏輯

1. 通過sched.NextPod()函數從優先隊列中擷取一個優先級最高的待排程Pod資源對象，如果沒有擷取到，那麼該方法會阻塞住；
2. 通過sched.Algorithm.Schedule排程函數執行Predicates的排程算法與Priorities算法，挑選出一個合适的節點；
3. 當沒有找到合适的節點時，排程器會嘗試調用prof.RunPostFilterPlugins搶占低優先級的Pod資源對象的節點；
4. 當排程器為Pod資源對象選擇了一個合适的節點時，通過sched.bind函數将合适的節點與Pod資源對象綁定在一起；

Volcano 排程器

根據上一節的内容可以看出k8s原生的排程器，在排程的最後階段（打分）是串行的排程每個pod，但是在AI訓練或者大資料處理的場景下，多個執行個體需要進行互相協作，此時，實際的需求為需要保證一組執行個體同時運作成功，而k8s原生排程器無法滿足此需求，是以kube-batch分組排程器應運而生，Volcano排程器則基于kube-batch進行了進一步的優化。

如圖為Volcano排程器的工作流，一個job會打包多個pod形成一個PodGroup。

排程工作流

Volcano scheduler的工作流程如下：

1. 用戶端送出的Job被scheduler觀察到并緩存起來。
2. 周期性的開啟會話，一個排程周期開始。
3. 将沒有被排程的Job發送到會話的待排程隊列中。
4. 周遊所有的待排程Job，按照定義的次序依次執行enqueue、allocate、preempt、reclaim、backfill等動作，為每個Job找到一個最合适的節點。将該Job 綁定到這個節點。action中執行的具體算法邏輯取決于注冊的plugin中各函數的實作。
5. 關閉本次會話。

Action作用

enqueue

Enqueue action負責通過一系列的過濾算法篩選出符合要求的待排程任務并将它們送入待排程隊列。經過這個action，任務的狀态将由pending變為inqueue。

allocate

Allocate action負責通過一系列的預選和優選算法篩選出最适合的節點。

preempt

Preempt action負責根據優先級規則為同一隊列中高優先級任務執行搶占排程。

reclaim

Reclaim action負責當一個新的任務進入待排程隊列，但叢集資源已不能滿足該任務所在隊列的要求時，根據隊列權重回收隊列應得資源。

backfill

backfill action負責将處于pending狀态的任務盡可能的排程下去以保證節點資源的最大化利用。

一些排程插件

Gang Scheduling

以組為機關進行排程，

DRF (dominant resource fairss)

優先排程請求資源較少的執行個體，yarn和mesos均有對應排程Sunday

​

binpack

該排程算法盡量先填滿已有節點，将負載聚攏到部分節點，有利于彈性伸縮，減少資源碎片

proportion(隊列)

與yarn的capacity Scheduler排程器類似，根據組織配置設定資源比例，在組織内部使用FIFO的隊列模式進行資源排程

最終優選

Volcano支援各種排程算法的插件，不同插件的排程邏輯可能出現互相沖突，是以Volcano可以給不同的排程插件設定不同的權重，根據權重值來最終決定po d的排程。

kubelet工作原理

叢集的每個Node均有一個kubelet程序，pod被排程到特定的Node後，由kubelet進行管理。

pod管理

Kubelet 以 PodSpec 的方式工作。PodSpec 是描述一個 Pod 的 YAML 或 JSON 對象。 kubelet 采用一組通過各種機制提供的 PodSpecs（主要通過 apiserver），并確定這些 PodSpecs 中描述的 Pod 正常健康運作

容器監控和健康檢查

• LivenessProbe
• ReadinessProbe

容器運作時

工作模式

kubelet通過容器運作時接口 (Container Runtime Interface，CRI)與容器進行互動。

CRI将kubelet與容器運作時解耦：

架構

kubelet通過CRI結構與實際的container runtime進行互動，解耦不同容器的實作細節。如下為容器運作時的具體架構：

容器運作時主要定義了CRI Server和Streaming Server兩個服務，其中CRI Server實作了具體的CRI服務接口，由Runtime Service和 Image Manger Service兩個服務組成，具體的實作可參考下文中的源碼分析。

CNI: Container Network Interface 容器網絡接口

通過CNI将容器運作時與底層的網絡插件實作解耦，使得容器無需關心底層的網絡細節。

互動

CRI接口定義源碼

// ImageManagerService 需要實作的功能
type ImageManagerService interface {
	// ListImages lists the existing images.
	ListImages(filter *runtimeapi.ImageFilter) ([]*runtimeapi.Image, error)
	// ImageStatus returns the status of the image.
	ImageStatus(image *runtimeapi.ImageSpec) (*runtimeapi.Image, error)
	// PullImage pulls an image with the authentication config.
	PullImage(image *runtimeapi.ImageSpec, auth *runtimeapi.AuthConfig, podSandboxConfig *runtimeapi.PodSandboxConfig) (string, error)
	// RemoveImage removes the image.
	RemoveImage(image *runtimeapi.ImageSpec) error
	// ImageFsInfo returns information of the filesystem that is used to store images.
	ImageFsInfo() ([]*runtimeapi.FilesystemUsage, error)
}

// RuntimeService的實作又分為4個子實作，分别實作不同類型的功能子產品
// RuntimeService interface should be implemented by a container runtime.
// The methods should be thread-safe.
type RuntimeService interface {
	RuntimeVersioner
	ContainerManager
	PodSandboxManager
	ContainerStatsManager

	// UpdateRuntimeConfig updates runtime configuration if specified
	UpdateRuntimeConfig(runtimeConfig *runtimeapi.RuntimeConfig) error
	// Status returns the status of the runtime.
	Status() (*runtimeapi.RuntimeStatus, error)
}

// 1. RuntimeVersioner contains methods for runtime name, version and API version.
type RuntimeVersioner interface {
	// Version returns the runtime name, runtime version and runtime API version
	Version(apiVersion string) (*runtimeapi.VersionResponse, error)
}

// 2. ContainerManager contains methods to manipulate containers managed by a
// container runtime. The methods are thread-safe.
type ContainerManager interface {
	// CreateContainer creates a new container in specified PodSandbox.
	CreateContainer(podSandboxID string, config *runtimeapi.ContainerConfig, sandboxConfig *runtimeapi.PodSandboxConfig) (string, error)
	// StartContainer starts the container.
	StartContainer(containerID string) error
	// StopContainer stops a running container with a grace period (i.e., timeout).
	StopContainer(containerID string, timeout int64) error
	// RemoveContainer removes the container.
	RemoveContainer(containerID string) error
	// ListContainers lists all containers by filters.
	ListContainers(filter *runtimeapi.ContainerFilter) ([]*runtimeapi.Container, error)
	// ContainerStatus returns the status of the container.
	ContainerStatus(containerID string) (*runtimeapi.ContainerStatus, error)
	// UpdateContainerResources updates the cgroup resources for the container.
	UpdateContainerResources(containerID string, resources *runtimeapi.LinuxContainerResources) error
	// ExecSync executes a command in the container, and returns the stdout output.
	// If command exits with a non-zero exit code, an error is returned.
	ExecSync(containerID string, cmd []string, timeout time.Duration) (stdout []byte, stderr []byte, err error)
	// Exec prepares a streaming endpoint to execute a command in the container, and returns the address.
	Exec(*runtimeapi.ExecRequest) (*runtimeapi.ExecResponse, error)
	// Attach prepares a streaming endpoint to attach to a running container, and returns the address.
	Attach(req *runtimeapi.AttachRequest) (*runtimeapi.AttachResponse, error)
	// ReopenContainerLog asks runtime to reopen the stdout/stderr log file
	// for the container. If it returns error, new container log file MUST NOT
	// be created.
	ReopenContainerLog(ContainerID string) error
}

// 3. PodSandboxManager contains methods for operating on PodSandboxes. The methods
// are thread-safe.
type PodSandboxManager interface {
	// RunPodSandbox creates and starts a pod-level sandbox. Runtimes should ensure
	// the sandbox is in ready state.
	RunPodSandbox(config *runtimeapi.PodSandboxConfig, runtimeHandler string) (string, error)
	// StopPodSandbox stops the sandbox. If there are any running containers in the
	// sandbox, they should be force terminated.
	StopPodSandbox(podSandboxID string) error
	// RemovePodSandbox removes the sandbox. If there are running containers in the
	// sandbox, they should be forcibly removed.
	RemovePodSandbox(podSandboxID string) error
	// PodSandboxStatus returns the Status of the PodSandbox.
	PodSandboxStatus(podSandboxID string) (*runtimeapi.PodSandboxStatus, error)
	// ListPodSandbox returns a list of Sandbox.
	ListPodSandbox(filter *runtimeapi.PodSandboxFilter) ([]*runtimeapi.PodSandbox, error)
	// PortForward prepares a streaming endpoint to forward ports from a PodSandbox, and returns the address.
	PortForward(*runtimeapi.PortForwardRequest) (*runtimeapi.PortForwardResponse, error)
}

// 4. ContainerStatsManager contains methods for retrieving the container
// statistics.
type ContainerStatsManager interface {
	// ContainerStats returns stats of the container. If the container does not
	// exist, the call returns an error.
	ContainerStats(containerID string) (*runtimeapi.ContainerStats, error)
	// ListContainerStats returns stats of all running containers.
	ListContainerStats(filter *runtimeapi.ContainerStatsFilter) ([]*runtimeapi.ContainerStats, error)
}           

複制

CNI接口源碼

type CNI interface {
   AddNetworkList(ctx context.Context, net *NetworkConfigList, rt *RuntimeConf) (types.Result, error)
   CheckNetworkList(ctx context.Context, net *NetworkConfigList, rt *RuntimeConf) error
   DelNetworkList(ctx context.Context, net *NetworkConfigList, rt *RuntimeConf) error
   GetNetworkListCachedResult(net *NetworkConfigList, rt *RuntimeConf) (types.Result, error)
   GetNetworkListCachedConfig(net *NetworkConfigList, rt *RuntimeConf) ([]byte, *RuntimeConf, error)

   AddNetwork(ctx context.Context, net *NetworkConfig, rt *RuntimeConf) (types.Result, error)
   CheckNetwork(ctx context.Context, net *NetworkConfig, rt *RuntimeConf) error
   DelNetwork(ctx context.Context, net *NetworkConfig, rt *RuntimeConf) error
   GetNetworkCachedResult(net *NetworkConfig, rt *RuntimeConf) (types.Result, error)
   GetNetworkCachedConfig(net *NetworkConfig, rt *RuntimeConf) ([]byte, *RuntimeConf, error)

   ValidateNetworkList(ctx context.Context, net *NetworkConfigList) ([]string, error)
   ValidateNetwork(ctx context.Context, net *NetworkConfig) ([]string, error)
}           

複制

k8s的可擴充性

k8s通過定義接口的方式，解耦了許多底層元件，極大的增強了k8s的可擴充性。

k8s的局限性

叢集管理

水準伸縮性

Kubernetes 社群對外宣傳的是單個叢集最多支援 5,000 節點，Pod 總數不超過 150,000，容器總數不超過 300,000 以及單節點 Pod 數量不超過 100 個3，與幾萬節點的 Apache Mesos 叢集、50,000 節點的微軟 YARN 叢集4相比，Kubernetes 的叢集規模整整差了一個數量級。雖然阿裡雲的工程師也通過優化 Kubernetes 的各個元件實作了 5 位數的叢集規模，但是與其他的資源管理方式相比卻有比較大的差距5。

多叢集管理

k8s的多叢集管理會帶來 資源不平衡、跨叢集通路困難等問題

現有的一些探索方案

kubefed

kubefed(Kubernetes Cluster Federation)是k8s社群給出的解決方案，提供了跨叢集資源和網絡管理的功能

應用場景

應用分發

Kubernetes 主項目提供了幾種部署應用的最基本方式，分别是

Deployment

、

StatefulSet

和

DaemonSet

，這些資源分别适用于無狀态服務、有狀态服務和節點上的守護程序，這些資源能夠提供最基本的政策，但是它們無法處理更加複雜的應用

很多常見的場景，例如隻運作一次的 DaemonSet11 以及金絲雀和藍綠部署等功能，現在的資源也存在很多問題，例如 StatefulSet 在初始化容器中卡住無法復原和更新12。

批處理排程

機器學習、批處理任務和流式任務等工作負載的運作從 Kubernetes 誕生第一天起到今天都不是它的強項，大多數的公司都會使用 Kubernetes 運作線上服務處理使用者請求，用 Yarn 管理的叢集運作批處理的負載。

硬多租戶

今天的 Kubernetes 還很難做到硬多租戶支援，也就是同一個叢集的多個租戶不會互相影響，也感覺不到彼此的存在。盡管目前k8s用命名空間來劃分虛拟叢集，但也很難實作。這裡是k8s社群相關的讨論小組位址

K8S的對比

排程算法的演進

1. 單階段

   使用一個單一的中心化排程器，排程所有資源，同時沒有并發，但是叢集規模過大時無法很好的處理。同時新增排程的規則變得十分困難，因為所有的使用者資源使用同樣的排程邏輯。

2. 兩階段排程

   增強了叢集的彈性，但是受到資源可見性和鎖的雙重限制，導緻很難排程挑剔的節點

3. 優化的兩階段排程

   使用共享狀态，進行樂觀的無鎖并發控制。Omega系統使用了該架構，增強了延展性和性能。

問題分類

對排程問題進行分類

資源選擇

互相幹擾

對資源進行排程時，如何解決并發沖突。

1.加鎖

2.回撤

配置設定粒度

叢集行為

集中排程

通過中央式排程器有且僅有一個執行個體，沒有并行，而且在一個單一的代碼庫，必須實作所有的政策選擇。這種方法常見于高性能計算（HPC），對于多種政策的支援有兩種方式：

1.通過複雜的計算，針對多個權重因子計算出整體的優先級

2.排程邏輯通過調用不同的代碼邏輯進行分離。谷歌之前采用的就是這種，雖然經過各種優化使得它有較好的性能和拓展性表現，但是最後決定将排程算法改進為支援并發、獨立排程元件的首要原因是出于軟體工程角度的考慮。

靜态分區排程

将資源分為不同的區，每個不同的區域采用不同的排程方式，區域之間互相隔離

兩層排程器

解決靜态分區排程器的一個顯而易見的方案是實作分區的動态化，這就是兩層排程器的工作原理，通過一個中心來對各個分區的資源進行協調配置設定，這種兩層排程被Mesos和Hadoop-on-Demand廣泛采用

mesos基于DRF政策和offer-based（主動提供）的方式由master向各個計算架構配置設定資源，并且提供了過濾器機制，計算架構可以事先描述自己需要的資源特征。該架構适用于短任務，并且存在一定的缺點：（1）offer-based的方式是悲觀鎖實作的，每次隻能給一個計算架構配置設定資源，導緻并發度低；（2）每次的配置設定都是基于目前狀況進行的，計算架構并不能感覺到系統的資源情況，是以配置設定不是全局最優的；（3）逐個計算架構進行配置設定導緻系統不能夠支援資源搶占；（4）當系統中被短任務填充時，會導緻長任務餓死；（5）資源保持可能會導緻死鎖現象的發生；

Yarn采用的是可能是一種兩層排程，但更多的是集中排程：

yarn是基于資源申請的方式進行資源配置設定的。AM向RM請求資源，RM基于NM的心跳觸發配置設定，按照一定的政策将資源配置設定給AM，AM與NM通信運作任務。目前的yarn還存在一些缺點：目前的AM隻負責進行任務管理并沒有提供排程的能力，這也是一部分人将YARN劃分為集中式排程器的原因；目前僅支援對記憶體的配置設定；雖然現在yarn支援AM在進行資源申請的時候選擇放置偏好點，但是并沒有說明這些偏好是根據什麼标準得到的。

共享狀态排程

針對兩層排程系統存在的并行性和不能進行全局最優的排程問題，共享狀态系統進行了優化。主要有兩點措施，第一存在多個排程器，每個排程器都擁有系統全量的資源資訊，可以根據該資訊進行排程。第二排程器将其排程的結果以原子的方式送出給cell state維護子產品，由其決定本次送出是否成功，這裡展現了樂觀并發的思想。

每個排程器會定期以私有的方式更新自己副本中的cell state；

每個排程器可以設定其私有得排程政策，有很大的自由度；

Omega隻是将優先級這一限制放到了共享資料的驗證代碼中，即當同時由多個應用程式申請同一份資源時，優先級最高的那個應用程式将獲得該資源，其他資源限制全部下放到各個子排程器。

對整個叢集中的所有資源分組，限制每類應用程式的資源使用量，限制每個使用者的資源使用量等，這些全部由各個應用程式排程器自我管理和控制。

引入多版本并發控制後，限制該機制性能的一個因素是資源通路沖突的次數，沖突次數越多，系統性能下降的越快，而google通過實際負載測試證明，這種方式的沖突次數是完全可以接受的。

Borg