[GATEWAY] 优化pixiu的字典树并发读写能力

[Alanxtl]

由 yuque 文档 Pixiu路由原理简介.pdf 总结而来，原作者 @yqxu

Pixiu路由字典树（Trie）并发优化方案

1. 背景：当前实现的瓶颈

在当前的Pixiu路由实现中，为了保证数据一致性，对字典树的所有读、写操作都由一把全局锁（LOCK）来控制。无论是读取路由规则进行匹配，还是通过RDS协议动态更新路由规则，操作前都必须先获取这把锁。

这种设计的直接问题是，当读、写操作并发进行时，会产生激烈的锁竞争。特别是在高并发场景下，大量的读请求（URL匹配）会被少数的写请求（规则更新）所阻塞，从而影响网关的整体性能和延迟。该实现之所以要求读操作也加锁，是因为底层大量使用了Go语言的map结构，该结构在并发读写时会直接导致程序崩溃。

当前实现示意图：

graph LR
    subgraph "读/写线程"
        A(读请求)
        B(写请求)
    end

    subgraph "全局锁控制"
        C{LOCK}
    end

    D[Trie]

    A -- "竞争锁" --> C
    B -- "竞争锁" --> C
    C -- "获取成功" --> D

Loading

2. 优化目标

为了解决全局锁带来的性能瓶颈，优化目标是实现对字典树的无锁读取，从而让路由匹配（读操作）的性能不受规则更新（写操作）的影响。

3. 优化方案：读写分离与双树切换

本次优化引入了读写分离的设计思想，核心是维护两棵功能上完全相同的字典树（Trie1和Trie2），一棵用于读取（“读树”），另一棵用于写入（“写树”）。

方案核心组件：

• Command队列：所有对字典树的写操作（如添加、删除路由）不再直接作用于树，而是先被封装成一个command对象，放入一个先进先出（FIFO）的队列中。
• 双字典树（Trie1 & Trie2）：系统中同时存在两个Trie实例。在任意时刻，一个作为“读树”对外提供无锁的路由匹配服务，另一个作为“写树”在后台消费Command队列中的指令。
• 追Log线程：一个独立的后台线程，负责从Command队列中读取指令，并将其应用到当前的“写树”上。由于只有这一个线程对“写树”进行操作，因此“写树”本身也无需加锁。
• 双游标（Index1 & Index2）：队列维护两个游标，分别对应两棵树追赶指令的进度。

整体架构示意图：

graph LR
    subgraph "用户写操作"
        A[Operator: url add /a/b/c] --> Q;
        B[Operator: url remove /a/b] --> Q;
    end

    subgraph "Command队列 (FIFO)"
        Q(Command Queue)
    end

    subgraph "后台追Log线程"
        T[追Log线程]
    end

    subgraph "双Trie实例"
        T1(Trie1 - 读树);
        T2(Trie2 - 写树);
    end

    R[读请求]

    Q -- "读取Command" --> T;
    T -- "写入" --> T2;

    R -- "无锁读取" --> T1;

    %% 切换逻辑
    style T1 fill:#cde,stroke:#333
    style T2 fill:#fce,stroke:#333

Loading

4. 角色切换逻辑

为了让“写树”上更新的配置能够生效，系统会周期性地（例如，每3秒）切换“读树”和“写树”的角色 [cite: 246, 247]。切换过程经过精心设计，以保证服务的平滑过渡：

1. 暂停写入：首先让“追Log线程”空转，即暂停向“写树”应用新的Command。这样做是为了避免在切换过程中树的状态发生变化，同时通过空转而非挂起线程来避免上下文切换的开销。
2. 确保无写入：保证当前没有任何写入线程在操作两棵树。
3. 切换读引用：将全局的“读引用”切换到另一棵树（即原来的“写树”）。从这一刻起，所有新的读请求都将从这棵更新过的树中读取数据。
4. 切换写引用：将“追Log线程”的“写引用”切换到原来的“读树”上。
5. 恢复写入：恢复“追Log线程”的工作，使其开始向新的“写树”同步Command队列中的指令。

通过这个机制，可以实现配置的“延迟生效”（例如延迟3秒），同时保证了最终一致性，因为两棵树追赶的是同一份操作日志（Command队列）。

5. 优化带来的收益

• 高性能读取：路由匹配（读操作）不再需要等待锁，实现了完全的无锁读取，性能得到极大提升。
• 消除竞争：写操作被异步化，读和写在不同的数据结构上进行，彻底消除了读写冲突。
• 高可用性：即使在频繁更新路由规则的场景下，网关对外的服务能力（路由匹配）也不会受到影响。

---

[Alanxtl]

性能benchmark