状態機械を合成してデッドロックを検出できる Go 言語パッケージを作ってみました
はじめに
マルチスレッドで動作するプログラムの設計は難しい問題です。個々のスレッドの動作は単純に見えても、複数が並行して動作する場合の動作は組み合わせ論的に複雑になります。また、タイミングに依存する不具合は狙って再現することが難しく、通常の単体テストによる検出にも限界があります。
そんなとき、有効な手法がモデル検査です。システムの取りうる状態をあらかじめ網羅的に探索することで、「実際に動作させた際にごく低い確率で踏むバグ」であっても、動作させることなく設計段階で発見することが可能になります。
ところでちょうど先日、デッドロック発見器を自作するハンズオンに参加する機会がありました。内容は非常にシンプルなモデル検査器を実装するというもので、せっかくなのでそのときの成果物を Go のパッケージとしてまとめたものを以下に公開しました。
以下、このパッケージで何ができるのかを具体例とともに紹介します。
例 1: 食事する哲学者の問題
まず、上に貼った GitHub の README にも挙げてある食事する哲学者の問題を試してみましょう。サンプルコードはこちらです。
このパッケージは、状態機械の遷移規則を定義するための DSL を提供します。例えば哲学者を表す状態機械は以下のようにして構築できます。
philo := func(me int, left, right vars.Name) deadlock.Process { return deadlock.NewProcess(). EnterAt("0"). Define(rule.At("0").Only(when.Var(left).Is(0)). Let("up_l", do.Set(me).ToVar(left)).MoveTo("1")). Define(rule.At("1").Only(when.Var(right).Is(0)). Let("up_r", do.Set(me).ToVar(right)).MoveTo("2")). Define(rule.At("2").Only(when.Var(right).Is(me)). Let("down_r", do.Set(0).ToVar(right)).MoveTo("3")). Define(rule.At("3").Only(when.Var(left).Is(me)). Let("down_l", do.Set(0).ToVar(left)).MoveTo("0")) }
単一のプロセスは deadlock.Process で表現されます。プロセスたちは int に値を取ることができる変数を共有しており、この変数を書き換えることで処理を行っています。ここでは哲学者を複数配置することを考えて、哲学者を識別する番号と左右のフォークを表す変数をパラメータとして与えられるようにしてあります。
定義されている遷移規則を読み下すと、個々の哲学者は以下のように動作することが主張されています。
- 実行は状態 0 からスタート
- 自分の左側のフォークを表す変数
leftの値が 0 なら、誰にも占有されていないと判断し、そこに自分の番号を代入して状態 1 に移行 - 同様に右側のフォーク
rightも確保して状態 2 に移行 - 取った時とは逆順で、右側のフォークの占有を解除するために 0 を代入して状態 3 に移行
- 残った左側のフォークも占有を解除して初期状態 0 に戻る
なお、実際のプロセスは状態 2 において獲得したフォークを使用する何らかのタスクを行うはずですが、ロックの取得や解放には直接関係しないため、ここではモデリングに含めていません。
さて、それでは定義を確認するために、まずは哲学者が一人しかいない場合について遷移グラフを書いてみましょう。検査を行うには、deadlock.System に変数の初期値と Process を登録します。以下は哲学者 P1 が一人だけいて、左右のフォークの状態を変数 f1 および f2 に割り当てています。
system := deadlock.NewSystem().
Declare(vars.Shared{"f1": 0, "f2": 0}).
Register("P1", philo(1, "f1", "f2"))
検査器本体は deadlock.Detector です。定義した System を引数として Detect を呼び出すことで検査が実行されて結果が返ります。
report, err := deadlock.NewDetector().Detect(system)
返ってきた Report 構造体から直接値を取り出すことも可能ですが、Graphviz の dot 形式で出力するためのプリティプリンタも提供されています。
_, err = deadlock.NewPrinter(os.Stdout).Print(report)
ここまでのコードを main() 内に記述し、得られた出力を dot コマンドに渡すと次のような画像が得られるはずです。なお、Go 言語の map が順序不定になっている関係で、出力は実行ごとに若干異なる可能性があります。
各時点でプロセスがいる状態と変数の値が図示されています。青い部分が初期状態で、意図した通り、up_l、up_r、down_r、down_l の順に遷移して初期状態に戻ってきていることがわかります。
デッドロックの検出
次に、同じ動作をする哲学者が複数いる場合を考えましょう。よく知られている通り、この場合はデッドロックが発生します。
哲学者 philo はあらかじめパラメータ化してあったので、同じ動作をするプロセスを複製して複数登録することも簡単です。
system := deadlock.NewSystem().
Declare(vars.Shared{"f1": 0, "f2": 0}).
Register("P1", philo(1, "f1", "f2")).
Register("P2", philo(2, "f2", "f1"))
二人目の哲学者 P2 は一人目の P1 と向かい合う形で座っていて、彼の左側にはフォーク f2 が、右側にはフォーク f1 があるとします。P1 から見たフォークとは左右が逆になっています。
同じようにして図示させてみると、デッドロックを表す赤い状態とそこへのエラートレース（のうち最初に見つけたもの）が表示されます。初期状態から P1.up_l、P2.up_l の順、すなわち「哲学者 1 が左のフォークを取る」「哲学者 2 が左のフォークを取る」と遷移した場合にデッドロックになることが検出されました。実際、デッドロック状態からは次に出て行く遷移がないことがわかります。
デッドロックの解消
それでは、哲学者の動作を少し変えて、このデッドロック状態を解消できるようにしてみましょう。
philo := func(me int, left, right vars.Name) deadlock.Process { return deadlock.NewProcess(). EnterAt("0"). Define(rule.At("0").Only(when.Var(left).Is(0)). Let("up_l", do.Set(me).ToVar(left)).MoveTo("1")). Define(rule.At("1").Only(when.Var(right).Is(0)). Let("up_r", do.Set(me).ToVar(right)).MoveTo("2")). // Add the new rule Define(rule.At("1").Only(when.Var(right).IsNot(0)). Let("down_l", do.Set(0).ToVar(left)).MoveTo("0")). Define(rule.At("2").Only(when.Var(right).Is(me)). Let("down_r", do.Set(0).ToVar(right)).MoveTo("3")). Define(rule.At("3").Only(when.Var(left).Is(me)). Let("down_l", do.Set(0).ToVar(left)).MoveTo("0")) }
追加された 2 行は「状態 1、すなわち左側のフォークを確保した時点で、もし右側のフォークが占有中であれば、確保した左側のフォークを一旦解放して戻る」という規則を表現しています。結果を図示してみると赤い状態がなくなっており、先ほどのデッドロックが解消したことがわかります。
なおこの修正を入れた場合であっても、すべての哲学者が「左側のフォークを確保」「右側のフォークが確保できないのでやり直し」だけを繰り返す、いわゆるライブロックの問題は解決していません。ライブロックの不在を保証する活性の検査は、現状スコープ外です。
例 2: 排他制御
先ほどの哲学者は二本のフォークで食事した後で最初に戻って無限にループしていましたが、今度は停止するタイプのプロセスを書いてみましょう。サンプルコードはこちらです。
二つのプロセスが一つのグローバル変数を共有していて、それぞれのプロセスはこの変数を 1 だけインクリメントするとします。より具体的には、各プロセスは次のように動作します。
コードは以下のようになります。HaltAt に指定された状態は受理状態と見なされ、デッドロックとして検出されなくなります。複数のプロセスを合成した結果に対しては、全てのプロセスが受理状態にあるとき全体として受理状態であると見なされます。
proc := func(global, local vars.Name) deadlock.Process { return deadlock.NewProcess(). EnterAt("0"). Define(rule.At("0"). Let("read", do.CopyVar(global).ToVar(local)).MoveTo("1")). Define(rule.At("1"). Let("incr", do.Add(1).ToVar(local)).MoveTo("2")). Define(rule.At("2"). Let("write", do.CopyVar(local).ToVar(global)).MoveTo("3")). HaltAt("3") } system := deadlock.NewSystem(). Declare(vars.Shared{"var": 0, "tmp1": 0, "tmp2": 0}). Register("P", proc("var", "tmp1")). Register("Q", proc("var", "tmp2"))
得られた図が以下です。受理状態は二重丸として表現されており、出て行く遷移がないにも関わらず赤く表示されてはいません。
図中には三つの受理状態がありますが、よく見ると最終的に var = 1 になる場合（中央）と var = 2 になる場合（左右）があることがわかります。二つのプロセスが独立にインクリメントした結果として意図される値は 2 ですが、第一のプロセスが値を書き戻す (P.write) より前に第二のプロセスの読み込み (Q.read) が発生すると、書き込んだ値が上書きされてしまうためです。
ミューテックスによる直列化
この問題を解決するために、変数 mutex を新しく導入し、値を操作する際にはロックを取得させるようにします。
proc := func(global, local, mutex vars.Name) deadlock.Process { return deadlock.NewProcess(). EnterAt("0"). // Add the new rule Define(rule.At("0").Only(when.Var(mutex).Is(0)). Let("lock", do.Set(1).ToVar(mutex)).MoveTo("1")). Define(rule.At("1"). Let("read", do.CopyVar(global).ToVar(local)).MoveTo("2")). Define(rule.At("2"). Let("incr", do.Add(1).ToVar(local)).MoveTo("3")). Define(rule.At("3"). Let("write", do.CopyVar(local).ToVar(global)).MoveTo("4")). // Add the new rule Define(rule.At("4"). Let("unlock", do.Set(0).ToVar(mutex)).MoveTo("5")). HaltAt("5") } system := deadlock.NewSystem(). Declare(vars.Shared{"var": 0, "tmp1": 0, "tmp2": 0, "mut": 0}). Register("P", proc("var", "tmp1", "mut")). Register("Q", proc("var", "tmp2", "mut"))
動作の最初でロックを取得し、最後に解放する動作を追加しています。表示された図の受理状態ではいずれも var = 2 となっており、各プロセスがread、incr、write の遷移を連続して割り込まれることなく実行していることがわかります。
例 3: 生産者・消費者問題
今度はもう少し複雑な動作をモデリングしてみましょう。
二つのプロセス「生産者」と「消費者」がキューを挟んで接続されている状況を考えます。生産者がキューに要素を詰めるプロセス、消費者はそれを取り出すプロセスです。
キューが容量いっぱいの時、生産者は要素の生成をブロックされます。逆に消費者は、キューが空の場合には要素が取り出せないためブロックされます。ただし、単にブロックされているのではなく、待ち状態に移行して待機するとします。
この待ち状態は、条件変数に送られるシグナルを検知することで解除されます。つまり、生産者は「キューから要素が取り出され空きができた」という条件変数、消費者は「キューに要素が投入された」という条件変数をそれぞれ監視します。
より具体的には、生産者は以下のように動作します。
- まずキューにアクセスするためにロックを取得
- キューを確認し、容量に空きがなければロックを解放して待ち状態に入る
- 待ち状態では条件変数へのシグナルを待ち、受信したら最初に戻る
- キュー容量に空きがあった場合、要素を一つ追加
- 条件変数にシグナルを送り、消費者が待ち状態にいれば起動させる
- キューに対するロックを解放し、最初に戻る
同様に、消費者は以下のように動作します。
- まずキューにアクセスするためにロックを取得
- キューを確認し、一つも要素がなければロックを解放して待ち状態に入る
- 待ち状態では条件変数へのシグナルを待ち、受信したら最初に戻る
- キューに要素が存在した場合、その要素を一つ削除
- 条件変数にシグナルを送り、生産者が待ち状態にいれば起動させる
- キューに対するロックを解放し、最初に戻る
これをそのまま実装したソースコードは次のようになります。
- キュー内の要素の個数:
queue - キューへのアクセスを保護するミューテックス:
mutex - キューが容量一杯になっているフラグ:
over - キューが空になっているフラグ:
under
capacity はキューの最大容量です。今回はキュー内の要素が何かは考えず、要素の個数だけを問題にします。
capacity = 1 producer := func(queue, mutex, over, under vars.Name) deadlock.Process { return deadlock.NewProcess(). EnterAt("0"). Define(rule.At("0").Only(when.Var(mutex).Is(0)). Let("lock", do.Set(1).ToVar(mutex)).MoveTo("1")). Define(rule.At("1").Only(when.Var(queue).Is(capacity)). Let("unlock", do.Set(0).ToVar(mutex)).MoveTo("2")). Define(rule.At("2"). Let("wait", do.Set(1).ToVar(over)).MoveTo("3")). Define(rule.At("3").Only(when.Var(over).Is(0)). Let("wakeup", do.Nothing()).MoveTo("0")). Define(rule.At("1").Only(when.Var(queue).IsLessThan(capacity)). Let("produce", do.Add(1).ToVar(queue)).MoveTo("4")). Define(rule.At("4"). Let("signal", do.Set(0).ToVar(under)).MoveTo("5")). Define(rule.At("5"). Let("unlock", do.Set(0).ToVar(mutex)).MoveTo("0")) } consumer := func(queue, mutex, over, under vars.Name) deadlock.Process { return deadlock.NewProcess(). EnterAt("0"). Define(rule.At("0").Only(when.Var(mutex).Is(0)). Let("lock", do.Set(1).ToVar(mutex)).MoveTo("1")). Define(rule.At("1").Only(when.Var(queue).Is(0)). Let("unlock", do.Set(0).ToVar(mutex)).MoveTo("2")). Define(rule.At("2"). Let("wait", do.Set(1).ToVar(under)).MoveTo("3")). Define(rule.At("3").Only(when.Var(under).Is(0)). Let("wakeup", do.Nothing()).MoveTo("0")). Define(rule.At("1").Only(when.Var(queue).IsGreaterThan(0)). Let("consume", do.Add(-1).ToVar(queue)).MoveTo("4")). Define(rule.At("4"). Let("signal", do.Set(0).ToVar(over)).MoveTo("5")). Define(rule.At("5"). Let("unlock", do.Set(0).ToVar(mutex)).MoveTo("0")) } system := deadlock.NewSystem(). Declare(vars.Shared{"que": 0, "mut": 0, "over": 0, "under": 0}). Register("P", producer("que", "mut", "over", "under")). Register("C", consumer("que", "mut", "over", "under"))
この実装では、キューの状態を確認して駄目ならロックを解放する遷移 unlock と自分が待ち状態に入ったフラグを立てる遷移 wait が、連続して発生するとは限らないことに注意してください。この二動作の間に、相手プロセスから割り込まれる可能性があります。
検査した結果が上の図です。例えば右のほうのデッドロックに至る経緯を観察すると、P.unlock、C.lock、C.consume、C.signal、P.wait というシーケンス、すなわち生産者がロックを解放した直後、待ち状態に入る前に消費者がシグナルを発信していることがわかります。このとき、生産者はシグナルを受け取ることができず、そのまま待ち状態で固定されてしまいます。
アトミック操作による割り込みの禁止
そこで、unlock と wait の間で他のプロセスが動かないように一つの遷移にまとめてしまうことを考えます。現状、deadlock パッケージが提供する DSL の範囲では一回の遷移で複数の変数を変更することができませんが、直接書き下すことにより実装が可能です。ロックを解放したと同時に待ち状態に入る遷移は以下のようになります。
waitConditionVar := func(mutex, cond vars.Name) do.Action { return func(vs vars.Shared) (vars.Shared, error) { newVars := vs.Clone() newVars[mutex] = 0 newVars[cond] = 1 return newVars, nil } }
これを用いて、先ほどの生産者と消費者の定義にあった「ロックの解放」「待ち状態への遷移」を一つの不可分な遷移に置き換えます。検査してみると、先程までのデッドロックが解消していることがわかります。ちなみに、キューの容量 capacity を増やしてもやはりデッドロックが発生することはありません。
producer := func(queue, mutex, over, under vars.Name) deadlock.Process { return deadlock.NewProcess(). EnterAt("0"). Define(rule.At("0").Only(when.Var(mutex).Is(0)). Let("lock", do.Set(1).ToVar(mutex)).MoveTo("1")). // Replaced Define(rule.At("1").Only(when.Var(queue).Is(capacity)). Let("wait", waitConditionVar(mutex, over)).MoveTo("3")). Define(rule.At("3").Only(when.Var(over).Is(0)). Let("wakeup", do.Nothing()).MoveTo("0")). Define(rule.At("1").Only(when.Var(queue).IsLessThan(capacity)). Let("produce", do.Add(1).ToVar(queue)).MoveTo("4")). Define(rule.At("4"). Let("signal", do.Set(0).ToVar(under)).MoveTo("5")). Define(rule.At("5"). Let("unlock", do.Set(0).ToVar(mutex)).MoveTo("0")) } consumer := func(queue, mutex, over, under vars.Name) deadlock.Process { return deadlock.NewProcess(). EnterAt("0"). Define(rule.At("0").Only(when.Var(mutex).Is(0)). Let("lock", do.Set(1).ToVar(mutex)).MoveTo("1")). // Replaced Define(rule.At("1").Only(when.Var(queue).Is(0)). Let("wait", waitConditionVar(mutex, under)).MoveTo("3")). Define(rule.At("3").Only(when.Var(under).Is(0)). Let("wakeup", do.Nothing()).MoveTo("0")). Define(rule.At("1").Only(when.Var(queue).IsGreaterThan(0)). Let("consume", do.Add(-1).ToVar(queue)).MoveTo("4")). Define(rule.At("4"). Let("signal", do.Set(0).ToVar(over)).MoveTo("5")). Define(rule.At("5"). Let("unlock", do.Set(0).ToVar(mutex)).MoveTo("0")) }
まとめ
以上、Go 言語でグローバル変数を共有した複数の状態機械を定義し、並行動作させた場合に生じうるデッドロックを検出するデモを紹介しました。トイモデルではありますが、これだけでも意外と色々なものが実装できて、遷移グラフを描いてみると割と面白い結果が出ます。よかったら遊んでみて、もし気に入ったらスターを付けてやってください。
実際にはまだ色々直したいところはあって、
- 最初の n 個のデッドロック状態を発見した時点で探索を打ち切る
- デッドロック以外にもユーザが与えたアサーションに対する違反を検出する
- 結果表示の見た目をオプションで変更できるようにする
- 状態のハッシュ値を使いまわすことで、内部の無駄な計算を削る
など、時間を見つけて改良したいと思っていますが、それはまた別の話。
CloudNative Days Tokyo 2019 登壇こぼれ話 #CNDT2019
先日行われた CloudNative Days Tokyo 2019 で、Kubernetes のスケジューリングについて発表してきました。公募 CFP 枠です。
今回の発表は、実は技術的に目新しい内容をほとんど含んでいません。各トピックは今までいくつかの勉強会で LT として発表しているものがほとんどです。
ただし、普段の発表では時間が短いこともあって断片的になりがちだった内容を 40 分の枠で再構成し、スケジューリングについて初めて聞く人にとっても入り口のギャップを少なく、できるだけ学習曲線がなだらかになるようにすることを念頭に置いてプレゼンを組み立てました。
当日の Twitter でも「これはわかりやすい」という反応を複数の方からもらっているので、狙いとしてはある程度成功したんじゃないかと思っています。
当日の質問に関して
Twitter から #CNDT2019 と #RoomG のタグで拾った反応です。いくつかコメントがつけられそうなものがあったので、当日の内容の補足を兼ねて以下に述べます。
なるほど、scoringはDeploymentなどのPodとJobのそれで異なるのか。 #cndt2019 #RoomG
— こば（右） (@tzkb) July 23, 2019
スライドの流れだとちょっと語弊があったかもしれません。「スケジューリングの要件はPod の用途によって異なる」ことの例として二種類のポリシーについて述べましたが、実際に（デフォルトの状態で）Deployment による Pod と Job による Pod でポリシーが内部的に切り替わるわけではありません。ポリシはあくまでも発表中に述べたように policy.cfg で定義します。
ちなみに過去には --algorithm-provider という実行時フラグで LeastRequestedPriority と MostRequestedPriority とを選択する機能（ソースコード）がありましたが、すでに非推奨になっています。
schedulerは各ノードの状態をどうやって把握してるのだろう？#CNDT2019 #RoomG
— m-daichang (@mdaichang) July 23, 2019
特に目新しい仕組みがあるわけではありません。普通に Scheduler 自身が NodeInformer を介して API Server にアクセスして（ソースコード）情報を取得しています。おおむね kubectl describe nodes で取れる情報と同じです。
VPAはPodが一回死ぬんだっけ？ #cndt2019 #RoomG
— こば（右） (@tzkb) July 23, 2019
はい、現状では VPA は Pod を一度 evict し、その後 Resource Request が調整された Pod が新規に再作成されます。evict を行わない、いわゆる in-place な request は現在検討段階で、KubeCon EU 2019 でもいくつか発表がありました。
- Resize Your Pods w/o Disruptions aka How to Have a Cake and Eat a Cake
- Restart-Free Vertical Scaling for Kubernetes Pods
Descheduler、これって成熟してたっけ？
— silverbirder (@silver_birder) July 23, 2019
#CNDT2019 #RoomG
Descheduler = リバランス？？
— m-daichang (@mdaichang) July 23, 2019
そんな機能があったのか、知らなかった
（manifestみるとv1alphaか）#CNDT2019 #RoomG
Descheduler は Scheduler の機能ではなく、独立した単体のコマンドラインツールです。動作は単純で、一回実行するとその時点で条件に違反している Pod を検出して evict して終わりです。逆に言えば、継続してクラスタの状態を調整し続けたいのであれば、例えば CronJob にするなど、他の仕組みと組み合わせる必要があります。
参考文献
スケジューラのアーキテクチャ
Kubernetes 全体
スケジューラのアルゴリズム
カスタムポリシー設定
フィードバックとリソース効率
Preemption
Vertical Pod Autoscaler
Descheduler
広がるスケジューラの世界
Scheduler Extender
- Extender の API
- Scheduler Extender のスケルトン実装
- kube-throttler
- TopoLVM
- Stork
- 明日、業務で使える Scheduler Extender
特殊スケジューラ
まとめ
以上、CloudNative Days Tokyo 2019 で行った講演の補足情報でした。
今回の講演では、エッジな新情報の提供については一旦優先度を下げ、スケジューラについてあまりよく知らない人が一通りの知識を得られることにフォーカスしてストーリーを作成しました。結果として、曲がりなりにも「スケジューラについてはとりあえずこれを読んでおけ」と言える資料になったのではないかと自負しています。
余談ですが、最後に名前だけ出した kube-batch と Poseidon はなかなか興味深い対象です。スライド中でも述べた通り、通常の kube-scheduler が Pod ひとつごとに Node を決定していくのに対して、これらの特殊スケジューラは複数の Pod の配置をまとめて考慮することができます。今回はあえて深入りしなかったこの詳細、いつかどこかで発表するのを狙っていますが、それはまた別の話。
Docker Meetup Tokyo #31 で Kubernetes 1.15 について話してきました
先日行われた Docker Meetup Tokyo #31 で、Kubernetes 1.15 の Scheduler 周りの新機能について発表してきました。
Kubernetes の Pod Preemption を利用すると、より重要な Pod にノードの計算リソースを割り当てる優先的に割り当てることができ、コストの最適化につながります。しかし優先度の低い Pod は実行中に強制的に終了されることとなり、長時間かかるバッチ処理が途中で中断されてしまうという弊害もあります。
本スライドでは、Kubernetes 1.15 から Alpha 機能として導入された NonPreemptingPriority と Scheduling Framework を利用して、中断されたくない Pod に対する Preemption を抑制する手法を提案します。
その他の変更点も含めて、1.15 のリリースノートの完全な解説については以下の記事を参照してください。
参考資料
Scheduler 一般
- Scheduling Special Interest Group
- SIG Scheduling Deep Dive (KubeCon EU 2019)
- kube-schedulerのソースコードを読みながらPodがNodeにBindされるまでを理解する (現状、最も詳しいソースコード解説)
- Configuring Multiple Schedulers (実験用にカスタム Scheduler を追加するとき)
Priority と Preemption
- Pod Priority and Preemption (Non-Preempting PriorityClasses)
- 猫でもわかる Pod Preemption
- Issue: Add non-preempting option to PriorityClasses
Scheduling Framework
- Scheduling Framework (あくまでもデザインプロポーザルの解説で、現状の実装とは一致しない)
- 猫でもわかる Scheduling Framework
- Issue: Scheduling Framework (Scheduling Framework 関連の親 Issue)
- Plugin 有効化のための設定項目
- 各 Plugin の Interface 定義
余談
思えば Scheduler についても色々なイベントで話したものです。今回のスライドを登録したことで Speaker Deck のスライド一覧 がついに 2 ページ目になりました。
そろそろ Scheduler 以外のコンポーネントについても手を広げていきたいなと思っていますが、それはまた別の話。
Kubernetes 1.15: SIG Scheduling の変更内容
はじめに
本記事では、Kubernetes 1.15 のリリースノート からスケジューリングに関する内容をまとめました。
なお、SIG Scheduling の変更内容については既に他の方から翻訳記事が出ていますが、本記事は後発ということもあり、すべての機能を実際に触ってみた上でサンプルコードを添えて解説していきます。
1.15 の新着情報 (1.15 What’s New)
今回、完全な変更ログは https://relnotes.k8s.io/ で、絞り込み可能なフォーマットで公開されています。確認とフィードバックお願いします！
特筆すべき機能アップデート (Additional Notable Feature Updates)
Scheduler のプラグインを作るための Scheduling Framework が新しく Alpha 版になりました。
Scheduler Framework は、Scheduler の各点に拡張できるポイントを設け、カスタム処理をプラグインとして差し込むための仕組みです。
Scheduler を拡張する仕組みとしては他に JSON Webhook を使用する Scheduler Extender もありますが、プラグインは本体と同時にコンパイルするため通信によるオーバヘッドを避けることができます。
今回の変更点を述べるためには全体像を説明する必要がありますが、ここに書くにはボリュームが多くなりそうなので別記事を立てる予定です。
(TODO: 別記事を書いたらリンク貼る)
既知の問題点 (Known Issues)
1.15 でオプション
--log-fileを指定すると問題が発生することが分かっています。一つのファイルにログが複数回出力される現象です。この問題の振る舞いや詳細、あるいは修正のための予備調査などは ここ に解説されています。
Scheduler もこの問題の影響を受けます。実際、kube-scheduler 起動時に --log-file=kube-scheduler.log および --logtostderr=false を指定した場合、以下のようなログファイルが出力されることを確認しました。*1
Log file created at: 2019/07/01 21:00:28 Running on machine: custom-scheduler-767dbc9c6-blhwk Binary: Built with gc go1.12.5 for linux/amd64 Log line format: [IWEF]mmdd hh:mm:ss.uuuuuu threadid file:line] msg Log file created at: 2019/07/01 21:00:29 Running on machine: custom-scheduler-767dbc9c6-blhwk Binary: Built with gc go1.12.5 for linux/amd64 Log line format: [IWEF]mmdd hh:mm:ss.uuuuuu threadid file:line] msg (snip)
通常の運用で Scheduler のログをファイルに書き出す必然性はまずないので実際には問題にはならないと思いますが、一応注意が必要です。
メトリクスの変更 (Metrics Changes)
追加されたメトリクス (Added metrics)
Scheduler について、それぞれのキュー内にある Pending 状態の Pod の個数を記録するメトリクスが追加されました。(#75501, @Huang-Wei)
追加されているメトリクスは以下の 3 種類です。
scheduler_pending_pods_num{queue="active"}scheduler_pending_pods_num{queue="backoff"}scheduler_pending_pods_num{queue="unschedulable"}
非推奨または変更されたメトリクス (Deprecated/changed metrics)
Scheduling Framework に Reserve、Pre-bind、Permit、Post-bind、Queue sort および Un-reserve の拡張点が実装されました。(#77567, @wgliang) (#77559, @ahg-g) (#77529, @draveness) (#77598, @danielqsj) (#77501, @JieJhih) (#77457, @danielqsj)
Scheduling Framework の進捗についてです。直接的にメトリクスに関連する話題ではないはずですが、なぜこの位置に置かれているのかよくわかりません。
ここに述べられている通り、v1.14 時点ですでに実装されていた Reserve と Pre-bind に加えて、さらに 4 つの拡張点が追加されました。これに伴い、設定項目として有効にする拡張点が選択できるようになるなど、前回まで場当たり的だった実装のリファクタリングも行われています。
ただし、Permit プラグインについては「戻り値として Wait を返すことで Bind 前の Pod を待機させる機能」は実装されているものの、その待機状態を解除する方法がまだ提供されていないようです。詳細は先にも挙げた詳細記事を参照してください。
(TODO: 別記事へのリンク)
特筆すべき機能 (Notable Features)
Preemption を行わない Pod の優先度 (NonPreemptingPriority) が作成できるようになりました。PriorityClass においてこれが指定された場合、対象の Pod は 優先度の低い Pod に対してキュー内では優先されますが、実行中の Pod を Preemption することはありません。(#74614, @denkensk)
実際に PriorityClass で指定する属性は preemptionPolicy で、値としては PreemptLowerPriority もしくは Never が指定可能です。デフォルトは前者になります。Preemption する側 の Pod に指定する点に注意してください。
なお、Pod の Priority と Preemption の一般論については以下に解説があります。
この機能は Alpha 版なので、使用するには FeatureGates の有効化が必要です。kube-scheduler と apiserver の実行時引数として --feature-gates "NonPreemptingPolicy=true" を与えておいてください。
実験してみましょう。以下、話を簡単にするためにシングルノードの Kubernetes クラスタを仮定します。
まず、以下のような 3 つの PriorityClass を用意します。low-priority が Preemption される側の Pod 用、preempting-priority と non-preempting-priority が Preemption する側の Pod 用です。
priority.yaml
apiVersion: scheduling.k8s.io/v1 kind: PriorityClass metadata: name: low-priority value: 100 description: "The priroity for preempted Pods." --- apiVersion: scheduling.k8s.io/v1 kind: PriorityClass metadata: name: preempting-priority value: 100000 description: "The priroity for preempting Pods." --- apiVersion: scheduling.k8s.io/v1 kind: PriorityClass metadata: name: non-preempting-priority value: 100000 preemptionPolicy: Never description: "The priroity for non-preempting Pods."
さらに、各 PriorityClass に対応した Pod を定義します。ここで resources.requests.memory: 5Gi が指定されていますが、これは Node の利用可能メモリが 8Gi 程度だったためです。実験に使用している Node の性能を鑑みて「1 個なら置けるが 2 個は無理」という値にしてください。
low-priority-pod.yaml
apiVersion: v1 kind: Pod metadata: name: low-priority-pod spec: containers: - name: low-priority-pod image: k8s.gcr.io/pause:2.0 resources: requests: memory: 5Gi priorityClassName: low-priority
preempting-pod.yaml
apiVersion: v1 kind: Pod metadata: name: preempting-pod spec: containers: - name: preempting-pod image: k8s.gcr.io/pause:2.0 resources: requests: memory: 5Gi priorityClassName: preempting-priority
non-preempting-pod.yaml
apiVersion: v1 kind: Pod metadata: name: non-preempting-pod spec: containers: - name: non-preempting-pod image: k8s.gcr.io/pause:2.0 resources: requests: memory: 5Gi priorityClassName: non-preempting-priority
それでは実験です。Pod に先立って PriorityClass を作成しておきます。
$ kubectl create -f priority.yaml priorityclass.scheduling.k8s.io/low-priority created priorityclass.scheduling.k8s.io/preempting-priority created priorityclass.scheduling.k8s.io/non-preempting-priority created
まず、low-priority-pod を作成後に preempting-pod を作成します。
$ kubectl create -f low-priority-pod.yaml pod/low-priority-pod created $ kubectl get pods NAME READY STATUS RESTARTS AGE low-priority-pod 1/1 Running 0 14s $ kubectl create -f preempting-pod.yaml pod/preempting-pod created (wait for a while...) $ kubectl get pods NAME READY STATUS RESTARTS AGE preempting-pod 1/1 Running 0 70s
Node のメモリが不足したことにより、優先度が低い low-priority-pod が Preemption されて終了したことが分かります。
次に、preempting-pod を削除したうえで再度 low-priority-pod を準備し、今度は non-preempting-pod を作成してみます。
$ kubectl delete -f preempting-pod.yaml pod "preempting-pod" deleted $ kubectl create -f low-priority-pod.yaml pod/low-priority-pod created $ kubectl create -f non-preempting-pod.yaml pod/non-preempting-pod created (wait for a while...) $ kubectl get pods NAME READY STATUS RESTARTS AGE low-priority-pod 1/1 Running 0 48s non-preempting-pod 0/1 Pending 0 25s
今度は low-priority-pod は Running 状態のまま、優先度の高い non-preempting-pod が Pending になっています。これが preemptingPolicy: Never の効果です。
その他の特筆すべき変更 (Other notable changes)
重複 Toleration の扱い
Best Effort の Pod に対して同じ key と effect を持った Toleration が複数指定されている場合、マージされて最後に指定された Toleration の値が有効になります。(#75985, @ravisantoshgudimetla)
気が付かないとわかりづらいですが、これは Admission Control で呼び出されるロジックのバグ修正です。
Admission Control のひとつ PodTolerationRestriction は、Namespace のラベルとしてホワイトリストされた以外の Toleration が付いた Pod の作成を拒否します。
その過程で Toleration を走査するのですが、Pod の QoS が Best Effort 以外の場合には、以前から「メモリが枯渇気味の Node にも配置を避けない」という Toleration を付加する処理が行われており、ここでマージが行われていました。今回、Best Effort の場合でも同じマージ関数を通すための修正です。
なお Taint と Toleration の一般論については以下に解説があります。
実験してみましょう。今回もシングルノードクラスタを仮定します。また PodTolerationRestriction はデフォルト無効なので、apiserver に --enable-admission-plugins=PodTolerationRestriction を指定して有効にしておいてください。
まず、Node に Taint を付加します。この Node には mykey = myvalue の Toleration を持つ Pod 以外は新たに配置されなくなります。
$ kubectl get nodes NAME STATUS ROLES AGE VERSION kind-control-plane Ready master 64m v1.15.0 $ kubectl taint node kind-control-plane mykey=myvalue:NoSchedule node/kind-control-plane tainted
ここで、以下の Pod を考えます。
tolerant-pod.yaml
apiVersion: v1 kind: Pod metadata: name: tolerant-pod spec: containers: - name: tolerant-pod image: k8s.gcr.io/pause:2.0 tolerations: - key: mykey value: myvalue effect: NoSchedule - key: mykey value: dummy effect: NoSchedule
この Pod は mykey = myvalue なる Toleration を持つため、一見すると配置可能なように見えます。試してみましょう。
$ kubectl create -f tolerant-pod.yaml pod/tolerant-pod created $ kubectl get pods NAME READY STATUS RESTARTS AGE tolerant-pod 0/1 Pending 0 38s
予想に反して、Pod は配置されず Pending のままになってしまいました。
では今度はふたつの Toleration の順序だけを入れ替えてみます。
tolerant-pod.yaml (edited)
apiVersion: v1 kind: Pod metadata: name: tolerant-pod spec: containers: - name: tolerant-pod image: k8s.gcr.io/pause:2.0 tolerations: - key: mykey value: dummy effect: NoSchedule - key: mykey value: myvalue effect: NoSchedule
同様に Pod を作成してみると、
$ kubectl delete -f tolerant-pod.yaml pod "tolerant-pod" deleted $ kubectl create -f tolerant-pod.yaml pod/tolerant-pod created $ kubectl get pods NAME READY STATUS RESTARTS AGE tolerant-pod 1/1 Running 0 18s
無事に Running になりました。
以上から、key と effect が同じで value が異なる 2 種類の Toleration が同時に指定されているとき、後から指定されたものが有効になっていることが分かります。
PodAffinity のパフォーマンス改善
PodAffinity 指定時、Required および Preferred の両指定とも 2 倍のパフォーマンス向上を達成しました。(#76243, @Huang-Wei)
Pod の Affinity に基づいて各 Node をスコア付けする部分に手が入っています。
アルゴリズムを抜本的に変更したわけではなく、Node を走査する際に、今までループの外側で手動で取っていたロックを sync/atomic パッケージ (GoDoc) に置き換えたようです。アトミックな加算 AddInt64 の使用に伴い、Node に対するスコアが int で保持されるようになっています。
なお Pod の Affinity については以下に解説があります。
競合状態の防止
高優先度の Pod に NominatedNodeName が登録されている際、その Node に対して低優先度の Pod をスケジュールしないようにすることで、競合状態が発生する問題を修正しました。(#77990. @Huang-Wei)
この変更ログの書き方はややミスリードで、今回、実際に入った変更は Pod のスケジューリングのロジックではありません。
NominatedNodeName は、Preemption 発生時にどの Node に対して Preemption を行ったかを記録する情報です。Preemption した側の Pod に付与されますが、必ずしも結果的にその Node に最終的に配置されることは保証していません。例えば、Preemption された低優先度 Pod の終了を待っているうちに他の Node に空きが出たり、逆に Preemption した Pod よりさらに高優先度の Pod が到着したりする状況も考えられます。
スケジューラは内部に Pod と NominatedNodeName の対応を保持しており、キュー内の Pod を操作すると同時にその対応を更新します。そして Premption 直後の特定のタイミングでは、Preemption した側の Pod の NominatedNodeName が空欄になった状態で更新関数が呼ばれるケースがあるようです。
今回の修正は、このような場合に NominatedNodeName が空欄で上書きされて消えてしまい、空いた Node に低優先度の Pod が横から入ることを防ぐためのものです。
まとめ
以上、Kubernetes v1.15.0 におけるリリースノートとその解説でした。押さえておくべき重要事項は次の 2 点です。
- Scheduling Framework に新しい拡張点が設定された
- Preemption は発生させない (ただしキュー内の順番としては優先される) PriorityClass の設定が可能になった
ところで、PriorityClass はもちろん Preemption 関連ですが、実は Scheduling Framework も Preemption と無関係ではありません。新しく実装された Queue sort プラグインを利用することで今まで難しかった Preemption の制御が可能になるのですが、それはまた別の話。
*1:なお 1.15.0 において --log-dir と --alsologtostderr が認識されていないように見えましたが、今回は深追いしていません。
Fun Fun Functional (1) で Haskell と Firebase を使ってライブコーディングしてきました
先日行われた Fun Fun Functional (1) で、Haskell と Firebase を使った Web アプリの作り方について発表してきました。
使用した要素技術は、GHCJS 上のフレームワーク Miso と、Fireabse SDK を呼び出すための DSL である JSaddle です。
GHCJS は Haskell のソースコードを JavaScript に変換するコンパイラで、GHC をフォークすることによって開発されています。
Miso は GHCJS 上で The Elm Architecture を実装するためのフレームワークです。Miso では事実上サーバサイドで書けない Elm と異なり、サーバサイドとの Model の共有や、初回アクセス時の HTML をサーバ側で構築するサーバサイドレンダリング (SSR) の仕組みが提供されています。
JSaddle は Haskell から JavaScript の関数を呼ぶための DSL です。Lens インタフェースに対応した JSM モナドが提供されており、GHCJS でコンパイルした場合は単に IO モナドに変換されます。
main :: IO () main = do -- console.log('Hello, JSaddle!'); jsg "console" ^. js1 "log" (val "Hello, JSaddle!")
これら要素技術の簡単な解説に加えて、LT の後半ではライブコーディングのパフォーマンスを披露しました。
作成したのは、簡単なコメントが残せるゲストブックを模した、以下のようなアプリです。バックエンドとして Firebase Realtime DB を利用しているため、複数のブラウザから開いた場合でも書き込みはリアルタイムで同期されます。
前掲のスライドは公開用にソースコードを補足してありますが、当日は文字通り、その場で段階的にコードを追記・変更することで機能が画面に反映されていく様子を紹介しました。
- まず動きのない HTML だけの View をレンダリングする
- ユーザからの入力に反応して Action を発行し、Update で Model に反映する
- Effect を利用してコメントを Realtime DB に保存する
- Subscription を利用して Realtime DB の変更を検知する
LT としてはあまり見ない形式ですが、Twitter 上で見る限り割と好評だったようです。こんな風に、実装の結果が目で見て分かりやすいのはフロントエンドの強みだなと改めて感じました。
（ちなみに @u_taka_23 ではなく @y_taka_23 です）最後は @u_taka_23 さんです！
— オプトテクノロジーズ (@OptTechnologies) May 27, 2019
なんとライブコーディングが始まりました...#FunFunFunctional pic.twitter.com/Yej8v4pG7a
チェシャ猫さんのライブコーディング素晴らしかった #miso #ghcjs #FunFunFunctional
— Yoshihiro503 (@yoshihiro503) May 27, 2019
ところで今回のライブコーディング、ハンズオン形式のチュートリアルとして仕立て直して公開しようかなとも思っているのですが、それはまた別の話。
Docker Meetup Tokyo #28 で Scheduler のカスタマイズについて話してきました
先日行われた Docker Meetup Tokyo #28で、Kubernetes Scheduler の挙動をカスタマイズする方法について発表してきました。
なお Scheduler のカスタマイズについては、つい最近 Kubernetes Meetup Tokyo #16 でも発表しています。ドキュメント類へのリンクも含めてまとめたものが以下の記事です。
両方のスライドを見比べて頂ければ分かる通り、内容としてはオーバラップしている部分がかなりあります。
ただし、前回はあくまでも Scheduling Framework の解説であったのに対し、今回は Scheduler のカスタマイズ全体を俯瞰する形で差別化を図っています。時間的にも前回 5 分に対して今回 9 分とやや余裕があったため、Amazon ECS の binpack 配置戦略やポリシの記述方法など、前回端折った具体的な設定についても少し触れてみました。
ちなみに、スライド中で挙げた 3 種類のカスタマイズ方法それぞれについて、ハンズオン形式で実装しながら学べるチュートリアルを作成するプランもあるのですが、それはまた別の話。
Kubernetes Meetup Tokyo #16 で Scheduling Framework について話してきました
先日行われた Kubernetes Meetup Tokyo #16 で、現在 Scheduling SIG で進められているプロジェクト Scheduling Framework について発表してきました。
Kubernetes では、Pod をどの Node に配置するかを決める手続きをスケジューリングと呼びます。
古典的な Kubernetes の用途、すなわち通常の long-running なサーバ群の管理においては、Pod のスケジューリングは比較的シンプルな問題でした。すなわち、Node の障害時でも可用性が保てるように Pod を複数の Node に散らし、一度立ち上がった Pod は基本的に動き続ける、というシナリオです。
しかし、Kubernetes は既にコンテナスケジューラのデファクトを獲得し、様々な性質を持ったアプリケーションがデプロイされる基盤となりました。この流れの中で、デフォルトの kube-scheduler ではカバーできないような複雑なスケジューリングの需要も生まれています。
この問題を解決するためのプロジェクトが Scheduling Framework です。本記事では、スライドに登場した用語や概念について、Scheduling SIG その他から提供されているドキュメントやサンプルを紹介します。
Scheduling SIG によるサブプロジェクト
kube-batch
kube-batch はバッチ処理向けのスケジューラで、かつて kube-arbitrator と呼ばれていたプロジェクトが改名しました。たった 1 行だけの Wiki が味わい深いです。
PodGroup を指定することで複数の Pod を組にして扱う機能を備えているのが特徴で、この仕組みは Kubernetes を機械学習用基盤として使用する kube-flow プロジェクトにも導入されるようです。
Poseidon
Poseidon は、グラフ理論を利用して複雑かつ効率的なスケジューリングを目指す新機軸のプロジェクトです。
元になっているのは Firmament Scheduler と呼ばれる汎用のタスクスケジューリングの仕組みで、配置の制約を最小費用流問題に帰着させて最適化を行うようです。Kubernetes の Pod と Node に対して Firmament を実装したものが Poseidon という関係になっています。
正直なところ、この記事を書いている時点ではまだ論文を充分読み込んでいないので何とも言えませんが、内容がきちんと把握できたら改めてどこかのイベントで発表したいと思います。
Scheduler Extender
スケジューリング処理の一部分を JSON Webhook で外部サーバに委譲するための仕組みが Extender です。
Extender が設定できる処理は以下の 4 か所で、Scheduler 起動時の設定ファイルに外部サーバのエンドポイントなどを記述することで有効になります。
- Filter - 後段の順序付けフェイズに候補として残す Node を絞ることができます。リクエストはデフォルトのフィルタリングプロセスを通過した Pod、レスポンスはフィルタリング後の Pod です。
- Prioritize - 最良の Node を選択するためのスコアリング関数を追加できます。引数はフィルタリングで残った Pod、レスポンスは Node ごとのスコアです。
- Preempt - Pod の Preemption が発生する際に、犠牲となる Pod を消極的に選択することができます。リクエストは Node ごとに犠牲となる予定の Pod、レスポンスは実際に犠牲にする Pod です。
- Bind - Pod を Node に配置する前の準備などを行うことができます。ただしその場合、Pod と Node を結びつけている
Bindingリソースの作成まで含めて自分で行う必要があります。Pod の情報と Node 名がリクエストされます。
なお、上記のドキュメントは古いためか Preempt Extender の記載がありませんが、ソースコードを見ると実装されていて実際に動きます。
もし Extender を使用したい場合は、ドキュメントよりもむしろ、構造体の定義および @everpeace さんによる実装サンプルを参考にするとよいでしょう。
Scheduling Framework
Scheduling Framework のプロポーザルです。今回のスライドは基本的にこのプロポーザルに沿って説明しています。
上でも挙げたような特定用途のために作られたスケジューラは、基本的にスクラッチから開発されています。というのも kube-scheduler の実装は歴史的事情から抽象化が十分でなく、拡張性に限界があるためです。
そこで、Scheduling Framework では設計を刷新して新しい拡張点を定式化します。それぞれの拡張点では、Go のインタフェースとして実装されたプラグインを登録し処理を差し込めるようにするとともに、プラグイン同士が情報をやり取りできる仕組みが構築される予定です。
そう、あくまでも予定です。 プロポーザルには多数の拡張点が述べられていますが、現状で以下の二点のみ実装されています。
- Reserve - Node が確定した後、Pod ごとの goroutine が生成される前
- Pre-Bind - Pod ごとの goroutine に入った後、API Server に Binding が登録される前
この二点は、Pod を配置する Node に前もって何かを準備する処理を想定したもので、典型的な用途はネットワークストレージをボリュームとして確保するというものです。
従来、ボリュームの確保とバインドは assumeVolume と bindVolume という専用の関数で行われています。一方 GPU などボリューム以外のネットワークリソースについてはユーザが Bind Extender という形で各自実装する必要があります。
そこで、assumeVolume に相当するものとして Reserve プラグインを、bindVolume に相当するものとして Pre-Bind プラグインを実装し、リソース関連の処理を統合して抽象化することが Scheduling Framework の第一弾として意図されていました。が、今のところ拡張点が準備されただけで止まっており、assumeVolume も bindVolume もそのまま残っています。まあ、今後の展開を見守りましょう……。
まとめ
本記事では、Kubernetes スケジューラの再設計を目的としたプロジェクト Scheduling Framework と、その周辺トピックについて紹介しました。Scheduling SIG のマンパワー不足もあって、当初の予定ほど華々しい進展が見られないのは残念ですが、それはまた別の話。
