use*_*246 22 algorithm web-services data-structures
有一个假设的Web服务器只支持一个非常简单的API - 在过去的小时,分钟和秒中收到的请求数.该服务器在世界上非常流行,每秒收到数千个请求.
瞄准它找到如何准确地将这3个计数返回到每个请求？
请求一直在进行,因此每个请求的一小时,一分钟和一秒的窗口是不同的.如何根据请求管理不同的窗口,以便每个请求的计数正确？
Duk*_*ing 26
如果需要100%的准确度:
拥有所有请求和3个计数的链接列表 - 最后一小时,最后一分钟和最后一秒.
你将有2个指针进入链表 - 一分钟前和一秒钟前.
一小时前将在列表的末尾.每当最后一次请求的时间超过当前时间之前一小时时,将其从列表中删除并减少小时计数.
分针和秒针将指向分别在一分钟和一分钟之后发生的第一个请求.每当请求的时间超过当前时间之前的一分钟/秒时,向上移动指针并减少分钟/秒计数.
当有新请求进入时,将其添加到所有3个计数并将其添加到链接列表的前面.
对计数的请求只涉及返还计数.
以上所有操作均按摊销常数计算.
如果准确度低于100%是可以接受的:
上述空间复杂度可能有点多,具体取决于您通常每秒获得的请求数量; 您可以通过略微牺牲精度来减少这一点,如下所示:
如上所述有链接列表,但仅限于最后一秒.还有3个计数.
然后有一个由60个元素组成的圆形数组,表示最后60秒的计数.每当第二次通过时,从分钟计数中减去数组的最后一个(最旧的)元素,并将最后一个第二个计数添加到数组中.
在过去的60分钟内有一个类似的圆形阵列.
精度损失:一分钟内所有请求都可以关闭分钟计数,一分钟内所有请求都可以关闭小时计数.
显然,如果你每秒只有一个或更少的请求,这就没有意义.在这种情况下,您可以将最后一分钟保留在链接列表中,并且在过去60分钟内只有一个圆形数组.
此外还有其他变化 - 可根据需要调整空间使用率的精度.
删除旧元素的计时器:
如果仅在新元素进入时删除旧元素,则它将按常量时间分摊(某些操作可能需要更长时间,但会平均到常量时间).
如果你想要真正的恒定时间,你还可以运行一个删除旧元素的计时器,每次调用它(当然插入和检查计数)只需要一个恒定的时间,因为你最多需要删除一些自上次计时器滴答以来在恒定时间内插入的元素.
Ant*_*ima 12
要在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()
为什么不使用圆形阵列？我们在该阵列中有3600个元素.
index = 0;
Array[index % 3600] = count_in_one_second.
++index;
如果你想要最后一秒,返回这个数组的最后一个元素.如果你想要最后一分钟,返回最后60个元素的总和.如果你想要最后一小时,返回整个数组的总和(3600个元素).
他不是一个简单而有效的解决方案吗？
谢谢
Deryk
一种解决方案是这样的：
1）使用长度为3600（一小时60 * 60秒）的圆形数组来存储最近一小时的每秒数据。
若要记录新的数据，请通过移动圆形数组的头指针将最后一秒钟的数据拖放到圆形数组中。
2）在循环数组的每个元素中，我们记录之前看到的请求数量的累积总和，而不是将请求数量保持在特定的秒数内，并且可以通过以下方式计算周期内的请求数量：requests_sum.get(current_second) - requests_sum.get(current_second - number_of_seconds_in_this_period)
所有的操作类似increament()，getCountForLastMinute()，getCountForLastHour()可以在完成O(1)时间。
================================================== =======================
这是一个如何工作的示例。
如果我们在最近3秒内有这样的请求计数：
1st second: 2 requests
2nd second: 4 requests
3rd second: 3 requests
圆形数组如下所示：
sum = [2, 6, 9]
其中6 = 4 + 2和9 = 2 + 4 + 3
在这种情况下：
1）如果要获取最后一秒的请求计数（第三秒的请求计数），只需计算 sum[2] - sum[1] = 9 - 6 = 3
2）如果您想获取最后两秒的请求计数（第三秒的请求计数和第二秒的请求计数），只需计算 sum[2] - sum[0] = 9 - 2 = 7