0

特定の時間枠で繰り返されるイベントの (おおよその) カウントを効率的に計算する方法が必要です。

例:ホストからファイルを繰り返しダウンロードしようとしています。通常は問題なく動作しますが、ネットワークが混雑しているとエラーが発生することがあります。これらの単一のエラーは気にしません。ただし、時々、ホストがオフラインになるため、すべての試行が失敗します。その場合、プログラムの再試行を自動的に停止したいと思います。

したがって、過去 x 分間に発生したエラーの数を調べる必要があります。数値が特定のしきい値を下回ると、何も起こりません。以上の場合は、アクションを起こしたい。カウントは 100% 正確である必要はありません。しきい値に達したかどうかを示すのに十分なだけ正確です。

単純だが効果的でない ( O(n)) これを行う方法は、イベントのタイムスタンプを保存するだけで、新しいイベントごとに、それらを反復してタイムスタンプを比較することにより、以前のイベントの数を決定することです (時間枠が達した）。[余談]これはWHERE timestamp BETWEEN NOW() AND INTERVAL X MINUTES、列にインデックスがない限り、SQLエンジンが に対して行うことだと思います。[/さておき]

O(1)定数 ( ) の複雑さを持つソリューションが必要です。これまでのところ、イベントごとに 1 ずつ増加するイベントのカウンターを保持することを考えています。また、最新の発生のタイムスタンプも保存します。次に、新しいイベントが発生すると、数学の魔法によって、現在の時刻と保存されているタイムスタンプを使用してカウンターを減らし、過去 x 分間に発生したイベントの数を概算できます。

残念ながら、私の数学のスキルはその仕事に耐えられません。誰かがヒントを提供できますか？

4

3 に答える 3

1

これを解決する簡単な方法は、エラーごとに 1 ずつ増やし、正常なダウンロードごとにゼロにリセットするしきい値カウンターを用意することです。これにより、連続して失敗したダウンロードの数が追跡され、問題を解決するのに十分な場合があります。

あるいは、ある種の移動平均を行うこともできます。次のコードは、これを行う簡単な方法です。

errorRate = errorRate * 0.8
if (error) {
   errorRate = errorRate + 0.2
}

次のような進行を示します。

Download#   Status  errorRate
     1      ok      0.000
     2      ok      0.000        <=
     3      error   0.200        <= Low rate of errors
     4      ok      0.160        <= 
     5      ok      0.128        
     6      error   0.302        
     7      error   0.442        
     8      ok      0.354
     9      ok      0.283
    10      ok      0.226
    11      error   0.381
    12      error   0.505
    13      error   0.603
    14      ok      0.483
    15      error   0.586
    16      error   0.669        <= High rate of errors shows 
    17      ok      0.535
    18      ok      0.428
    19      ok      0.343
    20      ok      0.274
    21      ok      0.219        <= goes back down after some ok downloads
    etc..

係数 0.8 と 0.2 で遊んで、好きな進行を得ることができます

于 2013-09-04T16:20:27.273 に答える
0

@ebbe-m-pedersen からのコメントに基づいて構築すると、Redis をデータ ストアとして使用する PHP でのソリューションは次のようになります。

function error_handler() {
    $threshold = 100; // how many errors may occur
    $timeframe = 60 * 5; // 5 minutes, how many minutes may pass
    $now = time();

    // get error stats from redis
    $key_base = 'errors:';
    $count = $redis->get($key_base . 'count'); // calculated count
    $last = $redis->get($key_base . 'last'); // timestamp

    // calculate damping factor
    $rate = ($now - $last) / $timeframe;
    $rate = min($rate, 1.0); // $rate may not be larger than 1
    $rate = 1 - $rate; // we need the inverse for multiplying

    // calculate new error count
    $count = (int)($count * $rate);

    if ($count > $threshold) {
        // take action
    }

    // increase error
    $count++;

    // write error stats back to redis
    $redis->set($key_base . 'count', $count);
    $redis->set($key_base . 'last'. $now);
}
于 2013-09-05T10:35:33.077 に答える