V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
hehe12980
V2EX  ›  程序员

某 Top 大厂面试的一个问题,欢迎大家讨论

  •  
  •   hehe12980 · 2021-04-21 21:40:49 +08:00 · 715 次点击
    这是一个创建于 1072 天前的主题,其中的信息可能已经有所发展或是发生改变。
    背景:之前去某 Top 级别大厂面试,面的 Java 30-50K 这个岗位,2 面,然后给我出了两题,时间 1 个小时左右,第一题多线程的题,还行基本上写出来了。主要第二题没有特别好的思路。题目如下

    设计一个黑名单系统,实现对访问 IP 的管理,要求如下:
    • 一分钟内,该 IP 访问超过 1000 次,加入黑名单
    • 一小时内,该 IP 访问超过 30000 次,加入黑名单
    • 黑名单库中的 IP,如果连续一个小时不违反 1 、2 两条,则解除黑名单

    单纯实现这个功能的话,我觉得不用 mysql 存下每个 ip 的访问记录感觉根本就弄不出来,因为时间是浮动的,但是问题来了,如果用 mysql 去存访问记录,这个表的设计其实不难,但是数据量是个问题,每个 ip 访问都得记,感觉不应该这么玩,不知道大家有没有好的方法

    如果用 mysql 的话 还得开个定时器扫 ,不断增删改去维护动态的 ip 数据,每次 ip 请求,就得查库判断。
    布隆过滤器也想过,但是这个地方有时效性,感觉布隆过滤器没法用

    该大厂最终是挂了,但是这个问题不失为一个好的问题,因为自己当初没想出来,然后静下心想,除了用 mysql 和定时器+拦截器,坦白说自己没有特别好的方案,所以在这里想请教一下大家的思路。
    hehe12980
        1
    hehe12980  
    OP
       2021-04-21 22:00:10 +08:00
    貌似被降权了 还是咋回事 发的帖子自己跑第二页去了
    Chinsung
        2
    Chinsung  
       2021-04-22 09:40:57 +08:00
    这个需求很奇怪,首先就是理论上黑名单库中的 ip,理论上都直接拒绝访问了,还要连续一个小时不违反就解除,也就是说黑名单的 ip 也能打到这个程序上么?
    做法的话拍脑袋一想,可以搞个桶,比如某 IP 访问,就创建一个以分钟为单位的桶,存内存或者 redis,该 IP 如果再次访问就 hash 到对应的桶,在 hash 到对应那个分钟单位里++,如果对应分钟的桶超过 1000 就黑名单。分钟的桶也就 60 个 int,小时的桶一天最多也就 24 个 int 。
    whileFalse
        3
    whileFalse  
       2021-04-22 13:48:45 +08:00
    令牌桶就行吧,弄俩桶。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   4129 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 24ms · UTC 05:25 · PVG 13:25 · LAX 22:25 · JFK 01:25
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.