Neo's Blog

不抽象就无法深入思考
不还原就看不到本来面目!

0%

常见系统设计题系列-滑动TopK

实时输出最近一个小时内访问频率最高的10个IP,要求:
(1)实时输出
(2)从当前时间向前数的1个小时
(3)QPS可能会达到10W/s

解决思路:

  • 如何计算某一个IP最近一小时的访问次数?
  • 如何实现类似滑动窗口的功能,将过去1s的访问次数给去掉

解决方案:

  • 滑动窗口:只是滑动窗口的元素是:HashMap
  • 最近一小时某个IP的访问次数:累计所有窗口中IP对应的Cnt即可
  • 如何淘汰1个小时之前的数据:1s的定时器,定期移除过期的HashMap
    -如何维护Top10:自然是小顶堆(如果新来的IP超过堆顶元素,则上位;否则NOOP)
你的支持是我坚持的最大动力!