亲!马上注册或者登录会查看更多内容!
您需要 登录 才可以下载或查看,没有帐号?立即注册
x
实时输出最近一个小时内访问频率最高的10个IP,要求: - 实时输出
- 从当前时间向前数的1个小时
- QPS可能会达到10W/s
这道题乍一看很像Top K 频繁项,是不是需要 Lossy Count 或 Count-Min Sketch 之类的算法呢? 其实杀鸡焉用牛刀,这道题用不着上述算法,请听我仔细分析。 以上就是该方案的全部内容。 有的人问,可不可以用"IP + 时间"作为key, 把所有pair放在单个HashMap里?如果把所有数据放在一个HashMap里,有两个巨大的缺点, - 第4步里,怎么淘汰掉一个小时前的pair呢?这时候后台线程只能每隔一秒,全量扫描这个HashMap里的所有pair,把过期数据删除,这是线性时间复杂度,很慢。
- 这时候HashMap里的key存放的是"IP + 时间"组合成的字符串,占用内存远远大于一个int。而前面的方案,不用存真正的时间,只需要开一个3600长度的数组来表示一个小时时间窗口。
|