minibend ，一個從零開始、使用 Rust 構(gòu)建的查詢引擎。這里是 minibend 系列技術(shù)主題分享的第一期，來自 @PsiACE[1] 。

前排指路視頻和 PPT 地址 視頻

嗶哩嗶哩：https://www.bilibili.com/video/BV1Ne4y1x7C

PPT：https://psiace.github.io/databend-internals/minibend/ppt/minibend-001-basic-intro.pdf

minibend:what,why,how

minibend 是什么

minibend 是一款從零開始、使用 Rust 構(gòu)建的查詢引擎。查詢引擎是數(shù)據(jù)庫系統(tǒng)的一個重要組件，需要具備以下幾點能力：

• 訪問數(shù)據(jù)

• 提供查詢接口

• 返回查詢結(jié)果

通常我們會使用 SQL 也就是結(jié)構(gòu)化查詢語言進行交互。minibend 同時也是 Databend Internals，或者說 Databend 內(nèi)幕大揭秘 這個手冊的實戰(zhàn)部分。Databend 內(nèi)幕大揭秘 將會透過 Databend 的設計與實現(xiàn)，為你揭開面向云架構(gòu)的現(xiàn)代數(shù)據(jù)庫的面紗。

為什么要設計 minibend

特別是在團隊已經(jīng)孵化出 Databend[2] 這個現(xiàn)代開源云數(shù)倉的前提下，為什么還需要這樣一個項目？先回到 Databend 內(nèi)幕大揭秘 的初衷，設立這個項目是為了吸引更多人參與到 Databend 的學習、開發(fā)和生態(tài)建設中，所以目標受眾定位在：

• 高校計算機專業(yè)的學生。

• 想從事數(shù)據(jù)庫研發(fā)的開發(fā)者。

• 對數(shù)據(jù)庫整體運作原理感興趣的朋友。

但是，Databend 的更新迭代速度、代碼量都意味著對剛開始接觸 Rust 并嘗試參與研發(fā)的新朋友會面臨一個比較高的門檻。從現(xiàn)存的教程上看，或多或少存在一些問題：

• 不是 Rust 實現(xiàn)（切換語言和生態(tài)需要一些努力）

• 缺乏 step by step 的體驗（細節(jié)上需要更深入和艱苦的挖掘）

• 從設計思想到實現(xiàn)邏輯上可能與 Databend 有比較明顯的差異（存算分離、面向云，這些可能都會有一些抉擇）。

所以開啟一個新的項目作為連接新開發(fā)者和 Databend 之間的紐帶就成為一種自然的選擇。

P.S. minibend 致力于解決這些問題，但可能很難完全解決，但至少，先開始運作起來。

minibend 這個項目計劃怎樣進行

首先，minibend 會提供視頻、文章和代碼三種材料。文章和代碼將會同步到 Databend 內(nèi)幕大揭秘 的 Repo 中，而視頻則會發(fā)布到 Databend 的 B 站官方帳號下。歡迎大家持續(xù)關注。

Databend 內(nèi)幕大揭秘：https://psiace.github.io/databend-internals/Databend（嗶哩嗶哩）：https://space.bilibili.com/275673537

更新頻率大概是每個月一到兩期。內(nèi)容上會包含必要的相關知識導讀、設計和實現(xiàn)相關的說明、并進行回顧和展望。當然，也會不定期精選一部分論文摘要供大家進一步研討和學習。

數(shù)據(jù)庫基礎概念

在這個部分，我們不會深入數(shù)據(jù)庫的細節(jié)，只是從部分組件的視角上進行觀察。

存儲

存儲解決的是兩個問題，存在哪以及怎么存 。

對于“怎么存”，不同背景的朋友可能會考慮到一些不同的細節(jié)，但大多數(shù)時候，可以想象到一個基本的模式是：數(shù)據(jù)以特定格式寫入到某幾類文件中，比如 Parquet 甚至 CSV 。但是“存在哪”呢？

過去的一些存儲方案更加關注上圖所示的存儲體系結(jié)構(gòu)，將需要在線處理的數(shù)據(jù)存放在閃存和硬盤中，用于備份的數(shù)據(jù)放入光盤和磁帶。云存儲的興起和網(wǎng)絡帶寬的不斷提高帶來了一些新的變化：云存儲能夠支持遠程保存數(shù)據(jù)和文件，并通過網(wǎng)絡連接進行訪問。不僅可以節(jié)約拓展物理器件所帶來的人力物力消耗，并能夠提供更好的彈性以便于即時增減容量，還支持按需按量付費從而做到更好的成本管理與控制。Databend 早期的實現(xiàn)是包含一套分布式文件系統(tǒng)的，但到現(xiàn)在，存儲的重心完全轉(zhuǎn)移到云廠商提供（AWS S3, Azure Blob 等）或者自托管（MinIO 等）的云存儲之上。盡管云存儲越來越重要，但原有的經(jīng)驗和見解依然有效，我們?nèi)匀豢梢允褂镁彺婧筒⑿屑夹g(shù)來改善性能，利用冗余來提高可靠性。

索引

引入索引的好處在于加快數(shù)據(jù)查詢的速度，而缺點則在于構(gòu)建和維護索引同樣需要付出代價。

不同的索引可以針對不同的場景提供優(yōu)化，B Tree 能夠加速范圍查詢，而等值查詢就可以使用 Hash 索引，BitMap（或者說更常用的 Bloom 索引）可以方便判斷數(shù)據(jù)是否存在。Databend 的索引無需人為創(chuàng)建，由部署的實例自行維護。同時也采用了像 Xor 索引[3]?這樣的新技術(shù)來進一步加速查詢并提高空間利用率。

查詢執(zhí)行

盡管有各種各樣的查詢引擎，但具體到查詢執(zhí)行的環(huán)節(jié)大同小異，這里以 Databend 為例，簡單講一下過程。

1. 解析 SQL 語法，形成 AST（抽象語法樹）。

2. 通過 Binder 對其進行語義分析，并且生成一個初始的 Logical Plan（邏輯計劃）。

3. 得到初始的 Logical Plan 后，優(yōu)化器會對其進行改寫和優(yōu)化，最終生成一個可執(zhí)行的 Physical Plan 。

4. 通過 Optimizer 生成 Physical Plan 后，將其翻譯成可執(zhí)行的 Pipeline 。

5. Pipeline 則會交由 Processor 執(zhí)行框架進行計算。

那么近年來新興數(shù)據(jù)庫大多受到 Morsel-Driven Parallelism 這篇論文的啟發(fā)，在運行時確定任務的并行度，按流水線的方式執(zhí)行操作，并通過調(diào)度策略來盡量保證數(shù)據(jù)的本地化，在實現(xiàn) load banlance 的同時最小化跨域數(shù)據(jù)訪問。同時，引入列式存儲和向量化執(zhí)行的技術(shù)，可以避免不必要的緩存和 I/O 資源浪費，同時，節(jié)約處理數(shù)據(jù)時需要傳遞的數(shù)據(jù)量，為進一步優(yōu)化提供更多空間。

查詢優(yōu)化

查詢執(zhí)行的路徑并非一成不變，不同的執(zhí)行計劃在不同場景下性能也存在差異，如何為查詢選擇合適的計劃就是查詢優(yōu)化需要關注的內(nèi)容。

• 更快的速度（更低的延遲）。

• 在 OLTP 場景下，則更強調(diào)性價比。

• 而對于 OLAP 場景，則追求更的高吞吐量。

下面的圖片展現(xiàn)的是一種典型的查詢優(yōu)化，對 JOIN 進行重排。

目前有兩種主要的查詢優(yōu)化方案，一種是基于關系代數(shù)和算法的等價優(yōu)化方案，一種是基于評估成本的優(yōu)化方案。根據(jù)命名，不難看出優(yōu)化的靈感來源和這兩種方案在優(yōu)化上的取舍。那么如何進行查詢優(yōu)化呢？查詢優(yōu)化通常包含以下四個步驟：

• 構(gòu)建框架來列舉可能的計劃

• 編寫轉(zhuǎn)換規(guī)則

• 引入成本模型來評估不同的計劃

• 選擇最理想的計劃

Databend 引入了基于規(guī)則的 Cascades 優(yōu)化器[4]，通過自頂向下探索、模式匹配以及記憶化來提供更好的查詢優(yōu)化能力。

大規(guī)模并行處理

大規(guī)模并行處理是大數(shù)據(jù)計算引擎的一個重要特性，可以提供高吞吐、低時延的計算能力。那么，當我們在討論大規(guī)模并行處理時，究竟在討論什么？

大規(guī)模并行處理（MPP，Massively Parallel Processing）意味著可以由多個計算節(jié)點（處理器）協(xié)同處理程序的不同部分，而每個計算節(jié)點都可能具備獨立的系統(tǒng)資源（磁盤、內(nèi)存、操作系統(tǒng)）。計算節(jié)點將工作拆分成易于管理、調(diào)度和執(zhí)行的任務執(zhí)行，通過添加額外的計算節(jié)點可以完成水平拓展。隨著計算節(jié)點數(shù)目的增加，對數(shù)據(jù)的查詢處理速度就越快，從而減少大數(shù)據(jù)集上處理復雜查詢所需的時間。在近些年，MPP 和分布式設計往往會同時出現(xiàn)在同一套系統(tǒng)中。

分布式

從某種視角上看，分布式系統(tǒng)與 MPP 系統(tǒng)有著驚人的相似。比如：通過網(wǎng)絡連接、對外作為整體提供服務、計算節(jié)點擁有資源等。但是這兩種架構(gòu)仍然會有一些不同。

• 從設計目標上看，分布式系統(tǒng)致力于改善系統(tǒng)的可靠性和可用性，而 MPP 系統(tǒng)需要充分利用計算節(jié)點的并行能力從而提高整體性能。

• 具體到實現(xiàn)上，分布式系統(tǒng)降低了對網(wǎng)絡的需求，采用局域網(wǎng)或廣域網(wǎng)相連，拓展性進一步增強。而 MPP 系統(tǒng)為了充分利用計算節(jié)點的處理能力，依賴高速網(wǎng)絡進行通訊。

• 同時，由于節(jié)點地位不同，分布式系統(tǒng)除了協(xié)同執(zhí)行任務之外，還具有自治執(zhí)行任務的能力；而 MPP 系統(tǒng)則專注于任務的協(xié)同執(zhí)行。

Rust?不完全指南

剛剛介紹了數(shù)據(jù)庫相關的一些基本概念，現(xiàn)在讓我們將目光轉(zhuǎn)向 Rust ，來一同了解這個正在走向流行的編程語言。

The Rust Programming Language

Rust 官方宣傳語是：Rust 是一門賦予每個人構(gòu)建可靠且高效軟件能力的語言，現(xiàn)在距離它第一個版本發(fā)布也已經(jīng)過去10年。Rust 沒有運行時和垃圾回收，速度快且內(nèi)存利用率高，幾乎可以與 C 和 C++ 競爭。Rust 的類型系統(tǒng)和所有權(quán)模型為內(nèi)存安全和線程安全提供保障，在編譯期就能夠消除各種各樣的錯誤。特別值得一提的是，Rust 工具鏈內(nèi)置很多實用工具，可以切實改善生產(chǎn)力：包管理器、構(gòu)建工具、格式化程序、用于代碼審計的 Clippy 等等。

函數(shù)

上面函數(shù)是兩個 32 位整數(shù)相加，返回值也是一個 32 位整數(shù)。值得注意的是，我們需要標注返回值類型，而函數(shù)體中的 x + y 是一種隱式返回，所以不需要添加 return 關鍵字，當然，也不需要在末尾添加分號。只添加末尾分號的話，則會將其視為普通語句執(zhí)行，就沒有返回值了（報錯）。

經(jīng)典的 Hello World 程序，大家應該會感覺到熟悉。main 函數(shù)也是 Rust 程序的入口點。通過調(diào)用 println! 這個宏，可以輸出文本到終端。

類型

除了基本的字符串、整數(shù)、浮點數(shù)、布爾類型之外，Rust 還支持結(jié)構(gòu)體和枚舉類型，代碼片段提供了一個基本的例子。為這些類型可以實現(xiàn)特定的方法，以支持各種各樣的操作，通用的接口可以使用 trait 關鍵字進行定義。

模式匹配

模式是 Rust 中特殊的語法，它用來匹配類型中的結(jié)構(gòu)，看起來有點像 switch，但要更加強大和簡潔。無論類型是簡單還是復雜，結(jié)合使用模式和 match 表達式以及其他結(jié)構(gòu)可以提供更多對程序控制流的支配權(quán)。通過將一些值與模式相比較來使用它。如果模式匹配這些值，就可以對值的部分進行相應處理。

控制流

上面是一些常見的控制流語法，for 循環(huán)和范圍迭代看起來和其他語言很相似；而通過 let - if 語句，可以輕松將 if 當作表達式來使用；當然，Rust 同樣支持 while 循環(huán)和無限 loop 循環(huán)。

內(nèi)存安全與指針

Owned Pointer，一次只能有一個對象“擁有”此指針，這意味著當 Box 離開其作用域時，它可以安全地自動釋放。

Reference – 引用其他數(shù)據(jù)的不可變指針。當引用某個值時，我們稱該值已被 “借用” 。當一個值被不可變借用時，它不能被修改或移動。借用直到在最后一次使用借用變量之前會一直處于活躍狀態(tài)。

可變引用，如果你有一個對該變量的可變引用，你就不能再創(chuàng)建對該變量的引用。

上面的這些 Rust 片段節(jié)選自 ?Learn X in Y minutes[5] ，只進行了一些粗淺的介紹。如果想要進一步學習，建議查閱以下資料：

• ?The Rust Programming Language[6] 。

• Databend 早期關于 Rust 的系列視頻。

• Rust 新手入門系列課程[7]

• Rust 培養(yǎng)提高計劃[8]

前進四：回顧和展望

回顧

首先我們介紹了 minibend 這個系列課程，一方面，這會是一個從零開始、使用 Rust 構(gòu)建的查詢引擎；另一方面，它會參考 Databend 的設計，并致力于降低數(shù)據(jù)庫內(nèi)核開發(fā)的門檻。而在數(shù)據(jù)庫相關基礎知識的部分，云存儲為現(xiàn)代數(shù)據(jù)庫設計帶來了一些新變化，而不同的索引又可以為不同的查詢場景帶來性能優(yōu)化，接著是查詢執(zhí)行和查詢優(yōu)化的相關知識，以及對大規(guī)模并行處理和分布式技術(shù)的介紹。Rust 不完全指南里，從函數(shù)、類型、模式匹配、控制流、內(nèi)存安全與指針進行了一個簡單的介紹，為閱讀 Rust 代碼提供了一個簡單的基礎。

展望

下一期，我們將會介紹 Apache Arrow - 一種列式存儲的內(nèi)存格式規(guī)范，以及查詢引擎中的類型系統(tǒng)，然后試著寫一些關于數(shù)據(jù)源的代碼。

閱讀材料

本期課程推薦兩本書給大家：一本是 The Rust Programming Language[9]? ，這是 rust 官方出品的 Rust 書籍，一般被稱作 the book 。另一本是 How Query Engines Work[10] ，Andy 同時也是 Datafusion 和 Ballista 的作者，不過這本書使用的是 kotlin 。

引用鏈接

[1]?@PsiACE:?https://github.com/psiace
[2]?Databend:?https://github.com/datafuselabs/databend
[3]?Xor 索引:?https://arxiv.org/abs/1912.08258
[4]?Cascades 優(yōu)化器:?https://15721.courses.cs.cmu.edu/spring2018/papers/15-optimizer1/graefe-ieee1995.pdf
[5]?Learn X in Y minutes:?https://learnxinyminutes.com/docs/rust/
[6]?The Rust Programming Language:?https://doc.rust-lang.org/book/
[7]?Rust 新手入門系列課程:?https://space.bilibili.com/275673537/channel/collectiondetail?sid=87507
[8]?Rust 培養(yǎng)提高計劃:?https://space.bilibili.com/275673537/channel/seriesdetail?sid=488491
[9]?The Rust Programming Language:?https://doc.rust-lang.org/book/
[10]?How Query Engines Work:?https://leanpub.com/how-query-engines-work

關于 Databend

Databend 是一款開源、彈性、低成本，基于對象存儲也可以做實時分析的新式數(shù)倉。期待您的關注，一起探索云原生數(shù)倉解決方案，打造新一代開源 Data Cloud。

• Databend 文檔：https://databend.rs/

• Twitter：https://twitter.com/Datafuse_Labs

• Slack：https://datafusecloud.slack.com/

• Wechat：Databend

• GitHub ：https://github.com/datafuselabs/databend