bra*_*tao 5 c algorithm performance
我开发了一个 Ip 过滤器，并猜测如何使用任何类型的 esque 数据结构开发一个非常高效且快速的黑名单过滤器。
\n\n我想做的很简单，每个传入/传出连接我都必须检查被阻止的 IP\xc2\xb4s 列表。
\n\nIP是分散的，内存使用应该是线性的（不依赖于阻止列表的数量，因为我想在有限的系统（自制路由器）上使用）。
\n\n我有时间，可以从零开始创造任何东西。难度对我来说并不重要。\n如果你可以使用任何东西，你应该做什么？
\n提高此类系统性能的一种方法是使用布隆过滤器。这是一种概率数据结构，占用很少的内存，其中可能出现误报，但不会出现误报。
当您想要查找 IP 地址时，首先检查布隆过滤器。如果错过了，您可以立即允许交通。如果有命中，您需要检查您的权威数据结构（例如哈希表或前缀树）。
您还可以创建一个“在布隆过滤器中命中但实际上允许”地址的小型缓存，该缓存在布隆过滤器之后但在权威数据结构之前进行检查。
基本上，其想法是以慢速路径（拒绝 IP 地址）为代价来加速快速路径（允许 IP 地址）。