kube-schedulerのソースコードを読みながらPodがNodeにBindされるまでを理解する

`kube-scheduler` は Kubernetesにおけるデフォルトスケジューラで、 `Pod` を `Node` に `Bind` する責務(+α)を担っています。

この文章は、(`kube-scheduler`)のソースコード(`v1.13.3`)を読み進めながら、「`Pod`がどのような処理を経て`Node`に`Bind`されるか」を理解する手助けすることを目的として書かれました。

また、[_2019-02-05 Kubernetes 読書会 #4_](https://www.wantedly.com/projects/276741)の資料としても用られました。

`kube-scheduler`の[エントリーポイント(`cmd/kube-scheduler/scheduler.go`)](https://sourcegraph.com/github.com/kubernetes/kubernetes@v1.13.3/-/tree/cmd/kube-scheduler)から順に読んでいくスタイルで解説しています。

# ソースコードをいきなり読む前に
この文章では図をつかったわかりやすい解説ができていません。これまでに、自分でソースコードを読み解いて、解説スライド・記事を作ってくださっている方がいますので、そちらをまず読むと、大まかな流れがつかめて、理解が大変進みやすいです。

- [Kubernetes: スケジューラの動作](https://qiita.com/tkusumi/items/58fdadbe4053812cb44e)
- [猫でもわかる Pod Preemption](https://speakerdeck.com/ytaka23/kubernetes-meetup-tokyo-10th)
- [schedulerとdevice-pluginをカスタムして機械学習ジョブクラスタを作っている話](https://www.slideshare.net/pfi/kubernetes-meetuptokyo13customizingkubernetesformlcluster)
- [The Kubernetes Scheduler](https://medium.com/@dominik.tornow/the-kubernetes-scheduler-cd429abac02f) 
    - kube-schedulerの仕様を TLA+ を使って書き下し&解説しています
- ちょっと範囲が広いですが[What happens when ... Kubernetes edition!](https://github.com/jamiehannaford/what-happens-when-k8s)
    - `kubectl run ...` と打ってから何が起きるかを一気通貫で概要を説明してくれています

# 対象ソースコード

- [kubernetes/kubernetes at v1.13.3 - Github](https://github.com/kubernetes/kubernetes/tree/v1.13.3)
  - [Sourcegraph extension](https://chrome.google.com/webstore/detail/sourcegraph/dgjhfomjieaadpoljlnidmbgkdffpack) を入れておくと読みやすいです
- [kubernetes/kubernetes - Sourcegraph](https://sourcegraph.com/github.com/kubernetes/kubernetes@v1.13.3) (こちら直接でも可)　

# パッケージ構造

CLIコマンドと、スケジューラ自身のロジックはパッケージが別れています。

## [`cmd/kube-scheduler`](https://sourcegraph.com/github.com/kubernetes/kubernetes@v1.13.3/-/tree/cmd/kube-scheduler)

CLIに関するの実装の[パッケージ](https://sourcegraph.com/github.com/kubernetes/kubernetes@v1.13.3/-/tree/cmd/kube-scheduler)です。

```

├── app             # CLI実装のほぼ全てはappパッケージ
│   ├── config      # scheduler本体へ渡すconfigオブジェクト用
│   ├── options     # kube-schedulerのcommand line flags/option用
│   └── server.go   # cliの処理本体, flag -> configへの変換(default値の補完含), scheduler本体の起動
└── scheduler.go    # kube-schedulerのエントリポイント
```

## [`pkg/scheduler`](https://sourcegraph.com/github.com/kubernetes/kubernetes@v1.13.3/-/tree/pkg/scheduler)

scheduler本体のコードが入っている[パッケージ](https://sourcegraph.com/github.com/kubernetes/kubernetes@v1.13.3/-/tree/pkg/scheduler)です。

```
├── algorithm             # Algorithm(predicates, prioritiesを組み合わせてSchedule(),Preempt()する)インターフェース関連
|                         #   predicatesやpriorityもこのパッケージで定義される. extenderのインターフェースもここで定義される.
|
├── algorithmprovider     # predicates, prioritiesの組を提供するAlgorithmProviderの初期化/定義
|
├── api                   # schedulerが外部に提供している api (types)
|
├── apis                  # いわゆるComponent Config用(kube-scheduler用のConfig type)
|
├── cache                 # kubernetes apiに負荷をかけないために、schedulerは常にキャッシュとやり取りするが、
|                         # そのキャッシュ内に格納されるデータ群の定義
|
├── core                  # Algorithm, Extenderインターフェースの実装用のパッケージ
|
├── factory               # Config Factory, そのFactoryからConfigを生成するロジック(DIっぽい)用
|
├── internal              # kube-scheduler内部用のパッケージ
|                         #   scheduleing queue, cache自体の実装
|
├── scheduler.go          # kube-scheduler本体(スケジューリングループ含む)
|
└── volumebinder          # 名前の通りvolumebinder. pkg/controller/volume/persistentvolume/SchedulerBinderのwrapper
```


# [cmd/kube-scheduler](https://sourcegraph.com/github.com/kubernetes/kubernetes@v1.13.3/-/tree/cmd/kube-scheduler) のブート処理

さて、まずは `kube-scheduler` コマンドがどう実行されるかから始めていきましょう。

- [cmd/kube-scheduler/app](https://sourcegraph.com/github.com/kubernetes/kubernetes@v1.13.3/-/blob/cmd/kube-scheduler/app) ディレクトリがほぼ全てです
- [app.NewSchedulerCommand()](https://sourcegraph.com/github.com/kubernetes/kubernetes@v1.13.3/-/blob/cmd/kube-scheduler/app/server.go#L70)が `cobra.Command` 本体を作る
- [app.runCommand()](https://sourcegraph.com/github.com/kubernetes/kubernetes@v1.13.3/-/blob/cmd/kube-scheduler/app/server.go#L117:6) で command line flags から [`schedulerserverconfig.CompletedConfig`](https://sourcegraph.com/github.com/kubernetes/kubernetes@v1.13.3/-/blob/cmd/kube-scheduler/app/config/config.go#L32-64) が作られて[app.Run()](https://sourcegraph.com/github.com/kubernetes/kubernetes@v1.13.3/-/blob/cmd/kube-scheduler/app/server.go#L167)が呼ばれる。
  - [`schedulerserverconfig.CompletedConfig`](https://sourcegraph.com/github.com/kubernetes/kubernetes@v1.13.3/-/blob/cmd/kube-scheduler/app/config/config.go#L32-64) に [`ComponentConfig`](https://sourcegraph.com/github.com/kubernetes/kubernetes@v1.13.3/-/blob/pkg/scheduler/apis/config/types.go#L43)が含まれている
  - kube-schedulerの挙動を変えるための[`SchedulerAlgorithmSource`](https://sourcegraph.com/github.com/kubernetes/kubernetes@v1.13.3/-/blob/pkg/scheduler/apis/config/types.go#L97-102)もここに含まれる
    - サンプルのyamlは[こちら](https://github.com/everpeace/k8s-scheduler-extender-example/blob/master/extender.yaml#L7-L19), Policyのサンプルは[こちら](https://github.com/everpeace/k8s-scheduler-extender-example/blob/master/extender.yaml#L27-L55)
- [app.Run()](https://sourcegraph.com/github.com/kubernetes/kubernetes@v1.13.3/-/blob/cmd/kube-scheduler/app/server.go#L167)の中で様々な `informer`, `informerFactory`が初期化される
- [`pkg.scheduler.New()`](https://sourcegraph.com/github.com/kubernetes/kubernetes@v1.13.3/-/blob/pkg/scheduler/scheduler.go#L131:6) が[呼ばれて]((https://sourcegraph.com/github.com/kubernetes/kubernetes@v1.13.3/-/blob/cmd/kube-scheduler/app/server.go#L174-193))、[`pkg.scheduler.Scheduler`](https://sourcegraph.com/github.com/kubernetes/kubernetes@v1.13.3/-/blob/pkg/scheduler/scheduler.go#L58:6) が作られる(以降明記が無い限り単に`Scheduler`と表記)
- その最後に[LeaderElection](https://sourcegraph.com/github.com/kubernetes/kubernetes@v1.13.3/-/blob/cmd/kube-scheduler/app/server.go#L257-272)及び[`Scheduler.Run()`](https://sourcegraph.com/github.com/kubernetes/kubernetes@v1.13.3/-/blob/pkg/scheduler/scheduler.go#L276-282)が[呼ばれる事によって](https://sourcegraph.com/github.com/kubernetes/kubernetes@v1.13.3/-/blob/cmd/kube-scheduler/app/server.go#L256-275)スケジューラーループが起動します
  - `scheduler.Config`(下記参照)内の`scheduler.Config.StopEverything` channelからシグナルを受けるまで動き続けます

# `Scheduler` インスタンスの初期化

- 初期化は [`pkg.scheduler.New()`](https://sourcegraph.com/github.com/kubernetes/kubernetes@v1.13.3/-/blob/pkg/scheduler/scheduler.go#L131:6)で行われる
- `Scheduler`インスタンスを初期化するための設定は3ステップ

## 1. [`scheduler.factory.configFactory`](https://sourcegraph.com/github.com/kubernetes/kubernetes@v1.13.3/-/blob/pkg/scheduler/factory/factory.go#L178-239)を作る

- [`scheduler.factory.NewConfigFactory()`](https://sourcegraph.com/github.com/kubernetes/kubernetes@v1.13.3/-/blob/pkg/scheduler/factory/factory.go#L265)を[呼んで](https://sourcegraph.com/github.com/kubernetes/kubernetes@v1.13.3/-/blob/pkg/scheduler/scheduler.go#L153)、[`scheduler.factory.configFactory`](https://sourcegraph.com/github.com/kubernetes/kubernetes@v1.13.3/-/blob/pkg/scheduler/factory/factory.go#L178-239)を作る
- [`scheduler.factory.configFactory`](https://sourcegraph.com/github.com/kubernetes/kubernetes@v1.13.3/-/blob/pkg/scheduler/factory/factory.go#L178-239)は[`Configurator`](https://sourcegraph.com/github.com/kubernetes/kubernetes@v1.13.3/-/blob/pkg/scheduler/factory/factory.go#L152-176) interfaceを実装している(主に[`scheduler.Config`](https://github.com/everpeace/k8s-scheduler-extender-example/blob/master/extender.yaml#L27-L55)(これが実質の`Scheduler`の入力)を生成する責務)
- この [`scheduler.factory.NewConfigFactory()`](https://sourcegraph.com/github.com/kubernetes/kubernetes@v1.13.3/-/blob/pkg/scheduler/factory/factory.go#L265) の中で多くの初期化作業が行われる
  - [scheduler queueの初期化](https://sourcegraph.com/github.com/kubernetes/kubernetes@v1.13.3/-/blob/pkg/scheduler/factory/factory.go#L280)
    - [各種Informerへの各種イベントハンドラの登録](https://sourcegraph.com/github.com/kubernetes/kubernetes@v1.13.3/-/blob/pkg/scheduler/factory/factory.go#L300-406)(スケジューラ内のキャッシュ, scheduling queueの呼び出しをたくさん登録)
  - [debuggerのactivate](https://sourcegraph.com/github.com/kubernetes/kubernetes@v1.13.3/-/blob/pkg/scheduler/factory/factory.go#L408-414): `SIGUSR2`シグナルによって、kube-scheduler内のnode cache, scheduling queuのダンプ、scheduler内のcacheと実際の比較結果のダンプ(logに出力)ができる

## 2. 指定された[AlgorithmSource](https://sourcegraph.com/github.com/kubernetes/kubernetes@v1.13.3/-/blob/pkg/scheduler/apis/config/types.go#L97-102)によって[`scheduler.Config`](https://github.com/everpeace/k8s-scheduler-extender-example/blob/master/extender.yaml#L27-L55)(これが実質の`Scheduler`の入力)を[作る](https://sourcegraph.com/github.com/kubernetes/kubernetes@v1.13.3/-/blob/pkg/scheduler/scheduler.go#L174-202)

- `AlgorithmProvider`の場合: [`configFactory.CreateFromProvider()`](https://sourcegraph.com/github.com/kubernetes/kubernetes@v1.13.3/-/blob/pkg/scheduler/factory/factory.go#L1156)で作られる (Providerの初期化と中身は下参照) 参照
- `Policy from File or ConfigMap`の場合: [`initPolicyFromFile()`](https://sourcegraph.com/github.com/kubernetes/kubernetes@v1.13.3/-/blob/pkg/scheduler/scheduler.go#L213:6) or [`initPolicyFromConfigMap()`](https://sourcegraph.com/github.com/kubernetes/kubernetes@v1.13.3/-/blob/pkg/scheduler/scheduler.go#L231:1)で`Policy`が作られた後[CreateFromConfig()](https://sourcegraph.com/github.com/kubernetes/kubernetes@v1.13.3/-/blob/pkg/scheduler/factory/factory.go#L1166)で作られる
- `scheduler.Config`内には、スケジューラのメインループから呼ばれる主要な挙動(podをbindするnodeを探す、preemption時のvictimを探す等は[`Algorithm`](https://sourcegraph.com/github.com/kubernetes/kubernetes@v1.13.3/-/blob/pkg/scheduler/algorithm/scheduler_interface.go#L78:6)でinterface化されていて、
- kube-schedulerでは [`GenericScheduler`](https://sourcegraph.com/github.com/kubernetes/kubernetes@v1.13.3/-/blob/pkg/scheduler/core/generic_scheduler.go#L1152:6) のみが実装していて`GenericScheduler` は `CreateFromConfig()` -> [`CreateFromKeys()`内で作られる](https://sourcegraph.com/github.com/kubernetes/kubernetes@v1.13.3/-/blob/pkg/scheduler/factory/factory.go#L1288-1303)
- この `scheduler.Config`に多くのロジックを持ったコンポーネントがDIされており、[`factory.go`](https://sourcegraph.com/github.com/kubernetes/kubernetes@v1.13.3/-/blob/pkg/scheduler/factory/factory.go)に多くのロジックが記述されていて少し読みにくい原因になっている

## 3. `Scheduler` instanceを[生成する](https://sourcegraph.com/github.com/kubernetes/kubernetes@v1.13.3/-/blob/pkg/scheduler/scheduler.go#L208)
- 作られた`scheduler.Config` から `Scheduler` instanceを[生成する](https://sourcegraph.com/github.com/kubernetes/kubernetes@v1.13.3/-/blob/pkg/scheduler/scheduler.go#L208)

## Algorithm Providerの初期化
- [pkg/scheduler/algorithmprovider](https://sourcegraph.com/github.com/kubernetes/kubernetes@v1.13.3/-/tree/pkg/scheduler/algorithmprovider) packageで定義
- [Algorithm Provider は `predicate`の集合、`priority`の集合で定義される](https://sourcegraph.com/github.com/kubernetes/kubernetes@v1.13.3/-/blob/pkg/scheduler/factory/plugins.go#L387)(双方ともに名前で指定するため, predefined(in-tree)なものしか指定できない)
  - [predefined predicate](https://sourcegraph.com/github.com/kubernetes/kubernetes@v1.13.3/-/tree/pkg/scheduler/algorithm/predicates)
  - [predefined priorities](https://sourcegraph.com/github.com/kubernetes/kubernetes@v1.13.3/-/tree/pkg/scheduler/algorithm/priorities)
- [defaults.init()](https://sourcegraph.com/github.com/kubernetes/kubernetes@v1.13.3/-/blob/pkg/scheduler/algorithmprovider/defaults/defaults.go#L38)内で [registerAlgorithmProvider(defaultPredicates(), defaultPriorities())](https://sourcegraph.com/github.com/kubernetes/kubernetes@v1.13.3/-/blob/pkg/scheduler/algorithmprovider/defaults/defaults.go#L222:6)が呼ばれて`"DefaultProvider"` と `"ClusterAutoscalerProvider"`が作られる
- "DefaultProvider": 
  - predicates = [`defaultPredicates()`](https://sourcegraph.com/github.com/kubernetes/kubernetes@v1.13.3/-/blob/pkg/scheduler/algorithmprovider/defaults/defaults.go#L106:6) 
  - priorities = [`defaultPriority()`](https://sourcegraph.com/github.com/kubernetes/kubernetes@v1.13.3/-/blob/pkg/scheduler/algorithmprovider/defaults/defaults.go#L231:6)
- "ClusterAutoscalerProvider": 
  - predicates = [`defaultPredicates()`](https://sourcegraph.com/github.com/kubernetes/kubernetes@v1.13.3/-/blob/pkg/scheduler/algorithmprovider/defaults/defaults.go#L106:6)
  - priorities = [`defaultPriority()`](https://sourcegraph.com/github.com/kubernetes/kubernetes@v1.13.3/-/blob/pkg/scheduler/algorithmprovider/defaults/defaults.go#L231:6) [- `LeastRequestedPriority` + `MostRequestedPriority`](https://sourcegraph.com/github.com/kubernetes/kubernetes@v1.13.3/-/blob/pkg/scheduler/algorithmprovider/defaults/defaults.go#L228:53) (Greedy Bin Packingできるようになっている)

# `Scheduler` のメインループ [`ScheduleOne`](https://sourcegraph.com/github.com/kubernetes/kubernetes@v1.13.3/-/blob/pkg/scheduler/scheduler.go#L513)
まずは[Kubernetes: スケジューラの動作 - 処理の流れ](https://qiita.com/tkusumi/items/58fdadbe4053812cb44e#%E5%87%A6%E7%90%86%E3%81%AE%E6%B5%81%E3%82%8C)をざっと読むとよい。大きく4ステップ


## 1. [NextPod()](https://sourcegraph.com/github.com/kubernetes/kubernetes@v1.13.3/-/blob/pkg/scheduler/scheduler.go#L514) : podをpop
- podをqueueから取り出す
- 本体は[configFactory.getNextPod()](https://sourcegraph.com/github.com/kubernetes/kubernetes@v1.13.3/-/blob/pkg/scheduler/factory/factory.go#L1389)で、queueからpopしているだけ
  - つまり、bind 候補 の pod の順序はすべてこの queue から pop される順序で決まる
  - queueに関しては 下記 "Topics" の節参照

## 2. [schedule()](https://sourcegraph.com/github.com/kubernetes/kubernetes@v1.13.3/-/blob/pkg/scheduler/scheduler.go#L290): nodeを探す

- popされたpodに対して割当ノードを探す処理
  - [Kubernetes: スケジューラの動作 - 最適なノードの選択](https://qiita.com/tkusumi/items/58fdadbe4053812cb44e#%E6%9C%80%E9%81%A9%E3%81%AA%E3%83%8E%E3%83%BC%E3%83%89%E3%81%AE%E9%81%B8%E6%8A%9E) が詳しい
- 本体は[genericScheduler.Schedule()](https://sourcegraph.com/github.com/kubernetes/kubernetes@v1.13.3/-/blob/pkg/scheduler/core/generic_scheduler.go#L139)で主に3ステップ

### 2.1.[findNodesThatFit](https://sourcegraph.com/github.com/kubernetes/kubernetes@v1.13.3/-/blob/pkg/scheduler/core/generic_scheduler.go#L389:28)

- [findNodesThatFit](https://sourcegraph.com/github.com/kubernetes/kubernetes@v1.13.3/-/blob/pkg/scheduler/core/generic_scheduler.go#L389:28) -> [podFitsOnNode](https://sourcegraph.com/github.com/kubernetes/kubernetes@v1.13.3/-/blob/pkg/scheduler/core/generic_scheduler.go#L537): fitするnodeを計算
- [各nodeに対して並列にチェックする](https://sourcegraph.com/github.com/kubernetes/kubernetes@v1.13.3/-/blob/pkg/scheduler/core/generic_scheduler.go#L419-458)
- [extenderはその後呼ばれる](https://sourcegraph.com/github.com/kubernetes/kubernetes@v1.13.3/-/blob/pkg/scheduler/core/generic_scheduler.go#L467)(なぜか逐次)
- [`pkg.scheduler.core.equivalence`](https://sourcegraph.com/github.com/kubernetes/kubernetes@v1.13.3/-/blob/pkg/scheduler/core/equivalence/eqivalence.go) パッケージで定義されている equivalence class cache を使ってpredicateの評価を高速化しているようだが詳細は把握できていない
  - 名前から察するに pod全体を __同値類__ に分割して管理したいように読める
  - schedulerが 毎pod に対して predicate を評価するのではなくpodを同値類に分割して管理することで、schedulerが即断(キャッシュから)できるようにしたいのだと思われる
  - [equivalencePod](https://sourcegraph.com/github.com/kubernetes/kubernetes@v1.13.3/-/blob/pkg/scheduler/core/equivalence/eqivalence.go#L395)に定義されているPodの属性群から[32-bit FNV-1a hashを生成してClassのidとしている](https://sourcegraph.com/github.com/kubernetes/kubernetes@v1.13.3/-/blob/pkg/scheduler/core/equivalence/eqivalence.go#L252-262)

### 2.2. [PrioritizeNodes()](https://sourcegraph.com/github.com/kubernetes/kubernetes@v1.13.3/-/blob/pkg/scheduler/core/generic_scheduler.go#L624:6)

-  [各nodeごとに並列Map](https://sourcegraph.com/github.com/kubernetes/kubernetes@v1.13.3/-/blob/pkg/scheduler/core/generic_scheduler.go#L677) -> [Prioirty毎に並列Reduce](https://sourcegraph.com/github.com/kubernetes/kubernetes@v1.13.3/-/blob/pkg/scheduler/core/generic_scheduler.go#L693-711)
-  [各nodeのweighted sumを取る](https://sourcegraph.com/github.com/kubernetes/kubernetes@v1.13.3/-/blob/pkg/scheduler/core/generic_scheduler.go#L719-724)
-  [extenderが呼ばれてscoreが合算される](https://sourcegraph.com/github.com/kubernetes/kubernetes@v1.13.3/-/blob/pkg/scheduler/core/generic_scheduler.go#L726-756)

### 2.3 [selectHost()](https://sourcegraph.com/github.com/kubernetes/kubernetes@v1.13.3/-/blob/pkg/scheduler/core/generic_scheduler.go#L225-237)
- [selectHost()](https://sourcegraph.com/github.com/kubernetes/kubernetes@v1.13.3/-/blob/pkg/scheduler/core/generic_scheduler.go#L225-237): 最大ScoreのNodeを選ぶ
-  最大Score Node は 1つとは限らないので、内部に`lastNodeindex`を保持してround-robbinでルーレット的に決める
- 見つからなかったら[`Pod.status.conditions`を変更する](https://sourcegraph.com/github.com/kubernetes/kubernetes@v1.13.3/-/blob/pkg/scheduler/scheduler.go#L296)
- 直接queueには戻さず、[イベントハンドラ(un assingedなpodのupdate)経由](https://sourcegraph.com/github.com/kubernetes/kubernetes@v1.13.3/-/blob/pkg/scheduler/factory/factory.go#L345)で[queueに戻ってくる](https://sourcegraph.com/github.com/kubernetes/kubernetes@v1.13.3/-/blob/pkg/scheduler/factory/factory.go#L850)

## 3a. [`preempt()`](https://sourcegraph.com/github.com/kubernetes/kubernetes@v1.13.3/-/blob/pkg/scheduler/scheduler.go#L311:25): 見つからなければpreemptionに挑戦

- `schedule()` 結果が `FitError` の場合のみ
- 下記がわかりやすい
  - [猫でもわかる Pod Preemption](https://speakerdeck.com/ytaka23/kubernetes-meetup-tokyo-10th)
  - [schedulerとdevice-pluginをカスタムして機械学習ジョブクラスタを作っている話](https://www.slideshare.net/pfi/kubernetes-meetuptokyo13customizingkubernetesformlcluster)(スライド 27)
- victimを選ぶ処理の本体は [`genericScheduler.Preempt()`](https://sourcegraph.com/github.com/kubernetes/kubernetes@v1.13.3/-/blob/pkg/scheduler/core/generic_scheduler.go#L239-251): 主に4つのmethodからなる

### 3.1  [`genericScheduler.Preempt()`](https://sourcegraph.com/github.com/kubernetes/kubernetes@v1.13.3/-/blob/pkg/scheduler/core/generic_scheduler.go#L239-251)

主に4つのメソッドからなる

#### [nodesWherePreemptionMightHelp](https://sourcegraph.com/github.com/kubernetes/kubernetes@v1.13.3/-/blob/pkg/scheduler/core/generic_scheduler.go#L1060)
- Selectorにマッチしない, NotReadyなnode等、自明なnodeを除外する

#### [selectNodesForPreemption](https://sourcegraph.com/github.com/kubernetes/kubernetes@v1.13.3/-/blob/pkg/scheduler/core/generic_scheduler.go#L895:6)->[selectVictimsOnNode](https://sourcegraph.com/github.com/kubernetes/kubernetes@v1.13.3/-/blob/pkg/scheduler/core/generic_scheduler.go#L983:6): 各nodeでvictimを選ぶ

- 一旦低優先度のpodを全部抜いて(victim候補にして)、fitするかチェック
- 抜きすぎかもしれないので、fitしなくなるギリギリまでvictimを順にreprieveする
- [PDB違反あり→なしの順](https://sourcegraph.com/github.com/kubernetes/kubernetes@v1.13.3/-/blob/pkg/scheduler/core/generic_scheduler.go#L1030-1055)に救済
- 各stepでは低優先度から処理されるが、[Priority](https://sourcegraph.com/github.com/kubernetes/kubernetes@v1.13.3/-/blob/pkg/scheduler/core/generic_scheduler.go#L994)でしかSortしているだけなので安定性はない
- __PDB違反が起きるかもしれないことに注意__([ドキュメントにも明記あり](https://kubernetes.io/docs/concepts/configuration/pod-priority-preemption/#poddisruptionbudget-is-supported-but-not-guaranteed))

#### [processPreemptionWithExtenders](https://sourcegraph.com/github.com/kubernetes/kubernetes@v1.13.3/-/blob/pkg/scheduler/core/generic_scheduler.go#L313:28)

- ここで extenderが呼ばれる。ここまでのphaseで選択された`Node->Victims`のmapが渡される
-  `Node -> Victims` の map を返せばよいだけなので原理上自分でどのvictimを選ぶかは自由だが現実的でない
-  別processでの観測結果で選ぶとデータ整合性が心配

#### [pickOneNodeForPreemption](https://sourcegraph.com/github.com/kubernetes/kubernetes@v1.13.3/-/blob/pkg/scheduler/core/generic_scheduler.go#L788:6)

- 複数のnodeにvictim候補がいるので、最終的に一つのnodeに絞る
- いくつかの指標で辞書式順に選択する
  - PDB違反数の少ない
  - victim内の最大優先度が小さい
  - victimの優先度合計が小さい
  - victim pod数が少ない
  - 配列の先頭

### 3.2 [Nomination を行う & VictimをDeleteする](https://sourcegraph.com/github.com/kubernetes/kubernetes@v1.13.3/-/blob/pkg/scheduler/scheduler.go#L330-352)

- victimが選ばれたら、[`nomination`を行う](https://sourcegraph.com/github.com/kubernetes/kubernetes@v1.13.3/-/blob/pkg/scheduler/scheduler.go#L330-352)
- pod がこの node の victim を殺して、preemptor としてここにスケジュールされる予定ですよ、というのを記録する
  - 具体的には `pod.status.NominatedNodeName` を更新する 
  - api経由でpod statusを更新しても、event handlerの通知を待っていたら、その通知が遅れた場合(raceが起きる)、このnodeに別podがスケジュールされてしまう可能性があるため、scheduler queueの管理しているnomination情報を更新する(このscheduler loop内でqueueを更新することで、次のpodがpopされるときにはqueue内のnomination情報が最新になっていることを保証する)
  - また、schedulerの再起動、複数scheduler環境の場合にnominationを伝えるためにも必要な処理
- [victimをdeleteする(victimとしてnominated podがある場合にはそのclearも行う)](https://sourcegraph.com/github.com/kubernetes/kubernetes@v1.13.3/-/blob/pkg/scheduler/scheduler.go#L345-363)
- __preemptionが起きた場合にはここでscheduler loop終了__

## 3b. [Bind処理](https://sourcegraph.com/github.com/kubernetes/kubernetes@v1.13.3/-/blob/pkg/scheduler/scheduler.go#L563)
- [`VolumeScheduling`](https://kubernetes.io/docs/reference/command-line-tools-reference/feature-gates/#feature-gates)が有効だったら[AssumePodVolumes()する](https://sourcegraph.com/github.com/kubernetes/kubernetes@v1.13.3/-/blob/pkg/scheduler/scheduler.go#L371-372)(PVCを全てPVにbindする)
  - [`persistentvolume.volumeBinder.AssumePodVolumes()`](https://sourcegraph.com/github.com/kubernetes/kubernetes@v1.13.3/-/blob/pkg/controller/volume/persistentvolume/scheduler_binder.go#L204)で行われる
  - ここではvolume binding/privsioningの詳細には触れない
- すべてのPVCがboundされなかったらエラーとして、`pod.status.conditions`を更新して終了
- キャッシュ内のpodの`spec.nodeName` を [assume()](https://sourcegraph.com/github.com/kubernetes/kubernetes@v1.13.3/-/blob/pkg/scheduler/scheduler.go#L571:14) する
- ここまでで選ばれたnode(変数名`suggestedHost`)にBindする準備が整ったが、実際のBind処理は複数のスケジューラが居た場合等、失敗することがある処理なので、非同期に行えるようにキャッシュ内のpod情報は楽観的にそのnodeにしておく
- [非同期にbindする](https://sourcegraph.com/github.com/kubernetes/kubernetes@v1.13.3/-/blob/pkg/scheduler/scheduler.go#L578-603)
- [失敗したらassumeを解除する](https://sourcegraph.com/github.com/kubernetes/kubernetes@v1.13.3/-/blob/pkg/scheduler/scheduler.go#L492)

# Selected Topics

## [`SchedulingQueue`](https://sourcegraph.com/github.com/kubernetes/kubernetes@v1.13.3/-/blob/pkg/scheduler/internal/queue/scheduling_queue.go#L60)
- unschedulable(nodeにassumeされていない) pod のスケジュール順はこの [`SchedulingQueue`]((https://sourcegraph.com/github.com/kubernetes/kubernetes@v1.13.3/-/blob/pkg/scheduler/internal/queue/scheduling_queue.go#L60)) から popされる順で制御される
- [インターフェースになっている](https://sourcegraph.com/github.com/kubernetes/kubernetes@v1.13.3/-/blob/pkg/scheduler/internal/queue/scheduling_queue.go#L60)ので原理的には自分で実装できる
- 現在2つが定義されている
  - [`FIFO`](https://sourcegraph.com/github.com/kubernetes/kubernetes@v1.13.3/-/blob/pkg/scheduler/internal/queue/scheduling_queue.go#L97-101): 単純なFIFO
  - [`PriorityQueue`](https://sourcegraph.com/github.com/kubernetes/kubernetes@v1.13.3/-/blob/pkg/scheduler/internal/queue/scheduling_queue.go#L195-228)
- [`PodPriority` feature gateが有効なら`PriorityQueue`が使われる](https://sourcegraph.com/github.com/kubernetes/kubernetes@v1.13.3/-/blob/pkg/scheduler/internal/queue/scheduling_queue.go#L88-93)ようになっている

### [`PriorityQueue`](https://sourcegraph.com/github.com/kubernetes/kubernetes@v1.13.3/-/blob/pkg/scheduler/internal/queue/scheduling_queue.go#L195-228)
- 名前の通り`PriorityClass`で定義される`Priority`の値に従ってスケジュールする優先度付きキュー
- 同優先度内、優先度間でstarvation (eventually に schedule候補になれない)を防ぐために色々な工夫がされている
- よく出る問題: queueへのpodの出し入れが頻繁なクラスタ(クラスタが満杯でpending podが大量)の場合、scheduleに失敗したpodが戻ってきて、先頭の方に入ってしまうと後続をずっとblockしてしまう
- 優先度間: 
  - 一旦 `ScheduleFailed` になったら実際にqueueに戻すのを(内部的には`PriorityQueue.activeQ`) backoff することで回避
  - 付け焼き刃的で完全なstarvationは防げない
- 同優先度内: scheduleに失敗した時刻の古い順に並べ替えることでちゃんとぐるぐる廻る用にする
  - nodeやpodの状態が変化しない限り、scheduleしてもしょうがないので、unschedulable pod は 一旦 `PriorityQueue.unschedulableQ`というところに入って、node, pod の status changeに伴って一気に `PriorityQueue.activeQ`に映るようになっている (例: [configFactory.addNodeToCache()内](https://sourcegraph.com/github.com/kubernetes/kubernetes@v1.13.3/-/blob/pkg/scheduler/factory/factory.go#L969))

## `SchedulerExtender`

- [`ExtenderConfig`](https://sourcegraph.com/github.com/kubernetes/kubernetes@v1.13.3/-/blob/pkg/scheduler/api/types.go#L177-217): Policy内で記述する
  - サンプル: [everpeace/k8s-scheduler-extender-example](https://github.com/everpeace/k8s-scheduler-extender-example)
  - 応用: [everpeace/kube-throttler](https://github.com/everpeace/kube-throttler)
  - [内部インターフェースの定義](https://sourcegraph.com/github.com/kubernetes/kubernetes@v1.13.3/-/blob/pkg/scheduler/algorithm/scheduler_interface.go#L28-74)
- [extener.go(extender を直接呼ぶコンポーネント)](https://sourcegraph.com/github.com/kubernetes/kubernetes@v1.13.3/-/blob/pkg/scheduler/core/extender.go)
- genericSchedulerから下記の箇所で呼ばれている
  - `Schedule()`-> [`findNodesThatFit()`内](https://sourcegraph.com/github.com/kubernetes/kubernetes@v1.13.3/-/blob/pkg/scheduler/core/generic_scheduler.go#L162)
  - `Schedule()`-> [`PrioritizeNodes()`内](https://sourcegraph.com/github.com/kubernetes/kubernetes@v1.13.3/-/blob/pkg/scheduler/core/generic_scheduler.go#L186:23)
  - [Preempt()内](https://sourcegraph.com/github.com/kubernetes/kubernetes@v1.13.3/-/blob/pkg/scheduler/core/generic_scheduler.go#L288)
- `Bind()`は一回しか呼べないので[`configFactory.getBinderFunc()`](https://sourcegraph.com/github.com/kubernetes/kubernetes@721bfa751924da8d1680787490c54b9179b1fed0/-/blob/pkg/scheduler/factory/factory.go#L1237-1252)で、もし`Bind()`できるextenderがあったらそれを返している

## `PercentageOfNodesToScore`
- 大きなclusterでpod毎に全nodeを評価せずに適当な割合のnode数が見つかったら探すのを早期にやめる
- 定義: [KubeSchedulerConfiguration.PercentageOfNodesToScore](https://sourcegraph.com/github.com/kubernetes/kubernetes@v1.13.3/-/blob/pkg/scheduler/apis/config/types.go#L76-83)
- ->[configFactory.percentageOfNodesToScore](https://sourcegraph.com/github.com/kubernetes/kubernetes@721bfa751924da8d1680787490c54b9179b1fed0/-/blob/pkg/scheduler/factory/factory.go#L296) -> [genericScheduler.percentageOfNodesToScore](https://sourcegraph.com/github.com/kubernetes/kubernetes@721bfa751924da8d1680787490c54b9179b1fed0/-/blob/pkg/scheduler/core/generic_scheduler.go#L1183) と引き回されて
- `genericScheduler.Schedule()` -> [`findNodesThatFit`内](https://sourcegraph.com/github.com/kubernetes/kubernetes@721bfa751924da8d1680787490c54b9179b1fed0/-/blob/pkg/scheduler/core/generic_scheduler.go#L397) で使われる
- fitするnodeが必要なだけ見つかったら、predicateの計算をやめてscoringに入る
- [最低100nodeは保証される](https://sourcegraph.com/github.com/kubernetes/kubernetes@v1.13.3/-/blob/pkg/scheduler/core/generic_scheduler.go#L56:2)

## [`pkg.scheduler.internal.cache.Cache`](https://sourcegraph.com/github.com/kubernetes/kubernetes@v1.13.3/-/blob/pkg/scheduler/internal/cache/interface.go#L60)
- scheduler内で保持されるcacheのインターフェース
- 基本的にschedulerはこのキャッシュの保持する状態に対してschedule判断を行う
- `Pod` と `Node` が対象
  - `Pod`には[状態遷移が規定されている(`Initial`, `Assumed`, `Expired`, `Added`, `Deleted`)](https://sourcegraph.com/github.com/kubernetes/kubernetes@v1.13.3/-/blob/pkg/scheduler/internal/cache/interface.go#L33-47)
  - bindが非同期なので、`Assumed` は一定時間後にexpireするようになっている
  - `Initial`, `Expired`, `Deleted` な状態のpodはキャッシュ内に実際には存在しない
- `Node` は [`NodeTree`](https://sourcegraph.com/github.com/kubernetes/kubernetes@v1.13.3/-/blob/pkg/scheduler/internal/cache/node_tree.go#L31)というデ 
 ータ構造で管理されている
  - と言っても再帰的な構造ではなく、単に[`failure-domain/{zone, region}`](https://sourcegraph.com/github.com/kubernetes/kubernetes@v1.13.3/-/blob/pkg/util/node/node.go#L116-133)ごとに[リストを管理しているのみ](https://sourcegraph.com/github.com/kubernetes/kubernetes@v1.13.3/-/blob/pkg/scheduler/internal/cache/node_tree.go#L32)
- 実装は [`cache.schedulerCache`](https://sourcegraph.com/github.com/kubernetes/kubernetes@v1.13.3/-/blob/pkg/scheduler/internal/cache/cache.go#L50)

# Selected Future Improvements
- Priority and preemption is [promoted to GA](https://github.com/kubernetes/kubernetes/pull/73498) in 1.14
- [`factory.go` に埋まっていたevent handler群を移動](https://github.com/kubernetes/kubernetes/pull/69504/files)
- [Non-preempting PriorityClass](https://github.com/kubernetes/kubernetes/pull/73331): PreemptionされないPriorityClass(内部で実装しようと思っていたのでとても嬉しい)
- [Coscheduling(aka gang scheduling)](https://github.com/kubernetes/kubernetes/issues/61012)
  - [KEP](https://github.com/kubernetes/enhancements/issues/583): このKEPでBrian Grantさんが "Gang"という名前に反対して"CoScheduling"になっている
- まだ始まったばかりらしいですが [in-place update of pod resources](https://github.com/kubernetes/enhancements/pull/686)に向けた作業も始まっているようです
  - KEP: [Vertical Scaling of Pods](https://github.com/kubernetes/enhancements/issues/21)
- [Scheduler Framework](https://github.com/kubernetes/community/blob/master/contributors/design-proposals/scheduling/scheduling-framework.md)
  - KubeCon 2018 Seattleでleadのお二人と話しましたが、まだ優先度が決まっていなくて具体的な開発スケジュールはないらしいです([Kubernetes Meetup Tokyo #16](https://k8sjp.connpass.com/event/116799/)で[チェシャ猫さん@y_taka_23](https://twitter.com/y_taka_23)のLTありです！)

# Scheduler開発に興味のある方へ
- [sig-scheduling](https://github.com/kubernetes/community/tree/master/sig-scheduling)
  - meeting notes/recordingに目を通すのがおすすめ
- sub projectもいくつかあります(どれもまだ開発段階)
  - [cluster-capacity](https://github.com/kubernetes-incubator/cluster-capacity): podの定義に対して、どのnodeがどのくらい空いてるか空いて無いかを分析してくれる
  - [descheduler](https://github.com/kubernetes-incubator/descheduler): deflagしたり, affinityを回復したりするために敢えて podをde-scheduler(delete)する(名前の通りscheduleはせず単にnodeから抜くだけ)
  - [kube-batch](https://github.com/kubernetes-sigs/kube-batch): A batch scheduler of Kubernetes for ML/BigData/HPC workload
  - [poseidon](https://github.com/kubernetes-sigs/poseidon): [http://www.firmament.io](http://www.firmament.io)ベース(グラフ理論ベース)のscheduler
- [sig/scheduling issues](https://github.com/kubernetes/kubernetes/issues?utf8=%E2%9C%93&q=is%3Aissue+is%3Aopen+label%3Asig%2Fscheduling)
  - まだまだたくさんありますので是非！
- [__PFN is hiring!!__](https://www.preferred-networks.jp/ja/jobs)
  - Engineer -> MLクラスターミドルウェア の職種を参照ください