チェシャ猫の消滅定理

数学にプログラミング、素敵なもの何もかも。

2019 年のスライド一挙公開、あるいは 2020 年の方針

あけましておめでとうございます。2019 年は大変お世話になりました。2020 年も張り切っていきましょう。

さて、2019 年には結構な回数の外部発表を行いました。これらの発表内容のうち一部は単独のブログ記事としてまとめてありますが、機を逸してしまって記事化されていないものも相当数あります。そこで本記事では、2019 年中に行った発表を一覧としてまとめてみました。

2019 年の活動実績

2019 年の登壇は全部で 19 件でした。うち（先着や抽選ではなく）CFP に応募して採択されたものは 4 件です。

チェシャ猫が普段活動している領域は、Twitter の Bio にも書いてある通り、大きく「Kubernetes」「Haskell」「形式手法」の三つのカテゴリに分かれています。このカテゴリで登壇内容を分類したところ、以下のようになりました。

CloudNative に関わるもの（12 件）

CloudNative 技術に関しては 12 件の発表を行いました。ほとんどが Kubernetes のスケジューリングをテーマにしています。

この分野は勉強が活発に行われており LT の機会も多かったため、LT で単発の新機能を紹介し、長尺の発表ではそれらの諸機能を体系的にまとめて解説する、という構図になっています。特に Kubernetes Meetup Tokyo で顕著ですが、LT の倍率が高いので運頼みになりがちだったりします。

関数型プログラミングに関わるもの（4 件）

関数型プログラミングに関しては、Haskell および Elm をテーマとして 2 件ずつ計 4 件の発表を行いました。Haskell の 2 件は AltJS である GHCJS を取り上げているため、Elm も含めて 4 件すべてが Web フロントエンドに関する発表ということになります。

形式手法に関わるもの（2 件）

形式手法に関しては、モデル検査と定理証明それぞれ 1 件ずつの発表を行いました。件数としては少ないですが、両者はいずれも CFP 審査を通過して採択されており、かつ持ち時間もそれぞれ 60 分、45 分と長めの発表です。

関連して、いくつかの会社でモデル検査器のハンズオンを開催しました。ツールとしては Alloy を使用し、2 時間ずつ 2 回、計 4 時間で一通りの使い方を学ぶコースです。内容については Pixiv 社の shimashima さんが記事にしてくださっています。

inside.pixiv.blog

本来であればもう少しちゃんとパッケージ化して募集するところではありますが、もし今この記事を読んで興味を持った方がいらっしゃいましたら、ぜひご連絡いただければ幸いです。

その他（1 件）

上記のどのカテゴリにも該当しませんが、型による値レベルの制約を TypeScript で実現する話です。強いていうなら関数型プログラミングが近いかもしれません。

2019 年のスライド一覧

猫でもわかる Scheduling Framework

Kubernetes Meetup Tokyo #16 での発表です。

Kubernetes の Scheduler の拡張点をインタフェースとして切り出し、実行速度を保ったままプラガビリティを提供するためのプロジェクト Scheduling Framework について解説しました。

この発表を行った時点ではごく一部しか実装されておらず、まだまだ先が長そうな印象でしたが、最新の v1.17 ではかなり進展し、既存の kube-scheduler の実装を Framework として置き換える作業も進んでいます。

ccvanishing.hateblo.jp

君だけの最強 Scheduler を作ろう！

Docker Meetup Tokyo #28 での発表です。

Kubernetes の Scheduler をカスタマイズするための方法を複数挙げ、それぞれの守備範囲について解説しました。

上で触れた Scheduling Framework の他にも、もともと kube-scheduler に備わっているポリシーの指定方法や、Webhook として実装する Extender についても触れています。

ccvanishing.hateblo.jp

明日、業務で使える Scheduler Extender

Cloud Native Meetup Tokyo #7 での発表です。

これまでと同じく Kubernetes の Scheduler カスタマイズをテーマに据えていますが、この発表では Extender に焦点を絞り、4 箇所あるそれぞれの各頂点でどのような設定が可能なのかについて解説しています。

なお、スライド中で「実行中の Job が Preemption で中断される問題」について言及していますが、後になって Extender 以外にも Preempting を抑制する機能として PreemptingPolicy の設定が導入されました。これについては Docker Meetup Tokyo #31 で触れています。

雲の世界の共通語 CloudEvents って何？

Cloud Native Developer JP #11 での発表です。

Event-driven なアーキテクチャは Serverless 界隈でよくみられますが、その仕様は各ベンダごとにバラバラで相互運用性がありません。この問題を解決するために、イベント仕様の規格策定を目指す CNCF プロジェクト CloudEvents について概要を解説しました。

ちなみに CloudEvents 自体その後も継続してバージョンアップが行われており、Knative や Argo CD などが新しいバージョンに対応しているようです。

サンプルで学ぶ The Elm Architecture

Meguro.es #21 での発表です。なお、上に貼ったスライドは別イベントの際のものですが、内容の大筋は共通しています。

ミニマルなカウンタアプリを例として、The Elm Architecture と呼ばれる状態管理の仕組み、および外部 JavaScript ライブラリとの連携について解説しています。

GHCJS Miso による Haskell + Firebase 10 分間クッキング

Fun Fun Functional #1 での発表です。

GHCJS を使用すると、Haskell のソースコードを JavaScript にコンパイルしてブラウザ上で動かすことができます。この発表ではさらに Elm 風のアーキテクチャを持つフレームワーク Miso および JavaScript 呼び出しのための DSL である JSaddle を使用して、Firebase Realtime DB をバックエンドとした簡単なチャットアプリをライブコーディングで実装しました。

ccvanishing.hateblo.jp

Kubernetes v1.15 の新機能で Preemption を制御せよ

Docker Meetup Tokyo #31 での発表です。

Kubernetes には、Node のリソースに余裕がないときに優先度の高い Pod が作成された場合、すでに稼働している優先度の低い Pod の立ち退かせてリソースを確保する機能が備わっており、この機能は Preemption と呼ばれます。

Preemption はクラスタのリソース効率を高める上では重要ですが、同時に実行中の Job が中断されて途中結果が失われる可能性を含んでいます。この問題を解決するため、v1.15 では Preemption を抑制するための PreemptingPolicy と呼ばれる設定項目が導入されました。

ccvanishing.hateblo.jp

そのコンテナ、もっと「賢く」置けますよ？

CloudNative Days Tokyo 2019 での発表です。

Kubernetes の Scheduler に関して包括的に解説を行なっています。内容としてはそれまでに LT 等で触れたものがほとんどで新規性はありませんが、スケジューラについてあまり知らない人であってもこのスライドの内容を抑えれば一通りの知識が得られるよう、スケジューラの役割から始まって、大枠から徐々に解像度を上げることで学習曲線が緩やかになるように構成が工夫してあります。

ccvanishing.hateblo.jp

CircleCI + Kind による Kubetentes E2E テスト

CircleCI Community Meetup LT 大会 での発表です。

Kind は、Kubernetes の Node をコンテナ化することで、マルチノードクラスタをローカルで簡単に立ち上げられるようにするツールです。要するにコンテナが動く環境ならどこでも使い捨ての Kuberentes クラスタを作成することができるわけで、発表中ではこの Kind を CircleCI 上で起動させて E2E テストを行う方法を解説しました。

形式手法による分散システムの検証

builderscon tokyo 2019 での発表です。

例えば決済処理がマイクロサービスに分割されている場合、複数のサービスに対して整合性を保ったままコマンドを発行するには工夫が必要です。この発表では一つの手法として TCC (Try-Confirm/Cancel) パターンを取り上げ、TLA+ を用いたモデリングと検査について解説しています。

余談ですが、この発表はタイムテーブル的に超人気セッションの裏番組になってしまい、集客が厳しかったです。こちらを聞いてくれた方の反応は割と好意的だったので、内容自体はよかったと信じたい。

TypeScript における型レベルバリデーション

We Are JavaScripters! @36th での発表です。

TypeScript は構造的部分型を持つため、一部の型引数を使用せず捨てる、いわゆる幽霊型を作成しようとしてもコンパイル時にチェックが効きません。そこで、区別したい型ごとに異なるフィールドを持たせた Branded Type を利用する方法を解説しています。

Kind で量産する使い捨て Kubernetes

CI/CD Test Night #5 での発表です。

CircleCI Community Meetup と同じく Kind を利用した E2E テストに関する発表ですが、今回はイベントの趣旨に合わせて「CI を Kubernetes で行う場合にどうやってクラスタを準備するか」という視点から解説しています。

従来、CI 用に Kubernetes クラスタが必要な場合、選択肢は「Pull Request ごとに Namespace を作成」もしくは「Pull Request ごとにマネージドクラスタを振り出し」のいずれかでしたが、Kind の登場により、簡単にクラスタを立ち上げて使い捨てることが可能になりました。

ライブで学ぶ The Elm Architecture

Meguro.es #23 での発表で、Meguro.es #21 の続編のような形になっています。

内容自体は前回と似ており、簡単なチャットアプリで The Elm Architecture の仕組みを説明しています。ただし今回は単に図解するだけでなく、ライブコーディングの要領でその場で一つづつ機能を追加していくことで、各動作がどのように実装されるのかについて順を追って解説しました。

GHCJS による Web フロントエンド開発

Haskell Day 2019 での発表です。

内容は Fun Fun Functional #1 での発表をよりリッチにしたものです。Firebase Realtime DB によるリアルタイムチャット機能に加えて Firebase Authentication を使用した Google ログインを提供し、会場にいた参加者にその場で書き込んでもらうデモを行いました。デモで使用したアプリケーションは以下に公開されています。

github.com

賢く「散らす」ための Topology Spread Constraints

Kubernetes Meetup Tokyo #25 での発表です。

この発表では、Kubernetes v1.16 でアルファ機能となった Topology Spread Constraints を取り上げました。複数の Node に Pod が分散している状況であっても、それらの Node が同じ Availability Zone やラックにホスティングされていた場合、障害により Pod が全滅する可能性があります。この問題を解決するため、Topology Spread では Node に Label を付与してグループ化し、そのグループ単位での Pod の分散方法を指定することができます。

CloudNative を学ぶにはまず KInd より始めよ

CloudNative Developer JP #13 での発表です。

ここまでにも何度か取り上げている Kind と、Topology Spread Constraints を組み合わせて発表しました。Topology Spread Constraints は実はかなりピーキーな機能で、設定を誤ると条件を満たす Node が見つからずに Pod が配置できない状態に陥ることがあります。ローカルに Kind で Kubernetes クラスタを作成した上でこの問題を実際に再現し、さらに修正するデモを行いました。

テスト駆動開発から証明駆動開発へ

July Tech Festa 2019 での発表です。

builderscon tokyo 2019 では TLA+ によるモデル検査を扱いましたが、こちらのテーマは定理証明です。

前半では builderscon と同様、通常のテストと分散システムとの相性の悪さについて述べ、分散システムに用いられるカオスエンジニアリングと対比する形で形式手法の考え方を導入します。また後半では、Curry-Howard 対応について触れたあと、Coq とそのフレームワークである Verdi を使用して分散システムを証明する仕組みを概説しています。

kube-batch による Gang Scheduling

Kubernetes Invitational Meetup Tokyo #4 での発表です。

複数の Pod が通信し合って実行を進めるような Job をデプロイする場合、一部の Pod だけが先に配置された状態で Node のリソースを使い切ってしまうと、後続の Pod が配置できずにデッドロックに陥ることがあります。これを防ぐため、特定のグループに属する Pod を一度に全て配置するか、あるいは全て Pending のまま留めるかという All of Nothing の配置戦略を Gand Scheduling あるいは CoScheduling と呼びます。

今回紹介した kube-batch は Gang Scheduling を実現する特殊スケジューラの一種です。Gang Scheduling 以外にも、複数のキューを定義してクラスタのリソースをキュー間で均等に配分するなどの機能が提供されています。

「詰める」と「散らす」の動力学

OpenShift.Run 2019 での発表です。

内容としては CloudNative Days Tokyo 2019 を元にした上で、いくつかの要素を追加して再構成しています。特に、CloudNative Days Tokyo 2019 時点では実装されていなかった Topology Spread Constraints への言及が追加されていますが、これは Pod の分散戦略を考える上で非常に重要な要素です。

ccvanishing.hateblo.jp

2020 年の方針

さほど具体的になっているわけではありませんが、今後の展開についていくつか考えていることがあるので、振り返りのついでにここで表明しておきたいと思います。

カテゴリ間の連携

冒頭で述べた通り、現在のチェシャ猫の活動カテゴリは「Kubernetes を中心とした CloudNative 技術」「Haskell をはじめとする関数型プログラミング」「形式手法、特にモデル検査」の三つに分かれています。しかし残念なことに、現状それぞれのカテゴリでそれぞれ登壇するに留まっており、複数カテゴリを扱っていることがうまく活かせていません。

そこで 2020 年は、これらの知見をうまくつなぎ合わせることを目標にしたいと思います。三つのうち関数型プログラミングと形式手法は比較的近い分野ですが、これらと CloudNative を組み合わせようとする人はあまり見ないため、独自色が出せる部分なのではないかと睨んでいます。

より具体的には、「CloudNative + 形式手法」の組み合わせでもう少し面白いことができないかを検討中です。あるいはその過程で定理証明を採用することになれば、おそらくは Extraction の関係で実装には関数型プログラミング言語を使用することになるでしょう。いずれにせよ、複数カテゴリを横断したネタを作るのが目標です。

登壇以外の活動の充実

2019 年の活動は登壇に偏りすぎました。

今回並べた 19 件のスライドには、他に日本語情報が存在しないようなトピックも相当量含まれており、それなりに価値があるものだと自負しています。しかしブログのような散文と比較したとき、登壇スライドに載せられる（あるいは載せるべき）情報量はどうしても限られており、また検索性にも乏しいことから、インターネット上に蓄積される情報源としてはどうしても劣ります。

また、登壇だけにエフォートを割いていると、結局のところ「単に新しい情報を発掘してきて解説する人」になりがちで、自分自身、居心地の悪さを感じることが少なくありませんでした。少し前に Qiita で話題になった「Web エンジニア業界に感じた違和感」とも共通するものがあります。

そこで 2020 年は、もう少し実務的な取り組みに力を入れたいと思います。より具体的には、kubernetes/kuberetens をはじめとする OSS へのソースコード貢献を継続的に行うのが目標です。また、登壇した際にはスライド公開に加えて、扱った要素技術について、ある程度踏み込んだ解説を参照可能な形でブログに記録しておきたいところです。

海外カンファレンスでの登壇

読んで字の如く、一度はやってみたい海外登壇です。まったくノープランですが、とりあえず出せそうなカンファレンスを見つけるところから始めたいと思います。

まとめ

本記事では、2019 年に行った計 19 回の外部発表について、スライド公開までで終わっていてブログ化されていなかったものも含め、簡単な解説を付けて一覧にしました。

さらに 2020 年の活動方針として「CloudNative と形式手法の統合を狙うこと」「登壇以外の活動にも力を入れること」「海外カンファレンスで登壇すること」の三つを設定しました。

ここで設定した 2020 年の目標が果たして達成されるのか、判明するのはまた 1 年先ですが、それはまた別の話。

OpenShift.run 2019 で Kubernetes のスケジューリングについて話してきました

先日行われた OpenShift コミュニティのイベント OpenShift.run 2019 にて、Kubernetes Scheduler とその関連ツールについて講演してきました。公募 CFP 枠です。

OpenShift のイベントでありながら、OpenShift についてはまったく触れずひたすら Kubernetes の内部実装を解説する異色の登壇でした。実際、40 分枠の講演の中で（RedHat 社以外も含め）ベンダニュートラルな立場で登壇したのは自分だけだったようです。これは私見ですが、逆に言えばそういう内容でも CFP 採択されているというのは、運営側も「単なるマーケティングイベントにしない」というスタンスなのかなと思います。

なお今回の発表は、CloudNative Days Tokyo 2019 での講演が元になっています。こちらについては参考文献や当日出た質問など補足情報を含めて以下の記事で扱っているので、今回のスライドと一緒に読むとより理解が深まるはずです。

ccvanishing.hateblo.jp

CloudNative Days Tokyo 2019 からのアップデート

見比べていただければわかる通り、今回のスライドは図解などかなりの部分を前回から引き続き使用していますが、各ツール・機能を紹介する順番など全体の構成がやや異なります。これはプレゼンのテーマ性をより強く押し出し、Scheduler の仕組みを学ぶ上での動機を強調するためです。

また、CloudNative Days Tokyo 2019 は 7 月の開催だったため、それから 五ヶ月の間に Kubernetes 自体にもいくつか進展が見られます。

キーワード「詰める」と「散らす」

前回の発表ではモチベーションの部分を特に述べることなくいきなりスケジューリングの話に入りました。これに対して今回は、タイトルにもある通りサーバ上にコンテナを「詰める」と「散らす」という二つのキーワードを設定しています。その上で、両者のバランスを考える上で「戦略」が必要であり、戦略のためには「仕組みへの理解」が必須なのだ、という導入です。

これはある意味では OpenShift の考え方、すなわち Kubernetes とそれにまつわる Image 管理などのエコシステムをラップする考え方、とはやや方向性が異なるものです。冒頭で自分だけ非ベンダ所属だという件を書きましたが、こちらの点でも異色な印象を与えたかもしれません。

今回のプレゼン自体の戦略を別にしても、「仕組みの理解」は自分自身が技術と向き合う際に重視している観点でもあります。「なんか知らんがよしなに動く」という表面的な事象に対して、「実は裏側には色々な仕組みがあり、それらは知るに値するのだ」というチェシャ猫の哲学を感じ取っていただけたなら幸いです。

Pod の Topology Spread Constraints

完全な新規要素として、Kubernetes v1.16 でアルファ機能として導入された Topology Spread Constraints について追加しました。

Topology Spread は、ユーザ側で Node に Label を付与することで故障ドメインを表現し、Pod の配置の際に故障ドメインをまたいだ分散を考慮することができる機能です。Kubernetes Meetup Tokyo 第 25 回でも登壇したので合わせてご参照ください。

今回は OpenShift のイベントでオンプレ運用勢が多いだろうという予測のもと、発表の際には口頭でラック障害についてちょっと触れたりもしています。

Scheduling Framework

Scheduling Framework は、Kubernetes 本体の実装の中でスケジューリングアルゴリズムの一部を interface として定義することで、レイテンシを維持したまま拡張性を提供するためのプロジェクトです。前回の発表のときは大した内容がなかったのでカットしましたが、時間経過によって重要性が増してきたと思われるので、今回はほんの 1 ページですが触れることにしました。

特に Kubernetes v1.17 では、既存の kube-scheduler の実装を Scheduling Framework のプラグインとして移植する試みが進められています。CHANGELOG では [migration phase 1]と呼ばれている項目です。

まとめ

今回は OpenShift.Run 2019 でプロポーザルが採択され、Kubernetes のスケジューリングについて、CloudNative Day Tokyo 2019 の講演を再構成する形でお話ししました。「スライド使い回しじゃん」という懸念もちょっと頭をよぎったのですが、前回とは参加者のクラスタが異なることもあり、Twitter で観測した限りでは会場の反応は概ね好評だったようです。

ところで、今回紹介した Scheduling Framework には Wait および Permit という「合図が来るまで配置を保留」という機能がありますね？ 一方で、数日前に別のイベントで「Pod の配置を保留するために kube-batch が開発されている」という説明をしています。それぞれについては語るべきポイントがあるのですが、それはまた別の話。

状態機械を合成してデッドロックを検出できる Go 言語パッケージを作ってみました

はじめに

マルチスレッドで動作するプログラムの設計は難しい問題です。個々のスレッドの動作は単純に見えても、複数が並行して動作する場合の動作は組み合わせ論的に複雑になります。また、タイミングに依存する不具合は狙って再現することが難しく、通常の単体テストによる検出にも限界があります。

そんなとき、有効な手法がモデル検査です。システムの取りうる状態をあらかじめ網羅的に探索することで、「実際に動作させた際にごく低い確率で踏むバグ」であっても、動作させることなく設計段階で発見することが可能になります。

ところでちょうど先日、デッドロック発見器を自作するハンズオンに参加する機会がありました。内容は非常にシンプルなモデル検査器を実装するというもので、せっかくなのでそのときの成果物を Go のパッケージとしてまとめたものを以下に公開しました。

github.com

以下、このパッケージで何ができるのかを具体例とともに紹介します。

例 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 に値を取ることができる変数を共有しており、この変数を書き換えることで処理を行っています。ここでは哲学者を複数配置することを考えて、哲学者を識別する番号と左右のフォークを表す変数をパラメータとして与えられるようにしてあります。

定義されている遷移規則を読み下すと、個々の哲学者は以下のように動作することが主張されています。

  1. 実行は状態 0 からスタート
  2. 自分の左側のフォークを表す変数 left の値が 0 なら、誰にも占有されていないと判断し、そこに自分の番号を代入して状態 1 に移行
  3. 同様に右側のフォーク right も確保して状態 2 に移行
  4. 取った時とは逆順で、右側のフォークの占有を解除するために 0 を代入して状態 3 に移行
  5. 残った左側のフォークも占有を解除して初期状態 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 が順序不定になっている関係で、出力は実行ごとに若干異なる可能性があります。

f:id:y_taka_23:20191104032903p:plain:w150
哲学者が一人の場合の状態遷移

各時点でプロセスがいる状態と変数の値が図示されています。青い部分が初期状態で、意図した通り、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 から見たフォークとは左右が逆になっています。

f:id:y_taka_23:20191104034227p:plain:w200
哲学者が二人いるとデッドロックする

同じようにして図示させてみると、デッドロックを表す赤い状態とそこへのエラートレース（のうち最初に見つけたもの）が表示されます。初期状態から 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"))
    }

f:id:y_taka_23:20191104035335p:plain:w200
一旦フォークを置くとデッドロックしない

追加された 2 行は「状態 1、すなわち左側のフォークを確保した時点で、もし右側のフォークが占有中であれば、確保した左側のフォークを一旦解放して戻る」という規則を表現しています。結果を図示してみると赤い状態がなくなっており、先ほどのデッドロックが解消したことがわかります。

なおこの修正を入れた場合であっても、すべての哲学者が「左側のフォークを確保」「右側のフォークが確保できないのでやり直し」だけを繰り返す、いわゆるライブロックの問題は解決していません。ライブロックの不在を保証する活性の検査は、現状スコープ外です。

例 2: 排他制御

先ほどの哲学者は二本のフォークで食事した後で最初に戻って無限にループしていましたが、今度は停止するタイプのプロセスを書いてみましょう。サンプルコードはこちらです。

二つのプロセスが一つのグローバル変数を共有していて、それぞれのプロセスはこの変数を 1 だけインクリメントするとします。より具体的には、各プロセスは次のように動作します。

  1. グローバル変数の値をローカル変数に読み込む
  2. ローカル変数の値をインクリメント
  3. ローカル変数の値をグローバル変数に書き戻す

コードは以下のようになります。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"))

得られた図が以下です。受理状態は二重丸として表現されており、出て行く遷移がないにも関わらず赤く表示されてはいません。

f:id:y_taka_23:20191104150814p:plain:w400
書き込みの競合

図中には三つの受理状態がありますが、よく見ると最終的に 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"))

f:id:y_taka_23:20191104152601p:plain:w200
ミューテックスによる競合の防止

動作の最初でロックを取得し、最後に解放する動作を追加しています。表示された図の受理状態ではいずれも var = 2 となっており、各プロセスがread、incr、write の遷移を連続して割り込まれることなく実行していることがわかります。

例 3: 生産者・消費者問題

今度はもう少し複雑な動作をモデリングしてみましょう。

二つのプロセス「生産者」と「消費者」がキューを挟んで接続されている状況を考えます。生産者がキューに要素を詰めるプロセス、消費者はそれを取り出すプロセスです。

キューが容量いっぱいの時、生産者は要素の生成をブロックされます。逆に消費者は、キューが空の場合には要素が取り出せないためブロックされます。ただし、単にブロックされているのではなく、待ち状態に移行して待機するとします。

この待ち状態は、条件変数に送られるシグナルを検知することで解除されます。つまり、生産者は「キューから要素が取り出され空きができた」という条件変数、消費者は「キューに要素が投入された」という条件変数をそれぞれ監視します。

より具体的には、生産者は以下のように動作します。

  1. まずキューにアクセスするためにロックを取得
  2. キューを確認し、容量に空きがなければロックを解放して待ち状態に入る
  3. 待ち状態では条件変数へのシグナルを待ち、受信したら最初に戻る
  4. キュー容量に空きがあった場合、要素を一つ追加
  5. 条件変数にシグナルを送り、消費者が待ち状態にいれば起動させる
  6. キューに対するロックを解放し、最初に戻る

同様に、消費者は以下のように動作します。

  1. まずキューにアクセスするためにロックを取得
  2. キューを確認し、一つも要素がなければロックを解放して待ち状態に入る
  3. 待ち状態では条件変数へのシグナルを待ち、受信したら最初に戻る
  4. キューに要素が存在した場合、その要素を一つ削除
  5. 条件変数にシグナルを送り、生産者が待ち状態にいれば起動させる
  6. キューに対するロックを解放し、最初に戻る

これをそのまま実装したソースコードは次のようになります。

  • キュー内の要素の個数: 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 が、連続して発生するとは限らないことに注意してください。この二動作の間に、相手プロセスから割り込まれる可能性があります。

f:id:y_taka_23:20191105023052p:plain:w500
デッドロックする生産者と消費者

検査した結果が上の図です。例えば右のほうのデッドロックに至る経緯を観察すると、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"))
}

f:id:y_taka_23:20191105024214p:plain:w400
不可分な遷移によるデッドロックの解消

まとめ

以上、Go 言語でグローバル変数を共有した複数の状態機械を定義し、並行動作させた場合に生じうるデッドロックを検出するデモを紹介しました。トイモデルではありますが、これだけでも意外と色々なものが実装できて、遷移グラフを描いてみると割と面白い結果が出ます。よかったら遊んでみて、もし気に入ったらスターを付けてやってください。

github.com

実際にはまだ色々直したいところはあって、

  • 最初の n 個のデッドロック状態を発見した時点で探索を打ち切る
  • デッドロック以外にもユーザが与えたアサーションに対する違反を検出する
  • 結果表示の見た目をオプションで変更できるようにする
  • 状態のハッシュ値を使いまわすことで、内部の無駄な計算を削る

など、時間を見つけて改良したいと思っていますが、それはまた別の話。

CloudNative Days Tokyo 2019 登壇こぼれ話 #CNDT2019

先日行われた CloudNative Days Tokyo 2019 で、Kubernetes のスケジューリングについて発表してきました。公募 CFP 枠です。

www.youtube.com

今回の発表は、実は技術的に目新しい内容をほとんど含んでいません。各トピックは今までいくつかの勉強会で LT として発表しているものがほとんどです。

ただし、普段の発表では時間が短いこともあって断片的になりがちだった内容を 40 分の枠で再構成し、スケジューリングについて初めて聞く人にとっても入り口のギャップを少なく、できるだけ学習曲線がなだらかになるようにすることを念頭に置いてプレゼンを組み立てました。

当日の Twitter でも「これはわかりやすい」という反応を複数の方からもらっているので、狙いとしてはある程度成功したんじゃないかと思っています。

当日の質問に関して

Twitter から #CNDT2019 と #RoomG のタグで拾った反応です。いくつかコメントがつけられそうなものがあったので、当日の内容の補足を兼ねて以下に述べます。

スライドの流れだとちょっと語弊があったかもしれません。「スケジューリングの要件はPod の用途によって異なる」ことの例として二種類のポリシーについて述べましたが、実際に（デフォルトの状態で）Deployment による Pod と Job による Pod でポリシーが内部的に切り替わるわけではありません。ポリシはあくまでも発表中に述べたように policy.cfg で定義します。

ちなみに過去には --algorithm-provider という実行時フラグで LeastRequestedPriority と MostRequestedPriority とを選択する機能（ソースコード）がありましたが、すでに非推奨になっています。

特に目新しい仕組みがあるわけではありません。普通に Scheduler 自身が NodeInformer を介して API Server にアクセスして（ソースコード）情報を取得しています。おおむね kubectl describe nodes で取れる情報と同じです。

はい、現状では VPA は Pod を一度 evict し、その後 Resource Request が調整された Pod が新規に再作成されます。evict を行わない、いわゆる in-place な request は現在検討段階で、KubeCon EU 2019 でもいくつか発表がありました。

Descheduler は Scheduler の機能ではなく、独立した単体のコマンドラインツールです。動作は単純で、一回実行するとその時点で条件に違反している Pod を検出して evict して終わりです。逆に言えば、継続してクラスタの状態を調整し続けたいのであれば、例えば CronJob にするなど、他の仕組みと組み合わせる必要があります。

参考文献

スケジューラのアーキテクチャ

Kubernetes 全体

スケジューラのアルゴリズム

カスタムポリシー設定

フィードバックとリソース効率

Preemption

Vertical Pod Autoscaler

Descheduler

広がるスケジューラの世界

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 のリリースノートの完全な解説については以下の記事を参照してください。

ccvanishing.hateblo.jp

参考資料

Scheduler 一般

Priority と Preemption

Scheduling Framework

余談

思えば 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 をフォークすることによって開発されています。

github.com

Miso は GHCJS 上で The Elm Architecture を実装するためのフレームワークです。Miso では事実上サーバサイドで書けない Elm と異なり、サーバサイドとの Model の共有や、初回アクセス時の HTML をサーバ側で構築するサーバサイドレンダリング (SSR) の仕組みが提供されています。

github.com

ccvanishing.hateblo.jp

JSaddle は Haskell から JavaScript の関数を呼ぶための DSL です。Lens インタフェースに対応した JSM モナドが提供されており、GHCJS でコンパイルした場合は単に IO モナドに変換されます。

main :: IO ()
main = do
    -- console.log('Hello, JSaddle!');
    jsg "console" ^. js1 "log" (val "Hello, JSaddle!")

github.com

これら要素技術の簡単な解説に加えて、LT の後半ではライブコーディングのパフォーマンスを披露しました。

作成したのは、簡単なコメントが残せるゲストブックを模した、以下のようなアプリです。バックエンドとして Firebase Realtime DB を利用しているため、複数のブラウザから開いた場合でも書き込みはリアルタイムで同期されます。

f:id:y_taka_23:20190529193951p:plain

前掲のスライドは公開用にソースコードを補足してありますが、当日は文字通り、その場で段階的にコードを追記・変更することで機能が画面に反映されていく様子を紹介しました。

  1. まず動きのない HTML だけの View をレンダリングする
  2. ユーザからの入力に反応して Action を発行し、Update で Model に反映する
  3. Effect を利用してコメントを Realtime DB に保存する
  4. Subscription を利用して Realtime DB の変更を検知する

LT としてはあまり見ない形式ですが、Twitter 上で見る限り割と好評だったようです。こんな風に、実装の結果が目で見て分かりやすいのはフロントエンドの強みだなと改めて感じました。

（ちなみに @u_taka_23 ではなく @y_taka_23 です）

ところで今回のライブコーディング、ハンズオン形式のチュートリアルとして仕立て直して公開しようかなとも思っているのですが、それはまた別の話。