algorithm - 如何统计最后一秒、一分钟、一小时的请求数？

Question

我有一个网络服务器，它只支持一个非常简单的 API——计算在过去一小时、一分钟和一秒内收到的请求数。该服务器在世界范围内非常流行，每秒接收数千个请求。

旨在找到如何将这 3 个值准确地返回给每个请求？

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

Answer 1

如果需要 100% 的准确度:

有一个包含所有请求和 3 个计数的链表 - 过去一小时、最后一分钟和最后一秒。

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

一小时前将在列表末尾。每当最后一个请求的时间比当前时间早一个多小时时，将其从列表中删除并减少小时数。

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

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

计数请求只涉及返回计数。

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

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

上述的空间复杂度可能有点大，具体取决于您通常每秒收到多少请求；您可以通过稍微牺牲准确性来减少这种情况，如下所示:

有一个如上的链表，但只是在最后一秒。还有 3 个计数。

然后有一个 60 元素的循环数组，指示最后 60 秒中每一秒的计数。每当一秒过去时，从分钟计数中减去数组的最后一个(最旧的)元素，并将最后一秒计数添加到数组中。

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

不准确:分钟计数可能会在一秒钟内被所有请求关闭，小时计数可能会在一分钟内被所有请求关闭。

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

还有其他变体 - 可以根据需要调整空间使用率的精度。

移除旧元素的计时器:

如果只有在新元素进来时才删除旧元素，它将按常数时间摊销(某些操作可能需要更长的时间，但它会平均到常数时间)。

如果你想要真正的恒定时间，你可以另外运行一个定时器来删除旧元素，每次调用这个(当然还有插入和检查计数)只会花费恒定的时间，因为你最多删除自上次计时器滴答以来，在恒定时间内插入的一些元素。