如何计算最后一秒、一分钟和一小时的请求数? [英] How can I count the number of requests in the last second, minute and hour?

问题描述

我有一个 Web 服务器，它只支持一个非常简单的 API——计算过去一小时、一分钟和一秒收到的请求数.该服务器在全球非常流行，每秒接收数千个请求.

I have a web server which supports only one very simple API- count the number of requests received in the last hour, minute and second. This server is very popular in the world and received thousands of requests per second.

旨在找出如何将这 3 个值准确返回给每个请求?

Aim it to find how to return accurately these 3 values to every request?

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

Requests are coming all the time, so the window of one hour, one minute and one second is different per request. How to manage a different window per request so that the counts are correct per request?

推荐答案

如果需要 100% 的准确度:

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

Have a linked-list of all requests and 3 counts - for the last hour, the last minute and the last second.

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

You will have 2 pointers into the linked-list - for a minute ago and for a second ago.

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

An hour ago will be at the end of the list. Whenever the time of the last request is more than an hour before the current time, remove it from the list and decrement the hour count.

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

The minute and second pointers will point to the first request that occurred after a minute and a second ago respectively. Whenever the time of the request is more than a minute / second before the current time, shift up the pointer and decrement the minute / second count.

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

When a new request comes in, add it to all 3 counts and add it to the front of the linked-list.

对计数的请求只涉及返回计数.

Requests for the counts would simply involve returning the counts.

以上所有操作均摊销常数时间.

All of the above operations are amortised constant time.

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

上面的空间复杂度可能有点高，这取决于您通常每秒会收到多少请求；您可以通过以下方式稍微牺牲准确性来减少这种情况:

The space-complexity for the above could be a bit much, depending on how many requests per second you would typically get; you can reduce this by sacrificing slightly on accuracy as follows:

有一个如上的链表，但仅限于最后一秒.也有 3 个计数.

Have a linked-list as above, but only for the last second. Also have the 3 counts.

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

Then have a circular array of 60 elements indicating the counts of each of the last 60 seconds. Whenever a second passes, subtract the last (oldest) element of the array from the minute count and add the last second count to the array.

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

Have a similar circular array for the last 60 minutes.

准确性损失:分钟计数可能会被一秒内的所有请求关闭，小时计数可能会被一分钟内的所有请求关闭.

Loss of accuracy: The minute count can be off by all the requests in a second and the hour count can be off by all the requests in a minute.

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

Obviously this won't really make sense if you only have one request per second or less. In this case you can keep the last minute in the linked-list and just have a circular array for the last 60 minutes.

对此还有其他变化 - 可以根据需要调整准确度与空间使用比率.

There are also other variations on this - the accuracy to space used ratio can be adjusted as required.

删除旧元素的计时器:

如果你只在新元素进来时删除旧元素，它会被摊销固定时间(有些操作可能需要更长的时间，但它会平均到固定时间).

If you remove old elements only when new elements come in, it will be amortised constant time (some operations might take longer, but it will average out to constant time).

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

If you want true constant time, you can additionally have a timer running which removes old elements, and each invocation of this (and of course insertions and checking the counts) will only take constant time, since you're removing at most a number of elements inserted in the constant time since the last timer tick.

这篇关于如何计算最后一秒、一分钟和一小时的请求数?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！