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

[feng32]

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

[zhs227]

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

[feng32]

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

[ipwx]

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

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

[ipwx]

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