2016年5月3日
ソフトウェアのための統計学 – 前編
(2016-04-11)by Mahmoud Hashemi
本記事は、原著者の許諾のもとに翻訳・掲載しております。
ソフトウェア開発の原点は可能性の追求であり、不可能を可能にすることです。ひとたび ソフトウェア が開発されると、エンジニアは次に 程度 という課題に向き合うことになります。企業向けのソフトウェアであれば、「速度はどれくらいか」と頻繁に問われ、「信頼性はどの程度か」という点が重視されます。
ソフトウェアのパフォーマンスに関する質問に答え、さらには正しい内容を語る上で欠かせないのが統計学です。
とはいえ、統計学について多くを語れる開発者はそうはいません。まさに数学と同じで、一般的なプロジェクトで統計学が話題に上ることなどないのです。では、新規にコーディングをしたり、古いコードのメンテナンスをしたりする合間に、手が空くのは誰でしょうか？
エンジニアの方は、ぜひ時間を作ってください。近頃は、15分でも貴重な時間と言えるでしょうから、 こちらの記事をブックマークに追加 しておいてもいいでしょう。とにかくTLDR（長文を嫌う人のための要約）を読みたいという方は、計測のセクションや、まとめまで飛んでいただいても構いません。
では、数少ない熱心な方のために説明を始めましょう。ここから本題に入り、効果的な手法を学びながら、勘に頼らないソフトウェア開発を目指していきます。価値あるシステム分析を行うには、中核となる数個の処理が大きな役割を果たします。逆に、少しのつまらないミスが原因で、プロジェクトが振り出しに戻ることもあります。この記事では応用統計学によって得られる答えを通じてソフトウェアのメンテナンスを簡易化し、今後の開発を高速化することを目標にしています。
データ収集と慣習
まずは、計測や改善を行うコンポーネントを決めましょう。PayPalの場合は大抵、何百とあるHTTPサーバアプリケーションの1つを対象にします。PayPalの内部フレームワークを見たことがある方なら、測定結果を次々と取得するためのコードパスが何百もあるのに気付いたでしょう。測定しているのは、関数の実行時間やサービス遅延、リクエストの長さ、応答コードなどです。
詳細は以下の計測のセクションで説明しますが、ひとまずこれらの計測ポイントは既に存在するものとして、実行時間などの数値計測に注目していきましょう。
出発点が適切であれば、偏りは最小限に抑えられます。ここでは極力、物事を決めてかからずに、計測結果をランダムな変数値として扱います。それでは、 要約統計量 という広大な世界への扉を開きましょう。要約統計量とは、ランダムな振る舞いを記述するための専門領域です。当たり前だと思うかもしれませんが、統計学の大半は未来の結果をモデル化するための 推計統計学 であることを忘れないでください。この2つは関連が深く、その違いと適切な名称を知っていると、今後の調査スピードが格段に上がります。 レッスン1は、「正しい統計学用語を知っておいて損はなし」です。
測定はバランスが全てです。データが少なすぎるのは、手抜きと言えるでしょう。さらには、情報不足で下した判断によってサービスがダウンしかねません。もちろん、データが多すぎてサービスがダウンすることもあるでしょう。メモリの消費量に注意していたとしても、超過データを管理できるだけのリソースは考慮するようにしましょう。「 ビッグデータ 」は重要ではありますが、大規模システムを理解する上で必須ではありません。重要なのは密度が高い、バランスの取れたデータです。
ではバランスのとれた測定をするために、エンジニアはどんなツールを使っているのでしょうか。メタデータにおいては常に十分な容量、ディメンション、手法があります。その中で迷わないように、ここでは最小限のオーバーヘッドで収集できる要約統計量に焦点を絞ります。では方向性が決まったので、おなじみの分野をいくつか見ていきましょう。
真なるモーメント
統計モーメントという言葉は耳慣れないかもしれませんが、その実態は誰もが使っているものです。10歳にもなれば大半の学生が平均、つまりは 算術平均 を計算できます。このような普通の平均は、統計学者の間では1次 モーメント と呼ばれます。算術平均は計算が楽で、実に有意義なものです。ただ、この記事では訳あって、さらに踏み込んだ内容を扱います。
最も有名な算術平均を含め、一般的に使用されているモーメントは4つあります。これらのモーメントを用いて構成された数列を足し合わせると、標準的なデータ記述になります。
算術平均、分散、歪度、尖度。どれも水色、黄色、ピンクの順に値が大きくなる。
これら4つの 標準化モーメント は、 分布図の説明 で、最も広く適用されている評価尺度です。測定回数が増えるほど値の有用性が下がるので、歪度と尖度は省かれることが多くなります。これらの尺度について初めて聞くという人が多いので、省略するのも悪くないでしょう。
パフォーマンス志向のエンジニアにとって、算術平均、分散、歪度、尖度が適切なツールとなることは、ほぼ あり得ません。 モーメントに基づく尺度では、私たちが求める重要な技術的メタデータの尺度として、信頼性のある情報を得られないのです。
モーメントに基づく尺度は ロバスト統計 ではありません。また、ロバスト統計ではないというのと同時に以下のことが言えます。
- 外れ値によってねじ曲がる。
- 外れ値の意味を希薄にする。
外れ値 とは、他の分布から離れているデータポイントのことです。「外れ値｣という言葉から、ごくわずかしかなく起こる確率の低い値だと想像するでしょう。しかし、実は至る所にあり、モーメントに基づく統計を役に立たない、どちらかというと危険な情報にしてしまうのです。外れ値はトラブルシューティングを扱うエンジニアにとって、最も重要なデータとなることもよくあります。
それでは、なぜ、ソフトウェアにモーメント（moments）を用いる人が、いまだに数多くいるのでしょうか。簡単な答えをシャレで言うと、勢い（momentum）です。算術平均と分散には2つの利点があります。簡単に導入できるという点と、用途が広いという点です。実際には、この良く知られた方法が、外れ値のような特殊な値を無視してしまい、有害な仮定を導きます。ソフトウェアのパフォーマンスにとって、算術平均と分散はロバスト統計のコンテキストとして のみ 有用です。
さあ、十分準備ができました。 レッスン2は、「算術平均や分散など、ロバスト統計以外の尺度だけに頼ってデータを分析するのはやめろ」です。 では、どんなロバスト統計のテクニックに頼ったらいいのでしょうか？
分位数の仕組み
国勢調査のデータや全国共通テストの結果を見たことがあれば、すでに 分位数 について、よくご存知でしょう。最も一般的なのは、 四分位数 （4分割）と、 パーセンタイル値 （100分割）です。 代表値 は、最も使用される機会が増えてきている手法です。50パーセンタイルとなる 中央値 も、同様によく使われるようになってきました。
経験豊富なエンジニアは、算術平均よりも中央値を好むようですが、極値を得る前のデータはあまり意味がりません。ソフトウェアのパフォーマンスと信頼性にとって、それは95パーセンタイルや、98パーセンタイル、99パーセンタイル、99.5パーセンタイルなどを意味します。私たちはこれを極値と呼びますが、高トラフィックのシステムでは、 いつでも起こり得る ことです。また、最小値と最大値の示す範囲についても見ていきます。この最小値と最大値は0番目と100番目のパーセンタイル値と呼ばれることもあります。
分位数と範囲に取り組むことが、効率的な計算につながります。例えば、中央値を求める王道は、 全て のデータをソートし、真ん中の値か2つの中央値の平均を選ぶことです。全てのデータを一度に考えることが、正確な分位数を計算する唯一の方法なのです。
私たちの使用事例を考えると、全てのデータをメモリに保持すると恐ろしいほど大きな負荷になるでしょう。そうではなく、「必要を満たせればいい」という考え方を用いれば、エンジニアはずっと効率的に分位数を計算することができます。統計学は効率との妥協の上に成り立っているのです。
ストリームに足を踏み入れる
統計学とは、供給の行き届かない母集団の近似値を出すという物流の問題を扱うための学問分野として生まれました。現代でも、全員の世論調査を行ったり、全てのリンゴの味見をしたり、全ての自動車を運転することは不可能です。そのため、統計は今後も必要です。
ソフトウェアのパフォーマンスという領域では、データの収集は自動化でき、測定も 必要以上に 自動化されています。そして問題は、照合やインデックス化、保管などへと移ってきました。問題は困難さを増し、働き詰めの人々があふれるようになっています。
私たちは、物ごとを簡単にしようと試みています。難しい問題は避けたいものです。膨大なデータを避ける最も簡単な方法は、データを捨ててしまうことです。廃棄されたデータは保管する必要もないでしょう。ただし、慎重に行わなければデータは残ってしまい、偏りとして出没します。私たちに必要なのは、最初の状態の意味のあるデータです。母集団に限りなく近い、ずっと小さなデータが望ましいでしょう。そのために、統計学には 無作為（ランダム）抽出 があります。
レザボアサンプリングは、ほんの少しのデータだけを保有し、そのほとんどが回収されません。
ひとひねりすると、1回につき1つのデータポイントだけを考慮して、未知の母集団からサンプルを求めたいということです。この使用事例は、コンピューターサイエンス特有の部分を必要とします。これは オンラインアルゴリズム で、 ストリームアルゴリズム のサブクラスです。”オンライン”が意味するのは、個々の点だけが単一パスで考慮されるということです。また”ストリーム”が意味するのは、プログラムは一度にデータのサブセットを考慮するだけですが、バッチで動かすことも複数のパスで実行することもできる、ということです。幸いなことに、 Donald Knuth のおかげで、ストリームから無作為抽出を可能にする明解なアプローチが普及しました。 レザボアサンプリング（Reservoir Sampling） です。さあ、足を踏み入れてみましょう。
まず、 counter を指定して、出現するデータポイントごとにインクリメントします。 reservoir は、通常、あらかじめ定義された size のリストまたは配列です。これでデータを追加する準備ができました。要素数が size 個にに行き当たるまで、要素は直接 reservoir に加えられます。 reservoir がいっぱいになってしまえば、後から入って来るデータポイントには、既存のサンプルポイントと置き換える size / counter のチャンスがあります。データポイントの値は考えませんし、定義からはランダムな偶然が保証されます。こんなふうに reservoir は、常にデータセット全体の代表となります。また、最後のデータポイントからの値と同様に、最初のデータポイントの値も持っている可能性が高いです。このことは全て、所有メモリ量の範囲内で、計算量もわずかです。下の計測のセクションで、Pythonの実装例を紹介しているのでご覧ください。
より簡単に言えば、レザボアは、固定サイズのサムネイルのような、データを小規模にしたバージョンのものを連続的に生成します。 未知の大きさの母集団を扱うレザボアサンプリングの能力は、レスポンス遅延や長時間続いているサーバプロセスの他の測定基準の追跡にとても適しています。
解釈
レザボアによりサンプルを得た後、必然的に生じる次のステップは何でしょう。PayPalの標準的な手順は下のようになっています。
- 最小値、最大値、他の割合の分位数を見る（一般的には中央値、95パーセンタイル、99パーセンタイル、99.9パーセンタイル）。
- データの形を把握するために 累積分布関数 と ヒストグラム を視覚化する。通常は Jupyter Notebookとでデータをロードして、 pandas と matplotlib を使用します。また時々 Bokeh も使います.
レザボアは、パフォーマンスデータのヒストグラムの全体像を把握するのに理想的です。CDFのオーバレイとQQのプロットは、比較をするのに便利です。
本当にこれだけです。このほかに、通常はより多くのディメンションを加えています、例えば、超過時間やデータセンター間の比較などです。データの範囲、変位量、サンプルビューを用いると、余計な推測を確実に消すことができ、結局は時間の節約になります。タイムアウトをしっかりと管理し、リトライを実装し、テストして、配備します。もしかしたら Apdex のスコアのような、より高水準の受け入れ基準を付け加えるかもしれません。パフォーマンス問題に関わらず、私たちはいつそれを修正したのか分かっています。また裏付けとなる正しい数値とチャートもあります。
制約
正確さとはは「適切な解像度を持つ」ことの問題です。
レザボアサンプリングには欠点があります。特に、画像のサムネイルと同じように、設定された解像度の範囲の正確さにしかならないのです。境界付近のデータに少しムラが生じる場合があります。レザボアサンプリングをうまく実装すると最大値と最小値が追跡できます。しかし境界に興味のあるエンジニアに対しては、外れ値を抽出した追加セットを保持することを進めます。例えば、クリティカルパスについては、直近に観測された n 番目に良いレスポンス時間を明示的に追跡することもあります。
実行環境により、リソースは重要なものとなるかもしれません。レザボアサンプリングに必要な処理能力はわずかなものです。ただし効率的な 擬似乱数 を生成できればの話です。これはArduinoにさえ備わっています。しかしメモリの費用がかさみます。一般的に言って、正確さはサイズの平方根に比例します。倍の正確さには4倍のコストが掛かります。これは正に「収穫逓減の法則」です。
PayPalでは、代表的なレザボアに16384個の浮動小数点スロットが割り当てられており、トータルで64キロバイトになります。この分では、サーバの前に、人間がメモリを使い果たしてしまいます。500個の変数の追跡に必要なのは、8メガバイトだけです。開発者として、全ての変数が何であるかを覚えていることとは、別の話です。
遷移
大抵の場合、レザボアから自分たちの欲しいものを得て、非統計的な開発を続けることは可能です。しかし、時には、より状況に即したアプローチが求められる場合があります。
パフォーマンスデータを処理するために、PayPalでは様々な点で、 q-digest 、偏りのある分位数推定、その他の高度なアルゴリズムに数多く取り組んできました。試行を重ねた結果、2つのアプローチが主力として残っています。どちらも人が推定するよりはるかに簡単な方法です。
最初のアプローチはヒストグラムカウンタで、特定のレザボアから収集された統計情報に基づいて、ビンまたはバケットと呼ばれる注目範囲を設定します。レザボアの集計は、データを収める場所を決定するために無作為に選んだ値だけを見るのでデータの内容には依存しません。一方、バケットの集計では値を見て、その値が含まれるバケットを見つけて、バケットに対応付けられたカウンタをインクリメントします。値自体は保存されません。コードはシンプルであり、メモリの消費もさらに少ないですが、重要な利点は実行速度です。バケットの集計はオーバーヘッドが非常に少ないので、他のアルゴリズムよりも、コードの奥深くまで統計情報を収集することができます。
2番目のアプローチは 区分的放物型分位数推定 （略してP2）で、エンジニアリングの代表的なものです。1980年代のエレクトロニクス産業から生まれたP2は、もともと単純なデバイス向けに設計された実用的なオンラインアルゴリズムです。レザボアの分布を見て、ある分位数に対してもっと分解が必要かどうかを決定する際、P2によって、前もって分位数を指定し、1つ1つの観測ごとにその値を保持することができます。メモリの消費量は非常に少ないのですが、関連する計算のせいで、P2は、レザボアサンプリングやバケットの集計よりもCPUを多く使用します。さらに、P2推定を複数組み合わせるのを見たことはありませんが、それは簡単ではないと想定されます。一方、P2推定が優れている点は、私たちが目にするほとんどの分布で、レザボアサンプリングよりも桁違いに正確だということです。
この2つのアプローチは、どちらもレザボアサンプルから記録したものを取って少ない方にそれを割り当てます。ヒストグラムは事前に設定された値の範囲に関する解を、P2は事前に設定された注目する分位数ポイントでの解を与えてくれます。 レッスン3は、あなたが解決しなければならない問題に合った統計学を選択することです。もしその問題が何かわからない場合は、レザボアサンプリングのような一般的なツールを使い続けてください。
