Kubernetes Scheduler deep dive

1st handler: progrunner17.icon

2nd handler: musaprg.icon

1. そもそもKubernetes Schedulerとは

公式ドキュメント: Kubernetes Scheduler

新規作成された（Nodeに割り当てられてない）Podを探してきて、一番最適なNodeに割り当てる担当。

割り当て <=> Podのspec.nodeNameを更新する

デフォルトの実装が kube-scheduler

kube-apiserver, kube-controller-managerなどとは独立したコマンドとして実行される

kube-scheduler command reference

https://scrapbox.io/files/62ea16741e38290021bfd886.png

画像出典: Kubernetesの内部アーキテクチャについて整理してみた

2. kube-scheduler 概要

大まかな流れ

Podを１つずつスケジュールする

各Podにつき、NodeをFiltering & Scoringする

Filtering: PodをscheduleできないNodeを除外

Scoring: 各Nodeにスコアをつける

最大ScoreのNodeの中からランダムに割り当てる

出典: Kubernetes Scheduler

3. Scheduling Framework概要

Scheduling Framework + 各種Pluginという構成

各Pluginが実際にFiltering, Scoringを行う

デフォルトで有効化されているPlugin

例 NodeAffinity

node selectorや nodeaffinityの機能を実現している

Pluginはスケジューリングの各ステージで動作できる

Extension points という

https://scrapbox.io/files/62e9422c3a4b29001f3fe29b.png

In this picture "Filter" is equivalent to "Predicate" and "Scoring" is equivalent to "Priority function".

各pluginの有効・無効化、重みなども調整できる

Scheduler Configuration

musaprg.icon たぶんweightを設定できるのはscore pluginだけっぽい

自分でPluginを実装、利用したい場合はこんな感じ

4. kube-scheduler deep dive

v1.24.3のコード https://github.com/kubernetes/kubernetes/tree/v1.24.3

全てはここから始まるkube-schedulerのentrypoint

https://github.com/kubernetes/kubernetes/blob/v1.24.3/cmd/kube-scheduler/scheduler.go

先人 https://qiita.com/everpeace/items/601dc613a0f424fb5619

sanposhiho先生の記事 https://engineering.mercari.com/blog/entry/20211220-create-your-kube-scheduler/

（なんなら各自でこれ読めば十分という説がある）

musaprg.icon 雑に雰囲気だけ書き殴っておきました、あとはgotanda-sanがなんとかしてくれるはず！！！

何よりもまず公式ドキュメントhttps://kubernetes.io/docs/concepts/scheduling-eviction/kube-scheduler/

Scheduling

どのPodをどのNodeに割り当てるか決める処理

Binding

実際にNodeへPodを割り当てる処理

Pod Preemption

High PriorityなPodをスケジューリングするためにLow PriorityなPodをterminateする処理

Pod Eviction

Podをterminateする処理

Schedulingの手順

1. Filtering

Podの動作条件に合うNodeを絞り込む（逆に言えばPodの実行に適さないものを除外していく）

PodFitsResource: resource requestsで指定している分のリソースがあるNodeだけに絞る

https://github.dev/kubernetes/kubernetes/blob/aef86a93758dc3cb2c658dd9657ab4ad4afc21cb/pkg/scheduler/framework/plugins/noderesources/fit.go これ

もっというとここ https://github.dev/kubernetes/kubernetes/blob/aef86a93758dc3cb2c658dd9657ab4ad4afc21cb/pkg/scheduler/framework/plugins/noderesources/fit.go#L217-L235

1つも引っ掛からなかった場合はスケジュールされない

2. Scoring

残ったNodeをスコアリングして、一番高い点数のものに割り当てる

Scheduling Frameworkという仕組みで拡張が可能（v1.19以降でstable）

自前のPluginを組み込むにはkube-schedulerをcloneしてビルドし直す必要はある

extenderというWebhookベースのdynamic configurationの仕組みも存在するけど問題があるとスケジュールが止まってしまうのでちょっと微妙

https://github.com/kubernetes/enhancements/tree/master/keps/sig-scheduling/1819-scheduler-extender

にしてはドキュメントが見当たらない（単に見落としてるだけ？）

https://kubernetes.io/docs/concepts/scheduling-eviction/scheduling-framework/

Pluginのinterfaceはここにある

https://github.dev/kubernetes/kubernetes/blob/aef86a93758dc3cb2c658dd9657ab4ad4afc21cb/pkg/scheduler/framework/interface.go#L302-L492

plugins/以下にいくつか既存で用意されてる実装が存在する。

https://github.dev/kubernetes/kubernetes/blob/aef86a93758dc3cb2c658dd9657ab4ad4afc21cb/pkg/scheduler/framework

デフォで有効なものは以下 https://kubernetes.io/docs/reference/scheduling/config/#scheduling-plugins

ImageLocality: Favors nodes that already have the container images that the Pod runs. Extension points: score.

TaintToleration: Implements taints and tolerations. Implements extension points: filter, preScore, score.

NodeName: Checks if a Pod spec node name matches the current node. Extension points: filter.

NodePorts: Checks if a node has free ports for the requested Pod ports. Extension points: preFilter, filter.

NodeAffinity: Implements node selectors and node affinity. Extension points: filter, score.

PodTopologySpread: Implements Pod topology spread. Extension points: preFilter, filter, preScore, score.

NodeUnschedulable: Filters out nodes that have .spec.unschedulable set to true. Extension points: filter.

NodeResourcesFit: Checks if the node has all the resources that the Pod is requesting. The score can use one of three strategies: LeastAllocated (default), MostAllocated and RequestedToCapacityRatio. Extension points: preFilter, filter, score.

NodeResourcesBalancedAllocation: Favors nodes that would obtain a more balanced resource usage if the Pod is scheduled there. Extension points: score.

VolumeBinding: Checks if the node has or if it can bind the requested volumes. Extension points: preFilter, filter, reserve, preBind, score.

VolumeRestrictions: Checks that volumes mounted in the node satisfy restrictions that are specific to the volume provider. Extension points: filter.

VolumeZone: Checks that volumes requested satisfy any zone requirements they might have. Extension points: filter.

NodeVolumeLimits: Checks that CSI volume limits can be satisfied for the node. Extension points: filter.

EBSLimits: Checks that AWS EBS volume limits can be satisfied for the node. Extension points: filter.

GCEPDLimits: Checks that GCP-PD volume limits can be satisfied for the node. Extension points: filter.

AzureDiskLimits: Checks that Azure disk volume limits can be satisfied for the node. Extension points: filter.

InterPodAffinity: Implements inter-Pod affinity and anti-affinity. Extension points: preFilter, filter, preScore, score.

PrioritySort: Provides the default priority based sorting. Extension points: queueSort.

DefaultBinder: Provides the default binding mechanism. Extension points: bind.

DefaultPreemption: Provides the default preemption mechanism. Extension points: postFilter.

Pluginのconfigurationは kube-scheduler --config scheduler-config.yaml みたいな感じで渡す

extension points(PreFilterとかScoreとか)ごとに、どのPluginを有効/無効にするか、みたいに設定できる。

Podの.spec.schedulerNameでschedulerを指定できるが、そのschedulerの設定も複数ここで設定する

scoreのpluginについてはweightを設定できる。

（musaprg.icon これが実際にどう使われてるのかよくわからない）

以下の図は、より細かく一連の処理を図解したもの。

PreFilter/PreScoreは、Filter/Scoreで使用する指標等の計算を行い、CycleStateへ書き込む。

Filter/ScoreはCycleState経由で事前計算された指標を読み込んで処理を行う。

https://github.dev/kubernetes/kubernetes/blob/aef86a93758dc3cb2c658dd9657ab4ad4afc21cb/pkg/scheduler/framework/plugins/noderesources/fit.go#L178-L182

PostFilterはスケジュールできなかったPodに対してかかるやつ。

Reserve（実装されてるmethodにはReserve/Unreserveの2つがある）はPodがNodeにBindされる前にあらかじめ諸々確保しておくやつ。

基本的にはBindされるまでの間でrace conditionが発生しないようにするため。

volume_binding.goがいっちゃんわかりやすいかも？

musaprg.icon このへんgotanda-sanのほうが詳しい気がする

FilterでひっかけたPV・PVCを先にassumeする

https://github.dev/kubernetes/kubernetes/blob/aef86a93758dc3cb2c658dd9657ab4ad4afc21cb/pkg/scheduler/framework/plugins/volumebinding/volume_binding.go#L295-L314

内部でvolumeBinder.AssumePodVolumesを呼ぶ

https://github.dev/kubernetes/kubernetes/blob/aef86a93758dc3cb2c658dd9657ab4ad4afc21cb/pkg/scheduler/framework/plugins/volumebinding/binder.go#L364-L425

i. If PVC binding is required, cache in-memory only:

* For manual binding: update PV objects for prebinding to the corresponding PVCs.

* For dynamic provisioning: update PVC object with a selected node from score phase)

* For the pod, which PVCs and PVs need API updates.

ii. Afterwards, the main scheduler caches the Pod->Node binding in the scheduler's pod cache. This is handled in the scheduler.

https://scrapbox.io/files/62e9422c3a4b29001f3fe29b.png

https://kubernetes.io/docs/concepts/scheduling-eviction/scheduling-framework/#extension-points

https://github.com/musaprg/kubernetes/blob/aef86a93758dc3cb2c658dd9657ab4ad4afc21cb/cmd/kube-scheduler/app/server.go#L327-L345 色々詰めてschedulerのオブジェクトを作成

https://github.dev/musaprg/kubernetes/blob/aef86a93758dc3cb2c658dd9657ab4ad4afc21cb/pkg/scheduler/scheduler.go#L234-L235 scheduler.Newはここ

Schedulerのstructはこれ https://github.dev/musaprg/kubernetes/blob/aef86a93758dc3cb2c658dd9657ab4ad4afc21cb/pkg/scheduler/scheduler.go#L64-L103

内部にqueueがあって、そこにscheduleをまつPodがenqueueされていく。

/icons/hr.icon

musaprg.icon なんかpluginの実装どれか読んでみるか〜〜〜やっていきという気持ちになり、完

/icons/hr.icon

メモ

exntension point間でのデータのやり取りは CycleState を使う

KVS

Extender

Extender is an interface for external processes to influence scheduling decisions made by Kubernetes. This is typically needed for resources not directly managed by Kubernetes.

https://github.com/kubernetes/kubernetes/blob/v1.24.3/pkg/scheduler/framework/extender.go

実装はHTTPExtenderぐらい

https://github.com/kubernetes/kubernetes/blob/v1.24.3/pkg/scheduler/extender.go

musaprg.icon https://github.com/kubernetes/enhancements/tree/master/keps/sig-scheduling/1819-scheduler-extender

各stage/extention pointについて

QueueSort

podのschedule順序を決める

比較関数を提供するといい感じにpriority queue でソートしてくれる

デフォルト

code:go

p1 := corev1helpers.PodPriority(pInfo1.Pod)

p2 := corev1helpers.PodPriority(pInfo2.Pod)

return (p1 > p2) || (p1 == p2 && pInfo1.Timestamp.Before(pInfo2.Timestamp))↲

https://github.com/kubernetes/kubernetes/blob/master/pkg/scheduler/framework/plugins/queuesort/priority_sort.go

PreFilter

https://pkg.go.dev/k8s.io/kubernetes/pkg/scheduler/framework#PreFilterPlugin

https://kubernetes.io/docs/concepts/scheduling-eviction/scheduling-framework/#pre-filter

These plugins are used to pre-process info about the Pod, or to check certain conditions that the cluster or the Pod must meet. If a PreFilter plugin returns an error, the scheduling cycle is aborted.

proelbtn.icon Nodeを見なくても落とせるような要件ならPreFilterでやるのがいいっぽい？https://github.com/kubernetes/kubernetes/issues/91904

kanata.icon Filter の計算では node の数だけ goroutine を立てるので、その必要のない filter 条件は PreFilter 使ったほうがいいよねという話っぽい

Filter

https://pkg.go.dev/k8s.io/kubernetes/pkg/scheduler/framework#FilterPlugin

https://kubernetes.io/docs/concepts/scheduling-eviction/scheduling-framework/#filter

設定順に呼ばれる

１つでもダメならfilter outされる

PostFilter

https://pkg.go.dev/k8s.io/kubernetes/pkg/scheduler/framework#PostFilterPlugin

https://kubernetes.io/docs/concepts/scheduling-eviction/scheduling-framework/#post-filter

全てのnodeがスケジュール不能な時に呼ばれる

Preemptionが典型例