前言

在閱讀了大量關(guān)于數(shù)據(jù)庫(kù)的資料后，筆者情不自禁產(chǎn)生了一個(gè)造數(shù)據(jù)庫(kù)輪子的想法。來(lái)驗(yàn)證一下自己對(duì)于數(shù)據(jù)庫(kù)底層原理的掌握是否牢靠。在筆者的github中給這個(gè)database起名為Freedom。

整體結(jié)構(gòu)

既然造輪子，那當(dāng)然得從前端的網(wǎng)絡(luò)協(xié)議交互到后端的文件存儲(chǔ)全部給擼一遍。下面是Freedom實(shí)現(xiàn)的整體結(jié)構(gòu)，里面包含了實(shí)現(xiàn)的大致模塊:

最終存儲(chǔ)結(jié)構(gòu)當(dāng)然是使用經(jīng)典的B+樹(shù)結(jié)構(gòu)。當(dāng)然在B+樹(shù)和文件系統(tǒng)block塊之間的轉(zhuǎn)換則通過(guò)Buffer(Page) Manager來(lái)進(jìn)行。當(dāng)然了，為了完成事務(wù)，還必須要用WAL協(xié)議，其通過(guò)Log Manager來(lái)操作。
Freedom采用的是索引組織表，通過(guò)DruidSQL Parse來(lái)將sql翻譯為對(duì)應(yīng)的索引操作符進(jìn)而進(jìn)行對(duì)應(yīng)的語(yǔ)義操作。

MySQL Protocol結(jié)構(gòu)

client/server之間的交互采用的是MySQL協(xié)議，這樣很容易就可以和mysql client以及jdbc進(jìn)行交互了。

query packet

mysql通過(guò)3byte的定長(zhǎng)包頭去進(jìn)行分包，進(jìn)而解決tcp流的讀取問(wèn)題。再通過(guò)一個(gè)sequenceId來(lái)再應(yīng)用層判斷packet是否連續(xù)。

result set packet

mysql協(xié)議部分最復(fù)雜的內(nèi)容是其對(duì)于result set的讀取，在NIO的方式下加重了復(fù)雜性。
Freedom通過(guò)設(shè)置一系列的讀取狀態(tài)可以比較好的在Netty框架下解決這一問(wèn)題。

row packet

還有一個(gè)較簡(jiǎn)單的是對(duì)row格式進(jìn)行讀取，如上圖所示,只需要按部就班的解析即可。

由于協(xié)議解析部分較為簡(jiǎn)單，在這里就不再贅述。

SQL Parse

Freedom采用成熟好用的Druid SQL Parse作為解析器。事實(shí)上，解析sql就是將用文本表示
的sql語(yǔ)義表示為一系列操作符(這里限于篇幅原因，僅僅給出select中where過(guò)濾的原理)。

對(duì)where的處理

例如where后面的謂詞就可以表示為一系列的以樹(shù)狀結(jié)構(gòu)組織的SQL表達(dá)式，如下圖所示:

當(dāng)access層通過(guò)游標(biāo)提供一系列row后，就可以通過(guò)這個(gè)樹(shù)狀表達(dá)式來(lái)過(guò)濾出符合where要求的數(shù)據(jù)。Druid采用了Parse中常用的visitor很方便的處理上面的表達(dá)式計(jì)算操作。

對(duì)join的處理

對(duì)join最簡(jiǎn)單處理方案就是對(duì)兩張表進(jìn)行笛卡爾積，然后通過(guò)上面的where condition進(jìn)行過(guò)濾，如下圖所示:

Freedom對(duì)于縮小笛卡爾積的處理

由于Freedom采用的是B+樹(shù)作為底層存儲(chǔ)結(jié)構(gòu)，所以可以通過(guò)where謂詞來(lái)界定B+樹(shù)scan(搜索)的范圍(也即最大搜索key和最小搜索key在B+樹(shù)種中的位置)?？紤]sql

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

那么就可以界定出在id這個(gè)索引上,a的scan范圍為[3,11],如下圖所示:

b的scan范圍為[19,31],如下圖所示(假設(shè)兩張表數(shù)據(jù)一樣，便于繪圖):

scan少了從原來(lái)的15*15(一共15個(gè)元素)次循環(huán)減少到4*4次循環(huán),即循環(huán)次數(shù)減少到7.1%

當(dāng)然如果存在join condition的話，那么Freedom在底層cursor遞歸處理的過(guò)程中會(huì)預(yù)先過(guò)濾掉一部分?jǐn)?shù)據(jù)，進(jìn)一步減少上層的過(guò)濾。

B+Tree的磁盤(pán)結(jié)構(gòu)

leaf磁盤(pán)結(jié)構(gòu)

Freedom的B+Tree是存儲(chǔ)到磁盤(pán)里的?？紤]到存儲(chǔ)的限制以及不定長(zhǎng)的key值，所以會(huì)變得非常復(fù)雜。Freedom以page為單位來(lái)和磁盤(pán)進(jìn)行交互。葉子節(jié)點(diǎn)和非葉子節(jié)點(diǎn)都由page承載并刷入磁盤(pán)。結(jié)構(gòu)如下所示:

一個(gè)元組(tuple/item)在一個(gè)page中分為定長(zhǎng)的ItemPointer和不定長(zhǎng)的Item兩部分。
其中ItemPointer里面存儲(chǔ)了對(duì)應(yīng)item的起始偏移和長(zhǎng)度。同時(shí)ItemPointer和Item如圖所示是向著中心方向進(jìn)行伸張，這種結(jié)構(gòu)很有效的組織了非定長(zhǎng)Item。

leaf和node節(jié)點(diǎn)在Page中的不同

雖然leaf和node在page中組織結(jié)構(gòu)一致，但其item包含的項(xiàng)確有區(qū)別。由于Freedom采用的是索引組織表，所以對(duì)于leaf在聚簇索引(clusterIndex)和二級(jí)索引(secondaryIndex)中對(duì)item的表示也有區(qū)別,如下圖所示:

其中在二級(jí)索引搜索時(shí)通過(guò)secondaryIndex通過(guò)index-key找到對(duì)應(yīng)的clusterId,再通過(guò)
clusterId在clusterIndex中找到對(duì)應(yīng)的row記錄。
由于要落盤(pán)，所以Freedom在node節(jié)點(diǎn)中的item里面寫(xiě)入了index-key對(duì)應(yīng)的pageno,
這樣就可以容易的從磁盤(pán)恢復(fù)所有的索引結(jié)構(gòu)了。

B+Tree在文件中的組織

有了Page結(jié)構(gòu)，我們就可以將數(shù)據(jù)承載在一個(gè)個(gè)page大小的內(nèi)存里面，同時(shí)還可以將page刷新到對(duì)應(yīng)的文件里。有了node.item中的pageno，我們就可以較容易的進(jìn)行文件和內(nèi)存結(jié)構(gòu)之間的互相映射了。
B+樹(shù)在磁盤(pán)文件中的組織如下圖所示:

B+樹(shù)在內(nèi)存中相對(duì)應(yīng)的映射結(jié)構(gòu)如下圖所示:

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

每個(gè)索引一個(gè)B+樹(shù)

在Freedom中，每個(gè)索引都是一顆B+樹(shù)，對(duì)記錄的插入和修改都要對(duì)所有的B+樹(shù)進(jìn)行操作。

B+Tree的測(cè)試

筆者通過(guò)一系列測(cè)試case,例如隨機(jī)變長(zhǎng)記錄對(duì)B+樹(shù)進(jìn)行插入并落盤(pán)，修復(fù)了其中若干個(gè)非常詭異的corner case。

B+Tree的todo

筆者這里只是完成了最簡(jiǎn)單的B+樹(shù)結(jié)構(gòu)，沒(méi)有給其添加并發(fā)修改的鎖機(jī)制，也沒(méi)有在B+樹(shù)做操作的時(shí)候記錄log來(lái)保證B+樹(shù)在宕機(jī)等災(zāi)難性情況下的一致性,所以就算完成了這么多的工作量，距離一個(gè)高并發(fā)高可用的bptree還有非常大的距離。

Meta Data

table的元信息由create table所創(chuàng)建。創(chuàng)建之后會(huì)將元信息落盤(pán)，以便Freedom在重啟的時(shí)候加載表信息。每張表的元信息只占用一頁(yè)的空間，依舊復(fù)用page結(jié)構(gòu)，主要保存的是聚簇索引和二級(jí)索引的信息。元信息對(duì)應(yīng)的Item如下圖所示:

如果想讓mybatis可以自動(dòng)生成關(guān)于Freedom的代碼，還需實(shí)現(xiàn)一些特定的sql來(lái)展現(xiàn)Freedom的元信息。這個(gè)在筆者另一個(gè)項(xiàng)目rider中有這樣的實(shí)現(xiàn)。原理如下圖所示:

實(shí)現(xiàn)了上述4類(lèi)SQL之后，mybatis-generator就可以通過(guò)jdbc從Freedom獲取元信息進(jìn)而自動(dòng)生成代碼了。

事務(wù)支持

由于當(dāng)前Freedom并沒(méi)有保證并發(fā)，所以對(duì)于事務(wù)的支持只做了最簡(jiǎn)單的WAL協(xié)議。通過(guò)記錄redo/undolog從而實(shí)現(xiàn)原子性。

redo/undo log協(xié)議格式

Freedom在每做一個(gè)修改操作時(shí)，都會(huì)生成一條日志，其中記錄了修改前(undo)和修改后(redo)的行信息，undo用來(lái)回滾,redo用來(lái)宕機(jī)recover。結(jié)構(gòu)如下圖所示:

WAL協(xié)議

WAL協(xié)議很好理解，就是在事務(wù)commit前將當(dāng)前事務(wù)中所產(chǎn)生的的所有l(wèi)og記錄刷入磁盤(pán)。
Freedom自然也做了這個(gè)操作，使得可以在宕機(jī)后通過(guò)log恢復(fù)出所有的數(shù)據(jù)。

回滾的實(shí)現(xiàn)

由于日志中記錄了undo，所以對(duì)于一個(gè)事務(wù)的回滾直接通過(guò)日志進(jìn)行undo即可。如下圖所示:

宕機(jī)恢復(fù)

Freedom如果在page全部刷盤(pán)之后關(guān)機(jī)，則可以由通過(guò)加載page的方式獲取原來(lái)的數(shù)據(jù)。
但如果突然宕機(jī),例如kill -9之后，則可以通過(guò)WAL協(xié)議中記錄的redo/undo log來(lái)重新
恢復(fù)所有的數(shù)據(jù)。由于時(shí)間和精力所限，筆者并沒(méi)有實(shí)現(xiàn)基于LSN的檢查點(diǎn)機(jī)制。

Freedom運(yùn)行

git clone https://github.com/alchemystar/Freedom.git

// 并沒(méi)有做打包部署的工作，所以最簡(jiǎn)單的方法是在java編輯器里面

run alchemystar.freedom.engine.server.main

以下是筆者實(shí)際運(yùn)行Freedom的例子:

join查詢(xún)

delete回滾

尾聲

在造輪子的過(guò)程中一開(kāi)始是非常有激情非?？鞓?lè)的。但隨著系統(tǒng)越來(lái)越龐大，復(fù)雜性越來(lái)越高，進(jìn)度就會(huì)越來(lái)越慢，還時(shí)不時(shí)要推翻自己原來(lái)的設(shè)想并重新設(shè)計(jì)，然后再協(xié)同修改關(guān)聯(lián)的所有代碼，就如同泥沼，越陷越深。至此，筆者才領(lǐng)悟了軟件工程最重要的其實(shí)是控制復(fù)雜度！始終保持簡(jiǎn)潔的接口和優(yōu)雅的設(shè)計(jì)是實(shí)現(xiàn)一個(gè)大型系統(tǒng)的必要條件。

github鏈接：https://github.com/alchemystar/Freedom

以上就是如何自己動(dòng)手寫(xiě)SQL執(zhí)行引擎的詳細(xì)內(nèi)容，更多關(guān)于自己動(dòng)手寫(xiě)SQL執(zhí)行引擎的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！