记录一个openresty路由算法的优化

最近在做一个Apigateway项目,目标就是做成类似AWS的Apigateway那样,但是只需要支持HTTP协议即可,由于配置非常灵活,而且性能要求比较高,我还是选择了 openresty 来作为这个网关的技术栈。但是我们需要对nginx.conf文件做一个改造,要做到添加或删除 路径的配置,修改Upstream的内容等都不能reload重启nginx,所以nginx原生的路由匹配功能我们就无法利用了。只能通过lua代码自己去匹配。

路由配置一共分4种,精确匹配,前缀匹配,占位符匹配和正则匹配。代码写完,单元测试都跑完之后,我就进入了性能压测阶段,当一个host只有数10条路由规则的时候,性能还是很OK的,在一台普通的web服务器上进行压测,2000个并发情况下,QPS每秒处理任务数都达到了4W+,符合我们的预期。

于是,我模拟一些苛刻的场景,在一个host里,我把路由数量增加到1000+,QPS瞬间就降下来了,精确匹配和前缀匹配下降的比较少一些,但也是只有2W+了,可悲的占位符和正则(通过ngx.re来进行匹配的)QPS甚至跌倒了900+,令人非常沮丧。

后来我们优化了一下算法,采用trietree来生成路由树,当每次有配置变更的时候,都需要重新去生成这棵树,在2000并发压力情况下,生成1000个路由的trietree也仅需要100毫秒以内,这个性能我们能接受。同时经过了trietree的优化,就算有1000个路由需要匹配,4钟路由匹配方式又都重新回到了4W+的QPS,相比原来直接循环匹配路由有了质的飞跃。