跳到主要內容

自己動手寫SQL執行引擎

自己動手寫SQL執行引擎


前言


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


整體結構


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

最終存儲結構當然是使用經典的B+樹結構。當然在B+樹和文件系統block塊之間的轉換則通過Buffer(Page) Manager來進行。當然了，為了完成事務，還必須要用WAL協議，其通過Log Manager來操作。
Freedom採用的是索引組織表，通過DruidSQL Parse來將sql翻譯為對應的索引操作符進而進行對應的語義操作。


MySQL Protocol結構


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


query packet


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


result set packet


mysql協議部分最複雜的內容是其對於result set的讀取，在NIO的方式下加重了複雜性。
Freedom通過設置一系列的讀取狀態可以比較好的在Netty框架下解決這一問題。


row packet


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

由於協議解析部分較為簡單，在這裏就不再贅述。
關注筆者公眾號，獲取更多乾貨文章


SQL Parse


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


對where的處理


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

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


對join的處理


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


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<=11 b.id and b.id>=19 b.id<=31

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

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

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


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


B+Tree的磁盤結構


leaf磁盤結構


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

一個元組(tuple/item)在一個page中分為定長的ItemPointer和不定長的Item兩部分。
其中ItemPointer裏面存儲了對應item的起始偏移和長度。同時ItemPointer和Item如圖所示是向著中心方向進行伸張，這種結構很有效的組織了非定長Item。


leaf和node節點在Page中的不同


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

其中在二級索引搜索時通過secondaryIndex通過index-key找到對應的clusterId,再通過
clusterId在clusterIndex中找到對應的row記錄。
由於要落盤，所以Freedom在node節點中的item裏面寫入了index-key對應的pageno,
這樣就可以容易的從磁盤恢復所有的索引結構了。


B+Tree在文件中的組織


有了Page結構，我們就可以將數據承載在一個個page大小的內存裏面，同時還可以將page刷新到對應的文件里。有了node.item中的pageno，我們就可以較容易的進行文件和內存結構之間的互相映射了。
B+樹在磁盤文件中的組織如下圖所示:

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

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


每個索引一個B+樹


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


B+Tree的測試


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


B+Tree的todo


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


Meta Data


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

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

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


事務支持


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


redo/undo log協議格式


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


WAL協議


WAL協議很好理解，就是在事務commit前將當前事務中所產生的的所有log記錄刷入磁盤。
Freedom自然也做了這個操作，使得可以在宕機后通過log恢復出所有的數據。


回滾的實現


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


宕機恢復


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的例子:

join查詢

delete回滾


Freedom todo


Freedom還有很多工作沒有完成，例如有層次的鎖機制和MVCC等，由於工作忙起來就耽擱了。
於是筆者就看了看MySQL源碼的實現理解了一下鎖和MVCC實現原理，並寫了兩篇博客。比起
自己動手擼實在是輕鬆太多了_。


MVCC


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


二階段鎖


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


尾聲


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


收穫與遺憾


這次造輪子的過程基本滿足了筆者的初衷，通過寫一個數據庫來學習數據庫。不僅僅是加深了理解，最重要的是筆者在寫的過程中終於明白了數據庫為什麼要這麼設計，為什麼不那樣設計，僅僅對書本的閱讀可能並不會有這些思考與領悟。
當然，還是有很多遺憾的，Freedom並沒有實現鎖機制和MVCC。由於只能在工作閑暇時間寫，所以斷斷續續寫了一兩個月，工作一忙就將這個項目閑置了。現在將Freedom的設計寫出來，希望大家能有所收穫。
更多乾貨，盡在解Bug之路:


github鏈接


https://github.com/alchemystar/Freedom

本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理

【其他文章推薦】



※廣告預算用在刀口上，台北網頁設計公司幫您達到更多曝光效益



※別再煩惱如何寫文案,掌握八大原則!



※教你寫出一流的銷售文案?



※超省錢租車方案



※廣告預算用在刀口上，台北網頁設計公司幫您達到更多曝光效益



※產品缺大量曝光嗎?你需要的是一流包裝設計!



Orignal From: 自己動手寫SQL執行引擎

留言

張貼留言

這個網誌中的熱門文章

架構設計 | 異步處理流程，多種實現模式詳解

本文源碼：GitHub·點這裏 || GitEE·點這裏 一、異步處理 1、異步概念 異步處理不用阻塞當前線程來等待處理完成，而是允許後續操作，直至其它線程將處理完成，並回調通知此線程。 必須強調一個基礎邏輯，異步是一種設計理念，異步操作不等於多線程，MQ中間件，或者消息廣播，這些是可以實現異步處理的方式。 同步處理和異步處理相對，需要實時處理並響應，一旦超過時間會結束會話，在該過程中調用方一直在等待響應方處理完成並返回。同步類似電話溝通，需要實時對話，異步則類似短信交流，發送消息之後無需保持等待狀態。 2、異步處理優點 雖然異步處理不能實時響應，但是處理複雜業務場景，多數情況都會使用異步處理。 異步可以解耦業務間的流程關聯，降低耦合度； 降低接口響應時間，例如用戶註冊，異步生成相關信息表； 異步可以提高系統性能，提升吞吐量； 流量削峰即把請求先承接下來，然後在異步處理； 異步用在不同服務間，可以隔離服務，避免雪崩； 異步處理的實現方式有很多種，常見多線程，消息中間件，發布訂閱的廣播模式，其根據邏輯在於先把請求承接下來，放入容器中，在從容器中把請求取出，統一調度處理。 注意 ：一定要監控任務是否產生積壓過度情況，任務如果積壓到雪崩之勢的地步，你會感覺每一片雪花都想勇闖天涯。 3、異步處理模式 異步流程處理的實現有好多方式，但是實際開發中常用的就那麼幾種，例如： 基於接口異步響應，常用在第三方對接流程； 基於消息生產和消費模式，解耦複雜流程； 基於發布和訂閱的廣播模式，常見系統通知 異步適用的業務場景，對數據強一致性的要求不高，異步處理的數據更多時候追求的是最終一致性。 二、接口響應異步 1、流程描述 基於接口異步響應的方式，有一個本地業務服務，第三方接口服務，流程如下： 本地服務發起請求，調用第三方服務接口； 請求包含業務參數，和成功或失敗的回調地址； 第三方服務實時響應流水號，作為該調用的標識； 之後第三方服務處理請求，得到最終處理結果； 如果處理成功，回調本地服務的成功通知接口； 如果處理失敗，回調本地服務的失敗通知接口； 整個流程基於部分異步和部分實時的模式，完整處理； 注意 ：如...
張貼留言
閱讀完整內容

.NET Core前後端分離快速開發框架(Core.3.0+AntdVue)

.NET Core前後端分離快速開發框架(Core.3.0+AntdVue) 目錄 引言 時間真快，轉眼今年又要過去了。回想今年，依次開源發布了 Colder.Fx.Net.AdminLTE(254Star) 、 Colder.Fx.Core.AdminLTE(335Star) 、 DotNettySocket(82Star) 、 IdHelper(47Star) ，這些框架及組件都是本着以實際出發，實事求是的態度，力求提高開發效率（我自己都是第一個使用者），目前來看反響不錯。但是隨着前端和後端技術的不斷變革，尤其是前端，目前大環境已經是前後端完全分離為主的開發模式，在這樣的大環境和必然趨勢之下，傳統的MVC就顯得有些落伍了。在這樣的背景下，一款前後端分離的.NET開發框架就顯得尤為必要，由此便定了框架的升級目標： 前後端分離 。 首先後端技術的選擇，從目前的數據來看，.NET Core的發展遠遠快於.NET Framework，最簡單的分析就是Colder.Fx.Core.AdminLTE發布比Colder.Fx.Net.AdminLTE晚，但是星星卻後來居上而且比前者多30%，並且這個差距在不斷擴大，由點及面的分析可以看出我們廣大.NET開發人員學習的熱情和积極向上的態度，並不是某些人所認為的那麼不堪（ 走自己的路，讓別人說去吧 ）。大環境上微軟积極擁抱開源，大力發展.NET Core， 可以說前途一片光明。因此後端決定採用 .NET Core3.0 ，不再浪費精力去支持.NET Framework。 然後是前端技術選擇，首選是三大js框架選擇，也是從實際出發，Vue相對其它而言更加容易上手，並且功能也毫不遜色，深得各種大小公司喜歡，如果偏要說缺點的話，那就是對TS支持不行，但是即將發布Vue3.0肯定會改變這一缺陷。選擇了Vue之後，然後就是UI框架的選擇了，這裏的選擇更多了，我選擇了Ant Design Vue，理由便是簡潔方便，十分符合我的設計理念。 技術選型完畢之後便...
張貼留言
閱讀完整內容

台北市住宅、社區建創儲能設備 最高可獲600萬元補助

為了推廣分散式發電，台北市環保局預計補助1億元供住宅社區設置創能、儲能設備，計有3種方案可供選擇。環保局說明，每案補助額度不超過建制總經費49％，社區每案最高可獲200萬至600萬元補助，住宅每案補助上限100萬元，5月1日起開放申請。 環保局說明，台北市溫室氣體排放量7成以上來自住商部門，其中以使用電力造成間接溫室氣體排放為大宗，台北市平均年用電量約159.86億度，1度電約等同排放0.5公斤二氧化碳，若想達成2050年淨零排放目標，僅靠節能減碳無法達成，必須發展綠色創能、儲能，並且參考歐洲、日本的做法，採分散式發電方式，推廣到社區、住家、商辦，達到供電自給自足目標。 因此，環保局推出「台北市住宅社區創能儲能及節能補助計畫」，補助對象為台北市轄內房屋所有權人及社區管理委員會，補助方案共計3種，每一申請人或每一場址僅能獲1次補助，每案補助額度不超過建置總經費49％為限，5月1日到7月31日開放申請，但補助經費用完即停止申請。 環保局說明，方案A補助對象以社區為主，公共區域申請創能儲能及節能項目，每案補助上限新台幣600萬元；方案B分為住宅或社區公共區域申請創能搭配儲能項目（創能或儲能方案不得單獨申請），社區每案補助上限新台幣400萬元，住宅每案補助上限100萬元。方案C補助對象也是社區，公共區域申請節能項目，每案補助上限新台幣200萬元。 網頁設計 最專業,超強功能平台可客製,窩窩以「數位行銷」「品牌經營」「網站與應用程式」「印刷品設計」等四大主軸，為每一位客戶客製建立行銷脈絡及洞燭市場先機,請問 台中電動車 哪裡在賣比較便宜可以到台中景泰電動車門市去看看總店：臺中市潭子區潭秀里雅潭路一段102-1號。 電動車補助 推薦評價好的 iphone維修 中心擁有專業的維修技術團隊，同時聘請資深iphone手機維修專家，現場說明手機問題，快速修理，沒修好不收錢住家的頂樓裝 太陽光電 聽說可發揮隔熱功效一線推薦東陽能源擁有核心技術、產品研發、系統規劃設置、專業團隊的太陽能發電廠商。 網頁設計 一頭霧水該從何著手呢? 回頭車 貨運收費標準宇安交通關係企業，自成立迄今，即秉持著「以誠待人」、「以實處事」的企業信念 台中搬家公司 教你幾個打包小技巧,輕鬆整理裝箱!還在煩惱搬家費用要多少哪？台中大展搬家線上試算搬家費用，從此不再擔心「物品怎麼計費」、「多...
張貼留言
閱讀完整內容