0

我想有一种有效的方法来计算给定时间范围内重复事件的（近似）计数。

示例：我正在尝试从主机重复下载文件。它通常可以正常工作，但有时会在网络拥塞时发生错误。我不在乎这些单一的错误。不过，每隔一段时间，主机就会离线，所以我所有的尝试都失败了。在这种情况下，我想自动停止我的程序再次尝试。

所以我需要找出在过去 x 分钟内发生了多少错误。当数字低于某个阈值时，什么也不会发生。当它在上面时，我想采取行动。计数不一定要 100% 准确，只要准确到足以告诉我是否达到阈值即可。

一种简单但无效O(n)（到达）。[旁白] 我想这就是 SQL 引擎对 a 所做的事情WHERE timestamp BETWEEN NOW() AND INTERVAL X MINUTES，除非它们在列上有索引。[/在旁边]

我想要一个具有恒定 ( O(1)) 复杂性的解决方案。到目前为止，我认为我会保留一个事件计数器，每次事件都会增加 1。我还将存储最近发生的时间戳。然后，当一个新事件发生时，通过一些数学魔法，我可以使用当前时间和存储的时间戳来减少计数器，以大致反映过去 x 分钟内发生了多少事件。

不幸的是，我的数学技能不能胜任这项任务。有人可以提供一些提示吗？

4

3 回答 3

2

如果您只是要在最后 x 分钟内设置故障计数的阈值，为什么不将故障时间戳存储在容量等于阈值的循环缓冲区中呢？插入显然是 O(1)，为了检查是否有足够的失败，测试最近最少插入的时间戳是否在最后 x 分钟内。

于 2013-09-04T16:26:58.477 回答
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 回答