区間ごとの p95 を平均したら本当の p95 より 108 ミリ秒高かった

目標

パーセンタイルを2つの方法で手計算して値が分かれることを確認し、区間ごとのp95の単純平均と加重平均が、全体のp95とどうずれるかを測り、ヒストグラムのバケットを足して合算する方法とその誤差を測ったあと、実際の負荷実行2回の結果を正しく合算するツールを作って提出します。

なぜ重要なのか

パーセンタイルは、平均と違って、部分から全体を作れません。平均は合計と個数でできているので、部分の合計を足せば全体になりますが、パーセンタイルはソートされた位置なので、部分の位置を足しても、全体の位置になりません。ところが、ダッシュボードやレポートは、区間ごとのp95を、何気なく平均します。その値は、真の値より高いことも低いこともあるので、「平均なら安全な側に間違うだろう」という直感も通用しません。さらに計算方法まで2つあるので、ツールを変えると、何も起きていないのにp95が悪化したように見えます。正しく合算する道は、元のデータをソートし直すか、ヒストグラムのバケットを足すかだけで、バケットに行くと、境界が誤差を決めます。この3つを手で一度やってみれば、次からは、元の出力ファイルを捨てなくなります。

ステップ

/opt/lab/lt/lt-percentiles/に、区間ごとのレイテンシのサンプルが3つあります(1行にミリ秒が1つ)。/root/lt-percentiles/shards.tsvを作成してください。3行で、各行はタブで区切った3列<파일이름> <표본 수> <p95>です(プレースホルダーはファイル名、サンプル数、p95です)。名前はshard-a・shard-b・shard-cの順に書き、p95は最近傍順位(ソートしたあとのceil(0.95 x n)番目の値)で求めて、小数第1位まで書きます。そして/root/lt-percentiles/01-note.txtに、total_n=<세 파일의 표본 수 합>とslowest=<p95 가 가장 큰 구간 이름>の2行を書いてください(プレースホルダーは、3つのファイルのサンプル数の合計と、p95が最大の区間の名前です)。
/root/lt-percentiles/pct.pyを作成してください。python3 pct.py <표본파일> <분위> <nearest|linear>で呼び出すと、パーセンタイル1つを小数第4位まで、1行で出力します(プレースホルダーは、サンプルファイルと分位です)。nearestはceil(분위 x n)番目に小さい値をそのまま使い、linearはh = (n - 1) x 분위の位置を、前後のサンプルの間で比例して作ります(プレースホルダーは分位です)。そのツールで/opt/lab/lt/lt-percentiles/tiny.txt(20行)を測って、/root/lt-percentiles/methods.tsvに3行を書いてください。各行はタブで区切った3列<분위> <nearest> <linear>で(プレースホルダーは分位です)、分位は0.50・0.95・0.99の順、値は小数第4位までです。そして/root/lt-percentiles/02-note.txtに、gap_p95=<0.95 에서 linear 빼기 nearest>の1行を、小数第4位まで書いてください(プレースホルダーは、0.95でlinearからnearestを引いた値です)。
/root/lt-percentiles/combine.txtに、5行を書いてください。mean_of_p95=は、ステップ1で求めた3つのp95の単純平均、weighted_mean_of_p95=は、サンプル数を重みとして使った平均、true_p95=は、3つのファイルの元のデータをすべて合わせて、最近傍順位で求め直したp95です。続いて、error_mean=にmean_of_p95からtrue_p95を引いた値を、error_weighted=にweighted_mean_of_p95からtrue_p95を引いた値を書きます。5つの値はすべて小数第1位まで、負の数ならマイナス記号を付けます。
/root/lt-percentiles/bound.tsvに、2行を書いてください。各行はタブで区切った3列<이름> <표본 수> <p95>で(プレースホルダーは名前、サンプル数、p95です)、1行目は名前がall(3つの区間をすべて合わせたもの)、2行目はno-c(shard-aとshard-bだけを合わせたもの)です。p95は最近傍順位で、小数第1位まで。そして/root/lt-percentiles/04-note.txtに、3行min_shard_p95=・max_shard_p95=・inside=<yes|no>を書いてください。insideは、allのp95が、区間ごとのp95の最小値と最大値の間にあればyesです。
/root/lt-percentiles/hist.pyを作成してください。python3 hist.py <경계를 쉼표로> <표본파일...>で呼び出すと、タブ2列の表を出力します(プレースホルダーは、カンマ区切りの境界と、サンプルファイルです)。各行は<경계> <그 경계 이하인 표본의 누적 개수>で、最後の行は+Inf <전체 개수>です(プレースホルダーは、境界、その境界以下のサンプルの累積個数、全体の個数です)。ファイルを複数渡すと、ファイルごとに数えたあと、同じ境界どうしを足します。このツールに、境界50,100,250,500,1000と、3つの区間のファイルをすべて渡して出た表を、/root/lt-percentiles/hist-coarse.tsvに保存してください。そして/root/lt-percentiles/hist-p95.txtに、3行est_p95=・true_p95=・abs_error=を、小数第1位まで書きます。est_p95は、その表から線形補間で推定したp95です。累積個数が0.95 x 전체以上になる最初の境界を探して(プレースホルダーは全体です)、前の境界とその境界の間を、累積個数に比例して分けます(前の境界がなければ0と見ます)。
同じサンプルを、細かい境界50,75,100,125,150,200,250,300,400,500,750,1000,1500で数え直して、/root/lt-percentiles/hist-fine.tsvに保存してください。そして/root/lt-percentiles/error.tsvに、2行を書きます。各行はタブで区切った3列<이름> <추정 p95> <절대 오차>で(プレースホルダーは、名前、推定p95、絶対誤差です)、名前はcoarse・fineの順、値は小数第1位までです。誤差は、ステップ3のtrue_p95との差の絶対値です。最後に/root/lt-percentiles/06-note.txtに、better=<coarse|fine>とreason=<40자 이상>の2行を書いてください(プレースホルダーは、40文字以上です)。reasonには、細かい境界がタダではない理由も、一緒に書きます。
/opt/lab/lt/lt-percentiles/target.pyを、ポート8080で起動してください(/fastは30ミリ秒、/slowは250ミリ秒)。heyを2回回して、元の出力を残します。hey -n 300 -c 10 -o csv http://127.0.0.1:8080/fastを/root/lt-percentiles/run-fast.csvに、hey -n 100 -c 10 -o csv http://127.0.0.1:8080/slowを/root/lt-percentiles/run-slow.csvに。そのあと/root/lt-percentiles/runs.txtに、4行を書いてください。p95_fast=・p95_slow=・mean_of_p95=(2つのp95の単純平均)・merged_p95=(2つの実行の元の応答時間をすべて合わせて、求め直したp95)です。すべて秒単位で小数第4位までで、status-codeが200の行だけを数えます。
/root/lt-percentiles/merge_p95.pyを作成してください。python3 merge_p95.py <분위> <hey CSV...>で呼び出すと(プレースホルダーは、分位とhey CSVです)、CSVのstatus-codeが200の行から、最初の列(応答時間、秒)をすべて1つの桶に集めて、最近傍順位でパーセンタイルを求め、小数第4位まで1行で出力します。実行ごとにパーセンタイルを求めて平均してはいけません。そのツールを、ステップ7の2つのCSVに対して実行して、/root/lt-percentiles/merged.txtに4行を書いてください。q=0.95・merged_p95=・mean_of_p95=・gap=(mergedからmeanを引いた値)です。最後に/root/lt-percentiles/policy.txtに、rule=で始まる1行を60文字以上で書き、今後、複数回の負荷テストの結果を合算するときに、チームが守るルールを書いてください。

参考

作業ディレクトリは/root/lt-percentilesです。なければ先に作成してください。
用意されたデータは/opt/lab/lt/lt-percentiles/にあります。shard-a.txt(6000行)・shard-b.txt(3000行)・shard-c.txt(1000行)は1行にミリ秒が1つで、tiny.txt(20行)は、計算方法の違いを見るための小さなサンプルです。make_shards.pyが、これらのファイルを作った固定シードのスクリプトで、target.pyは、ステップ7で起動する負荷対象です。
負荷対象は、コンテナではなく、Python標準ライブラリのサーバーです。このラボ環境では、コンテナを起動できません。(nohup python3 <경로>/target.py 8080 >/dev/null 2>&1 &)で起動し、curlで一度確認してから、負荷をかけてください(プレースホルダーはパスです)。
よくある間違い: heyの出力で、ステータスコードを絞り込まないこと。失敗したリクエストの時間が混ざると、パーセンタイルが変わります。
よくある間違い: サンプルが少ないときの2つの計算方法の差を、「誤差」と見てしまうこと。どちらも正しい定義で、何を使っているかを書いておかないことが問題です。
Histograms and summaries (Prometheus)・Query functions — histogram_quantile・k6 metrics reference・k6 thresholds・HdrHistogram・hey

区間ごとに何件で、p95はいくつか

/opt/lab/lt/lt-percentiles/に、区間ごとのレイテンシのサンプルが3つあります(1行にミリ秒が1つ)。/root/lt-percentiles/shards.tsvを作成してください。3行で、各行はタブで区切った3列<파일이름> <표본 수> <p95>です(プレースホルダーはファイル名、サンプル数、p95です)。名前はshard-a・shard-b・shard-cの順に書き、p95は最近傍順位(ソートしたあとのceil(0.95 x n)番目の値)で求めて、小数第1位まで書きます。そして/root/lt-percentiles/01-note.txtに、total_n=<세 파일의 표본 수 합>とslowest=<p95 가 가장 큰 구간 이름>の2行を書いてください(プレースホルダーは、3つのファイルのサンプル数の合計と、p95が最大の区間の名前です)。

ソートはsort -n、行数はwc -lです。最近傍順位の位置の番号はceil(0.95 x n)で、awkではint(0.95*n) + (0.95*n > int(0.95*n) ? 1 : 0)で作ります。3つの区間のサンプル数が互いに違うという点に注目してください。あとのステップで、その違いが答えを変えます。

同じサンプル、2つの計算方法

/root/lt-percentiles/pct.pyを作成してください。python3 pct.py <표본파일> <분위> <nearest|linear>で呼び出すと、パーセンタイル1つを小数第4位まで、1行で出力します(プレースホルダーは、サンプルファイルと分位です)。nearestはceil(분위 x n)番目に小さい値をそのまま使い、linearはh = (n - 1) x 분위の位置を、前後のサンプルの間で比例して作ります(プレースホルダーは分位です)。そのツールで/opt/lab/lt/lt-percentiles/tiny.txt(20行)を測って、/root/lt-percentiles/methods.tsvに3行を書いてください。各行はタブで区切った3列<분위> <nearest> <linear>で(プレースホルダーは分位です)、分位は0.50・0.95・0.99の順、値は小数第4位までです。そして/root/lt-percentiles/02-note.txtに、gap_p95=<0.95 에서 linear 빼기 nearest>の1行を、小数第4位まで書いてください(プレースホルダーは、0.95でlinearからnearestを引いた値です)。

ソートしたリストで、nearestはインデックスk-1、linearはvalues[lo] + (h-lo) x (values[hi]-values[lo])です。20個のサンプルは、2つの方法の差が目に見えるように選んだものです。特に、一番上の2つの値が遠く離れています。採点ツールは、自分で作ったサンプルファイルでこのツールを直接実行してみます。

区間ごとのp95を平均しても、全体のp95にはならない

/root/lt-percentiles/combine.txtに、5行を書いてください。mean_of_p95=は、ステップ1で求めた3つのp95の単純平均、weighted_mean_of_p95=は、サンプル数を重みとして使った平均、true_p95=は、3つのファイルの元のデータをすべて合わせて、最近傍順位で求め直したp95です。続いて、error_mean=にmean_of_p95からtrue_p95を引いた値を、error_weighted=にweighted_mean_of_p95からtrue_p95を引いた値を書きます。5つの値はすべて小数第1位まで、負の数ならマイナス記号を付けます。

元のデータを合わせるのは、cat /opt/lab/lt/lt-percentiles/shard-*.txtの1回でよいのです。ステップ2で作ったpct.pyを、そのまま使ってください。2つの誤差の符号が互いに違うという点が、このステップの核心です。平均は、片方にだけ間違うわけではありません。

合算したp95が収まりうる枠

/root/lt-percentiles/bound.tsvに、2行を書いてください。各行はタブで区切った3列<이름> <표본 수> <p95>で(プレースホルダーは名前、サンプル数、p95です)、1行目は名前がall(3つの区間をすべて合わせたもの)、2行目はno-c(shard-aとshard-bだけを合わせたもの)です。p95は最近傍順位で、小数第1位まで。そして/root/lt-percentiles/04-note.txtに、3行min_shard_p95=・max_shard_p95=・inside=<yes|no>を書いてください。insideは、allのp95が、区間ごとのp95の最小値と最大値の間にあればyesです。

トラフィックの10%しかない遅い区間を1つ除くと、全体のp95がどれだけ下がるかを見てください。そして枠を考えてみると、すべての区間で95%がある値以下なら、混ぜても95%はその値以下です。そのため、「合算したら、すべての区間より大きかった」という報告は、データではなく、計算を疑う必要があります。

バケットは足せる

/root/lt-percentiles/hist.pyを作成してください。python3 hist.py <경계를 쉼표로> <표본파일...>で呼び出すと、タブ2列の表を出力します(プレースホルダーは、カンマ区切りの境界と、サンプルファイルです)。各行は<경계> <그 경계 이하인 표본의 누적 개수>で、最後の行は+Inf <전체 개수>です(プレースホルダーは、境界、その境界以下のサンプルの累積個数、全体の個数です)。ファイルを複数渡すと、ファイルごとに数えたあと、同じ境界どうしを足します。このツールに、境界50,100,250,500,1000と、3つの区間のファイルをすべて渡して出た表を、/root/lt-percentiles/hist-coarse.tsvに保存してください。そして/root/lt-percentiles/hist-p95.txtに、3行est_p95=・true_p95=・abs_error=を、小数第1位まで書きます。est_p95は、その表から線形補間で推定したp95です。累積個数が0.95 x 전체以上になる最初の境界を探して(プレースホルダーは全体です)、前の境界とその境界の間を、累積個数に比例して分けます(前の境界がなければ0と見ます)。

バケットは累積です。le=100は「100以下のものが何件」であって、「50と100の間」ではありません。推定式は、Prometheusのhistogram_quantileと同じです。目標の個数が、バケットの中のどのあたりかを、比例で見ます。採点ツールは、自分で作ったサンプルと境界で、このツールを直接実行してみます。

境界が誤差を決める

同じサンプルを、細かい境界50,75,100,125,150,200,250,300,400,500,750,1000,1500で数え直して、/root/lt-percentiles/hist-fine.tsvに保存してください。そして/root/lt-percentiles/error.tsvに、2行を書きます。各行はタブで区切った3列<이름> <추정 p95> <절대 오차>で(プレースホルダーは、名前、推定p95、絶対誤差です)、名前はcoarse・fineの順、値は小数第1位までです。誤差は、ステップ3のtrue_p95との差の絶対値です。最後に/root/lt-percentiles/06-note.txtに、better=<coarse|fine>とreason=<40자 이상>の2行を書いてください(プレースホルダーは、40文字以上です)。reasonには、細かい境界がタダではない理由も、一緒に書きます。

バケットの推定の誤差は、「目標が入っているバケットの幅」が決めます。250から500まで1つの欄の表と、250から300まで1つの欄の表で、同じ目標を探してみてください。その代わり、境界を増やすと、時系列もその分増えます。Prometheusでは、境界1つがそのまま時系列1本です。

実際の2つの実行を合算してみる

/opt/lab/lt/lt-percentiles/target.pyを、ポート8080で起動してください(/fastは30ミリ秒、/slowは250ミリ秒)。heyを2回回して、元の出力を残します。hey -n 300 -c 10 -o csv http://127.0.0.1:8080/fastを/root/lt-percentiles/run-fast.csvに、hey -n 100 -c 10 -o csv http://127.0.0.1:8080/slowを/root/lt-percentiles/run-slow.csvに。そのあと/root/lt-percentiles/runs.txtに、4行を書いてください。p95_fast=・p95_slow=・mean_of_p95=(2つのp95の単純平均)・merged_p95=(2つの実行の元の応答時間をすべて合わせて、求め直したp95)です。すべて秒単位で小数第4位までで、status-codeが200の行だけを数えます。

hey -o csvの最初の列が応答時間(秒)、7番目の列がステータスコードです。ヘッダーの1行は飛ばしてください。ステップ2のpct.pyをそのまま使うには、cut -d, -f1で数字だけを取り出して、一時ファイルに集めればよいのです。2つの実行の件数が違うという点に注意してください。合算した結果がどちらに傾くかが見えます。

複数の実行を正しく合算するツール

/root/lt-percentiles/merge_p95.pyを作成してください。python3 merge_p95.py <분위> <hey CSV...>で呼び出すと(プレースホルダーは、分位とhey CSVです)、CSVのstatus-codeが200の行から、最初の列(応答時間、秒)をすべて1つの桶に集めて、最近傍順位でパーセンタイルを求め、小数第4位まで1行で出力します。実行ごとにパーセンタイルを求めて平均してはいけません。そのツールを、ステップ7の2つのCSVに対して実行して、/root/lt-percentiles/merged.txtに4行を書いてください。q=0.95・merged_p95=・mean_of_p95=・gap=(mergedからmeanを引いた値)です。最後に/root/lt-percentiles/policy.txtに、rule=で始まる1行を60文字以上で書き、今後、複数回の負荷テストの結果を合算するときに、チームが守るルールを書いてください。

ヘッダーの1行を飛ばして、列が7個より少ない行は捨ててください。ステータスコードを絞り込まないと、失敗したリクエストの時間まで混ざって、答えが変わります。採点ツールは、自分で作った2つのCSVで、このツールを2つの分位で実行してみます。実行ごとに平均する実装や、ステータスコードを絞り込まない実装は、その場で落ちます。