ToB企服应用市场:ToB评测及商务社交产业平台

标题: Pisa-Proxy 之 SQL 解析实践 [打印本页]
作者: 祗疼妳一个    时间: 2022-8-20 16:39
标题: Pisa-Proxy 之 SQL 解析实践
SQL 语句解析是一个重要且复杂的技术，数据库流量相关的 SQL 审计、读写分离、分片等功能都依赖于 SQL 解析，而 Pisa-Proxy 作为 Database Mesh 理念的一个实践，对数据库流量的治理是其核心，因此实现 SQL 解析是一项很重要的工作。本文将以 Pisa-Proxy 实践为例，为大家展现 Pisa-Proxy 中的 SQL 解析实现，遇到的问题及优化。
一、背景

关于语法分析

语法分析一般通过词法分析器，如 Flex，生成相应的 token，语法分析器通过分析 token，来判断是否满足定义的语法规则。
语法分析器一般会通过解析生成器生成。
语法分析算法常用的有以下：
与上下文无关文法，从左到右扫描，从最左推导语法树，相比 LR 更容易理解，错误处理更友好。
与上下文无关文法，从左到右扫描，从最右节点推导语法树，相比 LL 速度快。
与 LR 类似，在解析时比 LR 生成的状态更少，从而减少 Shift/Reduce 或者 Reduce/Reduce 冲突，被业界广泛使用的 bison/yacc 生成的就是基于 LALR 解析器。
关于调研

在开发 SQL 解析之初，我们从性能、维护性、开发效率、完成度四方面分别调研了 antlr_rust，sqlparser-rs，nom-sql 项目，但都存在一些问题。
ShardingSphere 实现了基于 Antlr 的不同的 SQL 方言解析，为了使用它的 Grammar，我们调研了 antlr_rust 项目，此项目不够活跃，成熟度不够高。
在 Rust 社区里，sqlparser-rs 项目是一个较为成熟的库，兼容各种 SQL 方言，Pisa-Proxy 在未来也会支持多种数据源，但是由于其词法和语法解析都是纯手工打造的，对我们来说会不易维护。
nom-sql 是基于 nom 库实现的 SQL 解析器，但是未实现完整，性能测试不如预期。
Grmtools 是在寻找 Rust 相关的 Yacc 实现时发现的库，该库实现了兼容绝大部分 Yacc 功能，这样就可以复用 MySQL 官方的语法文件，但是需要手写 Lex 词法解析，经过对开发效率及完成度权衡后，我们决定做难且正确的事，实现自己的 SQL 解析器，快速实现一个 Demo 进行测试。
编码完成后，测试效果还不错。
总结如下：
工具antlr_rustsqlparser-rsnom-sqlgrmtools完成度✅✅性能✅✅维护性✅开发效率✅✅最终我们选择了 Grmtools 来开发 Pisa-Proxy 中的 SQL 解析。
二、Grmtools 使用

使用 Grmtools 解析库大致分为两个步骤，下面以实现计算器为例。
Lex：创建 calc.l，内容如下：
  1. /%%
  2. [0-9]+ "INT"
  3. \+ "+"
  4. \* "*"
  5. \( "("
  6. \) ")"
  7. [\t ]+ ;
复制代码
Grammar：创建 calc.y 内容如下：
  1. %start Expr
  2. %avoid_insert "INT"
  3. %%
  4. Expr -> Result<u64, ()>:
  5.       Expr '+' Term { Ok($1? + $3?) }
  6.     | Term { $1 }
  7.     ;
  9. Term -> Result<u64, ()>:
  10.       Term '*' Factor { Ok($1? * $3?) }
  11.     | Factor { $1 }
  12.     ;
  14. Factor -> Result<u64, ()>:
  15.       '(' Expr ')' { $2 }
  16.     | 'INT'
  17.       {
  18.           let v = $1.map_err(|_| ())?;
  19.           parse_int($lexer.span_str(v.span()))
  20.       }
  21.     ;
  22. %%
复制代码
Grmtools 需要在编译时生成词法和语法解析器，因此需要创建 build.rs，其内容如下：
  1. use cfgrammar::yacc::YaccKind;
  2. use lrlex::CTLexerBuilder;
  3. fn main() -> Result<(), Box<dyn std::error::Error>> {
  4.     CTLexerBuilder::new()
  5.         .lrpar_config(|ctp| {
  6.             ctp.yacckind(YaccKind::Grmtools)
  7.                 .grammar_in_src_dir("calc.y")
  8.                 .unwrap()
  9.         })
  10.         .lexer_in_src_dir("calc.l")?
  11.         .build()?;
  12.     Ok(())
  13. }
复制代码
  1. use std::env;
  3. use lrlex::lrlex_mod;
  4. use lrpar::lrpar_mod;
  6. // Using `lrlex_mod!` brings the lexer for `calc.l` into scope. By default the
  7. // module name will be `calc_l` (i.e. the file name, minus any extensions,
  8. // with a suffix of `_l`).
  9. lrlex_mod!("calc.l");
  10. // Using `lrpar_mod!` brings the parser for `calc.y` into scope. By default the
  11. // module name will be `calc_y` (i.e. the file name, minus any extensions,
  12. // with a suffix of `_y`).
  13. lrpar_mod!("calc.y");
  15. fn main() {
  16.     // Get the `LexerDef` for the `calc` language.
  17.     let lexerdef = calc_l::lexerdef();
  18.     let args: Vec<String> = env::args().collect();
  19.     // Now we create a lexer with the `lexer` method with which we can lex an
  20.     // input.
  21.     let lexer = lexerdef.lexer(&args[1]);
  22.     // Pass the lexer to the parser and lex and parse the input.
  23.     let (res, errs) = calc_y::parse(&lexer);
  24.     for e in errs {
  25.         println!("{}", e.pp(&lexer, &calc_y::token_epp));
  26.     }
  27.     match res {
  28.         Some(r) => println!("Result: {:?}", r),
  29.         _ => eprintln!("Unable to evaluate expression.")
  30.     }
  31. }
复制代码
详见: grmtools - grmtools
上文已经提到，我们需要手写词法解析，是因为在原生的 Grmtools 中，词法解析是用正则匹配的，对于灵活复杂的 SQL 语句来说，不足以满足，因此需要手工打造词法解析，在 Grmtools 中实现自定义词法解析需要我们实现以下 Trait：
  1. lrpar::NonStreamingLexer
复制代码
另外也提供了一个方便的方法去实例化：
  1. lrlex::LRNonStreamingLexer::new()
复制代码
三、遇到的问题

基于以上，我们开发了 SQL 词法解析，复用了 MySQL 官方的 sql_yacc 文件，在开发过程中，也遇到了以下问题。
  1. Shift/Reduce conflicts:
  2.      State 619: Shift("TEXT_STRING") / Reduce(literal: "text_literal")
复制代码
这是使用 LALR 算法经常出现的错误，错误成因一般通过分析相关规则解决，例如常见的 If-Else 语句，规则如下：
  1. %nonassoc LOWER_THEN_ELSE
  2. %nonassoc ELSE
  3. stmt:
  4.     IF expr stmt %prec LOWER_THEN_ELSE
  5.   | IF expr stmt ELSE stmt
复制代码
当 ELSE 被扫描入栈时，此时会有两种情况。
1）按第二条规则继续 Shift
2）按第一条规则进行 Reduce
这就是经典的 Shift/Reduce 错误。
回到我们的问题，有如以下规则：
  1. literal -> String:
  2.     text_literal
  3.     { }
  4.   | NUM_literal  
  5.     { }
  6. ...
  8. text_literal -> String:
  9.     'TEXT_STRING' {}
  10.   | 'NCHAR_STRING' {}
  11.   | text_literal 'TEXT_STRING' {}
  12. ...
复制代码
分析：
stackInput tokenactiontestShift testtest$Reduce: text_literal/Shift: TEXT_STRING方案：
需要设置优先级解决，给 text_literal 设置更低的优先级，如以下：
  1. %nonassoc 'LOWER_THEN_TEXT_STRING'
  2. %nonassoc 'TEXT_STRING'
  5. literal -> String:
  6.     text_literal  %prec 'LOWER_THEN_TEXT_STRING'
  7.     { }
  8.   | NUM_literal  
  9.     { }
  10. ...
  12. text_literal -> String:
  13.     'TEXT_STRING' {}
  14.   | 'NCHAR_STRING' {}
  15.   | text_literal 'TEXT_STRING' {}
  16. ...
复制代码
在使用词法解析时，.chars() 生成字符串数组会出现数组长度和字符长度不一致的情况，导致解析出错，要更改为 .as_bytes() 方法。
四、优化

  1. [mworks@fedora examples]$ time ./parser
  3. real        0m4.788s
  4. user        0m4.781s
  5. sys         0m0.002s
复制代码
尝试优化，以下是火焰图：

通过火焰图发现，大部分 CPU 耗时在序列化和反序列化，以下是定位到的代码：

可以看出在每次解析的时候都需要反序列化数据，在编译完之后，__GRM_DATA 和 __STABLE_DATA 是固定不变的, 因此 grm，stable 这两个参数可以作为函数参数传递，更改为如下：

再看代码，发现 actions 数组是有规律的，如以下：
  1. ::std::vec![&__gt_wrapper_0,
  2.                &__gt_wrapper_1,
  3.                &__gt_wrapper_2,
  4.                ...
  5.             ]
复制代码
因此我们可以手动构造函数，以下是伪代码：
  1. match idx {
  2.     0 => __gt_wrapper_0(),
  3.     1 => __gt_wrapper_1(),
  4.     2 => __gt_wrapper_2(),
  5.     ....
  6. }
复制代码
通过 gobolt 查看汇编，发现差异还是很大，省去了数组的相关开销，也能极大地减少内存使用。

详见：https://rust.godbolt.org/z/zTjW479f6
但是随着 actions 数组的不断增大，会有大量的 je，jmp 指令，不清楚是否会影响 CPU 的分支预测，如影响是否可以通过 likely/unlikely 方式优化，目前还没有进行测试。
最终火焰图对比


最终测试结果
  1. [mworks@fedora examples]$ time ./parser
  3. real        0m2.677s
  4. user        0m2.667s
  5. sys         0m0.007s
复制代码
五、总结

本文为 Pisa-Proxy SQL 解析解读系列第一篇，介绍了在 Pisa-Proxy 中开发 SQL 解析背后的故事，后续我们会陆续为大家详细介绍 Yacc 语法规则的编写，Grmtools 中组件及实用工具等内容，敬请期待。
附录

Pisa-Proxy 的 SQL 解析代码：
pisanix/pisa-proxy/parser/mysql at master · database-mesh/pisan
测试代码
  1.     let input = "select id, name from t where id = ?;"
  2.     let p = parser::Parser::new();
  3.     for _ in 0..1_000_000
  4.     {
  5.         let _ = p.parse(input);
  6.     }
复制代码
Pisanix
项目地址：https://github.com/database-mesh/pisanix
官网地址：https://www.pisanix.io/
Database Mesh：https://www.database-mesh.io/
SphereEx 官网：https://www.sphere-ex.com

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！



欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/) Powered by Discuz! X3.4