このトピックに関するブログ投稿を公開したことがあります。ブログは現在廃止されていますが、記事は以下に完全に含まれています。
基本的な考え方は、正確な計算の要件を減らして、「応答の 95% パーセントが 500ms ～ 600ms 以下である」 (すべての正確な 500ms ～ 600ms のパーセンタイル) を優先することです。
最近、Web アプリケーションの 1 つの応答時間が遅くなったと感じ始めたので、アプリケーションのパフォーマンスを微調整することに時間を費やすことにしました。最初のステップとして、現在の応答時間を完全に把握したいと考えました。パフォーマンス評価では、最小、最大、または平均の応答時間を使用することはお勧めできません。「『平均』はパフォーマンス最適化の悪であり、多くの場合、『病院内の患者の平均体温』と同じくらい役に立ちます」( MySQL パフォーマンス ブログ)。代わりに、パフォーマンス チューナーはパーセンタイルを確認する必要があります。: 「パーセンタイルは、観測値の特定の割合がそれを下回る変数の値です」(ウィキペディア)。つまり、95 パーセンタイルは、リクエストの 95% が完了した時間です。したがって、パーセンタイルに関連するパフォーマンス目標は、「95 パーセンタイルは 800 ミリ秒未満にする必要がある」のようになります。このようなパフォーマンス目標を設定することは 1 つのことですが、稼働中のシステムでそれらを効率的に追跡することは別のことです。
パーセンタイル計算の既存の実装を探すのにかなりの時間を費やしました (例: ここまたはここ)。それらはすべて、すべてのリクエストの応答時間を保存し、オンデマンドでパーセンタイルを計算するか、新しい応答時間を順番に追加する必要がありました。これは私が欲しかったものではありませんでした。私は、何十万ものリクエストに対してメモリと CPU の効率的なライブ統計を可能にするソリューションを望んでいました。何十万ものリクエストの応答時間を保存し、必要に応じてパーセンタイルを計算することは、CPU 効率もメモリ効率も良くないように思えます。
私が望んでいたような解決策は、単に存在しないようです。考え直して、別のアイデアを思いつきました。私が探していたタイプのパフォーマンス評価では、正確なパーセンタイルを取得する必要はありません。「95 パーセンタイルは 850 ミリ秒から 900 ミリ秒の間です」のようなおおよその答えで十分です。このように要件を下げると、特に可能な結果の上限と下限がわかっている場合は、実装が非常に簡単になります。たとえば、私は数秒を超える応答時間には興味がありません。10 秒であろうと 15 秒であろうと、いずれにしても非常に悪い結果です。
したがって、実装の背後にあるアイデアは次のとおりです。
- ランダムな数の応答時間バケットを定義します (例:
0-100ms、100-200ms、200-400ms、…)400-800ms800-1200ms
- 応答数と各バケットの応答数をカウントします (応答時間が 360ms の場合、200ms ～ 400ms のバケットのカウンタをインクリメントします)
- 合計が合計の n パーセントを超えるまでバケットのカウンタを合計して、n 番目のパーセンタイルを推定します
それはとても簡単です。そして、ここにコードがあります。
いくつかのハイライト:
public void increment(final int millis) {
final int i = index(millis);
if (i < _limits.length) {
_counts[i]++;
}
_total++;
}
public int estimatePercentile(final double percentile) {
if (percentile < 0.0 || percentile > 100.0) {
throw new IllegalArgumentException("percentile must be between 0.0 and 100.0, was " + percentile);
}
for (final Percentile p : this) {
if (percentile - p.getPercentage() <= 0.0001) {
return p.getLimit();
}
}
return Integer.MAX_VALUE;
}
このアプローチでは、バケットごとに 2 つの int 値 (= 8 バイト) しか必要なく、1K のメモリで 128 のバケットを追跡できます。50 ミリ秒の粒度を使用して Web アプリケーションの応答時間を分析するには十分です)。さらに、パフォーマンスのために、一部のインクリメントが失われる可能性があることを認識して、意図的に同期を行わずに (たとえば AtomicIntegers を使用して) これを実装しました。
ちなみに、Google チャートと 60 パーセンタイル カウンターを使用して、収集した 1 時間の応答時間から素敵なグラフを作成できました。
