V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX 提问指南
myzincx
V2EX  ›  问与答

高效匹配百万级黑名单

  •  
  •   myzincx · 2020-04-01 23:50:51 +08:00 via Android · 1870 次点击
    这是一个创建于 1457 天前的主题,其中的信息可能已经有所发展或是发生改变。

    小白请教大家一个问题,

    项目有个需求,有一个百万级的黑名单库,

    是如五元组之类的信息库,

    在万兆网口上进行抓包,要求在满载的情况下能不丢包还能实时匹配黑名单库进行报警等处理

    开发语言是 c++,请问大家有什么较好的解决方案吗?

    2 条回复    2020-04-02 00:37:49 +08:00
    paoloo
        1
    paoloo  
       2020-04-01 23:59:24 +08:00 via Android
    布隆过滤器的典型场景
    auser
        2
    auser  
       2020-04-02 00:37:49 +08:00   ❤️ 1
    五元组哈希计算得到 Key [核心] ,查缓存 [核心(主要是快速处理热数据)] 知道黑不黑,考虑业务模式可以使用 0 、1 、2 、3 作为 Value,比如放行、报警处理的动作集索引。没有命中的话在百万黑名单的 Hash (与缓存数组的实现看具体场景,这个一般没缓存要求高要求)或者 Set 中找到或者没找到(重要,没找到也要写缓存)然后快速更新缓存 [核心] 。

    就按每秒一百万个包来算,这已经不是 C++这个编程语言本身的问题了。当然不能触发内存分配这种潜台词就不提了,这是必须要做到的。

    这个黑名单库如果要动态更新,就有并发锁的问题。内存充足( x86 体系)情况下,可以直接创建新的 Hash,然后在临界区交换 /清空上述 Hash/缓存的指针即可。这样临界区通常是可以做成无锁的形式 [难点] 。

    报警之类功能思路跟上述一致,也就是内核驱动开发常说的 top/bottom half 避免性能问题。转发层面尽量快,后续耗时的工作放到额外线程甚至进程里边去做。

    Bloom Filter 用来统计百万日活文章阅读量还好,不适合数据转发过滤的偏底层业务场景。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   5386 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 35ms · UTC 08:40 · PVG 16:40 · LAX 01:40 · JFK 04:40
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.