Kubernetes: スケジューラの動作

Kubernetes で Pod をノードに割り当てるスケジューラ [kube-scheduler](https://kubernetes.io/docs/reference/generated/kube-scheduler/) の動作についてまとめてみました。動作の検証やソースコードの参照は [kubernetes v1.9.2](https://github.com/kubernetes/kubernetes/tree/v1.9.2) のものを使っています[^1]。

[^1]: 記載時点の直近にソースコードの移動 [plugin/pkg/scheduler -> pkg/scheduler](https://github.com/kubernetes/kubernetes/pull/57852) があったので、将来のバージョンではディレクトリが異なっていると思われます。

# スケジューラのお仕事

Kubernetes のスケジューラの仕事は、新規に Pod が作成されたときに最適なノードを選択して割り当てることです。スケジューラで重要なのは最適なノードをどう選択をするかで、様々なフィルタと優先度付けが実装されています。

スケジューラは [kube-scheduler](https://kubernetes.io/docs/reference/generated/kube-scheduler/) という独立したバイナリになっています。[Policy ファイルにより柔軟なカスタマイズ](https://github.com/kubernetes/kubernetes/blob/v1.9.2/examples/scheduler-policy-config-with-extender.json)が可能で、フィルタや優先度付けの選択や、優先度の重み付け、WebHook による拡張などが可能です。

大雑把な動作は以下のようになります。

- 新規 Pod が作成される
  - スケジューラは API サーバー を監視(watch) してこのイベントを検知します
- スケジューラが最適なノードを選択してノードに割り当てる
  - Pod の `.spec.NodeName` にノード名が設定されます
- ノード上の kubelet が自ノードへ割り当てられた Pod を検知して作成します

<img src="https://qiita-image-store.s3.amazonaws.com/0/100377/1f1e9838-cfb0-73ce-a3ab-2e5b0bf13c87.png" width="600">


# 処理の流れ

スケジューラは起動後にリーダー選出(`--leader-elect` を指定した場合) や Pod の監視 (非同期) などの準備を行った後、[Scheduler.scheduleOne()](https://github.com/kubernetes/kubernetes/blob/v1.9.2/plugin/pkg/scheduler/scheduler.go#L430) というメソッドをメインループとして呼び出します。

ソースコード: [main()](https://github.com/kubernetes/kubernetes/blob/v1.9.2/plugin/cmd/kube-scheduler/scheduler.go#L32) -> [Options.Run()](https://github.com/kubernetes/kubernetes/blob/v1.9.2/plugin/cmd/kube-scheduler/app/server.go#L292:19)-> [SchedulerServer.Run()](https://github.com/kubernetes/kubernetes/blob/v1.9.2/plugin/cmd/kube-scheduler/app/server.go#L549:10) -> [Scheduler.Run()](https://github.com/kubernetes/kubernetes/blob/v1.9.2/plugin/pkg/scheduler/scheduler.go#L170:25) -> [Scheduler.scheduleOne()](https://github.com/kubernetes/kubernetes/blob/v1.9.2/plugin/pkg/scheduler/scheduler.go#L430)


```go:scheduler.go
// Scheduler.Run() のメインループの設定
func (sched *Scheduler) Run() {
    // ... 省略
    // StopEverything チャネルが閉じられるまで shced.ScheduleOne を繰り返す
    go wait.Until(sched.scheduleOne, 0, sched.config.StopEverything)
```

[Scheduler. scheduleOne()](https://github.com/kubernetes/kubernetes/blob/v1.9.2/plugin/pkg/scheduler/scheduler.go#L430) では下記のように一つずつ未割り当ての Pod をキューから取り出して最適なノードに対して紐付けを行っていきます。割り当てる Pod がない場合はキューから取り出す [NextPod()](https://github.com/kubernetes/kubernetes/blob/v1.9.2/plugin/pkg/scheduler/scheduler.go#L431) でブロックされます。Pod のキューへの追加は InformerFramework を利用して Pod の変更を検知し非同期に行われます(参考: [podInformer の イベントハンドラ](https://github.com/kubernetes/kubernetes/blob/v1.9.2/plugin/pkg/scheduler/factory/factory.go#L215))。

**

<img src="https://qiita-image-store.s3.amazonaws.com/0/100377/d46b1c1f-a68c-18ef-f67d-b7ff7918077d.png" width="800">


# 最適なノードの選択

Pod に対しての最適なノードの選択は、下記の図のように **predicates** と呼ばれる条件によるノードのフィルタと、 **priorities** という優先度付けによって行われます。[Policy ファイルにより柔軟にカスタマイズ](https://github.com/kubernetes/kubernetes/blob/v1.9.2/examples/scheduler-policy-config-with-extender.json)が可能です。

- **predicates**: ノードをフィルタする条件。例えば nodeSelector によるノードの選択やrequest に対するリソースの空き状況によるフィルタがある
- **priorities**: ノードの優先度付け。例えば Pod を出来る限りノード、ゾーンを分散させるような優先度付けがある。

なお、[Pod / Node Affinity](https://kubernetes.io/docs/concepts/configuration/assign-pod-node/) のように、必須 (`requiredDuringSchedulingIgnoredDuringExecution`)、
 と優先(`preferredDuringSchedulingIgnoredDuringExecution`)の両方があるものは、predicates, priorities の両方で実装されています。

ソースコード: [Scheduler.scheduleOne()](https://github.com/kubernetes/kubernetes/blob/v1.9.2/plugin/pkg/scheduler/scheduler.go#L430) -> [Scheduler.schedule()](https://github.com/kubernetes/kubernetes/blob/v1.9.2/plugin/pkg/scheduler/scheduler.go#L188:25) -> [genericScheduler.Schedule()](https://github.com/kubernetes/kubernetes/blob/v1.9.2/plugin/pkg/scheduler/core/generic_scheduler.go#L109)

<img src="https://qiita-image-store.s3.amazonaws.com/0/100377/a8b4aca7-6d48-f5a4-038b-af4d6d3f1afd.png" width="900">

## Predicates (ノードのフィルタ)

Predicates はノードをフィルタする条件です。各 Predicate の処理はそのノードが条件を満たすかを bool で返す、下記の `FitPredicate` インタフェースを実装した関数となります。高速化のため [predicate のフィルタはノードごとに並列に評価されます。](https://github.com/kubernetes/kubernetes/blob/v1.9.2/plugin/pkg/scheduler/core/generic_scheduler.go#L320)

```go
// FitPredicate is a function that indicates if a pod fits into an existing node.
// The failure information is given by the error.
type FitPredicate func(pod *v1.Pod, meta PredicateMetadata, nodeInfo *schedulercache.NodeInfo) (bool, []PredicateFailureReason, error)
```

- ソースコード(全体処理): [genericScheduler.Schedule()](https://github.com/kubernetes/kubernetes/blob/v1.9.2/plugin/pkg/scheduler/core/generic_scheduler.go#L109) -> [findNodesThatFit()](https://github.com/kubernetes/kubernetes/blob/v1.9.2/plugin/pkg/scheduler/core/generic_scheduler.go#L278)
- ソースコード(各 Predicate): [predicates.go](https://github.com/kubernetes/kubernetes/blob/v1.9.2/plugin/pkg/scheduler/algorithm/predicates/predicates.go)(定義), [defaults.go](https://github.com/kubernetes/kubernetes/blob/v1.9.2/plugin/pkg/scheduler/algorithmprovider/defaults/defaults.go)(登録)


Predicates | 説明
--- | ---
`PodFitsResources` | ノードの空きリソースがPod の要求するリソースの request 値に合うか。参考: [How Pods with resource requests are scheduled](https://kubernetes.io/docs/concepts/configuration/manage-compute-resources-container/#how-pods-with-resource-requests-are-scheduled)
`PodFitsHostPorts` | Pod が hostPort を利用する場合に、ノードのポートが空いているか
`HostName` | PodSpec の `nodeName` の指定が合った場合、ノードのホスト名と一致するか
`MatchNodeSelector` | [nodeSelector](https://kubernetes.io/docs/concepts/configuration/assign-pod-node/#nodeselector) で指定したラベルとノードが合うか
`NoDiskConflict` | Pod がマウントするディスクが既に他でマウントされていないかチェックする
`NoVolumeZoneConflict` | Pod が要求するボリュームが同じゾーン内にあるか
`MatchInterPodAffinityPred` | [Pod 間の affinity](https://kubernetes.io/docs/concepts/configuration/assign-pod-node/#inter-pod-affinity-and-anti-affinity-beta-feature) に合っているかチェックする
`CheckNodeMemoryPressure` | メモリの空き容量が逼迫している場合そのノードを避ける (NodeCondition の MemoryPressure を見ている)
`CheckNodeDiskPressure` | ディスクの空き容量が逼迫している場合そのノードを避ける (NodeCondition の DiskPressure を見ている)
`MaxGCEPDVolumeCount`, `MaxAzureDiskVolumeCount`, `MaxEBSVolumeCount` | 各 Persistent Volume のアタッチ数制限のチェック


## Priorities (ノードの優先度付け)

Priorities はノードの優先度を付ける処理です。各 Priorities の処理はノードに対して 0 ~ 10 の優先度を設定します。各 Priorities には重み付けが設定でき、全ての Priorities の処理が終わると下記のように Node のスコアが計算されます。

```
NodeA のスコア = (prioritiesA のスコア * 重み付け) + (prioritiesB のスコア * 重み付け) ....
```

Priorities も高速化のため[ノードごとに並列に評価されます](https://github.com/kubernetes/kubernetes/blob/v1.9.2/plugin/pkg/scheduler/core/generic_scheduler.go#L559)。Predicates と違って、ノードごとに独立して計算できないものもあるため、下記のように Map / Reduce の２つの関数で構成されています。(参考: [Change interface of priority functions for easier "framework-based" parallelization #24246](https://github.com/kubernetes/kubernetes/issues/24246))

```go
// PriorityMapFunction is a function that computes per-node results for a given node.
// TODO: Figure out the exact API of this method.
// TODO: Change interface{} to a specific type.
type PriorityMapFunction func(pod *v1.Pod, meta interface{}, nodeInfo *schedulercache.NodeInfo) (schedulerapi.HostPriority, error)

// PriorityReduceFunction is a function that aggregated per-node results and computes
// final scores for all nodes.
// TODO: Figure out the exact API of this method.
// TODO: Change interface{} to a specific type.
type PriorityReduceFunction func(pod *v1.Pod, meta interface{}, nodeNameToInfo map[string]*schedulercache.NodeInfo, result schedulerapi.HostPriorityList) error
```

- ソースコード (全体処理): [genericScheduler.Schedule()](https://github.com/kubernetes/kubernetes/blob/v1.9.2/plugin/pkg/scheduler/core/generic_scheduler.go#L109) -> [PrioritizeNodes()](https://github.com/kubernetes/kubernetes/blob/v1.9.2/plugin/pkg/scheduler/core/generic_scheduler.go#L494:6)
- ソースコード (各 Priority): [scheduler/algorithm/priorities/](https://github.com/kubernetes/kubernetes/tree/v1.9.2/plugin/pkg/scheduler/algorithm/priorities)(定義), [defaults.go](https://github.com/kubernetes/kubernetes/blob/v1.9.2/plugin/pkg/scheduler/algorithmprovider/defaults/defaults.go)(登録)

重み付けのデフォルトは `NodePreferAvoidPodsPriority` を除いて全て 1 です。

Priority | 説明
--- | ---
`SelectorSpreadPriority` | 同じ種類の Pod が出来る限りノードやゾーンに対して分散するようにする
`InterPodAffinityPriority` | [Pod 間の affinity](https://kubernetes.io/docs/concepts/configuration/assign-pod-node/#inter-pod-affinity-and-anti-affinity-beta-feature) に合っているかチェックする
`LeastRequestedPriority` | リソースの request 値の合計が少ないノードを優先する
`BalancedResourceAllocation` | CPU とメモリの使用率のバランスを取る
`NodePreferAvoidPodsPriority` | `preferAvoidPods` という Node のアノテーションの考慮。他に優先されるよう、これだけ[優先度が 10000 に設定](https://github.com/kubernetes/kubernetes/blob/v1.9.2/plugin/pkg/scheduler/algorithmprovider/defaults/defaults.go#L247-L249)されています。
`NodeAffinityPriority` | [Node Affinity](https://kubernetes.io/docs/concepts/configuration/assign-pod-node/#node-affinity-beta-feature) による優先度
`TaintTolerationPriority` | [Taint](https://kubernetes.io/docs/concepts/configuration/taint-and-toleration/) の `PreferNoSchedule` の考慮

# まとめ

Kubernetes のスケジューラは、様々なフィルタ (predicates) と優先度 (priorities) を使って Pod を最適なノードに割り当てます。ノードやゾーンに対して Pod を分散させる `SelectorSpreadPriority` のように、耐障害性について重要な優先度もあるので興味があればスケジューラのソースコードを覗いてみてください。


# 参考
- https://github.com/kubernetes/community/blob/master/contributors/devel/scheduler.md
- https://github.com/kubernetes/community/blob/master/contributors/devel/scheduler_algorithm.md