GitHub user Alanxtl reopened 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 [email protected]. To unsubscribe, please send an email to: [email protected] --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
