Kubernetes 1.13: SIG Scheduling の変更内容
はじめに
本記事では、Kubernetes 1.13 の CHANGELOG からスケジューリングに関する内容をまとめました。
主な変更点
1.13 における SIG Scheduling の取り組みは主に安定性に焦点を当てており、いくつかの大きな機能の導入は次のバージョンまで延期することになりました。特記すべき変更として次に挙げる 2 点があります。
#69824: Taint based Eviction の有効化
TaintBasedEvictions
がベータに移行し、デフォルトで有効になりました。この機能が有効になっている場合、Node には自動的に条件 Taint が付加され、Pod は必要であれば Toleration を使用することができます。
Taint based eviction は、Node に問題が発生した際、その内容に応じて Node Controller が以下のような Taint を自動的に付加する仕組みです。
node.kubernetes.io/not-ready
node.kubernetes.io/unreachable
node.kubernetes.io/out-of-disk
node.kubernetes.io/memory-pressure
node.kubernetes.io/disk-pressure
node.kubernetes.io/network-unavailable
node.kubernetes.io/unschedulable
node.cloudprovider.kubernetes.io/uninitialized
今まで Pod のスケジューリングには「Not Ready な Node を避ける」といったロジックが入っていました。1.13 からこの TaintBasedEvictions
がデフォルトで有効になったことにより、障害時の Pod 退避は Taint による管理に統一されます。
Taint と Tolaration によるスケジューリングに統一されることで、Node 障害時の挙動をユーザがより柔軟にコントロールできるようになります。例えば Pod に tolerationSeconds
を指定することで「Node に問題 X が発生した際は n 秒以内に回復しなければ移動」といった挙動の調整が可能です。
tolerations: - key: "node.kubernetes.io/unreachable" operator: "Exists" effect: "NoExecute" tolerationSeconds: 6000
ちなみに、tolerationSeconds
が設定されていない場合、Admission Control により not-ready
と unreachable
に 300 秒の tolerationSeconds
が設定されます。要するに何も設定していない場合は Node の障害から最大 300 秒待って Pod が削除される、ということです。
#70298: critical-pod
アノテーションが非推奨に
Pod に対するクリティカルアノテーションが非推奨になりました。アノテーションの代わりに Pod の優先度を使用すべきです。
DNS や Metrics Server といった死なれるとクラスタ全体の動作に影響するような Pod のために、従来 scheduler.alpha.kubernetes.io/critical-pod
というアノテーションが用意されていましたが、今回から非推奨になりました。
代わりに、デフォルトで定義されている優先度クラス system-cluster-critical
と system-node-critical
を使用します。両者の定義は以下のようになっており、Node の移動が許容できるかどうかで用途が分かれています。
Name: system-cluster-critical Value: 2000000000 GlobalDefault: false Description: Used for system critical pods that must run in the cluster, but can be moved to another node if necessary. Annotations: <none> Events: <none> --- Name: system-node-critical Value: 2000001000 GlobalDefault: false Description: Used for system critical pods that must not be moved from their current node. Annotations: <none> Events: <none>
ただしこれらの優先度クラスは、1.11 以降 kube-system
Namespace 内でしか使えないことに注意が必要です。
- https://kubernetes.io/docs/tasks/administer-cluster/guaranteed-scheduling-critical-addon-pods/
- https://kubernetes.io/docs/concepts/configuration/pod-priority-preemption/
また、この件とは直接関係しませんが、優先度による Preemption の動作原理については半年ほど前に書いた記事があるのでよければこちらもご笑覧ください。
#70040: 要対応
1.13 では kube-scheduler の設定ファイルの
apiVersion
がcomponentconfig/v1alpha1
ではなくkubescheduler.config.k8s.io/v1alpha1
になります。
API グループ componentconfig
は解体されつつあり、Scheduler 以外にも例えば kubeproxy.config.k8s.io
が 1.9 から導入されています。
しかし、そもそもこの設定ファイルの書式はドキュメントに記載されていないし、サンプルファイルのようなものも提供されていません。対応する構造体が以下に定義されているので、ファイルの記載項目を確認することは一応可能です。
SIG Scheduling リリースノート
メトリクス追加を除き、内部ロジックの修正のみです。
#59529
ボリュームをスケジューリングする操作にメトリクスが追加されました。
以下のメトリクスが登録されるようになっています。
binder_cache_requests_total
scheduling_duration_seconds
scheduling_stage_error_total
#65350
Toleration を含む大量の Pod を処理する際のメモリ使用量とパフォーマンスが向上しました。
#69758
ゾーン内の Node がすべて削除された際、スケジューラが無限ループに陥るバグを修正しました。
#71212
Pod のバインディングでエラーが発生した際、古いキャッシュが使用されないよう削除するようにしました。
#71063
スケジューラ内部のキャッシュが不整合になった際、panic になる挙動を修正しました。
#71085
kube-scheduler のリーダ選出がデッドロックに陥った際、unhealthy を報告するようになりました。
#70898
必要のない Pod まで preemption してしまう潜在的なバグを修正しました。
まとめ
ユーザ側にとってさほど大きな変更点はありませんが、これまで Pod の優先度を導入しないまま運用していた場合、critical-pod
アノテーションの件で影響を受ける可能性があります。まだ非推奨になっただけで廃止ではありませんが、早めに変更しておきましょう。
なお、このところ機能追加という意味では SIG Scheduling はやや低調で、実際マンパワーが足りていない印象がありますが、水面下では興味深い動きもいくつか見られます。
- スケジューラに拡張点を設けてカスタマイズ可能にする Scheduling Framework
- 複数の Pod を同時に All or Nothing でスケジューリングする coscheduling(旧称 Gang Scheduling)
あたりが目下のところ予定されている大きな機能追加ですが、それはまた別の話。
We Are JavaScripters! @26th で Elm と Firebase の連携について話してきました
先日行われた We Are JavaScripters! @19th で Elm と JavaScript ライブラリの連携について発表してきました。
Elm の初心者向けの解説としてよく Msg, Model, update からなるアーキテクチャが挙げられていますが、今回の発表ではもう一歩だけ進んで、Cmd と Sub を使って Elm から JavaScript のライブラリを呼ぶ方法について解説しました。
サーバとしての JS ライブラリ
他の AltJS では JavaScript を呼び出す際、ソースコードの内部に埋め込む形になるのが普通です。
例えば Haskell を JavaScript にコンパイルする GHCJS の場合、JSaddle という DSL を利用して次のように呼び出すことになります。
store :: Int -> IO () store n = runJSaddle () $ do ref <- jsg "firebase" ^. js0 "database" ^. js1 "ref" (val "/counter") ref ^. js1 "set" (val n) return ()
Firebase SDK を呼び出して Realtime DB に値をセットする部分です。JavaScript 側の関数を文字列で指定することで、直接 Haskell のソースコード内に IO
アクションとして JS の呼び出しが定義されていることがわかります。この場合、Haskell とは別に JavaScript 側を自分で実装する必要はありません。
一方、Elm で同様の呼び出しを実装する場合、「Port」「Command」「JavaScript 側での subscribe」という 3 つの部分に分割されます。
まず、JavaScript 側へのインタフェースとなる Port を次のように定義します。
port module RealtimeCounter.Port exposing (store) import Json.Encode as E port store : E.Value -> Cmd msg
JSON を受け取って、Cmd を発生させる関数 store
が定義されています。port
に指定された関数は型シグネチャだけが存在し、中身は記述しません。
次に、実際に update
関数の中でこの Cmd を発生させるために、Elm の Int
値を JSON エンコードしてこの port に流し込む関数を定義します。
import Json.Encode as E storeCount : Int -> Cmd msg storeCount = store << E.int
最後に、Elm 側から発生した Cmd を受け取るための JavaScript を実装します。
const { Elm } = require('./Main.elm'); const app = Elm.Main.init({ node: document.getElementById('app') }); app.ports.store.subscribe((count) => { firebase.database().ref('count').set(count); });
上に挙げたコールバックによる実装を見ても分かる通り、JavaScript 側はあたかも Web サーバのコントローラのように subscribe
で待ち受けており、Elm から Cmd によって JSON が渡されると実際に Realtime DB に値をセットします。
逆に、JavaScript 側から Elm 側に値を戻す必要がある場合には、JavaScript 側で send
関数を使用すると Elm 側からは Sub となって観測されます。具体的には下記のサンプルレポジトリを参照してください。
なお、実際に JS 連携する部分をコーディングする際には、boiyaa さんが書かれている詳しい記事も参考になると思います。
boiyaa さんの記事は Elm v1.18 時点で書かれているので起動時に Html.programWithFlags
を使用していますが、Elm v1.19 ではここに相当する関数は Browser.element
に変更になっています。
動作サンプル
実際に触って動かせるデモもデプロイしておきました。先に挙げたソースコードと合わせて、よかったら参考にしてみてください。
プレゼンの際にお見せしたデモは単にテキストを置いただけの画面でしたが、公開版はちょっと凝った CSS を付けてみました。カウンタ自体の Elm 側のロジックは非常にシンプルで行数も少ないので、GitHub からは Elm ではなく CSS のレポジトリ扱いされてしまっていますが、それはまた別の話。
猫でもわかる Vertical Pod Autoscaler
先日行われた Kubernetes Meetup Tokyo #13 で、Vertical Pod Autoscaler (VPA) について発表してきました。
VPA は、各コンテナの Resource Request の値を自動的に調整してくれるコンポーネント群です。必要とするリソース(CPU、メモリ)量があらかじめ推測しにくいアプリケーションに対して、実績に基づいてそれらしい値を決めたい場合に効果を発揮します。
本記事ではスライドの補足として、VPA が動作する流れをクラスタ上での実際の挙動を通じて確認し、また内部実装についても踏み込んで解説します。
なお、本記事中で引用している仕様やソースコードは執筆時点で最新のコミット ab9c27e
を基準にしています。
はじめに
Kubernetes の Pod には、コンテナごとにリソース使用量を指定する機能があります。指定できる項目は Request と Limit の二種類がありますが、今回のテーマである VPA に関係するのは Request の方です。
Kubernetes Scheduler は、Node の利用可能リソースと Pod の Resource Request を比較してどの Node に Pod を配置するか決定します。
Managing Compute Resources for Containers - Kubernetes
重要なのは、Request の値はあくまでもユーザが指定した値であり、実際のリソース使用量とは無関係であるという点です。そのため、Request が小さすぎると実際の動作時にリソースが不足してアプリケーションの挙動に悪影響を与える可能性がある一方、大きすぎるとリソースが余っているのにもかかわらず Pod が配置されないスペースが増えるため、集積度が下がり無駄なコストを抱えることになります。
この Request と実績値の乖離という問題を解決するのが VPA です。VPA は、リソース使用量の実績値をモニタして、過去の履歴から算出した推奨値を自動で Request として設定してくれます。結果として、Scheduler はその Pod をより実態に合った Node に配置することができ、クラスタ全体のリソースを有効活用することができます。
コンポーネント群とその役割
ここからは、実際にクラスタ上に VPA をデプロイしtて、Resource Request が変更される際の各コンポーネントの挙動を確認してみましょう。手元のクラスタが必要な条件を満たしていることを確認しておいてください。
なお、VPA は amd64
用のバイナリしか提供していません。Raspberry Pi で試したい場合、ARM 用の差分をフォークしたので参考にしてください。対応した Docker イメージも Docker Hub に push してあります。
起動の準備
VPA は、次に挙げた三つのコンポーネントがそれぞれの役割を分担することで成り立っています。
- Recommender : 実際のリソース使用量データから Request の推奨値を算出する
- Updater : 推奨値に合致しない Pod を見つけて evict する
- Admission Controller : evict された Pod が再作成される際に Request の値を差し替える
これらのコンポーネントを作成するための YAML は deploy
ディレクトリ以下にありますが、証明書の作成などの作業とひとまとめにしたスクリプト vpa-up.sh
が提供されているのでこれを使用します。
$ mkdir -p $GOPATH/src/k8s.io $ cd $GOPATH/src/k8s.io $ git clone https://github.com/kubernetes/autoscaler.git $ cd autoscaler/vertical-pod-autoscaler $ git checkout -b ab9c27e
ただし今回は、起動スクリプト実行前にちょっとした工夫を加えます。コンポーネント群を生成する *-deployment.yaml
の replicas
を 0 に書き換えておきましょう。
$ find deploy -name *-deployment.yaml | xargs sed -i.bak "s/replicas: 1/replicas: 0/" $ ./hack/vpa-up.sh
こうすることで、必要な準備は整えた上で、コンポーネント群はまだ起動していない状態をつくることができます。以下、各コンポーネントをひとつづつ起動し、それぞれのコンポーネントの役割を確認します。
VPA CustomResource
VPA の設定および現在の状態は CustomResource として保持されます。
VPA の作成
先ほど実行した vpa-up.sh
によって VPA 用の CustomResourceDefinition が作成されているはずなので確認してみましょう。
$ kubectl get crd | grep verticalpodautoscaler verticalpodautoscalercheckpoints.poc.autoscaling.k8s.io 2018-10-01T08:17:20Z verticalpodautoscalers.poc.autoscaling.k8s.io 2018-10-01T08:17:20Z
二種類の CustomResource が作成されていますが、VPA の状態を保持するのは verticalpodautoscalers
です。
提供されているサンプル hamster.yaml
から Deployment とそれを管理する VPA を作成します。
$ kubectl create -f examples/hamster.yaml verticalpodautoscaler.poc.autoscaling.k8s.io/hamster-vpa created deployment.extensions/hamster created
Pod が 2 個作成されますが、この段階では Pod の Resource Request は hamster.yaml
で定義されている通り CPU 100m、メモリ 50 Mi です。
$ kubectl get pods | grep hamster hamster-6db596f5b4-46g4g 1/1 Running 0 6s hamster-6db596f5b4-9hlw2 1/1 Running 0 7s $ kubectl describe pods/hamster-6db596f5b4-46g4g ... Requests: cpu: 100m memory: 50Mi ...
同時に作成された VPA についても確認しておきましょう。出力に Status
の項目がないことに注意してください。Status
を埋める役割を担っているのは Recommender ですが、この段階ではまだ起動していないためです。
$ kubectl describe vpa/hamster-vpa ...
以上の状態はいわば「初期状態」です。必要なコンポーネント群がまだ起動していないので、このまま待っても状態は変化しません。ここから一つずつコンポーネントを立ち上げていって、VPA の変化を観察します。
VPA の設定項目
今回のサンプルでは最低限の項目のみ定義されていますが、可能な設定をすべて明示すると以下のようになります。
apiVersion: "poc.autoscaling.k8s.io/v1alpha1" kind: VerticalPodAutoscaler metadata: name: my-app-vpa spec: selector: matchLabels: app: my-app updatePolicy: updateMode: Auto resourcePolicy: containerPolicies: - containerName: my-app mode: Auto minAllowed: cpu: 200m memory: 100Mi maxAllowed: cpu: 1000m memory: 500Mi
各項目はおおむね見た通りですが、updatePolicy
は少し説明が必要かもしれません。可能な値は Auto
、Recreate
、Initial
、Off
で、それぞれ次のような挙動になります。
Auto
はデフォルト値です。現時点では Kubernetes が Pod を起動させたまま Resource Request の値を変更する機能を提供していないため、暫定的に Recreate
と同じ挙動になります。
Recreate
の場合、Resouce Request が推奨値のレンジに収まらない Pod が存在したとき、その Pod は evict されます。
Initial
の場合、Pod が最初に作成されるときのみ Resource Request の変更を行いますが、すでに起動状態の Pod を能動的に evict しようとはしません。
Off
の場合、Resource Request の推奨値の算出だけを行うのみで Pod には影響を与えません。
なお resourcePolicies[].mode
には Auto
もしくは Off
のみが指定できます。また resourcePolicies[].containerName
を *
とすると、その Pod に属するコンテナの内 containerName
が指定されていないものすべてに適用されるデフォルト値になります。
Recommender
Recommender は Metrics Server 経由で Pod のリソース使用実績を取得し、Resource Request の推奨値を算出して VPA に保存します。
Recommender の起動
まず、先ほど 0 に差し替えていた replicas
を 1 に戻して Recommender を起動させます。
$ mv deploy/recommender-deployment.yaml.bak deploy/recommender-deployment.yaml $ kubectl apply -f deploy/recommender-deployment.yaml serviceaccount/vpa-recommender configured deployment.extensions/vpa-recommender configured $ kubectl -n kube-system get pods | grep recommender vpa-recommender-6d8cddc856-rw7m2 1/1 Running 0 6s
これで Recommender が立ち上がりました。数分待つと、算出された推奨値が VPA の Status
として書き込まれているのが確認できます。
$ kubectl describe vpa/hamster-vpa ... Status: Conditions: Last Transition Time: 2018-10-01T08:52:56Z Status: True Type: RecommendationProvided Recommendation: Container Recommendations: Container Name: hamster Lower Bound: Cpu: 115m Memory: 53677237 Target: Cpu: 688m Memory: 319572800 Upper Bound: Cpu: 991408m Memory: 460504404800 ...
Recommender は Target、Lower Bound、Upper Bound の三種類の値を提示します。もし現に起動している Pod の Resource Request がこの Lower Bound を割っている場合、その Pod が実際に動作するためには想定よりも多くのリソースが必要です。また Upper Bound を超えている場合、Node の選択時に必要以上に余裕を見ていることでクラスタ全体のリソースに無駄が生じていることになります。
ただし、Recommender は推奨値を算出して VPA の Status
に記録するだけで、実際の調整作業は行いません。例えば先ほど作成した Pod の Request は CPU 100m、メモリ 50 Mi だったので推奨値の範囲からは外れていますが、しばらく放置しても再作成されたりはしないはずです。
推奨値を算出するアルゴリズム
アルゴリズムについて解説する前に、もう一度 VPA の状態を確認してみましょう。
$ kubectl describe vpa/hamster-vpa ... Status: Conditions: Last Transition Time: 2018-10-01T08:52:56Z Status: True Type: RecommendationProvided Recommendation: Container Recommendations: Container Name: hamster Lower Bound: Cpu: 529m Memory: 237494649 Target: Cpu: 712m Memory: 319572800 Upper Bound: Cpu: 114632m Memory: 51451220800 ...
先ほどと値が変わっています。もちろん、Recommender はリアルタイムの実績値を使用しているのでタイミングによって多少のブレはありますが、Lower Bound と Upper Bound が Target に近づいている、言い換えれば許容される値の幅が狭くなっているのが特徴的です。
推奨値の算出ロジックは、estimator.go
に定義された ResourceEstimator
インタフェースとして抽象化されています。
type ResourceEstimator interface { GetResourceEstimation(s *model.AggregateContainerState) model.Resources
内部で使用されている ResourceEstimator
の実装はいわゆる Decorator パターンになっていて、ベースとなる Estimator を次々にラップすることで算出ロジックを組み立てていきます。
例として、実装の一つである minResourceEstimator
を見てみましょう。
type minResourcesEstimator struct { minResources model.Resources baseEstimator ResourceEstimator } func (e *minResourcesEstimator) GetResourceEstimation(s *model.AggregateContainerState) model.Resources { originalResources := e.baseEstimator.GetResourceEstimation(s) newResources := make(model.Resources) for resource, resourceAmount := range originalResources { if resourceAmount < e.minResources[resource] { resourceAmount = e.minResources[resource] } newResources[resource] = resourceAmount } return newResources }
構造体の内側にベースとなる baseEstimator
を保持していて、ベースが返す値がもし許容される最小値 minResources
より大きい場合はそのまま、小さい場合には切り上げた値を返すようになっています。
実際に Lower Bound、Target、Upper Bound を算出している Estimator は、recommender.go
内の CreatePodResourceRecommender
関数で構築されています。過去データのパーセンタイル値をベースとして、最小値と安全係数を加味した Estimator です。
推奨値 | リソース | 基準パーセンタイル | 最小値 | 安全係数 |
---|---|---|---|---|
Lower Bound | CPU | 50% | 25m | *1.15 |
memory | 50% | 250Mi | *1.15 | |
Target | CPU | 90% | 25m | *1.15 |
memory | 90% | 250Mi | *1.15 | |
Upper Bound | CPU | 95% | 25m | *1.15 |
memory | 95% | 250Mi | *1.15 |
Lower Bound と Upper Bound については、ここからさらに「信頼区間」を加味するためのスケーリング操作が入ります。
Lower Bound の計算式は
Upper Bound の計算式は
で与えられます。N は算出に使用する過去データのサンプルサイズを表すパラメータで、デフォルトのサンプリング間隔(1 回/分)の場合はデータを使用する期間の日数に一致します。
計算式から、使用する過去データの期間が長ければ長いほど scaledResource は originalResource に近くなり、また Upper Bound よりも Lower Bound の方が急激に収束することがわかります。このことは、先ほど VPA をしばらく放置した際、値の幅が狭くなっていた観察結果とも一致します。
なお、このサンプリング間隔は Recommender 起動の際に --recommender-interval
オプションで指定できますが、なぜか無駄に細かくナノ秒単位で指定する仕様になっています。
Updater
Updater は、Recommender が VPA に書き込んだ推奨値と実際に起動中の Pod に指定されている Resource Request を比較し、推奨値のレンジから外れている場合はその Pod を evict します。
Updater の起動
Recommender に引き続き、Updater も起動させてみましょう。
$ mv deploy/updater-deployment.yaml.bak deploy/updater-deployment.yaml $ kubectl apply -f deploy/updater-deployment.yaml serviceaccount/vpa-updater configured deployment.extensions/vpa-updater configured $ kubectl -n kube-system get pods | grep updater vpa-updater-664996d6dd-sjrz4 1/1 Running 0 6s
これで Recommender + Updater が立ち上がった状態になりました。数分待つと Pod が evict され、Deployment の作用で再作成されます。しかし、この新しい Pod の Resource Request は元の Pod と同様、CPU 100m、メモリ 50Mi のままです。
$ kubectl get pods | grep hamster hamster-6db596f5b4-9hlw2 1/1 Running 0 12m hamster-6db596f5b4-wls85 1/1 Running 0 4s $ kubectl describe pods/hamster-6db596f5b4-wls85 ... Requests: cpu: 100m memory: 50Mi ...
Updater の担当はあくまでも Pod を evict することまでであり、Resource Request の値を変更することはありません。したがって当然ながら Pod は Deployment で定義されている通りの設定で再作成されます。すると新しい Pod もやはり推奨値のレンジからは外れているので、結果として evict と再作成が繰り返されるはずです。
ちなみに、Updater が delete ではなく evict API を使用するという事実は地味ですが有用です。というのも、あらかじめ Pod Disruption Budget を指定しておくことで、すべての Pod が同時に再作成されて一時的にサービス不能になる事態を避けることができるからです。
evict される Pod の割合
ところで、今回は特に Pod Disruption Budget が設定されていないにもかかわらず、evict される Pod は必ず一個ずつであることに気づいたかもしれません。これは、Updater 自身が evict する Pod を制限する仕組みを持っているためです。
Pod を evict できるかどうかの判定は、pods_eviction_restriction.go
内で定義されたインタフェース PodsEvictionRestriction
によって行われます。インタフェースは切られていますが実装は事実上podsEvictionRestrictionImpl
のみで、判定を行う関数 canEvict
は以下のような内容になっています。
func (e *podsEvictionRestrictionImpl) CanEvict(pod *apiv1.Pod) bool { ... shouldBeAlive := singleGroupStats.configured - singleGroupStats.evictionTolerance if singleGroupStats.running-singleGroupStats.evicted > shouldBeAlive { return true } ... }
ここで、configured
は設定上存在する Pod の個数、例えば今回の場合なら Deployment に指定された replicas
の値が格納されています。条件判定の内容から、evictionTolerance
は evict したくない Pod の個数であるらしいことが見て取れます。
evictionTolerance
の値を実際に計算しているのは、同じファイル内の NewPodsEvictionRestriction
関数です。
func (f *podsEvictionRestrictionFactoryImpl) NewPodsEvictionRestriction(pods []*apiv1.Pod) PodsEvictionRestriction { ... singleGroup.evictionTolerance = int(float64(configured) * f.evictionToleranceFraction) ... }
この evictionToleranceFraction
のデフォルト値は 0.5 なので、 Updater は一度に replicas
の半分まで evict しようとします。今回、2 個ある Pod が 1 個ずつ evict されていたのはこのロジックが原因です。
なお evictionToleranceFraction
の値は Updaer 起動の際に --eviction-tolerance
オプションで指定できますが、VPA ごとに Pod の用途に合わせて設定することはできないため注意しましょう。
Admission Controller
Admission Controller は、Updater により evict された Pod が再作成される際、API Server への Pod 作成リクエストに割り込んで Resource Request の値を書き換えます。
Admission Controller の起動
最後のコンポーネントとして、Admission Controller を起動させます。
$ mv deploy/admission-controller-deployment.yaml.bak deploy/admission-controller-deployment.yaml $ kubectl apply -f deploy/admission-controller-deployment.yaml deployment.extensions/vpa-admission-controller configured service/vpa-webhook configured $ kubectl -n kube-system get pods | grep admission-controller vpa-admission-controller-76744566cc-t6m9d 1/1 Running 0 9s
これで Recommender + Updater + Admission Controller の全コンポーネントが揃った状態になりました。先ほど Updater のみ起動した状態では元と同じ設定で Pod が再作成されるだけでしたが、Admission Controller の起動によって状況が変わったことを確認しましょう。
$ kubectl get pods | grep hamster hamster-6db596f5b4-7xm84 1/1 Running 0 1m hamster-6db596f5b4-9dn55 1/1 Running 0 22s $ kubectl describe pods/hamster-6db596f5b4-9dn55 ... Requests: cpu: 712m memory: 319572800...
ここで hamster-6db596f5b4-9dn55
は Admission Controller 起動後に作成された Pod です。Resource Request の値が VPA に保持された Target と同じ値に差し替えられていることがわかります。
以上で VPA が推奨値を算出して Pod に適用する一連の流れが確認できました。
Request を差し替える仕組み
ところで、なぜ Pod の Resource Request が差し替えられたのでしょうか? Pod を再作成している Deployment と、そこから作られる ReplicaSet の状況を確認してみましょう。
$ kubectl describe deploy/hamster ... Requests: cpu: 100m memory: 50Mi ... $ kubectl get rs | hamster hamster-78568d5fbc 2 2 2 29m $ kubectl describe rs/hamster-78568d5fbc ... Requests: cpu: 100m memory: 50Mi ...
Deployment と ReplicaSet はいずれも元の設定である CPU 100m、メモリ 50 Mi から変化していません。すなわち他には影響を与えず、Pod を作成するリクエストだけが差し替えられていることがわかります。
ここまで VPA の動作に必要な特定のコンポーネントを Admission Controller と呼んできましたが、実はこれは固有名詞ではありません。もっと広く Kubernetes API へのリクエストに割り込んで特殊な操作を行う機能の総称です。
Using Admission Controllers - Kubernetes
Kubernetes の API にはいわゆる認証・認可の後にこの Admission Control のフェイズがあり、リクエストの内容が特定の条件を満たさない場合にエラーを返したり、あるいはリクエストの一部を書き換えたりすることができます。
Admission Contoller はあらかじめ API Server に組み込まれているものの他に、JSON Webhook の形でユーザが定義することもできます。
Dynamic Admission Control - Kubernetes
VPA の Admission Controller は、その名の通りこの仕組みを利用しています。先ほど立ち上げた VPA Admission Controller の実体は Webhook を提供する HTTP サーバで、API Server は Pod 作成リクエストを受け取った際、この Webhook サーバに問い合わせることでリクエスト内容の書き換えを行います。
それでは VPA Admission Controller の実装を確認してみましょう。
まず Admission Controller は、API Server に対して自分自身を Webhook サーバとして登録し、Pod の作成リクエストがあったとき自分に問い合わせが来るようにします。ソースコード上では config.go
内の selfRegistration
関数が相当します。
func selfRegistration(clientset *kubernetes.Clientset, caCert []byte) { ... Webhooks: []v1beta1.Webhook{ { Name: "vpa.k8s.io", Rules: []v1beta1.RuleWithOperations{ { Operations: []v1beta1.OperationType{v1beta1.Create}, Rule: v1beta1.Rule{ APIGroups: []string{""}, APIVersions: []string{"v1"}, Resources: []string{"pods"}, }, }, ... ClientConfig: v1beta1.WebhookClientConfig{ Service: &v1beta1.ServiceReference{ Namespace: "kube-system", Name: "vpa-webhook", }, CABundle: caCert, }, }, }, } }
VAP Admission Controller がこの設定を API Server に登録しておくことで、API Server は Pod に対する Create リクエストを受け取った際、Namespace kube-system
内の Service vpa-webhook
にアクセスするようになります。
そしてアクセスされた VAP Admission Controller 側では、recommendation_provider.go
内の getContainersResources
関数によって、VPA が保持している Target が Resource Request の値として設定されます。
func getContainersResources(pod *v1.Pod, podRecommendation vpa_types.RecommendedPodResources) []ContainerResources { resources := make([]ContainerResources, len(pod.Spec.Containers)) for i, container := range pod.Spec.Containers { resources[i] = newContainerResources() ... resources[i].Requests = recommendation.Target } return resources }
ここで取得した resources
を元にして、最終的には server.go
内の getPatchesForPodResourceRequest
関数が JSON Patch を組み立てて API Server に送り返す流れになっています。
まとめ
本記事では、Kubernetes Pod の Resource Request を実績値から判断し、自動で変更する仕組みである Vertical Pod Autoscaler (VPA) の実装について解説しました。
VPA を使用することで、リソースの使用実績が Pod の配置にフィードバックされるため、クラスタのリソースを有効に活用することができます。
より具体的には、実績から推奨値を算出する Recommender、推奨値に合わない Pod を evict する Updater、Pod の再作成時にリクエストを書き換える Admission Controller の三つのコンポーネントがそれぞれの役割を果たすことで、最終的に Pod の Resource Request が更新されます。現時点では稼働中 Pod の Resource Request を動かしたまま(In-Place で)変更することができないという制限のため、一度 evict する手法が取られています。
ところで、この稼働中の In-Place な変更という問題も深入りすると実はなかなか興味深いのですが、それはまた別の話。
elm/time の使い方
はじめに
先日、Elm v0.19 がリリースされました。公式ライブラリのリポジトリが elm-lang
から elm
に変更され、その中身も大きく再構成されています。
本記事では、これらの変更のうち特に時刻や日付の扱いに関する部分について、新しい API の使い方を含めて簡単に解説します。
v0.18 における時刻の扱い
v0.18 では、時刻を扱う機能は標準パッケージ elm-lang/core
の中で提供されていました。時刻を扱う Time
モジュールと日付を扱う Date
モジュールで、それぞれデータ型や関数が定義されているのが特徴です。
なお、旧バージョンのライブラリは現在 Elm Packages の検索にはヒットしない ので、中身を確認するためには直接 URL にアクセスする必要があります。
旧 Time モジュール
時刻を扱う Time
型を提供します。Time
型の実体は Float
型のエイリアスで、Unix Epoch からの経過ミリ秒数を表します。
メインの関数は現在時刻を取得する now
と指定した時間間隔で Msg を送出する every
です。その他、every
と組み合わせて使用する単位として second : Time
や minute : Time
が定義されており、例えば毎秒何かを行う Subscription は次のように書けます。
type Msg = DoSomethingAt Time.Time subscriptions : Model -> Sub Msg subscriptions _ = Time.every Time.second DoSomethingAt
旧 Date モジュール
日付を扱う Date
型を提供します。また Time
型との変換用の関数もこちらで定義されています。
その他、紛らわしいですが Date
モジュールでも now
関数がエクスポートされており、こちらは現在の日付を取得します。
特徴的なのは、Time
型と Date
型の変換においてタイムゾーンを指定する機能がないことです。したがって API 定義上は
toTime : Date -> Time fromTime : Time -> Date
の変換は純粋な関数に見えますが、実際にはシステムのタイムゾーンに依存する副作用を持っていることになります。
v0.19 における時刻の扱い
さて、今回新しくなったバージョンでは、旧 Time
と Date
に相当する機能が再編成されてひとつのモジュール Time
になり、さらに別ライブラリ elm/time
として切り出されました。
新 Time モジュール
大きな変更点は、Unix 時間を表す Posix
型に加えて、タイムゾーンを表す Zone
型が陽に導入されたことです。
現在時刻を取得するには今まで通り now
で、現在のタイムゾーンを取得するには here
を使用します。例えば初期化の際、両者を同時に取得する Cmd
は以下のように書けます。
type Msg = SetSystemTime (Time.Zone, Time,Posix) setSystemTime : Cmd Msg setSystemTime = Task.perform SetSystemTime <| Task.map2 Tuple.pair Time.here Time.now
旧 Date
モジュールにあった日付への変換も Time
の中にまとめられました。Unix 時間が同じでも実際の日付はタイムゾーンに依存するため、変換には Zone
型が必要になっているのが分かります。新しい変換関数名には toXXX
で統一されており、Day
型は Weekday
型に、dayOfWeek
は toWeekday
に変更されました。
toYear : Zone -> Posix -> Int toMonth : Zone -> Posix -> Month toWeekday : Zone -> Posix -> Weekday toHour : Zone -> Posix -> Int toMinute : Zone -> Posix -> Int toSecond : Zone -> Posix -> Int toMillis : Zone -> Posix -> Int
また、旧 Time
モジュールにあった時間の単位 minute
や second
は外されました。ミリ秒単位で直接指定する必要があります。
サンプル:デジタル時計
以上をまとめると、Elm v0.19 対応の簡単なデジタル時計は次のように実装することができます。
- 初期化時に
setSystemTime
で現在のタイムゾーンと時刻を取得 - それ以後 1000 ミリ秒ごとに
setCurrentTime
で現在時刻を更新 - 表示の際は
toHour
とtoMinute
でタイムゾーン依存の時刻に変換
という流れになっています。
module Main exposing (main) import Browser import Html exposing (..) import Task import Time main : Program () Model Msg main = Browser.element { init = init , update = update , view = view , subscriptions = subscriptions } type alias Model = { zone : Time.Zone , posix : Time.Posix } type Msg = SetSystemTime ( Time.Zone, Time.Posix ) | SetCurrentTime Time.Posix init : () -> ( Model, Cmd Msg ) init _ = ( { zone = Time.utc, posix = Time.millisToPosix 0 }, setSystemTime ) update : Msg -> Model -> ( Model, Cmd Msg ) update msg model = case msg of SetSystemTime ( zone, time ) -> ( { zone = zone, posix = time }, Cmd.none ) SetCurrentTime time -> ( { model | posix = time }, Cmd.none ) view : Model -> Html Msg view model = let h = Time.toHour model.zone model.posix m = Time.toMinute model.zone model.posix in div [] [ text <| String.fromInt h ++ ":" ++ String.fromInt m ] setSystemTime : Cmd Msg setSystemTime = Task.perform SetSystemTime <| Task.map2 Tuple.pair Time.here Time.now subscriptions : Model -> Sub Msg subscriptions _ = Time.every 1000 SetCurrentTime
Time.Extra モジュール
ところで、実際に時刻を扱うアプリを書いてみると、elm/time
はかなり非力であることがわかります。特に以下のようなケースは問題になりそうです。
- 時刻 + タイムゾーンから Unix 時間に変換できない(例:特定の日付と現在時刻を比較したい)
- 時刻の和や差が取れない(例:ちょうど 1 か月後の日付が欲しい)
- 時刻を丸めることができない(例:次に 00 秒になるタイミングで Msg を発生させたい)
このような問題を解決するために、justinmimbs/time-extra
が使用できます。
Time.Extra
モジュールでは旧 Date
型に代わるものとして Parts
型を定義しており、Zone
型を組み合わせることで各タイムゾーンにおけるその時刻の Unix 時間を得ることができます。
partsToPosix : Zone -> Parts -> Posix -- UTC における 2018/09/26 11:23.45.00 time1 : Posix time1 = partsToPosix utc <| Parts 2018 Sep 26 11 23 45 0
また、旧 Time
モジュールの minute
や second
や代わる時間単位として Interval
型を定義しており、これを使って「1 か月後の日付」や「次に 00 秒ちょうどになる時刻」が取得できるようになっています。
add : Interval -> Int -> Zone -> Posix -> Posix ceiling : Interval -> Zone -> Posix -> Posix -- UTC における 2018/09/26 11:23.45.00 の 1 か月後 time2 : Posix time2 = add Month 1 utc <| partsToPosix utc <| Parts 2018 Sep 26 11 23 45 0 -- UTC における 2018/09/26 11:23.45.00 以降、最初に 00 秒になる瞬間 time3 : Posix time3 = ceiling Minute utc <| partsToPosix utc <| Parts 2018 Sep 26 11 23 45 0
まとめ
本記事では Elm v0.19 で刷新された elm/time
について、旧バージョンとの違いや使い方について簡単に解説しました。
- 時刻パッケージは
elm-lang/core
からelm/time
に移動 - 原則
Posix
を操作し、通常の時刻表示に変換した時はZone
と合わせる - 時刻を操作するには
justinmimbs/time-extra
ライブラリが使える
ところで、今回紹介した新しい API を使ってちょっと面白いサンプルアプリを作ってみたので、GIF アニメにしたものを貼っておきます。
元ネタは Humans since 1982 の作品 ClockClock 24 です。ソースコードは以下にあるので elm/time
の使い方の参考に。
ちなみにこのサンプル、実際には elm/time
ではなくそれ以外の部分の実装のほうが大変だったのですが、それはまた別の話。
詳解! Elm における Fuzzing
先日行われた We Are JavaScripters! @23rd で、Elm のテストフレームワーク elm-test に搭載されている Fuzzing 機能について発表してきました。
Fuzzing を利用するとテストデータを自動で生成することができるため、例えば「encode と decode を行うと元に戻る」といった、入力に依存しない 関数の性質に関するテスト をより簡単かつ効率的に実装することができます。
さらに、後で詳しく解説する通り、elm-test の Fuzzer にはバグが起こりやすいエッジケースを集中的に生成してくれるというメリットもあります。
elm-test の使い方は、すでに偉大なる先達によって大部分が解説済みです。普通にテストする上では、これらの内容を押さえておけば困ることはないでしょう。
- [Elm] Fuzzer でテストデータを量産しよう (by jinjor さん)
- [Elm]キミだけのッ最強Fuzzerを手に入れろ! (by arowM さん)
そこでこの記事では、もう少し内部の実装にも踏み込んで説明します。なお、ソースコードを載せる際には執筆時点の master
ブランチ (19f0bb3
) を参照しています。
Fuzzer コンビネータの一覧
elm-test では、Fuzzing 関連の機能は Fuzz
モジュールで定義されています。このモジュールが expose しているすべての関数を以下にリストアップしました。
便宜上「コンビネータ」と呼んではいますが種類さほど多くなく、Persec のような色々入ったライブラリを想像するとちょっと肩透かしかもしれません。特定の条件に従うような値を生成したい場合は、自分で Fuzzer を定義する必要があります。
組み込み型に対応するタイプ
基本パーツとなる Fuzzer です。読んで字のごとく、生成する値の型名に対応した Fuzzer が用意されています。
bool : Fuzzer Bool int : Fuzzer Int float : Fuzzer Float char : Fuzzer Char string : Fuzzer String order : Fuzzer Order unit : Fuzzer ()
最後の unit
は常にユニット値 ()
のみを生成する Fuzzer です。テストに直接関係しない引数をプレースホルダーとして埋めるために用意されていて、例えば elm-test の内部では Result
型のエラー側に unit
が使用されています。
パラメータが付いたタイプ
Int
および Float
用には、範囲を指定するとその間の値を生成する Fuzzer が用意されています。
intRange : Int -> Int -> Fuzzer Int floatRange : Float -> Float -> Fuzzer Float percentage : Fuzzer Float
percentage
は 0 から 1 の値を生成するための Fuzzer です。パーセンテージなら 0 から 100 であるべき気がしますがどうしてこうなった。
用途によっては最小値(もしくは最大値)のみ指定したいこともあるでしょう。その場合は intRange 0 Random.intMax
のようにすれば表現することができます。
候補から選択するタイプ
あらかじめいくつかの Fuzzer を与えると、その中から乱択するタイプです。
constant : a -> Fuzzer a oneOf : List (Fuzzer a) - Fuzzer a frequency : List ( Float, Fuzzer a ) -> Fuzzer a
constant x
は常に同じ値 x
を返す Fuzzer です。これと oneOf
を組み合わせると、与えられた選択肢からランダムにどれかを選ぶ Fuzzer になります。
logLevel = Fuzzer String logLevel = Fuzz.oneOf [ Fuzz.constant "ERROR" , Fuzz.constant "WARN" , Fuzz.constant "INFO" ]
また oneOf
の代わりに frequency
を使用すると、選択される割合に重みを掛けることができます。例えば次のように書けば、"ERROR"
を 10%、"WARN"
を 30%。"INFO"
を 60% の内訳で生成する Fuzzer が得られます。
logLevel = Fuzzer String logLevel = Fuzz.frequency [ (1, Fuzz.constant "ERROR") , (3, Fuzz.constant "WARN") , (6, Fuzz.constant "INFO") ]
コンテナタイプ
中身の型に対する Fuzzer が与えられているとき、外側のコンテナ部分を含めた値を生成させるために使用します。
maybe : Fuzzer a -> Fuzzer (Maybe a) result : Fuzzer error -> Fuzzer value -> Fuzzer (Result error value) list : Fuzzer a -> Fuzzer (List a) array : Fuzzer a -> Fuzzer (Array a) tuple : (Fuzzer a, Fuzzer b) -> Fuzzer (a, b) tuple3 : (Fuzzer a, Fuzzer b, Fuzzer c) -> Fuzzer (a, b. d) tuple4 : (Fuzzer a, Fuzzer b, Fuzzer c, Fuzzer d) -> Fuzzer (a, b. c. d) tuple5 : (Fuzzer a, Fuzzer b, Fuzzer c, Fuzzer d, Fuzzer e) -> Fuzzer (a, b, c, d, e)
合成を定義するタイプ
必要な Fuzzer が以上の関数の組み合わせで表現できない場合は、Fuzzer どうしの合成を自分で定義しましょう。
Fuzz.map
map : (a -> b) -> Fuzzer a -> Fuzzer b map2 : (a -> b -> c) -> Fuzzer a -> Fuzzer b ->Fuzzer c map3 : (a -> b -> c -> d) -> Fuzzer a -> Fuzzer b ->Fuzzer c -> Fuzzer d map4 : (a -> b -> c -> d -> e) -> Fuzzer a -> Fuzzer b -> Fuzzer c -> Fuzzer d -> Fuzzer e map5 : (a -> b -> c -> d -> e -> f) -> Fuzzer a -> Fuzzer b -> Fuzzer c -> Fuzzer d -> Fuzzer e -> Fuzzer f
典型的な用途として、自作のデータ型に対して、各フィールド用の Fuzzer にコンストラクタを map
すればそのデータ型用の Fuzzer を定義することができます。例えば以下は、String
、Int
、Bool
をそれぞれ生成する Fuzzer を組み立てて User
型の Fuzzer を得る例です。
type alias User = { name : String , age : Int , active : Bool } user : Fuzzer User user = Fuzz.map3 User Fuzz.string (Fuzz.intRange 20 60) Fuzz.bool
map
は 5 引数までしか用意されていません。6 個以上のフィールドを持つようなレコードに対して Fuzzer を定義したい場合には、次の andMap
を使用しましょう。
Fuzz.andMap
andMap : Fuzzer a -> Fuzzer (a -> b) -> Fuzzer b
Haskell でいうところの Applicative
型クラスの <*>
に相当します。部分適用を繰り返すことで、任意個の引数を持つ関数を Fuzzer に持ち上げることができます。
上で map3
を用いて定義した User
の例は、次のように書き換えることが可能です。
user : Fuzzer User user = Fuzz.map User Fuzz.string |> Fuzz.andMap (Fuzz.intRange 20 60) |> Fuzz.andMap Fuzz.bool
Fuzz.andThen
andThen : (a -> Fuzzer b) -> Fuzzer a -> Fuzzer b
Haskell でいうところの Monad
型クラスの =<<
に相当します。複数の Fuzzer に対して依存関係にある値を生成させることができます。
あまり効果的な用途が思いつかなかったのですが、例えば以下の Fuzzer は一度生成した文字列を逆順にしてくっつけることで、偶数文字からなる回文をランダムに生成します。
mkPalindrome : String -> Fuzzer String mkPalindrome x = Fuzz.constant <| x ++ String.reverse x palindrome : Fuzzer String palindrome = Fuzz.string |> Fuzz.andThen mkPalindrome
その他
それ以外にも、特殊な用途を持つ Fuzzer がいくつか定義されています。
Fuzz.invalid
invalid :: String -> Fuzzer a
常に失敗する Fuzzer で、第一引数はエラーメッセージを表します。
他の Fuzzer コンビネータに対して無効値が与えられたときに使用します。例として、elm-test 内では oneOf
に空リストが与えられた場合の値として使用されています。
Fuzz.conditional
conditional : { retries : Int, fallback : a -> a, condition : a -> Bool } -> Fuzzer a -> Fuzzer a
いったん値を生成した後、それが条件 condition
に合わないときに生成し直します。retries
は再生成の最大回数で、それでも条件に合う値が得られなかった場合は fallback
から得られる値を(condition
は無視して)使用します。
ちなみに ドキュメント によれば retries
の推奨値は 10 です。
custom
custom : Generator a -> Shrinker a -> Fuzzer a
ここまでに挙げたすべての Fuzzer の大元になっている最も抽象的な定義です。
定義を見ると、a
型に対する Fuzzer を定義するためには、a
型に対する Generator
と Shrinker
を与えればよいことが分かります。次節でそれぞれの役割を確認しましょう。
Fuzzer の構成要素と役割
Generator と Shrinker について説明する前に、Fuzz
モジュール冒頭の ドキュメンテーションコメント を少し眺めてみましょう。
A `Fuzzer a` knows how to create values of type `a` in two different ways. It
can create them randomly, so that your test's expectations are run against many
values. Fuzzers will often generate edge cases likely to find bugs. If the
fuzzer can make your test fail, it also knows how to "shrink" that failing input
into more minimal examples, some of which might also cause the tests to fail. In
this way, fuzzers can usually find the smallest or simplest input that
reproduces a bug.
ここでは Fuzzing に関する重要なふたつの性質が述べられています。
- エッジケース(コーナーケース)をより頻繁に生成する
- テストに失敗した場合、入力を「縮小する」ことで失敗を再現する最小例を求める
前者の戦略を定義するのが Generator、後者の戦略を定義するのが Shrinker です。
Generator
エッジケースの判定
まずドキュメント通り、本当にエッジケースが多めに選ばれていることを確認するために、-4 以上 5 以下の整数を生成させてみましょう。intRange -4 5
により 10,000 ケース生成したところ、内訳は次のようになりました。
value | count |
---|---|
-4 | 1833 |
-3 | 745 |
-2 | 823 |
-1 | 802 |
0 | 825 |
1 | 825 |
2 | 787 |
3 | 758 |
4 | 788 |
5 | 1814 |
一見して、-4 と 5 が他の数値より特異的に多く生成されていることがわかります。区間の両端の値ですね。確かにバグの原因になる可能性は高そうです。
では、範囲を指定しない int
ではどうでしょう? 同じく 10,000 ケース生成して 0 の個数を数えてみると、10,000 個中 424 個が 0 でした。int
は Int
値全体を生成する可能性があるため、424/10000 というのは特異的に多く 0 が生成されていることを予想させます。
もし仮に、intRange
が単純に int
により整数を生成してから -5 以下と 6 以上の数を捨てているとしたら、intRange
の場合でも 0 にピークがあるはずです。このことから、生成される値の「エッジケースらしさ」は Fuzzer によって異なるロジックで判定されていることがわかります。
Generator の実装
この「エッジケースらしさ」を Fuzzer ごとに定義しているのが Generator です。
intRange
の定義を見てみましょう。hi < lo
の部分はエラー処理ですが本筋に関係ないので省略してあります。
intRange : Int -> Int -> Fuzzer Int intRange lo hi = if hi < lo then ... else custom (Random.frequency [ ( 8, Random.int lo hi ) , ( 1, Random.constant lo ) , ( 1, Random.constant hi ) ] ) (Shrink.keepIf (\i -> i >= lo && i <= hi) Shrink.int)
custom
の第一引数に注目してください。Fuzzer 一覧の中に登場した Fuzz.frequency
と紛らわしいですが、ここでは Random.frequency
によって Generator が定義されていることがわかります。
区間の下端 lo
と上端 hi
の間の整数に対して 80%、さらに上下端の値については固定値に 10% の重みが掛けられています。これが、先ほど intRange -4 5
で -4 と 5 が多めになっていた原因です。
同様に int
の実装を確認すると次のようになっています。
int : Fuzzer Int int = let generator = Random.frequency [ ( 3, Random.int -50 50 ) , ( 0.2, Random.constant 0 ) , ( 1, Random.int 0 (Random.maxInt - Random.minInt) ) , ( 1, Random.int (Random.minInt - Random.maxInt) 0 ) ] in custom generator Shrink.int
こちらも同じく、ケースごとの生起確率が定義されています。int
の場合は区間ごとに確率が変えられていて、特に注意すべきケースは 0、また極端な値よりも -50 から 50 までの範囲を重視する、という定義になっています。
Shrinker
反例の発見
それでは二点目の論点に移りましょう。Shrinker について説明するために、まずわざと失敗するテストを書いてみます。
suite : Test suite = describe "String.reverse" [ fuzz Fuzz.string "is identity" <| \randomString -> randomString |> String.reverse |> Expect.equal randomString ]
このテストが判定しているのは「任意の文字列は、反転すると元の文字列に等しい」ですね。当然、回文でない文字列に対してこのテストは失敗します。
elm-test 0.18.12 ---------------- Running 1 test. To reproduce these results, run: elm-test --fuzz 100 --seed 1428851996 ↓ Example ↓ String.reverse ✗ is identity Given "\t\n" "\n\t" ╷ │ Expect.equal ╵ "\t\n" ...
テストの反例として "\t\n"
が見つかりました。これ以外に複数挙げられる反例も 2 文字になっているはずです。
しかし、Generator がランダムに生成した値に対して単純に条件を判定しているとするとこれはやや奇妙です。当然もっと長い(回文でない)文字列も検出されてしかるべきに思えます。
逆に言えば、ドキュメントにうたわれている通り、Fuzzer は何らかの戦略によってテストを失敗させる「最小の例」を見つけていることになります。この戦略を定義しているのが Shrinker です。
Shrinker の役割
Shrinker は別パッケージ eeue56/elm-shrink で定義されています。
type alias Shrinker a = a -> LazyList a
標語的に述べるならば、入力された値を何らかの意味で「縮小」する関数が Shrinker です。複数の縮小結果を候補として考えるため、戻り値は(遅延)リストになっています。
Fuzzer は、次のような考え方で Shrinker 利用してテストが失敗する最小の入力を探します。
- テストが失敗した入力に対して、Shrinker で一段階「縮小」した値の候補の一覧を得る
- 「縮小」した値を新しい入力とし、テストが失敗する限り同じ手順を繰り返す
- 失敗しなくなったひとつ手前の入力が最小の反例
つまり先ほどの回文の例で言えば、最初に生成した(ほぼ確実にテストが失敗する)例から始めて文字列を「縮小」していくと、1 文字まで縮小された時点でテストが成功するようになります。結果として 2 文字の例が「最小の反例」として出力されるわけです。
Shrinker の実装
上では「文字列を縮小する」と簡単に書きましたが、実際の Shrinker は単に文字列の長さを縮めているだけではありません。実際にどのような実装になっているかも確認しておきましょう。以下に挙げたのが Shrink.string
の実装です。
string : Shrinker String string = convert String.fromList String.toList (list character)
convert
は文字列と文字のリストを相互変換するために使用されますが、「縮小」の動作にとって本質的ではありません。構成要素である Shrink.character
と Shrink.list
についてそれぞれ追いかけます。
Shrink.character
まず Char
型に対して定義された Shrinker です。
character : Shrinker Char character = atLeastChar (Char.fromCode 32) atLeastChar : Char -> Shrinker Char atLeastChar char = convert Char.fromCode Char.toCode (atLeastInt (Char.toCode char)) atLeastInt : Int -> Shrinker Int atLeastInt min n = if n < 0 && n >= min then -n ::: Lazy.List.map ((*) -1) (seriesInt 0 -n) else seriesInt (max 0 min) n
定義を追いかけていくと、文字コード n
を持つ文字の「縮小」は、最終的に Int
区間の「縮小」である seriesInt 32 n
に帰着されています。seriesInt
の実装は以下です。
seriesInt : Int -> Int -> LazyList Int seriesInt low high = if low >= high then empty else if low == high - 1 then low ::: empty else let low_ = low + ((high - low) // 2) in low ::: seriesInt low_ high
このロジックに従うと、例えば文字コード 42 の '*'
を「縮小」すると得られる候補は以下のリストであることがわかります。
Char.fromCode 32 ::: Char.fromCode 37 ::: Char.fromCode 39 ::: Char.fromCode 40 ::: Char.fromCode 41 ::: empty
すなわち、テストを失敗させる Char
型の値が発見された場合 Fuzzer は、元の値より文字コードが小さい側の印字可能文字を(元の値に近いほど密に)いくつかピックアップし、それでもテストが失敗するかどうか試す、ということになります。
Shrink.list
次に List a
型に対する Shrinker の実装です。
実際には遅延リストである Lazy.List a
型を経由して定義されていますが、ここではアルゴリズムに対する分かりやすさを優先して通常の List a
で書き直してあります。擬似コードみたいなものだと思ってください。
list : Shrinker a -> Shrinker (List a) list shrink l = let n : Int n = List.length l in List.Extra.andThen (\k -> removes k n l) (List.Extra.takeWhile (\x -> x > 0) (List.Extra.iterate (\n -> n // 2) n)) +++ shrinkOne l shrinkOne : Shrinker a -> List a -> List (List a) shrinkOne shrink l = case l of [] -> [] x :: xs -> List.map (flip (::) xs) (shrink x) ++ List.map ((::) x) (shrinkOne xs) removes : Int -> Int -> Shrinker (List a) removes k n l = if k > n then [] else if List.isEmpty l then [ [] ] else let first = List.take k l rest = List.drop k l in rest :: List.map ((++) first) (removes k (n - k) rest)
ロジックを追っていくと、リストを「縮小」した結果は
shrinkOne
によって得られる、リストの各要素に Shrinker を適用したものremoves
によって得られる、元のリストから一部の要素を除外したもの
のいずれかに由来することがわかります。
具体例で考えましょう。a
型の値 x
、y
、z
があって、あらかじめ与えられた shrink : Shrinker a
によってそれぞれ
shrink x == x1 ::: x2 ::: empty shrink y == y1 ::: y2 ::: y3 empty shrink z == z1 ::: empty
のように「縮小」されるとします。このとき、List a
型の値 [x, y, z]
は新しく組み立てられた list shrinker : Shrinker (List a)
によって
list shrinker [x, y, z] == [] ::: [y, z] ::: [x, z] ::: [x, y] ::: [x1, y, z] ::: [x2, y, z] ::: [x, y1, z] ::: [x, y2, z] ::: [x, y3, z] ::: [x, y, z1] ::: empty
と「縮小」されます。リストの長さもしくは各構成要素のいずれかの意味で、元の値 [x, y, z]
より小さくなっていることがわかります。
まとめ
今回の記事では、elm-test の Fuzz モジュールの実装について簡単にソースコードを挙げながら解説しました。特に
- 小さく単純な Fuzzer を組み立てることでより大きなデータ型や複雑な条件を表現する Fuzzer を構築できる
- Fuzzer は Generator と Shrinker によって構成される
という二点がポイントです。
ところで、つい先日 Elm の v0.19 がリリース されましたね。かなりいろいろな変更が入ったらしく、現在の elm-test はコンパイルできなくなる気がしますが、それはまた別の話。
July Tech Festa 2018 で分散システムの検証について話してきました / #JTF2018
先日行われた July Tech Festa 2018 で、モデル検査を使った分散アルゴリズムの検証について発表してきました。
前半はオートマトンによるシステムの記述と検査の基礎について、後半は三種類のツール SPIN、TLA+、P による記述方法の紹介、といった内容です。
後半のソースコード紹介が散文的な感じになってしまって、いまいちメリットが伝わらない感じだったので、次回があればもっとエモいスライドにしようと思います。
分散アルゴリズムの形式化
定理証明による検証
今回の話の流れとして「分散システムにはモデル検査が有効」と述べていますが、必ずしも定理証明が分散システムの検証に向かないという趣旨ではありません。
例えば、定理証明器 Coq によって分散システムを証明するためのフレームワークとして Verdi が開発されています。
さらに、Coq は実行可能なコードも出力できるので、Coq で Raft 合意アルゴリズムを証明したものから OCaml を出力して作られた「証明済み分散 KVS」も公開されています。
トランザクションコミットの形式化
今回の発表では、分散アルゴリズムの例として、古典的な二相コミット(を単純化したもの)を使用しました。元ネタになっているのは以下の論文で、発表中取りあげた TLA+ による形式化もこれに基づきます。
アブストラクトを読むとわかる通り、実はこの論文は二相コミットに関するものではありません。「トランザクションコミットに Paxos を使用した」というのが趣旨で、二相コミットは単なる引き立て役です。とはいえ今回の発表と無関係というわけでもなく、Paxos を用いたコミットについても TLA+ コードが載っているので、興味がある人は読んでみると面白いでしょう。
各ツールの簡単な紹介
SPIN
今回紹介した中では、おそらくもっともメジャーなツールです。日本語の書籍も出ています。
形式化の特徴
記述には Promela と呼ばれる DSL を使用します。C 言語にチャンネルと非決定性を足したような言語ですが、配列以外のデータ構造のサポートがほとんどないため複雑な処理を書こうとすると辛いことがあります。
チャンネルの送受信はそれぞれ !
と ?
です。pi 計算にルーツを持つ記号ですが、*1今風に言うなら Go 言語をイメージするとわかりやすいでしょう。
非決定性は if .. fi
または do .. od
内のブランチとして記述し、ブランチの先頭の文が実行可能なものの中から非決定的に次の状態が定義されます。例えば
if :: chan_a ! msg -> ... :: chan_b ? msg -> ... fi
と書くと、この if
節全体として chan_a
への送信または chan_b
からの受信のうちその状態において可能なもの(両方なら非決定的)が選択されます。
ちなみに発表中でも述べましたが、SPIN のチャンネルは完全な FIFO です。もちろんこれはこれで便利なのですが、表現しづらい状況もあって、例えば今回の例で使用した「Transaction Manager から Resource Manager 全体に Commit 命令をブロードキャスト」はとても書きにくい例です。
「ブロードキャスト用のキュー」を用意すると最初の RM が受信した時点でメッセージがキューから消えてしまい他の RM が読めなくなります。「受信できるかどうか確認だけする文」もありますが、これを使うと逆にチャンネル内に残ったメッセージを処理する方法に困ります。さらに、システムが停止したタイミングで中身が残ったチャンネルがあると、SPIN は一種のデッドロックであると考えエラーを報告します。
困った末、今回は各 RM 宛に一つづつチャンネルを用意するという形になりました。
検査の特徴
特定のプロセスの特定の箇所における条件を記述するために assert
文が使えます。通常のプログラム言語と同じように使ってももちろん機能しますが、SPIN の場合はその並列性を生かして「条件を監視するだけのプロセス」を用意しておくという tips が使えます。
byte counter = 0; proctype Incrementer { do :: counter = counter + 1; od } proctype Monitor { do :: assert(counter < 2) od }
上のシステムの実行パスの中には、例えば次のような実行パスがエラーとして含まれます。
Incrementer
が遷移してcounter
を 0 から 1 へ- もう一度
Incrementer
が遷移してcounter
を 1 から 2 へ Monitor
が遷移してassert
文を踏む
Incrementer
と Monitor
は実際には積オートマトンとして検査されるため、任意のタイミングの組み合わせについて、つまり Incrementer
が n 回続けて遷移した後に Monitor
が遷移するパターンはすべて検査されます。要するに「他のプロセスがどんな動き方をしても常に counter < 2
」という大域的な条件が検査できるわけです。
また LTL による検査も可能です。この場合は定義の中に直接書き込むのではなく、外部ファイルとして準備して実行時にオプションで与えます。その他、詳しくは以前に開催した勉強会の資料を参照してください。
TLA+
AWS 内で S3 や DynamoDB の検証に採用されたことで有名なツールです。
GUI サポート (TLA Toolbox) が充実している他、マニュアルやチュートリアルの類も公開されているので始めるための敷居は割と低いです。とりあえず雰囲気を掴みたいなら ビデオチュートリアル を眺めてみるのもよいでしょう。"These videos are not light entertainment." という脅し文句が太字で書かれていますが、言うほど難しくはありませんし、スクリプトも付いています。
形式化の特徴
生のままの TLA+ では、システムの初期状態と遷移を直接記述します。スライド中のサンプルよりもっと簡単な例で見たほうが分かりやすいでしょう。
VARIABLE b Init == /\ b = TRUE Next == b' = ~b
1 ステップごとに真偽値を反転させるだけのシステムです。b'
は b
の遷移先での値を表します。検査についてはこの後で述べますが、この Init
を初期状態、Next
を遷移関係として指定して検査させることになります。
プロセスについては陽には現れません。複数のプロセスが存在する場合、ナイーブにはそれらすべてを状態については /\
で、遷移については \/
でそれぞれ繋いで人間が積オートマトンを書くことになります。例えばこの真偽値反転システムが二つ非同期で動いているとしたら以下のようになります。
VARIABLES b1, b2 Init == /\ b1 = TRUE /\ b2 = TRUE Next == \/ b1' = ~b1 \/ b2' = ~b2
今回の発表で触れたのはここまでですが、実際にシステムを表現しようとすると、人間が明示的に各ステップを状態遷移に書き換える必要があるため非常に大変です。
この問題を解決するユーティリティとして、TLA+ では +CAL あるいは PlusCal と呼ばれるプログラミング言語チックな DSL も用意していて、ブロックコメント内に +CAL を記述すると、自動的に TLA+ の記法に変換されるようになっています。まずは単純な例から。
--algorithm SingleOscillator { variable b = TRUE; { while (TRUE) { b := ~b; } } }
ここから生成される TLA+ の仕様は以下のようになります。
VARIABLE b vars == << b >> Init == (* Global variables *) /\ b = TRUE Next == b' = ~b Spec == Init /\ [][Next]_vars
手書きの場合とおおむね同じような出力になりました。最後の Spec
は検査に使用する LTL 式ですが、後ほど説明します。
さらに、複数プロセスがある場合の +CAL 記述は次のようになります。
--algorithm MultiOscillator { process (oscillator \in {0, 1, 2}) variable b = TRUE; { start:while (TRUE) { b := ~b; } } }
新しい要素として、ラベル start
が導入されました。ラベルはブレイクポイントのように働き、不可分実行される単位を決めます。
生成される TLA+ 仕様は以下です。ハイライトがないとちょっと見づらいですね。
VARIABLE b vars == << b >> ProcSet == ({0, 1, 2}) Init == (* Process oscillator *) /\ b = [self \in {0, 1, 2} |-> TRUE] oscillator(self) == b' = [b EXCEPT ![self] = ~b[self]] Next == (\E self \in {0, 1, 2}: oscillator(self)) Spec == Init /\ [][Next]_vars
先ほどと違うのは、変数 b
が単なる TRUE
から [self \in {0, 1, 2} |-> TRUE]
、すなわちプロセスの識別子を取って TRUE
を返す関数に変わっていることです。これに伴って遷移条件 Next
もパラメータを導入した形に変わっています。\E
は存在量化子なので、遷移の条件は「プロセス 0, 1, 2 のいずれか一つについて遷移 occillator
が発生」と読むことができます。
検査の特徴
TLA+ でも、検査すべき性質として常に成立する条件 (Invariant) もしくは LTL による指定 (property) が可能です。
また、システムの遷移として Init
と Next
をナイーブに与える代わりに、LTL 式を指定することもできます。上で登場している
Spec == Init /\ [][Next]_vars
という記述がそれです。_vars
の部分は状態として含める変数の集合を指定しますが、特に意図がない限り VARIABLES
に定義したものをすべて入れておけば大丈夫です。
さらに、WF_vars(A)
と SF_vars(A)
という記法があらかじめ用意されています。前者は論理式 A
についての弱い公平性、後者は強い公平性をそれぞれ表現していて、公平性自体を検査対象にしたり、あるいは公平性を仮定して別の性質を検証できます。
P
Microsoft Research によるツールです。ちなみに同じチームから .NET 用のフレームワーク P# もリリースされています。
実行可能コードが出力できることを売り文句にしていて、MS Research の公式ブログでも SPIN や TLA+ に対して名指しで優位性を主張しています。SPIN はともかく TLA+ の開発者はかの Lamport 先生で、MS Research 所属なんですけども。
形式化の特徴
P による記述は、他の二つのツールより明らかに複雑です。各プロセス(P では machine と呼ばれます)の定義は、state とその state で反応すべき event、反応の内容を列挙する記述が基本になります。
machine Server { start state WaitPing { on PING goto SendPong; } state SendPong { entry (payload: machine) { send payload, PONG; raise SUCCESS; } on SUCCESS goto WaitPing; } }
上記のコードで定義された machine は以下のようなリアクティブな挙動をします。
- 初期状態は
WaitPing
PING
イベントを受信すると状態SendPong
に遷移payload
に格納されたクライアントの PID 宛にPONG
イベントを送り返し、かつ自分自身にSUCCESS
を発行- 状態
WaitPing
に遷移して次のイベントを待機
プロセスと独立にチャンネルが存在する SPIN とは異なり、メッセージの受信は 各 machine が所持している自分用の入力キューを介して行われます。送信側にキューはなく、送信したメッセージは即座に相手の入力キューに積まれます。
コード中に state
という予約語が出てきますが、紛らわしいことに、この state は実はオートマトンとしての状態とは必ずしも対応しません。というのも、P では「state を push/pop する」という操作があり、実際にオートマトンとしての状態に相当するのは state がスタックされたものになっているからです。新しい state が push されると、スタックの下側にある state に由来するハンドラは上書きされます。次に挙げたのはやや人工的な例です。
machine Server { start stat Init { entry { ... raise UNIT; } on TIMEOUT do {...} on UNIT push WaitPing; } start state WaitPing { on PING goto SendPong; } }
このとき、state Init
の上に state WaitPing
が積まれた状態になり、WaitPing
にいる間も Init
で定義された TIMEOUT
に対するハンドラが継承されます。
なお、イベントに対して処理を定義する以外にも、特定のイベントが発生した際にメッセージをデキューだけして捨てる ignore
、およびデキュー自体をブロックする deferred
が存在します。
検査の特徴
P では、検査したい条件も他の machine と同様、イベントハンドリングを用いて定義する必要があります。大域的な条件を検査するための記述は、例えば次のようなものです。
spec Safety observes PONG {
on PONG do (payload: machine) {
assert (...);
}
}
上のように spec
と observes
を定義すると、指定したイベント(ここでは PONG
)がシステム全体のどこかで発生したときは常にキャプチャされるようになり、内部に記述した assert
文の成立をチェックすることができます。ちょうど SPIN で「監視専用のプロセス」を定義したのと同じような仕組みです。
残念なことに、P は LTL による検査を直接にはサポートしません。その代わり、state に cold
および hot
のラベルを付けることが可能になっています。検査の際には、そのシステムの任意の実行パスが
cold
状態を無限回通過するかどうかhot
状態を無限回通過しないかどうか
が検査され、この二つを組み合わせることで LTL に相当する検査を行うことができます。
実は、SPIN ではこれに相当するプロセス (never claim) を処理系が生成してくれているのですが、このあたりをきちんと述べるには、スライドにも名前だけ出てきた Büchi オートマトンに関する説明が必要です。長くなりそうなのでまた記事を改めて解説したいと思います。
まとめ
この記事では、July Tech Festa 2018 での発表スライドを補足する形で、SPIN、TLA+、P のそれぞれについて簡単に紹介しました。ただ、ツールの特徴というか、書き心地みたいなものは実際に触ってみないとわからない部分も大きいので、もし今回の発表でモデル検査に興味を持った方はインストールして動かしてみて頂ければ幸いです。
ところで、ここまで説明しておいてなんですが、個人的には本当の初心者にまず薦めたいモデル検査ツールは Alloy なんですよね。近々 Alloy の初心者向けハンズオンを開催しようという腹案も温めていますが、それはまた別の話。
*1:2018/08/01 勘違いだったので撤回
We Are JavaScripters! @19th で Haskell 製フレームワーク Miso について話してきました
先日行われた We Are JavaScripters! @19th で Haskell によるフロントエンド開発について発表してきました。
Elm の代わりにフレームワーク Miso を使うことで、クライアントサイドとサーバサイドの両方を Haskell で実装することができる、という内容です。
なお今回のプレゼンでは、参加者のほとんどは Haskell に馴染みがないだろう*1ということもあって、実装上の詳細にはほとんど触れませんでした。
Elm と Miso の詳しい比較、さらに Servant と組み合わせた Isomorphic なアプリの作り方については、記事を改めて解説する予定です。特に現在、よく知られた Elm のチュートリアルを Miso で書き直している のですが、それはまた別の話。
*1:実際、Elm ですら聞いたことない人は結構いました。