高效匹配百万级黑名单

[myzincx]

小白请教大家一个问题，

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

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

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

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

[paoloo]

布隆过滤器的典型场景

[auser]

五元组哈希计算得到 Key [核心] ，查缓存 [核心（主要是快速处理热数据）] 知道黑不黑，考虑业务模式可以使用 0 、1 、2 、3 作为 Value，比如放行、报警处理的动作集索引。没有命中的话在百万黑名单的 Hash （与缓存数组的实现看具体场景，这个一般没缓存要求高要求）或者 Set 中找到或者没找到（重要，没找到也要写缓存）然后快速更新缓存 [核心] 。

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

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

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

Bloom Filter 用来统计百万日活文章阅读量还好，不适合数据转发过滤的偏底层业务场景。