iptables 匹配 n 条 rule 的时间复杂度是多少?

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

For Existing Member Sign In

• 请不要在回答技术问题时复制粘贴 AI 生成的内容

This topic created in 2260 days ago, the information mentioned may be changed or developed.

简单起见, 假设都在一个 chain 中, 每个 rule 是 /32 地址, ACCEPT 或 DROP

4 replies • 2020-02-26 11:36:48 +08:00

zhs227

Feb 26, 2020

建议使用 ipset，只知道效率很低，具体有多低不知道。基本上相当于 O(n)?

feng32

Feb 26, 2020

@zhs227 我知道 ipset，只是有点好奇 iptables 原始规则是不是真的那么低效

ipwx

Feb 26, 2020

iptables 应该是 O(n)，不然管不住它这么复杂的规则。

用上 ipset 应该可以 O(logN)。

ipwx

Feb 26, 2020

@feng32 iptables 非常强大，规则之间有先后匹配顺序。现在有两条路，第一是让运维人员用 ipset 优化规则集，第二是算法自动优化。考虑到人工都优化不了的规则集，算法肯定优化不了，所以我觉得这个优化器大概率内核没写。（摊手