Приблизительное количество событий за данный период времени

Question

Я хотел бы иметь эффективный способ подсчета (приблизительного) количества повторяющихся событий за определенный период времени.

Пример: Я пытаюсь повторно загрузить файл с хоста. Обычно он работает нормально, но иногда происходит ошибка при переполнении сети. Меня не волнуют эти одиночные ошибки. Каждый раз в то время, хотя хост отключен, все мои попытки терпят неудачу. В этом случае я хотел бы автоматически остановить свою программу от повторной попытки.

Поэтому мне нужно выяснить, сколько ошибок произошло за последние x минут. Когда число ниже определенного порога, ничего не происходит. Когда он выше, я хочу принять меры. Счет не должен быть на 100% точным, только достаточно точным, чтобы сообщить мне, был ли достигнуто пороговое значение.

Простой, но неэффективный (O(n)) способ сделать это будет просто хранить временные метки событий, а затем для каждого нового события определять количество предыдущих событий путем итерации по ним и сравнения временных меток (вверх пока не достигнут временной интервал). [в сторону] Я предполагаю, что это то, что делают SQL-машины для WHERE timestamp BETWEEN NOW() AND INTERVAL X MINUTES, если у них нет индекса в столбце. [/ aside]

Я хочу решение с постоянной (O(1)) сложностью. Пока я думаю, что я буду держать счетчик события, который увеличивается на 1 с каждым событием. Я также сохраню временную метку самого последнего события. Затем, когда происходит новое событие, с помощью некоторой математической магии я могу уменьшить счетчик, используя текущее время и сохраненную метку времени, чтобы отразить примерно количество событий за последние x минут.

К сожалению, мои математические навыки не соответствуют задаче. Может кто-нибудь дать некоторые подсказки?

Answer 1

Опираясь на комментарии от @ Эббе-м-Педерсен, это то, что решение будет выглядеть в PHP с помощью Redis в качестве хранилища данных:

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); 
} 

Answer 2

Простой способ решить эту проблему, чтобы иметь пороговый счетчик, который вы увеличиваете на единицу для каждого ошибки, и сбрасывается в ноль для каждого ок загрузки. Это будет отслеживать, что многие загрузки загрузились подряд, и может быть достаточно, чтобы решить вашу проблему.

В качестве альтернативы вы можете сделать какую-то скользящую среднюю. Следующий код представляет собой простой способ сделать это:

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, чтобы получить прогрессию вы хотите

Answer 3

Если вы только что достигли порога сбоя в течение последних шести минут, почему бы не сохранить временные метки отказа в круговом буфере с пропускной способностью, равной порогу? Вставка явно O (1), и чтобы проверить, было ли достаточно ошибок, проверьте, не установлена ​​ли последняя временная метка в последние минуты.