Re: [D] [GATEWAY] 优化pixiu的字典树并发读写能力 [dubbo-go-pixiu]

["Alanxtl (via GitHub)" <gi...@apache.org>]

GitHub user Alanxtl edited a discussion: [GATEWAY] 优化pixiu的字典树并发读写能力


由 yuque 文档 [Pixiu路由原理简介.pdf](https://github.com/user-attachments/files/21966865/Pixiu.pdf) 总结而来，原作者 @yqxu 


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

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

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

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

**当前实现示意图：**

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

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

    D[Trie]

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

#### **2. 优化目标**

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

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

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

**方案核心组件：**

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

**整体架构示意图：**

```mermaid
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
```

#### **4. 角色切换逻辑**

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

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

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

#### **5. 优化带来的收益**

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

-----

GitHub link: https://github.com/apache/dubbo-go-pixiu/discussions/743

----
This is an automatically sent email for notifications@dubbo.apache.org.
To unsubscribe, please send an email to: notifications-unsubscribe@dubbo.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: notifications-unsubscribe@dubbo.apache.org
For additional commands, e-mail: notifications-help@dubbo.apache.org