如何计算最后一秒、每分钟和每小时的请求数？

Question

我有一个Web服务器，它只支持一个非常简单的API -计算在最后一小时，每分钟和每秒收到的请求数。该服务器在世界上非常受欢迎，每秒接收数千个请求。

目标是找到如何准确地将这3个值返回到每个请求？

请求一直在到来，因此每个请求的一小时、一分钟和一秒的窗口是不同的。如何管理每个请求的不同窗口，以便每个请求的计数都是正确的？

Answer 1

为什么不直接使用圆形数组呢？我们在该数组中有 3600 个元素。

index = 0;
Array[index % 3600] = count_in_one_second. 
++index;

如果需要最后一秒，则返回此数组的最后一个元素。如果要在最后一分钟，返回最后 60 个元素的总和。如果需要最后一小时，则返回整个数组的总和（3600 个元素）。

他的解决方案难道不是一个简单而有效的解决方案吗？

谢谢

德瑞克

Answer 2

要在T秒的时间窗口中执行此操作，请使用队列数据结构，以便在单个请求到达时对其时间戳进行排队。当您想读取在最近的T秒窗口内到达的请求数时，首先从队列的“旧”端删除那些早于T秒的时间戳，然后读取队列的大小。每当向队列添加新请求时，您还应该删除元素，以保持其大小有界（假定传入请求的速率有界）。

这个解决方案可以达到任意精度，例如毫秒精度。如果您满足于返回近似答案，您可以将T=3600（一小时）的时间窗口合并到单个队列元素中，使队列大小以3600为界。我认为这非常好，但理论上会失去准确性。对于T=1，如果您愿意，您可以在毫秒级别上进行合并。

在伪代码中:

queue Q

proc requestReceived()
  Q.insertAtFront(now())
  collectGarbage()

proc collectGarbage()
  limit = now() - T
  while (! Q.empty() && Q.lastElement() < limit)
    Q.popLast()

proc count()
  collectGarbage()
  return Q.size()

Answer 3

如果需要 100% 的准确性：

有一个所有请求和3个计数的链表-最后一小时，最后一分钟和最后一秒。

您将有两个指向链接列表的指针-一分钟前和一秒钟前。

一小时前将位于列表的末尾。每当最后一个请求的时间比当前时间早一小时以上时，请将其从列表中删除并递减小时计数。

分钟和秒钟指针将分别指向一分钟和一秒钟前出现的第一个请求。每当请求时间比当前时间早一分钟/秒以上时，向上移动指针并减少分钟/秒计数。

当一个新的请求进来时，将其添加到所有3个计数中，并将其添加到链表的前面。

对计数的请求将简单地包括返回计数。

上述所有操作都是摊销常数时间。

如果低于100%的准确度是可接受的:

以上内容的空间复杂度可能有点大，这取决于您通常每秒会收到多少请求；您可以通过略微牺牲精度来降低这一点，如下所示:

有一个如上所述的链表，但仅限于最后一秒。还有3个计数。

然后有一个由60个元素组成的圆形数组，指示过去60秒中每个元素的计数。每当第二秒通过时，从分钟计数中减去数组的最后一个（最旧）元素，并将最后一秒计数添加到数组中。

在过去的60分钟里有一个类似的圆形阵列。

准确性降低：一秒钟内所有请求都可以取消分钟计数，一分钟内所有请求也可以取消小时计数。

显然，如果每秒只有一个或更少的请求，那么这就没有意义了。在这种情况下，您可以保留链接列表中的最后一分钟，只需在最后60分钟使用一个循环数组。

这方面还有其他变化 - 精度与空间使用比率可以根据需要进行调整。

删除旧元素的计时器：

如果您仅在新元素进入时删除旧元素，它将被摊销为常数时间(某些操作可能需要更长时间，但它将平均为常数时间)。

如果您想要真正的常量时间，您可以额外运行一个计时器来删除旧的元素，并且每次调用它(当然还有插入和检查计数)将只需要常量时间，因为您最多删除自上次计时器滴答以来常量时间内插入的一些元素。