Categories
程式開發

自己動手寫SQL執行引擎


自己動手寫SQL執行引擎

前言

在閱讀了大量關於數據庫的資料後,筆者情不自禁產生了一個造數據庫輪子的想法。來驗證一下自己對於數據庫底層原理的掌握是否牢靠。在筆者的github中給這個database起名為Freedom。

整體結構

既然造輪子,那當然得從前端的網絡協議交互到後端的文件存儲全部給擼一遍。下面是Freedom實現的整體結構,裡麵包含了實現的大致模塊:

自己動手寫SQL執行引擎 1

最終存儲結構當然是使用經典的B+樹結構。當然在B+樹和文件系統block塊之間的轉換則通過Buffer(Page) Manager來進行。當然了,為了完成事務,還必須要用WAL協議,其通過Log Manager來操作。

Freedom採用的是索引組織表,通過DruidSQL Parse來將sql翻譯為對應的索引操作符進而進行對應的語義操作。

MySQL Protocol結構

client/server之間的交互採用的是MySQL協議,這樣很容易就可以和mysql client以及jdbc進行交互了。

查詢包

mysql通過3byte的定長包頭去進行分包,進而解決tcp流的讀取問題。再通過一個sequenceId來再應用層判斷packet是否連續。

自己動手寫SQL執行引擎 2

結果集包

mysql協議部分最複雜的內容是其對於result set的讀取,在NIO的方式下加重了複雜性。

Freedom通過設置一系列的讀取狀態可以比較好的在Netty框架下解決這一問題。

自己動手寫SQL執行引擎 3

行包

還有一個較簡單的是對row格式進行讀取,如上圖所示,只需要按部就班的解析即可。

自己動手寫SQL執行引擎 4

由於協議解析部分較為簡單,在這裡就不再贅述。

SQL解析

Freedom採用成熟好用的Druid SQL Parse作為解析器。事實上,解析sql就是將用文本表示

的sql語義表示為一系列操作符(這裡限於篇幅原因,僅僅給出select中where過濾的原理)。

對where的處理

例如where後面的謂詞就可以表示為一系列的以樹狀結構組織的SQL表達式,如下圖所示:

自己動手寫SQL執行引擎 5

當access層通過游標提供一系列row後,就可以通過這個樹狀表達式來過濾出符合where要求的數據。 Druid採用了Parse中常用的visitor很方便的處理上面的表達式計算操作。

對join的處理

對join最簡單處理方案就是對兩張表進行笛卡爾積,然後通過上面的where condition進行過濾,如下圖所示:

自己動手寫SQL執行引擎 6

Freedom對於縮小笛卡爾積的處理

由於Freedom採用的是B+樹作為底層存儲結構,所以可以通過where謂詞來界定B+樹scan(搜索)的範圍(也即最大搜索key和最小搜索key在B+樹種中的位置)。考慮sql

select a.*,b.* from t_archer as a join t_rider as b where a.id>=3 and a.id=19 b.id<=31

那麼就可以界定出在id這個索引上,a的scan範圍為[3,11],如下圖所示:

自己動手寫SQL執行引擎 7

b的scan範圍為[19,31],如下圖所示(假設兩張表數據一樣,便於繪圖):

自己動手寫SQL執行引擎 8

scan少了從原來的15*15(一共15個元素)次循環減少到4*4次循環,即循環次數減少到7.1%

當然如果存在join condition的話,那麼Freedom在底層cursor遞歸處理的過程中會預先過濾掉一部分數據,進一步減少上層的過濾。

B+Tree的磁盤結構

leaf磁盤結構

Freedom的B+Tree是存儲到磁盤裡的。考慮到存儲的限制以及不定長的key值,所以會變得非常複雜。 Freedom以page為單位來和磁盤進行交互。葉子節點和非葉子節點都由page承載並刷入磁盤。結構如下所示:

自己動手寫SQL執行引擎 9

一個元組(tuple/item)在一個page中分為定長的ItemPointer和不定長的Item兩部分。

其中ItemPointer裡面存儲了對應item的起始偏移和長度。同時ItemPointer和Item如圖所示是向著中心方向進行伸張,這種結構很有效的組織了非定長Item。

leaf和node節點在Page中的不同

雖然leaf和node在page中組織結構一致,但其item包含的項確有區別。由於Freedom採用的是索引組織表,所以對於leaf在聚簇索引(clusterIndex)和二級索引(secondaryIndex)中對item的表示也有區別,如下圖所示:

自己動手寫SQL執行引擎 10

其中在二級索引搜索時通過secondaryIndex通過index-key找到對應的clusterId,再通過

clusterId在clusterIndex中找到對應的row記錄。

由於要落盤,所以Freedom在node節點中的item裡面寫入了index-key對應的pageno,

這樣就可以容易的從磁盤恢復所有的索引結構了。

B+Tree在文件中的組織

有了Page結構,我們就可以將數據承載在一個個page大小的內存裡面,同時還可以將page刷新到對應的文件裡。有了node.item中的pageno,我們就可以較容易的進行文件和內存結構之間的互相映射了。

B+樹在磁盤文件中的組織如下圖所示:

自己動手寫SQL執行引擎 11

B+樹在內存中相對應的映射結構如下圖所示:

自己動手寫SQL執行引擎 12

文件page和內存page中的內容基本是一致的,除了一些內存page中特有的字段,例如dirty等。

每個索引一個B+樹

在Freedom中,每個索引都是一顆B+樹,對記錄的插入和修改都要對所有的B+樹進行操作。

B+Tree的測試

筆者通過一系列測試case,例如隨機變長記錄對B+樹進行插入並落盤,修復了其中若干個非常詭異的corner case。

B +樹形待辦事項

筆者這裡只是完成了最簡單的B+樹結構,沒有給其添加並發修改的鎖機制,也沒有在B+樹做操作的時候記錄log來保證B+樹在宕機等災難性情況下的一致性,所以就算完成了這麼多的工作量,距離一個高並發高可用的bptree還有非常大的距離。

元數據

table的元信息由create table所創建。創建之後會將元信息落盤,以便Freedom在重啟的時候加載表信息。每張表的元信息只佔用一頁的空間,依舊復用page結構,主要保存的是聚簇索引和二級索引的信息。元信息對應的Item如下圖所示:

自己動手寫SQL執行引擎 13

如果想讓mybatis可以自動生成關於Freedom的代碼,還需實現一些特定的sql來展現Freedom的元信息。這個在筆者另一個項目rider中有這樣的實現。原理如下圖所示:

自己動手寫SQL執行引擎 14

實現了上述4類SQL之後,mybatis-generator就可以通過jdbc從Freedom獲取元信息進而自動生成代碼了。

事務支持

由於當前Freedom並沒有保證並發,所以對於事務的支持只做了最簡單的WAL協議。通過記錄redo/undolog從而實現原子性。

redo/undo log協議格式

Freedom在每做一個修改操作時,都會生成一條日誌,其中記錄了修改前(undo)和修改後(redo)的行信息,undo用來回滾,redo用來宕機recover。結構如下圖所示:

自己動手寫SQL執行引擎 15

WAL協議

WAL協議很好理解,就是在事務commit前將當前事務中所產生的的所有log記錄刷入磁盤。

Freedom自然也做了這個操作,使得可以在宕機後通過log恢復出所有的數據。

自己動手寫SQL執行引擎 16

回滾的實現

由於日誌中記錄了undo,所以對於一個事務的回滾直接通過日誌進行undo即可。如下圖所示:

自己動手寫SQL執行引擎 17

宕機恢復

Freedom如果在page全部刷盤之後關機,則可以由通過加載page的方式獲取原來的數據。

但如果突然宕機,例如kill -9之後,則可以通過WAL協議中記錄的redo/undo log來重新

恢復所有的數據。由於時間和精力所限,筆者並沒有實現基於LSN的檢查點機制。

Freedom運行

git clone https://github.com/alchemystar/Freedom.git
// 并没有做打包部署的工作,所以最简单的方法是在java编辑器里面
run alchemystar.freedom.engine.server.main

以下是筆者實際運行Freedom的例子:

自己動手寫SQL執行引擎 18

join查詢

自己動手寫SQL執行引擎 19

delete回滾

自己動手寫SQL執行引擎 20

一切都自由

Freedom還有很多工作沒有完成,例如有層次的鎖機制和MVCC等,由於工作忙起來就耽擱了。

於是筆者就看了看MySQL源碼的實現理解了一下鎖和MVCC實現原理,並寫了兩篇博客。比起

自己動手擼實在是輕鬆太多了^_^。

MVCC

https://my.oschina.net/alchemystar/blog/1927425

二階段鎖

https://my.oschina.net/alchemystar/blog/1438839

尾聲

在造輪子的過程中一開始是非常有激情非常快樂的。但隨著系統越來越龐大,複雜性越來越高,進度就會越來越慢,還時不時要推翻自己原來的設想並重新設計,然後再協同修改關聯的所有代碼,就如同泥沼,越陷越深。至此,筆者才領悟了軟件工程最重要的其實是控制複雜度!始終保持簡潔的接口和優雅的設計是實現一個大型系統的必要條件。

收穫與遺憾

這次造輪子的過程基本滿足了筆者的初衷,通過寫一個數據庫來學習數據庫。不僅僅是加深了理解,最重要的是筆者在寫的過程中終於明白了數據庫為什麼要這麼設計,為什麼不那樣設計,僅僅對書本的閱讀可能並不會有這些思考與領悟。

當然,還是有很多遺憾的,Freedom並沒有實現鎖機制和MVCC。由於只能在工作閒暇時間寫,所以斷斷續續寫了一兩個月,工作一忙就將這個項目閒置了。現在將Freedom的設計寫出來,希望大家能有所收穫。

自己動手寫SQL執行引擎 21

github鏈接

https://github.com/alchemystar/Freedom