怎么算的最后一秒，分钟和小时的请求数量 [英] how to count number of requests in last second, minute and hour

问题描述

有是仅支持一个非常简单的API一个假设的Web服务器 - 在最后一小时，分，秒收到的请求数。 这个服务器是世界上很受欢迎，并获得每秒数千次的请求。

There is a hypothetical web server which supports only one very simple API - count 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 counts 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 constant time.

如果低于100％的准确率是可以接受的：

由于上面已经是恒定的时间，你不能得到任何比这快得多。但是，空间的复杂性可能是一个有点吃不消了，这取决于每秒，你通常会得到多少请求;您可以通过精确度稍微有所牺牲如下减少这样的：

Since the above is already constant time, you can't get anything to be much quicker than that. However, the space-complexity 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.

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