IRedis开发记3:编译正则的难题

这篇文章是 IRedis 的第三篇开发笔记。一直以来,IRedis 的补全都是基于 prompt_toolkit 的 regular_language 来实现的(一个例子)。我需要用正则表达式来验证用户输入的 Redis 命令是否合法,从中抓出来 token,然后对这些 token 进行自动补全。随着开发,支持的 Redis 的命令越来越多,这个正则表达式已经膨胀到 200+ 行了,编译速度也令人难以忍受。

这个问题困扰了我将近3个月,我尝试过各种各样的方法,从身边的朋友那里听取不同的思路和建议,终于在最近近乎完美地解决了这个问题。以至于兴奋的睡不着觉。

这篇文章分享一下这个问题,为了解决这个问题尝试过的方案,以及最终采用的方案的工作原理。读者从这个问题和方案本身可能并不会学到什么可以 Take away 的东西,因为很难在遇到这种问题(这也是这个问题比较难解决的原因之一)。但是我更想分享一下解决的思路,以及它带给我的启发。可能对于将来的我,再回来看的时候,会发现解决问题是如此美妙的一个过程,编程本身又是多么充满乐趣的事情。

问题:用正则来匹配输入……

为了接下来的讨论,我先描述一下我面临的问题。

我要写一个 Redis 命令行的客户端,支持对 Redis 命令的自动补全。(相关文章 IRedis 开发记录:Redis 命令语法的处理 )。但是我不会从头开始写这个命令行客户端的输入输出,而是选择了 IPython 和 mycli/pgcli 都用的一个库:prompt_toolkit. 它是用了 Python 的正则表达式的 named group 功能,从输入的内容中抓出来 token。比如这个例子中,语法的正则是这么写的:

当输入 abc  (注意后面有个空格)的时候,abc 就匹配到了 <operator1> ,然后空格匹配到了 \s+ ,框架就知道后面要输入的是一个 var1 了。

类似的,我写的 Redis 的命令节选如下:

因为 Redis 的命令不像 SQL 那样是结构化的语法,每个数据类型的命令格式都不一样,所以写起来要用或 | 将这些语法都连接起来。

另外还要补充一点的是,我写的这个正则并不是直接拿去匹配用户输入了,因为框架需要知道这个 token 的下一个 token 可能是什么,以此来做自动补全的提示。所以其实我的这个正则是交给框架去解析了,而不是直接 re.compile() 。框架会将这个正则拆散,然后一个一个编译。这一点也导致了后面会讲到的一些方案行不通。

另另外要补充的是,不光是拆开这些正则就可以了,如果这样到好了,也就是不到 100 个正则,编译一下也是很快的。作为用来匹配用户输入的问题是,即使用户只输入了一部分,也应该认为是合法的。比如正则是要匹配 SET 命令,而用户输入了 SE,那么也应该认为这是一个合法输入,而不应该显示成下图这样的非法提示。

那么怎么做到这一点呢?这个框架的方案是解析正则,然后分析出更多的正则来匹配部分输入。比如 SET,那么根据此应该生成 SET|SE|S,看起来也不复杂,但是如果支持的参数越来越多,需要编译的正则的数量将会呈指数级上涨。

举个简单的例子,下面这个语法:

最终生成的正则是这样子:

这就很恐怖了。

当 IRedis 支持 Redis-server 的 197 个命令语法的时候,需要编译的正则已经达到了 ~8000 个。IRedis 启动的时候需要等待 ~8s 编译正则完成。

这就是问题了。作为一个命令行客户端(对比一下 mysql/redis-cli/mongo 这种客户端),需要等待 8s 才能使用,是非常影响体验的。

缓兵之计:异步线程加载

这个问题没解决之前,我将这些正则的编译改到了一个 daemon 线程中去编译(这个PR)。在编译结束之前,最下方的 bottom-bar 会显示一个 ascii 动画提示正在编译,并且 Lexer 高亮,补全这些功能都没有激活,像一个 redis-cli 那样只有基本的功能。

但是这段时间 CPU 在不停的做正则编译,占用量会很高。以及用户体验也有影响,相比 redis-cli 秒开,太伤了。

 

如果要从根本上解决这个问题,现在看来有以下几个思路:

  1. 能否缓存下来正则,不要每次都编译?
  2. 能不能替换掉编译正则的方案?
  3. 能否加速正则的编译?
  4. 减少需要编译的正则的数量;
  5. 不要一下子编译好所有的正则,用到哪个编译那个。

尝试1:缓存正则

这是一个比较直觉的方案。我尝试过用 pickle/dill (应该还尝试过一个,不过名字忘记了)。发现 dump 出来,下次启动直接 load,从方案上是可行的。但是速度依然很慢。后来发现 pickle 只是去打包一个对象的 __init__ 参数,当 load 的时候,再用类初始化一次(这样对于大部分 pickle 的使用场景来说是合理的)。所以还是相当于编译了一次。(资料

理论上,直接缓存 C 语言层面的 regex 编译结果也是可行的,但是会遇到 Python 跨版本不兼容的问题,因为这部分并没有公开的 API,所以没有人能保证它的兼容性。

我觉得这将会是一个大坑,所以没有继续沿着这条路走下去了。

尝试2:另寻没有正则的方案

老实说,用正则来处理语法并不是很好。比如 Redis 的命令有一些是下面的这种语法,而这种是无法用正则来表达的:

ZINTERSTORE 这个命令 后面有个 numkeys 表示后面紧跟着几个 key,然后再是 WEIGHTS。只有知道了 key 的数量,才不会将 WEIGHT 也作为 一个 key。而正则是不支持从前面解析出来数字然后应用到后面的 match 中的。

于是我想拿 pygments 来做一个基于状态机的 Grammar。参考 这个PR。理论上是可行的,但是并没有最终采用这个方案。原因是工作量太大了。如果我直接用正则,那么我可以用 prompt_toolkit 框架中的一些补全,Lexer。否则的话,我就要重写 Grammar,match 前缀的逻辑,Lexer,判断下一个 token 可能是什么来推测补全列表。相当于另外写一个 prompt_toolkit 了。所以这条路也放弃了。

Jonath(prompt_toolkit的作者)建议过我用状态机实现,这个方案同样也是工作量太大。本来 IRedis 就是因为另一个项目而生的,我不太想因为 IRedis 要先去完成另一外一个新的项目 :)

尝试3:编译更快的正则

这个方案比较好理解,Python 的 re 比较慢,能否用更快的 re 来替换呢。Python monkey patch 比较简单,我只要将系统 buildin 的那个 re 替换掉就好了。大部分其他 re 的库也是兼容 buildin re 的 API的。

我尝试过的库有:

  1. google 的 re2
  2. Rust 写的 rure
  3. Python 的 regex

效果不是很好,原因很简单:这些库可能在一些情况下编译正则的速度快一些。但是我这里的问题并不是编译一个正则太慢,而是要编译的正则太多。对于 8000 个正则来说,就算能快上一倍,效果也不明显的。

尝试4:减少编译正则的数量

guyskky 提到可以将正则 merge 一下,类似 werkzeug 处理 URL 的方式(werkzeug.routing.Rule.compile)。我觉得这个比较可行,但是还没有尝试。

但是跟 Jonath 讨论之后,Jonath 开始优化这一块正则的 merge,这个 PR 到我写这篇文章的时候,已经 work 了。

经过优化之后,需要正则的数量降低到了 496 个,1.7s 就可以编译完成。

尝试5:即时编译

上面的方案4是一个治本的方案,但是在我这个方案之前,我并不是方案4是不是可行的(因为对 prompt_toolkit 读的代码不多),所以我上周用“即时编译”的思路进行了重构。

这个想法很简单:既然启动的时候编译那么多正则表达式很慢,那么我为什么要一开始就全部编译好呢?用到哪一个再编译哪一个不就好了吗?

比如用户输入了 KEYS 那么我就编译好 KEYS 的语法,然后将当前的语法替换成这个。当用户输入了 GET,我再编译 GET 的语法并进行替换。

能够这么做基于两点:

  1. Python 在运行时动态地替换一个对象的属性非常简单,并且我这个 client 也是单线程的,不会存在线程安全问题;
  2. Redis 的不同命令的语法都是独立的,不像 SQL 那样,你不能只编译一部分。当然,问题的根源也是它。

核心代码是下面这个 Processor,Processor 是框架的一个概念,每次用户按下什么键都会执行。

核心代码是 24-27 行,当用户输入的命令匹配到 Redis 命令了,就替换当前的 Lexer 和 Completer。

这样问题就完美的解决了,当然还有一些细节问题。

比如当用户输入了一个命令语法比较复杂的时候,会感觉到一点卡顿,因为在编译正则。我在编译的函数上加个一个装饰器 @lru_cache(maxsize=256) ,将编译结果直接缓存下来,这样只在第一次输入的时候会卡,后面就好多了。

等 prompt_toolkit 那个 PR 合并,配合我修改的“即时编译”,这个问题就算完美的解决了。

 

解决这个问题,大概花了 3 个月。但是最终解决的那一刻,感觉真的很奇妙。这件事情给我一些很强烈的感受:

  1. 编程这件事情本身,我是说就算没有带来任何名誉、财富上的收获,也实在太有意思了;
  2. Python 社区的人太好了,除了 Jonath 给我很多很多建议,Dbcli 的 amjith 还和我视频通话,跟我说他之前也想做一个 redis 的 cli,跟我说了一些他的想法,非常有用。此外还得到了很多很多其他人的帮助和建议。Python 社区很温暖!
  3. 用 Python 编程太快乐了!比如本文的 @lru_cache ,这一行能完美解决问题!IRedis 项目中,我遇到了很多类似的体验,我打算单独写一篇文章讨论这个。

Happy hacking!

IRedis开发记3:编译正则的难题”已经有10条评论

    • 现在想想,也许这些尝试都不是白费的。这个方案难想出来的点在于,Redis 的每一个命令之间都是不相关的,而我们设计语法的时候总是默认用一个树形来表示(所以叫做语法树),而 Redis 的更像一个 Hash。

Leave a comment

电子邮件地址不会被公开。 必填项已用*标注