找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 32001|回复: 3
收起左侧

【最近一个小时内访问频率最高的10个IP】【系统设计面经题目精选系列】

[复制链接]
发表于 11-14-2017 11:01 PM | 显示全部楼层 |阅读模式

亲!马上注册或者登录会查看更多内容!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
实时输出最近一个小时内访问频率最高的10个IP,要求:
  • 实时输出
  • 从当前时间向前数的1个小时
  • QPS可能会达到10W/s
这道题乍一看很像Top K 频繁项,是不是需要 Lossy Count 或 Count-Min Sketch 之类的算法呢?
其实杀鸡焉用牛刀,这道题用不着上述算法,请听我仔细分析。
  • QPS是 10万/秒,即一秒内最高有 10万个请求,那么一个小时内就有 100000*3600=360000000≈[size=1.21em]2^{28.4}2​28.4​​,向上取整,大概是 [size=1.21em]2^{29}2​29​​个请求,也不是很大。我们在内存中建立3600个HashMap<Int,Int>,放在一个数组里,每秒对应一个HashMap,IP地址为key, 出现次数作为value。这样,一个小时内最多有[size=1.21em]2^{29}2​29​​个pair,每个pair占8字节,总内存大概是 [size=1.21em]2^{29} \times 8=2^{32}2​29​​×8=2​32​​字节,即4GB,单机完全可以存下。
  • 同时还要新建一个固定大小为10的小根堆,用于存放当前出现次数最大的10个IP。堆顶是10个IP里频率最小的IP。
  • 每次来一个请求,就把该秒对应的HashMap里对应的IP计数器增1,并查询该IP是否已经在堆中存在,
    • 如果不存在,则把该IP在3600个HashMap的计数器加起来,与堆顶IP的出现次数进行比较,如果大于堆顶元素,则替换掉堆顶元素,如果小于,则什么也不做
    • 如果已经存在,则把堆中该IP的计数器也增1,并调整堆
  • 需要有一个后台常驻线程,每过一秒,把最旧的那个HashMap销毁,并为当前这一秒新建一个HashMap,这样维持一个一小时的窗口。
  • 每次查询top 10的IP地址时,把堆里10个IP地址返回来即可。
以上就是该方案的全部内容。
有的人问,可不可以用"IP + 时间"作为key, 把所有pair放在单个HashMap里?如果把所有数据放在一个HashMap里,有两个巨大的缺点,
  • 第4步里,怎么淘汰掉一个小时前的pair呢?这时候后台线程只能每隔一秒,全量扫描这个HashMap里的所有pair,把过期数据删除,这是线性时间复杂度,很慢。
  • 这时候HashMap里的key存放的是"IP + 时间"组合成的字符串,占用内存远远大于一个int。而前面的方案,不用存真正的时间,只需要开一个3600长度的数组来表示一个小时时间窗口。

我们始终相信IT会持续改造甚至创新传统行业,我们始终全面看好咱们的CS专业!

0

主题

0

精华

0

积分

新米人

Rank: 1

积分
0
发表于 11-14-2017 11:02 PM 来自美国米群网手机版 | 显示全部楼层
感谢TeamEditor分享~~~
回复 支持 反对

使用道具 举报

0

主题

0

精华

0

积分

新米人

Rank: 1

积分
0
发表于 11-15-2017 06:51 PM | 显示全部楼层
感谢TeamEditor分享~~~
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表