Pisa-Proxy 之 SQL 解析實踐

来源:https://www.cnblogs.com/sphereex/archive/2022/06/27/16415904.html
-Advertisement-
Play Games

SQL 語句解析是一個重要且複雜的技術，資料庫流量相關的 SQL 審計、讀寫分離、分片等功能都依賴於 SQL 解析，而 Pisa-Proxy 作為 Database Mesh 理念的一個實踐，對資料庫流量的治理是其核心，因此實現 SQL 解析是一項很重要的工作。本文將以 Pisa-Proxy 實踐為 ...


SQL 語句解析是一個重要且複雜的技術，資料庫流量相關的 SQL 審計、讀寫分離、分片等功能都依賴於 SQL 解析，而 Pisa-Proxy 作為 Database Mesh 理念的一個實踐，對資料庫流量的治理是其核心，因此實現 SQL 解析是一項很重要的工作。本文將以 Pisa-Proxy 實踐為例，為大家展現 Pisa-Proxy 中的 SQL 解析實現，遇到的問題及優化。

一、背景

關於語法分析

語法分析一般通過詞法分析器，如 Flex，生成相應的 token，語法分析器通過分析 token，來判斷是否滿足定義的語法規則。

語法分析器一般會通過解析生成器生成。

語法分析演算法常用的有以下：

  • LL（自上而下）

與上下文無關文法，從左到右掃描，從最左推導語法樹，相比 LR 更容易理解，錯誤處理更友好。

  • LR（自下而上）

與上下文無關文法，從左到右掃描，從最右節點推導語法樹，相比 LL 速度快。

  • LALR

與 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_rust sqlparser-rs nom-sql grmtools
完成度 ✅ ✅
性能 ✅ ✅
維護性 ✅
開發效率 ✅ ✅

最終我們選擇了 Grmtools 來開發 Pisa-Proxy 中的 SQL 解析。

二、Grmtools 使用

使用 Grmtools 解析庫大致分為兩個步驟，下麵以實現計算器為例。

  1. 編寫 Lex 和 Yacc 文件

Lex：創建 calc.l，內容如下：

/%%
[0-9]+ "INT"
\+ "+"
\* "*"
\( "("
\) ")"
[\t ]+ ;

Grammar：創建 calc.y 內容如下：

%start Expr
%avoid_insert "INT"
%%
Expr -> Result<u64, ()>:
      Expr '+' Term { Ok($1? + $3?) }
    | Term { $1 }
    ;

Term -> Result<u64, ()>:
      Term '*' Factor { Ok($1? * $3?) }
    | Factor { $1 }
    ;

Factor -> Result<u64, ()>:
      '(' Expr ')' { $2 }
    | 'INT'
      {
          let v = $1.map_err(|_| ())?;
          parse_int($lexer.span_str(v.span()))
      }
    ;
%%
  1. 構造詞法和語法解析器

Grmtools 需要在編譯時生成詞法和語法解析器，因此需要創建 build.rs，其內容如下：

use cfgrammar::yacc::YaccKind;
use lrlex::CTLexerBuilder;
fn main() -> Result<(), Box<dyn std::error::Error>> {
    CTLexerBuilder::new()
        .lrpar_config(|ctp| {
            ctp.yacckind(YaccKind::Grmtools)
                .grammar_in_src_dir("calc.y")
                .unwrap()
        })
        .lexer_in_src_dir("calc.l")?
        .build()?;
    Ok(())
}
  1. 在應用中集成解析
use std::env;

use lrlex::lrlex_mod;
use lrpar::lrpar_mod;

// Using `lrlex_mod!` brings the lexer for `calc.l` into scope. By default the
// module name will be `calc_l` (i.e. the file name, minus any extensions,
// with a suffix of `_l`).
lrlex_mod!("calc.l");
// Using `lrpar_mod!` brings the parser for `calc.y` into scope. By default the
// module name will be `calc_y` (i.e. the file name, minus any extensions,
// with a suffix of `_y`).
lrpar_mod!("calc.y");

fn main() {
    // Get the `LexerDef` for the `calc` language.
    let lexerdef = calc_l::lexerdef();
    let args: Vec<String> = env::args().collect();
    // Now we create a lexer with the `lexer` method with which we can lex an
    // input.
    let lexer = lexerdef.lexer(&args[1]);
    // Pass the lexer to the parser and lex and parse the input.
    let (res, errs) = calc_y::parse(&lexer);
    for e in errs {
        println!("{}", e.pp(&lexer, &calc_y::token_epp));
    }
    match res {
        Some(r) => println!("Result: {:?}", r),
        _ => eprintln!("Unable to evaluate expression.")
    }
}

詳見: grmtools - grmtools

上文已經提到，我們需要手寫詞法解析，是因為在原生的 Grmtools 中，詞法解析是用正則匹配的，對於靈活複雜的 SQL 語句來說，不足以滿足，因此需要手工打造詞法解析，在 Grmtools 中實現自定義詞法解析需要我們實現以下 Trait：

lrpar::NonStreamingLexer

另外也提供了一個方便的方法去實例化：

lrlex::LRNonStreamingLexer::new()

三、遇到的問題

基於以上，我們開發了 SQL 詞法解析，復用了 MySQL 官方的 sql_yacc 文件，在開發過程中，也遇到了以下問題。

  1. Shift/Reduce 錯誤
Shift/Reduce conflicts:
     State 619: Shift("TEXT_STRING") / Reduce(literal: "text_literal")

這是使用 LALR 演算法經常出現的錯誤，錯誤成因一般通過分析相關規則解決，例如常見的 If-Else 語句，規則如下：

%nonassoc LOWER_THEN_ELSE 
%nonassoc ELSE 
stmt: 
    IF expr stmt %prec LOWER_THEN_ELSE
  | IF expr stmt ELSE stmt

當 ELSE 被掃描入棧時，此時會有兩種情況。

1）按第二條規則繼續 Shift

2）按第一條規則進行 Reduce

這就是經典的 Shift/Reduce 錯誤。

回到我們的問題，有如以下規則：

literal -> String:
    text_literal 
    { }
  | NUM_literal  
    { }
 ...
 
 text_literal -> String:
    'TEXT_STRING' {}
  | 'NCHAR_STRING' {}
  | text_literal 'TEXT_STRING' {}
 ...

分析：

stack Input token action
test Shift test
test $ Reduce: text_literal/Shift: TEXT_STRING

方案：

需要設置優先順序解決，給 text_literal 設置更低的優先順序，如以下：

%nonassoc 'LOWER_THEN_TEXT_STRING'
%nonassoc 'TEXT_STRING'


literal -> String:
    text_literal  %prec 'LOWER_THEN_TEXT_STRING' 
    { }
  | NUM_literal  
    { }
 ...
 
 text_literal -> String:
    'TEXT_STRING' {}
  | 'NCHAR_STRING' {}
  | text_literal 'TEXT_STRING' {}
 ...
  1. SQL 包含中文問題

在使用詞法解析時，.chars() 生成字元串數組會出現數組長度和字元長度不一致的情況，導致解析出錯，要更改為 .as_bytes() 方法。

四、優化

  1. 在空跑解析（測試代碼見附錄），不執行 action 的情況下，性能如下：
[mworks@fedora examples]$ time ./parser

real        0m4.788s
user        0m4.781s
sys         0m0.002s

嘗試優化，以下是火焰圖：

通過火焰圖發現，大部分 CPU 耗時在序列化和反序列化，以下是定位到的代碼：

可以看出在每次解析的時候都需要反序列化數據，在編譯完之後，__GRM_DATA 和 __STABLE_DATA 是固定不變的, 因此 grm，stable 這兩個參數可以作為函數參數傳遞，更改為如下：

  1. 再分析，每次解析的時候，都會初始化一個 actions 的數組，隨著 grammar 中語法規則的增多，actions 的數組也會隨之增大，且數組元素類型是 dyn trait 的引用，在運行時是有開銷的。

再看代碼，發現 actions 數組是有規律的，如以下：

::std::vec![&__gt_wrapper_0,
               &__gt_wrapper_1,
               &__gt_wrapper_2,
               ...
            ]

因此我們可以手動構造函數，以下是偽代碼：

match idx {
    0 => __gt_wrapper_0(),
    1 => __gt_wrapper_1(),
    2 => __gt_wrapper_2(),
    ....
}

通過 gobolt 查看彙編，發現差異還是很大，省去了數組的相關開銷，也能極大地減少記憶體使用。

詳見：https://rust.godbolt.org/z/zTjW479f6

但是隨著 actions 數組的不斷增大，會有大量的 je，jmp 指令，不清楚是否會影響 CPU 的分支預測，如影響是否可以通過 likely/unlikely 方式優化，目前還沒有進行測試。

最終火焰圖對比

最終測試結果

[mworks@fedora examples]$ time ./parser

real        0m2.677s
user        0m2.667s
sys         0m0.007s

五、總結

本文為 Pisa-Proxy SQL 解析解讀系列第一篇，介紹了在 Pisa-Proxy 中開發 SQL 解析背後的故事，後續我們會陸續為大家詳細介紹 Yacc 語法規則的編寫，Grmtools 中組件及實用工具等內容，敬請期待。

附錄

Pisa-Proxy 的 SQL 解析代碼：

pisanix/pisa-proxy/parser/mysql at master · database-mesh/pisan

測試代碼

    let input = "select id, name from t where id = ?;"
    let p = parser::Parser::new();
    for _ in 0..1_000_000
    {
        let _ = p.parse(input);
    }

Pisanix

項目地址：https://github.com/database-mesh/pisanix

官網地址：https://www.pisanix.io/

Database Mesh：https://www.database-mesh.io/

SphereEx 官網：https://www.sphere-ex.com


您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
一周排行
    -Advertisement-
    Play Games
  • 移動開發（一）：使用.NET MAUI開發第一個安卓APP
    移動開發（一）：使用.NET MAUI開發第一個安卓APP 對於工作多年的C#程式員來說，近來想嘗試開發一款安卓APP，考慮了很久最終選擇使用.NET MAUI這個微軟官方的框架來嘗試體驗開發安卓APP，畢竟是使用Visual Studio開發工具，使用起來也比較的順手，結合微軟官方的教程進行了安卓 ...
  • wpf ToggleButton選中效果和一個登錄界面
    前言 QuestPDF 是一個開源 .NET 庫，用於生成 PDF 文檔。使用了C# Fluent API方式可簡化開發、減少錯誤並提高工作效率。利用它可以輕鬆生成 PDF 報告、發票、導出文件等。 項目介紹 QuestPDF 是一個革命性的開源 .NET 庫，它徹底改變了我們生成 PDF 文檔的方 ...
  • 彈幕樹洞項目功能新增篇
    項目地址 項目後端地址： https://github.com/ZyPLJ/ZYTteeHole 項目前端頁面地址： ZyPLJ/TreeHoleVue (github.com) https://github.com/ZyPLJ/TreeHoleVue 目前項目測試訪問地址： http://tree ...
  • 第27篇 sqlserver2022詳細安裝步驟
    話不多說，直接開乾 一.下載 1.官方鏈接下載： https://www.microsoft.com/zh-cn/sql-server/sql-server-downloads 2.在下載目錄中找到下麵這個小的安裝包 SQL2022-SSEI-Dev.exe，運行開始下載SQL server； 二. ...
  • .NET 開源高性能 MQTT 類庫
    前言 隨著物聯網（IoT）技術的迅猛發展，MQTT（消息隊列遙測傳輸）協議憑藉其輕量級和高效性，已成為眾多物聯網應用的首選通信標準。 MQTTnet 作為一個高性能的 .NET 開源庫，為 .NET 平臺上的 MQTT 客戶端與伺服器開發提供了強大的支持。 本文將全面介紹 MQTTnet 的核心功能 ...
  • Serilog文檔翻譯系列（六） - 可用的接收器、增強器、格式化輸出
    Serilog支持多種接收器用於日誌存儲，增強器用於添加屬性，LogContext管理動態屬性，支持多種輸出格式包括純文本、JSON及ExpressionTemplate。還提供了自定義格式化選項，適用於不同需求。 ...
  • 警惕 Visual Studio 屬性求值副作用導致邏輯不符合預期
    目錄簡介獲取 HTML 文檔解析 HTML 文檔測試參考文章 簡介 動態內容網站使用 JavaScript 腳本動態檢索和渲染數據，爬取信息時需要模擬瀏覽器行為，否則獲取到的源碼基本是空的。 本文使用的爬取步驟如下： 使用 Selenium 獲取渲染後的 HTML 文檔 使用 HtmlAgility ...
  • [使用目前最新版]HybridCLR6.9.0+YooAsset2.2.4實現純C# Unity熱更新方案 (一)
    1.前言 什麼是熱更新 游戲或者軟體更新時，無需重新下載客戶端進行安裝，而是在應用程式啟動的情況下，在內部進行資源或者代碼更新 Unity目前常用熱更新解決方案 HybridCLR，Xlua，ILRuntime等 Unity目前常用資源管理解決方案 AssetBundles，Addressable， ...
  • 在 ASP.NET Core Web API 中使用操作篩選器統一處理通用操作
    本文章主要是在C# ASP.NET Core Web API框架實現向手機發送驗證碼簡訊功能。這裡我選擇是一個互億無線簡訊驗證碼平臺，其實像阿裡雲，騰訊雲上面也可以。 首先我們先去 互億無線 https://www.ihuyi.com/api/sms.html 去註冊一個賬號 註冊完成賬號後，它會送 ...
  • 第28篇 如何.net中實現高效可靠數據同步api
    通過以下方式可以高效，並保證數據同步的可靠性 1.API設計 使用RESTful設計，確保API端點明確，並使用適當的HTTP方法（如POST用於創建，PUT用於更新）。 設計清晰的請求和響應模型，以確保客戶端能夠理解預期格式。 2.數據驗證 在伺服器端進行嚴格的數據驗證，確保接收到的數據符合預期格 ...
所有分類