ライブ データ キャプチャのパーセンタイル

Question

ライブ データ キャプチャのパーセンタイルを決定するアルゴリズムを探しています。

たとえば、サーバー アプリケーションの開発を考えてみましょう。

サーバーの応答時間は次のようになります。17 ms 33 ms 52 ms 60 ms 55 msなど

90 パーセンタイル応答時間、80 パーセンタイル応答時間などをレポートすると便利です。

単純なアルゴリズムでは、各応答時間をリストに挿入します。統計が要求された場合は、リストをソートして適切な位置の値を取得します。

メモリ使用量はリクエスト数に比例して増加します。

メモリ使用量が限られている場合に、「おおよその」パーセンタイル統計を生成するアルゴリズムはありますか?たとえば、何百万ものリクエストを処理する方法でこの問題を解決したいとしますが、パーセンタイルの追跡にはたとえば 1 キロバイトのメモリのみを使用したいとします (パーセンタイルはすべてのリクエストに対応します)。

また、分布に関する事前知識がないことも必要です。たとえば、事前にバケットの範囲を指定したくありません。

Answer 1

私はこの問題のために多くの良い近似したアルゴリズムがあると信じています。良好な第一カット手法は、単に、固定サイズの配列（データの発言1K価値）を使用することです。いくつかの確率pを修正。各要求に対して、確率pで、配列（そこで最も古い時刻を置換）にその応答時間を書きます。配列は、ライブストリームのサブサンプリングされ、サブサンプリングは、ディストリビューションを維持するので、あなたの完全な、ライブストリームの統計の近似値を与えるであろう、そのアレイ上の統計をやっているので。

この手法にはいくつかの利点があります。それには、A-事前情報を必要とせず、それがコードに簡単です。あなたはすぐにそれを構築し、実験的にバッファを成長するとの回答に対する影響が無視できる持っているものの時点で、あなたの特定のサーバのために、決定することができます。つまり、近似が十分に正確である点である。

あなたはあなたに十分に正確で統計を与えるためにあまりにも多くのメモリを必要としていることが判明した場合、

、あなたはさらに掘るする必要があります。良いキーワードは以下のとおりです。「ストリーム・コンピューティング」、「ストリームの統計」、そしてもちろん「パーセンタイル」。また、「怒りと呪い」のアプローチを試すことができます。

Answer 2

長期保存を希望する場合のメモリ使用量を一定としており、データを使って き データのなかのどこかにあるのですね。これを適用しなければなりませんか rebinning スキームです。すで取得するまでに一定量の原料の投入を開始する前にrebinningができな動きが出始めている。

お問いは何だろう"と自問している最善の方法を動的にビニングデータ"?多くのアプローチがしたい場合は最小限に抑えるために前提での範囲の値を受け、その後簡単なアプローチは平均以上のバケットの固定サイズ k, は、対数分布幅.たとえば、イしていて1000値をメモリです。送迎サイズ k, というは100です。Pick your最小分解能という1ms.その

• 最初のバケツにお得な価値0-1ms(幅=1ms)
• 第二バケット:1-3ms(w=2ms)
• 第三にバケット:3-7ms(w=4ms)
• 第四にバケット:7-15ms(w=8ms)
• ...
• 目バケット:511-1023ms(w=512ms)

このタイプの logスケール このチャンキングシステムの使用 ハッシュテーブルのアルゴリズム, これを使用すると、一部のファイルシステムおよびメモリの割り当てアルゴリズムうまく動作している場合のデータを大きくダイナミックレンジです。

として新しい価値観を、できる方法を選びきりの方法で購入できます。例えば、ジョイント 移動平均, を使用し 先入れ先出し, 又はその他のより高度な方法です。を参照 Kademlia アルゴリズムの一つのアプローチによる使用 Bittorrent).

最終的には、rebinningけない一部の情報です。に関するお客様の選択"については、ビニングを決定する内容の情報は失われます。もうこれは、一定のメモリサイズ店が、トレードオフの関係 ダイナミックレ の サンプリングを忠実に再現;どのようにするトレードオフができますが、このサンプリングの問題がないこの基本であること。

ご本当に興味があるんだったら、是非を押し付けるのではなく、その答えはこのフォーラムできると思うんですが、どうし十分です。す拡大する見通しとなってい サンプリング理論.が膨大な量の研究が可能。

そのような思いをサーバーに回して相対的に小さなダイナミックレンジ、そしてよりリラックスしたスケーリングする高サンプリングの共通の価値をより正確な結果をもたらします。

編集:お答えしコメントを参照してください例の簡単にビニングアルゴリズムです。

• お店1000値は、10箱に入っています。各binそのため100値です。各binの実施としての動的配列（ａ'list'では、PerlやPythonです。

• 新しい価値を付:

  • かを決める箱で保管してくださのbin限界です。
  • 場合にはbinになっていないか、追加価値のbin一覧です。
  • 場合、binある値を削除し最binリストに追加、新しい価値の下のbin一覧です。この古い値でくつろいだりして過ごしたらスローされます。

• の90パーセンタイル、ソbin10.の90%は最初の値をソートリストの要素900/1000).

ない場合はのように捨てる古い価値観、そして実践できる何らかの代替制度への代わりに使います。例えば、binファイル(100値、例などに連れて行くことができ、平均で最も古い50の要素(すなわち第50のリストを破棄しその要素として追加の平均要素のbinいbin51要素にしていくことを大変うれしく思ペ49新しい値です。これは簡単な例rebinning.

別の例rebinningは オンセット;捨てる毎に5価値のソート、またはソートされたリストです。

このコンクリートの例です。のキーポイントを持つことができるのは、様々な方法があり安定メモリの高齢化アルゴリズム;限できるどのようになるのかは十分与えられます。

Answer 3

私はちょうど上のブログ記事を公開しましたこのトピックを。基本的な考え方は、

（500msの-600msのすべての正確なパーセンタイルのため）、「500msの-600msの以下を取る応答の95％パーセント」の賛成で正確な計算のための要件を軽減することです

あなたは、任意のサイズ（例えば0msと-50msの、50msの-100msの、...あなたのユースケースに合う何でも）のバケットの任意の数を使用することができます。通常、それは問題ではなく、最後のバケット（すなわち> 5000ms）で（Webアプリケーションのための、例えば5秒）一定の応答時間を超えて、すべての要求すべきではありません。

は、それぞれ、新たに撮影した応答時間のために、あなたは、単にそれが該当するバケットのカウンタをインクリメントします。合計が全体のnパーセントを超えるまで、n番目のパーセンタイルを推定するために、必要だということは全てのカウンタを加算されます。

このアプローチは、メモリの1K 128個のバケットを追跡できるように、バケットごとに8バイトを必要とします。 ）50ミリ秒の粒度を使用して、Webアプリケーションの応答時間を分析するための十分以上

は、一例として、ここで私は1時間から作成したの Googleのチャートであります（バケット当たり200ミリ秒で60個のカウンタを使用して）取り込まれたデータの

" ここに画像の説明を入力する

ニース、そうではありませんか？ :) 私のブログの上の続きを読みます。

Answer 4

(でもこうしたかという点数及びこれに関連する研究論文)

多額の研究概偏差値のデータストリームにあるのです。少数の興味深い論文のフルアルゴリズム定義:

• 高速アルゴリズム近似quantiles高速データストリーム

• 空間-時間-効率的な決定論的アルゴリズムの偏quantiles間データストリーム

• 効果的な計算の偏quantiles間データストリーム

これらすべての論文を提案アルゴリズムのサブ-リニアスペースの複雑さの計算の概偏差値以上のデータストリームです。

Answer 5

紙「いくつかのパーセンタイルの同時推定のためのシーケンシャル手順」（Raatikainen）で定義された単純なアルゴリズムを試してみてください。それは、高速で2 * M +（Mパーセンタイル用）3つのマーカーを必要とし、迅速に正確な近似値になる傾向がある。

Answer 6

大きな整数の動的配列 T[] または T[n] が応答時間が n ミリ秒だった回数をカウントするものを使用します。実際にサーバー アプリケーションの統計を実行している場合は、おそらく 250 ミリ秒の応答時間が絶対的な制限になります。したがって、1 KB には 0 ～ 250 のミリ秒ごとに 1 つの 32 ビット整数が保持され、オーバーフロー ビン用にある程度の余裕があります。より多くのビンを含むものが必要な場合は、1000 ビンに対して 8 ビット数値を使用します。その瞬間にカウンターがオーバーフローします (つまり、その応答時間における 256 番目のリクエスト)、すべてのビンのビットを 1 だけ下にシフトします。(すべてのビンの値を実質的に半分にします)。これは、最もアクセスされたビンが捕捉する遅延の 1/127 未満を捕捉するビンをすべて無視することを意味します。

特定のビンのセットが本当に必要な場合は、リクエストの初日に適切な固定のビンのセットを作成することをお勧めします。ライブのパフォーマンス重視のアプリケーションでは、動的なものは非常に危険です。その道を選ぶなら、自分が何をしているのかをよく知っておくべきです。そうでないと、ある日、統計トラッカーが運用サーバー上の CPU の 90% とメモリの 75% を突然消費するようになった理由を説明するためにベッドから呼び出されるでしょう。

追加の統計については、次のとおりです。平均と分散についてはいくつかあります 素晴らしい再帰アルゴリズム メモリをほとんど消費しません。これら 2 つの統計は、多くの分布においてそれ自体で十分に役立ちます。 中心極限定理 十分に多数の独立変数から生じる分布は正規分布 (平均と分散によって完全に定義される) に近づくと述べています。次のいずれかを使用できます。 正規性テスト 最後の N (N は十分大きいが、メモリ要件によって制限される) を調べて、正規性の仮定がまだ保持されているかどうかを監視します。