scheduler
kubernetes
sig-scheduling
kube-scheduler

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

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

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

また、2019-02-05 Kubernetes 読書会 #4の資料としても用られました。

kube-schedulerエントリーポイント(cmd/kube-scheduler/scheduler.go)から順に読んでいくスタイルで解説しています。


ソースコードをいきなり読む前に

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


対象ソースコード


パッケージ構造

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


cmd/kube-scheduler

CLIに関するの実装のパッケージです。


├── 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

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 のブート処理

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


Scheduler インスタンスの初期化


  • 初期化は pkg.scheduler.New()で行われる


  • Schedulerインスタンスを初期化するための設定は3ステップ


1. scheduler.factory.configFactoryを作る


2. 指定されたAlgorithmSourceによってscheduler.Config(これが実質のSchedulerの入力)を作る



  • AlgorithmProviderの場合: configFactory.CreateFromProvider()で作られる (Providerの初期化と中身は下参照) 参照


  • Policy from File or ConfigMapの場合: initPolicyFromFile() or initPolicyFromConfigMap()Policyが作られた後CreateFromConfig()で作られる


  • scheduler.Config内には、スケジューラのメインループから呼ばれる主要な挙動(podをbindするnodeを探す、preemption時のvictimを探す等はAlgorithmでinterface化されていて、

  • kube-schedulerでは GenericScheduler のみが実装していてGenericSchedulerCreateFromConfig() -> CreateFromKeys()内で作られる

  • この scheduler.Configに多くのロジックを持ったコンポーネントがDIされており、factory.goに多くのロジックが記述されていて少し読みにくい原因になっている


3. Scheduler instanceを生成する


  • 作られたscheduler.Config から Scheduler instanceを生成する


Algorithm Providerの初期化


Scheduler のメインループ ScheduleOne

まずはKubernetes: スケジューラの動作 - 処理の流れをざっと読むとよい。大きく4ステップ


1. NextPod() : podをpop


  • podをqueueから取り出す

  • 本体はconfigFactory.getNextPod()で、queueからpopしているだけ


    • つまり、bind 候補 の pod の順序はすべてこの queue から pop される順序で決まる

    • queueに関しては 下記 "Topics" の節参照




2. schedule(): nodeを探す


2.1.findNodesThatFit


2.2. PrioritizeNodes()


2.3 selectHost()


3a. preempt(): 見つからなければpreemptionに挑戦


3.1 genericScheduler.Preempt()

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


nodesWherePreemptionMightHelp


  • Selectorにマッチしない, NotReadyなnode等、自明なnodeを除外する


selectNodesForPreemption->selectVictimsOnNode: 各nodeでvictimを選ぶ


  • 一旦低優先度のpodを全部抜いて(victim候補にして)、fitするかチェック

  • 抜きすぎかもしれないので、fitしなくなるギリギリまでvictimを順にreprieveする


  • PDB違反あり→なしの順に救済

  • 各stepでは低優先度から処理されるが、PriorityでしかSortしているだけなので安定性はない


  • PDB違反が起きるかもしれないことに注意(ドキュメントにも明記あり)


processPreemptionWithExtenders


  • ここで extenderが呼ばれる。ここまでのphaseで選択されたNode->Victimsのmapが渡される

  • Node -> Victims の map を返せばよいだけなので原理上自分でどのvictimを選ぶかは自由だが現実的でない

  • 別processでの観測結果で選ぶとデータ整合性が心配


pickOneNodeForPreemption


  • 複数のnodeにvictim候補がいるので、最終的に一つのnodeに絞る

  • いくつかの指標で辞書式順に選択する


    • PDB違反数の少ない

    • victim内の最大優先度が小さい

    • victimの優先度合計が小さい

    • victim pod数が少ない

    • 配列の先頭




3.2 Nomination を行う & VictimをDeleteする


  • victimが選ばれたら、nominationを行う

  • 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も行う)

  • preemptionが起きた場合にはここでscheduler loop終了


3b. Bind処理


Selected Topics


SchedulingQueue


PriorityQueue


  • 名前の通り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()内)




SchedulerExtender


PercentageOfNodesToScore


pkg.scheduler.internal.cache.Cache


Selected Future Improvements


Scheduler開発に興味のある方へ



  • sig-scheduling


    • meeting notes/recordingに目を通すのがおすすめ



  • sub projectもいくつかあります(どれもまだ開発段階)



    • cluster-capacity: podの定義に対して、どのnodeがどのくらい空いてるか空いて無いかを分析してくれる


    • descheduler: deflagしたり, affinityを回復したりするために敢えて podをde-scheduler(delete)する(名前の通りscheduleはせず単にnodeから抜くだけ)


    • kube-batch: A batch scheduler of Kubernetes for ML/BigData/HPC workload


    • poseidon: http://www.firmament.ioベース(グラフ理論ベース)のscheduler




  • sig/scheduling issues


    • まだまだたくさんありますので是非!




  • PFN is hiring!!


    • Engineer -> MLクラスターミドルウェア の職種を参照ください