18

我有消息以毫秒分辨率进入我的程序（每毫秒从零到几百条消息）。

我想做一些分析。具体来说，我想维护消息计数的多个滚动窗口，随着消息的进入而更新。例如，

  • # 最后一秒的消息数
  • # 最后一分钟的消息数
  • 过去半小时内的消息数除以过去一小时内的消息数

我不能只维持一个简单的计数，例如“最后一秒有 1,017 条消息”，因为我不知道消息何时超过 1 秒，因此不应再计入计数......

我想维护所有消息的队列，搜索超过一秒的最年轻消息，并从索引中推断计数。但是，这似乎太慢了，并且会占用大量内存。

我可以做些什么来跟踪我的程序中的这些计数，以便我可以有效地实时获取这些值？

4

5 回答 5

17

这最容易由循环缓冲区处理。

循环缓冲区具有固定数量的元素和指向它的指针。您可以将一个元素添加到缓冲区，并且当您这样做时，您将指针递增到下一个元素。如果您通过了固定长度的缓冲区，您将从头开始。这是一种存储“最后 N 个”项目的空间和时间有效的方式。

现在，在您的情况下，您可以拥有一个包含 1,000 个计数器的循环缓冲区，每个计数器计算一毫秒内的消息数。添加所有 1,000 个计数器可以为您提供最后一秒的总计数。当然，您可以通过增量更新计数来优化报告部分，即从计数中减去插入时覆盖的数字，然后添加新数字。

然后，您可以拥有另一个具有 60 个插槽的循环缓冲区，并以整秒为单位计算消息的总数；每秒一次，您获取毫秒缓冲区的总计数并将计数写入分辨率为秒的缓冲区，等等。

这里类似 C 的伪代码：

int msecbuf[1000]; // initialized with zeroes
int secbuf[60]; // ditto
int msecptr = 0, secptr = 0;
int count = 0;
int msec_total_ctr = 0;
void msg_received() { count++; }
void every_msec() {
  msec_total_ctr -= msecbuf[msecptr];
  msecbuf[msecptr] = count;
  msec_total_ctr += msecbuf[msecptr];
  count = 0;
  msecptr = (msecptr + 1) % 1000;
}
void every_sec() {
  secbuf[secptr] = msec_total_ctr;
  secptr = (secptr + 1) % 60;
}
于 2010-02-16T01:00:32.330 回答
9

您需要指数平滑，也称为指数加权移动平均线。取自最后一条消息到达以来的时间的 EWMA，然后将该时间划分为一秒。您可以使用不同的权重运行其中的几个，以有效地覆盖更长的时间间隔。实际上，您使用的是无限长的窗口，因此您不必担心数据过期；减轻重量为您完成。

于 2010-02-16T00:47:48.667 回答
3

对于最后一个毫秒，保持计数。当毫秒切片进入下一个切片时，重置计数并将计数添加到毫秒滚动缓冲区数组。如果保持这种累积性，则可以使用固定的内存量提取消息数/秒。

当 0,1 秒切片（或 1 分钟旁边的其他小值）完成时，将滚动缓冲区数组中的最后 0,1*1000 个项目相加，并将其放入下一个滚动缓冲区。通过这种方式，您可以保持毫秒滚动缓冲区较小（1s 最大查找 1000 个项目）和分钟查找缓冲区（600 个项目）。

您可以在 0.1 分钟间隔的整分钟内执行下一个技巧。提出的所有问题都可以通过对几个整数求和（或使用 cummulative 时减去两个值）来查询。

唯一的缺点是，最后一秒的值将每毫秒更改一次，分钟值仅每 0.1 秒更改一次，小时值（以及最后 1/2 小时的百分比的导数）每 0.1 分钟更改一次。但至少你可以控制你的内存使用。

于 2010-02-16T10:24:18.740 回答
2

您的滚动显示窗口只能更新这么快，假设您希望每秒更新 10 次，因此对于 1 秒的数据，您需要 10 个值。每个值将包含在 1/10 秒内显示的消息数。让我们将这些值称为 bin，每个 bin 保存 1/10 秒的数据。每 100 毫秒，其中一个垃圾箱被丢弃，并且一个新垃圾箱被设置为在那 100 毫秒内显示的消息数。

如果您想在整个小时内保持 1/10 秒的精度，您将需要一组 36K 箱来保存有关您的消息速率的一个小时的价值信息。但这似乎有点矫枉过正。

但我认为随着时间间隔变大，精度下降会更合理。

也许您将 1 秒的数据精确到 100 毫秒，将 1 分钟的数据精确到秒，将 1 小时的数据精确到分钟，等等。

于 2010-02-16T01:04:40.707 回答
0

我想维护所有消息的队列，搜索超过一秒的最年轻消息，并从索引中推断计数。但是，这似乎太慢了，并且会占用大量内存。

一个更好的主意是维护消息的链接列表，将新消息添加到头部（带有时间戳），并在它们过期时从尾部弹出它们。甚至不弹出它们 - 只需保留一个指向在所需时间范围内传入的最旧消息的指针，并在该消息到期时将其向前推进（这允许您使用一个列表跟踪多个时间范围）。

您可以在需要时通过从尾部走到头部来计算计数，或者只是单独存储计数，每当您向头部添加值时将其递增，并在您推进尾部时将其递减。

于 2010-02-16T00:45:11.950 回答