如果想要获得最近1小时访问服务器的请求数,有什么好算法呢?:因为日志分析比较慢,如何通过统计来实现这一功能呢?
目录
注意不要盲目相信以下内容! 不要盲目相信以下内容! 不要盲目相信以下内容! (重要的事情说三遍),虽然以下内容也经过了我的验证,但是我的验证可能有错误的地方,欢迎大家留言告知。希望这篇文章成为你深入探索相关领域的引子和启发,而不是标准答案。
问题描述
假设你可以屏蔽掉http请求解析的部分,已经封装好了,如果有请求到来,就会告诉你XXh:XXm:XXs:XXms有一个请求来了,那怎么做到统计最近一个小时的请求数?
队列
队列因为请求是按时间顺序排列的,所以其实是个先进先出的,那么使用的数据结构肯定是队列。
这时可以维护一个struct,里面有时间,id。来了一个请求,这个请求就进入队列,每次取队头,看看是不是超过1小时。超过1小时就出队,每次统计队列的size就可以了。
把队列作为缓冲区的话,这时的size只需要出队时size–,入队时size++即可。每次有request的时候,就取size。
但这种解法需要时刻扫描队头的状态,看是否超过1小时。而且,如果这样高并发时需要维护很大的内存空间。
不过这样时间用long类型的话,有的栈空间可能存不了,1ms一个请求的话,就要27M,就要动态申请或者调整栈。
优化方法Bit Map
为了提高空间复杂度,可以使用bit map,用1位表示一个值的节省内存的方法。假设1ms一个,那个一小时也就3600000个。然后一个Bit表示该毫秒有没有请求,位运算掩码就可以求里面有多少个1,也可以映射到1us。
tcp是50us,那样请求就不会超过1us一个。这时我们就不需要维护队头的刷新,只需要每毫秒检测是否有请求进入即可。
这时还有一个不需要每毫秒刷新的算法,即使用一个变量记录队头时间,每次有请求进入服务器时,就用请求时间减去队头时间然后减去1小时,再转换为毫秒,这样我们就可以得到让这个二进制数右移的位数。只需要移位补1即可。