nftables Set：用 O(1) 哈希查找替代 O(N) 链表遍历

一句话核心：nftables 把”原本要逐条匹配的规则”抽象成”集合 (set) 元素”，数据面只需对集合做一次哈希/树查找就能拿到结果，从根本上消除了 iptables 时代”规则数 = 服务数 × k”带来的 O(N) 线性遍历瓶颈。

---

0.1. 一、问题起源：iptables 为何慢

在 iptables 时代，K8s 5000 个 Service 会被翻译成几万条规则。数据面处理一个包，必须按链表顺序逐条匹配：

KUBE-SERVICES 链
├── -d 10.0.0.1 -p tcp --dport 80   -j KUBE-SVC-A
├── -d 10.0.0.2 -p tcp --dport 80   -j KUBE-SVC-B
├── -d 10.0.0.3 -p tcp --dport 443  -j KUBE-SVC-C
├── ... (5000 条)
└── -d 10.0.0.N -p tcp --dport ...  -j KUBE-SVC-N

每多 1 个 Service，所有数据包的平均匹配延迟都增加一点——典型 O(N) 扩展性灾难。

---

0.2. 二、nftables Set：把”规则”重塑成”数据”

nftables 引入了一等公民的集合 (set / map / vmap) 概念。同样 5000 个 Service，数据面只剩 1 条规则：

# 1. 创建一张哈希表（key = ip + 协议 + 端口，value = 跳转动作）
nft add map ip filter service_ips {
    type ipv4_addr . inet_proto . inet_service : verdict \;
}

# 2. 动态加入元素（每加 1 个 Service 只做这一步）
nft add element ip filter service_ips {
    10.0.0.1 . tcp . 80  : goto svc_a,
    10.0.0.2 . tcp . 80  : goto svc_b,
    10.0.0.3 . tcp . 443 : goto svc_c
}

# 3. 唯一一条数据面规则
nft add rule ip filter services \
    ip daddr . meta l4proto . th dport vmap @service_ips

数据面执行的事情变成：

取 (daddr, l4proto, dport) → jhash → 查 service_ips 哈希表 → 拿到 verdict → goto

与 N 完全无关，O(1)。

---

0.3. 三、为什么会快？源码视角拆解

0.3.1. 3.1 数据结构：从单链表 → rhashtable

项	iptables	nftables (rhash 后端)
数据结构	struct ipt_entry 单链表	struct rhashtable (可调整大小哈希表)
单次查找	逐条 match callback	1 次 jhash + 1~2 次 memcmp
元素增删	重写整张 table	单元素 rhashtable_insert_fast (O(1) 平均)
时间复杂度	O(N)	O(1)

0.3.2. 3.2 数据面入口：nft_lookup_eval

文件: net/netfilter/nft_lookup.c | 行号: 95-122 | 函数: nft_lookup_eval

void nft_lookup_eval(const struct nft_expr *expr,
                     struct nft_regs *regs,
                     const struct nft_pktinfo *pkt)
{
    const struct nft_lookup *priv = nft_expr_priv(expr);
    const struct nft_set *set = priv->set;
    const struct nft_set_ext *ext;

    /* 用寄存器里已经拼好的 key 去 set 查找 */
    ext = nft_set_do_lookup(net, set, &regs->data[priv->sreg]);
    ...
    if (ext) {
        /* vmap：把命中元素附带的 verdict (如 goto svc_chain) 写回寄存器 */
        nft_set_elem_update_expr(ext, regs, pkt);
    }
}

0.3.3. 3.3 哈希后端实现：nft_rhash_lookup

文件: net/netfilter/nft_set_hash.c | 行号: 86-104 | 函数: nft_rhash_lookup

const struct nft_set_ext *
nft_rhash_lookup(const struct net *net, const struct nft_set *set,
                 const u32 *key)
{
    struct nft_rhash *priv = nft_set_priv(set);
    const struct nft_rhash_elem *he;
    struct nft_rhash_cmp_arg arg = {
        .genmask = nft_genmask_cur(net),
        .set     = set,
        .key     = key,
        .tstamp  = get_jiffies_64(),
    };

    he = rhashtable_lookup(&priv->ht, &arg, nft_rhash_params);
    if (he != NULL)
        return &he->ext;
    return NULL;
}

哈希函数和比较函数：

文件: net/netfilter/nft_set_hash.c | 行号: 46-83 | 函数: nft_rhash_key / nft_rhash_cmp

static inline u32 nft_rhash_key(const void *data, u32 len, u32 seed)
{
    const struct nft_rhash_cmp_arg *arg = data;
    return jhash(arg->key, len, seed);     /* Jenkins Hash */
}

static inline int nft_rhash_cmp(struct rhashtable_compare_arg *arg,
                                const void *ptr)
{
    const struct nft_rhash_cmp_arg *x  = arg->key;
    const struct nft_rhash_elem  *he   = ptr;
    if (memcmp(nft_set_ext_key(&he->ext), x->key, x->set->klen))
        return 1;
    ...
    return 0;   /* 命中 */
}

朴素固定桶后端更直观地展示了三步操作：

文件: net/netfilter/nft_set_hash.c | 行号: 600-616 | 函数: nft_hash_lookup

const struct nft_set_ext *
nft_hash_lookup(const struct net *net, const struct nft_set *set,
                const u32 *key)
{
    ...
    hash = jhash(key, set->klen, priv->seed);          /* ① 算 hash */
    hash = reciprocal_scale(hash, priv->buckets);      /* ② 桶定位 */
    hlist_for_each_entry_rcu(he, &priv->table[hash], node) {
        if (!memcmp(nft_set_ext_key(&he->ext), key, set->klen) &&
            nft_set_elem_active(&he->ext, genmask))
            return &he->ext;                           /* ③ 桶内 memcmp */
    }
    return NULL;
}

三步：算哈希 → 桶定位 → 桶内 memcmp。 与集合元素总数无关。

0.3.4. 3.4 多种后端按场景自动选择

__nft_set_do_lookup 在用户态创建 set 时根据 key 类型/标志自动挑选最优后端：

文件: net/netfilter/nft_lookup.c | 行号: 28-57 | 函数: __nft_set_do_lookup

后端	数据结构	复杂度	适用场景
nft_set_rhash	rhashtable	O(1)	K8s Service 默认，动态增删多
nft_set_hash	固定桶 hash + hlist	O(1)	元素数量基本固定
nft_set_hash_fast	同上但 key ≤ 4B	O(1)	单字段精确匹配
nft_set_bitmap	位图	O(1)	key ≤ 16 bit 的小区间
nft_set_rbtree	红黑树	O(log N)	范围匹配（如 10.0.0.0/8）
nft_set_pipapo	“pile-of-piles”	O(1)~O(field)	多字段 + 范围（NetworkPolicy）

---

0.4. 四、复合 key 是怎么来的：寄存器拼接

vmap @service_ips 的 key 是 ipv4_addr . inet_proto . inet_service 三个字段拼起来的。拼接发生在用户态编译期：

阶段	谁做	做什么
编译期	用户态 nft / libnftnl	把规则拆成多条表达式，给每条分配相邻寄存器槽位
加载期	内核 *_init 钩子	把 dreg/sreg/offset/len 读进 priv，并校验范围
运行期	nft_do_chain 主循环	各表达式按顺序写 regs.data[]，最后 lookup 读连续 12B 当 key

举例 ip daddr . meta l4proto . th dport vmap @service_ips 编译后：

表达式①  nft_payload_eval  → regs.data[8]  = 172.30.0.41   (4B)
表达式②  nft_meta_get_eval → regs.data[9]  = TCP (0x06)    (1B + 3B pad)
表达式③  nft_payload_eval  → regs.data[10] = 80            (2B + 2B pad)
表达式④  nft_lookup_eval   → 读 &regs.data[8] 共 12B 当 key

regs.data 内存视图（连续 12 字节）：
  AC 1E 00 29 | 06 00 00 00 | 00 50 00 00
  └── daddr ──┘└── proto ──┘└── port ──┘

寄存器是栈上分配，per-CPU、零拷贝、无锁、SMP-safe：

文件: include/net/netfilter/nf_tables.h | 行号: 118-124 | 结构: struct nft_regs

struct nft_regs {
    union {
        u32              data[NFT_REG32_NUM];   /* 20 个 u32 */
        struct nft_verdict verdict;
    };
};

文件: net/netfilter/nf_tables_core.c | 行号: 254-266 | 函数: nft_do_chain

unsigned int nft_do_chain(struct nft_pktinfo *pkt, void *priv)
{
    ...
    struct nft_regs regs;          /* 栈上分配，本次包专用 */
    ...
}

---

0.5. 五、性能优化的几个关键设计

优化点	说明
Set 名称早绑定	用户态 @service_ips 在 nft_lookup_init 时已解析为 struct nft_set * 指针，运行时无需字符串查找
Retpoline 旁路	expr_call_ops_eval 把热点 eval 函数硬编码进 if 链，避开间接调用代价
静态 generation + RCU	rhashtable_lookup 全程无锁，仅 rcu_dereference
reciprocal_scale 替代取模	用乘法做 [0, buckets) 映射，去掉数据面除法
automatic shrinking	元素增多时 rhashtable 自动 rehash 扩容，保持桶链平均长度 ≈ 1
per-CPU 栈寄存器	struct nft_regs 栈上分配，无锁、无竞争、SMP-safe
零拷贝拼接	复合 key 通过相邻寄存器槽位自然形成，没有任何 memcpy

---

0.6. 六、控制面同样受益：Set 元素增删 ≠ 重写规则

# 加 1 个 Service：只往哈希表插一条，规则、chain 完全不动
nft add element ip filter service_ips {
    10.0.0.99 . tcp . 8080 : goto svc_x
}

文件: net/netfilter/nf_tables_api.c | 行号: 6944-6958 | 函数: nft_setelem_insert

static int nft_setelem_insert(const struct net *net,
                              struct nft_set *set,
                              const struct nft_set_elem *elem,
                              struct nft_elem_priv **elem_priv,
                              unsigned int flags)
{
    int ret;
    if (flags & NFT_SET_ELEM_CATCHALL)
        ret = nft_setelem_catchall_insert(net, set, elem, elem_priv);
    else
        ret = set->ops->insert(net, set, elem, elem_priv);  /* 仅插这个 set */
    return ret;
}

O(1) 平均时间，规则、chain、其它 set 不受影响——这与 iptables 必须重写整张 table 形成鲜明对比。

---

0.7. 七、整体调用链路一图收束

flowchart LR
    subgraph 控制面["控制面 (nft 命令)"]
        U1[nft add element<br>service_ips ...]
        U1 --> NL[netlink: NEWELEM<br>O 1 哈希插入]
    end

    subgraph 数据面["数据面 (每包一次)"]
        Pkt[数据包到达] --> DC[nft_do_chain<br>VM 主循环]
        DC --> P1[nft_payload_eval<br>regs 8 = daddr]
        P1 --> M[nft_meta_get_eval<br>regs 9 = l4proto]
        M --> P2[nft_payload_eval<br>regs 10 = dport]
        P2 --> L[nft_lookup_eval<br>读 12B key]
        L --> SDL[nft_set_do_lookup]
        SDL --> RH[nft_rhash_lookup]
        RH --> J[jhash + memcmp]
        J --> V[regs.verdict<br>= goto svc_chain]
        V --> DC
    end

    NL -.set 元素.-> RH

    style 数据面 fill:#dfd
    style 控制面 fill:#fef

---

0.8. 八、对比总结

维度	iptables 链表规则	nftables vmap + set
数据结构	struct ipt_entry 单链表	rhashtable / rbtree / pipapo
单包查找成本	平均 N/2 次 match callback	1 次 jhash + 1~2 次 memcmp
加 1 个 Service	重写整张 table	1 次 add element，规则 0 改动
控制面 sync 延迟 (5000 svc)	数百 ms ~ 数秒	< 1 ms
数据面延迟	与 N 成正比	与 N 几乎无关
失败回滚	半残	完整事务，可 abort

---

0.9. 九、一句话总结

nftables 的 Set/Map/vmap 把”原本是规则、需要逐条比对”的元素抽象成”哈希表里的数据”。
数据面只需 1 条 vmap 规则 + 1 次 jhash + 1~2 次 memcmp 就能从几万元素中拿到命中结果；控制面增删元素也只是 1 次 O(1) 哈希插入——既消除了 iptables 数据面的 O(N) 线性遍历，也消除了控制面”加 1 条规则要重写整张表”的扩展性灾难。这正是 K8s 大规模 Service 场景下 kube-proxy 的 nftables 后端能把延迟从秒级降到毫秒级的根本原因。