Categories
程式開發

數據庫內核雜談(一):一小時實現一個基本功能的數據庫


數據庫內核博大精深,很多子系統的設計初看不知所云,但是細讀就會發現其已經做到了極致。但是市面上很少有類似的資源或者課程把數據庫內容的精髓講解出來,因此Facebook 現任 Tech Lead 顧仲賢撰寫了《數據庫內核雜談》的系列文章。

開篇詞

為啥想寫這樣一個系列?

最主要的原因肯定是出於興趣吧,自從接觸了數據庫內核開發,覺得里面真的是博大精深,很多子系統的設計初看不知所云,細讀就發現已經做到了極致。然後特別希望有大牛能夠深入淺出地把這些精髓講解出來。但可惜,一直沒有發現類似的資源或者課程(筆者雖然工作多年,但自覺還是比較注重積累,每天都關注科技新聞,技術博客甚至領域內的新的學術文章)。近期也看到有越來越多的付費培訓,從算法到系統設計,到大數據,應有盡有,但唯獨沒有發現非常好的關於數據庫內核設計的資源。自己當然沒有實力可以去開那樣一門課程,但我希望可以通過寫blog來完善自己的知識儲備。也希望讀者能有所收穫。不過想歸想,自己從來沒下定決心去做這樣一件事,因為總是覺得自己積累還不夠,還要準備準備云云。

什麼契機讓你真正去行動了?

這契機真的是一個非常偶然的故事。上個週末的一天晚上,小葡萄(我最愛且僅愛的老婆大人)正在給我洗臉。感覺閒著也是閒著,加之正好下午剛討論過SQL,我就半開玩笑地說,“老婆,你不是對數據庫感興趣嗎?我給你講講數據庫是怎麼實現的,數據庫是怎麼去執行一個SQL語句的” 小葡萄:“你說呀,你能說得出來嗎?”;“嘿,小看我,你聽著哦。。。” 然後我就blahblah地講了大半個小時,用盡量通俗易懂的語言給老婆描述了數據庫最初是怎麼起源的;怎麼去實現最基本的存儲;有了存儲,怎麼去實現基本的數據讀取;有了讀取怎麼去實現基本的數據操作,等等。聽完,小葡萄真的是突然有種對我肅然起敬地感覺(極有可能是我自己的一廂情願)。也正是小葡萄的支持,我決定,要真正去做這件想了很久卻從未開始的事情。就像她說的,與其過多地去get ready but do nothing, 還不如去實踐一個不怎麼ready的事!

啥背景呀,就敢寫數據庫內核

說真的,我自己也信心不足呢。說說背景吧(偶爾咱也知乎體一下):咳咳,謝邀。本人上海交通大學軟件學院本科畢業,University of California, Davis 計算機博士畢業。現在在臉書做一個老年程序員。自己並不算一個數據庫的科班出身,博士學的也不是數據庫專業。一個很偶然的機會,我得到了一份數據庫公司Greenplum(Pivotal)的實習的機會,又陰差陽錯地畢業後正式加入了Query Processing組。在Pivotal的兩年,非常有幸地參與了Orca Query Optimizer (已在Apache開源) 的開發。在這期間也混了幾篇VLDB,SIGMOD的papaer。正是這份工作讓我開始對內核有所了解。再後來原Pivotal的director離開開了個做數據庫虛擬化的初創公司就把我一起拉去了。這個初創公司做的也非常有趣,database virtualization:旨在不用改變任何application code的前提下(包括不用換JDBC, 或者ODBC driver),就讓application code可以直接運行在另一個數據庫上(舉個例子, Teradata BTEQ script可以直接通過我們的中間件,運行在Pivotal Greenplumn Database上),當時我們用的最多的簡介就是VMWare in terms of databases。這份工作讓我更細緻地了解了不同數據庫原生接口的不同以及如何rewrite不同的SQL dialect來使它們之間互相兼容,我覺得也算變相的query optimization吧。總的來說,自己對各個部件都有所了解,但知識點比較分散,不夠系統,也希望在寫blog的過程中去學習和完善知識儲備。

這個系列會分為哪幾個模塊?有沒有大綱

真心覺得自己還不夠格去系統地講解數據庫的各個模塊。所以我才把這個系列的名稱定義為雜談。咱們就暫不列什麼提綱了,但我會把最核心的部件包括存儲,SQL語言,數據優化器和執行器都cover了。然後我們也能夠自由發揮,分享一些我對NoSQL以及NewSQL的理解。在這個過程中,我也會去查最新的資料,在寫的同時也能更好地去鞏固和訂正知識。

閱讀這個系列會有啥收穫?

我希望能夠深入淺出地去講解數據庫是一個什麼樣的系統,以及為什麼它最後會演化成這樣一個系統,為什麼我們都用SQL來操作數據,而不是AQL或BQL. 希望讀者閱讀後,對數據庫的理解不再單單只是知道簡單的table, row等的基本概念或者單單會寫些join, select的SQL語句。而是能從源頭真正做到知其所以然。希望能從對數據庫系統的認知來進一步提高對general系統設計的認知。

雖然沒有大綱,但是這篇的題目想好了:一小時實現一個基本數據庫。

一小時實現一個基本數據庫

今天我們摒棄直接介紹數據庫內核各個模塊的思路,而是從應用開發者的角度出發,來看實現一個數據庫需要哪些基本功能,然後把這些功能細分成最小的模塊再手把手一起實現,幫你揭開數據庫內核的神秘面紗。希望能夠減輕你對學習數據庫內核的壓力。我們也可以從中體會到,九層之台,起於累土。所有復雜的系統,都是通過模塊化的架構和設計,以及工程階段的精益求精,一步一步累計起來。

對與應用開發者而言,一個數據庫需要哪些必要的功能呢?我覺得,下面這些是必不可少的:

1)創建數據庫和數據表:create database,schema, table等

2)存儲數據:insert /update數據,或者從其他方式導入數據(比如csv文件)

3)讀取查詢數據:通過SQL語句,對數據進行讀取和查詢,比如sort,aggregate,filter等

根據這三個功能,再回看標題,你可能產生疑問,一個小時就能實現上面這些功能,不會是標題黨吧。我承認,有一點小小得標題黨了。因為要和數據庫交互,最必要的條件是有個客戶端程序可以接受用戶送來的指令。但要實現一個功能齊全的Parser可得花不少精力。既然是內核雜談,請允許我偷個懶,假設Parser已經有實現,從而把精力都關注在數據庫系統內部的實現。拋開Parser,又該從哪開始呢?我的思路是跟著數據的流向,自下而上,依次從存儲數據,讀取數據和查詢數據來看。

創建和存儲數據

當用戶創建一個新的數據庫,並導入數據時,數據庫系統就需要存儲這些數據。說到存儲,第一個想法就是文件系統(其實說到底數據庫系統就是一個特殊的文件系統,區別與普通文件系統提供的的讀寫文件的接口,數據庫只是提供了一個面向數據的接口:存儲,讀取和查詢;整個系統為這些接口提供服務)。以下圖student表作為示例,要怎麼把這張表存在文件中呢?

數據庫內核雜談(一):一小時實現一個基本功能的數據庫 1

Student表
最顯而易見的就是用Comma-separated value(CSV)格式存:

1,“Xiaoputao”,3,“Hiking”

2,“Zgu”,3,“Running”

3,“Xiaopang”,2,“Walking”

讀取CSV文件的邏輯也非常簡單: 一行一行讀取數據,然後根據”;”把每個數據段取出。

除了CSV存儲,另一種常見的方式就是json格式:

( {"id":1, "name":"Xiaoputao", "class":3, "hobby":"running}, ... )

聊聊CSV和JSON存儲的優缺點。兩者都屬於文本存儲,優點一在於易於人類理解。另一個優點就是直接兼容其他支持CSV和JSON的數據庫。缺點也很明顯,存儲效率不高,讀取效率也會隨之降低。另一個問題在於,上述例子中存儲的內容只有值,沒有type和size(metadata),這些信息在後續操作如校驗中是很重要的。當然,我們可以把metadata加入到存儲中,比如,把json的每個val變成一個obj:{“colName”:“id”,“colType”:“int”,“colSize”:4,“colVal” :1}。專業數據庫肯定不會選擇用CSV或JSON作為默認存儲,但幾乎都支持CSV和JSON數據作為external table。如果要追求更高的性能,我們可以選擇更高效的編碼方式把數據以字節流的形式存儲在文件中;只要數據庫系統自身能夠讀取這些數據即可。咱們既然時間有限,當然是一切從簡,就選擇CSV或者JSON的文件格式來存儲我們的數據。

只要有一個文本編輯器,能夠創建和編輯CSV或者JSON文件。這其實這已經完成了創建數據表,輸入,修改以及存儲數據的功能。

讀取數據

基於上述用CSV或JSON的存儲,讀取數據非常簡單(允許我們調用第三方支持CSV或者JSON的API)。重點在於讀取完存放在怎樣一個數據結構中方便後續對數據進一步的查詢操作。根據數據的特性,結果集(RowSet)是由一序列的行數據(Row)組成,每一行又由多個單元(Cell)組成。我們試著根據這個概念設計下面這些類:

數據庫內核雜談(一):一小時實現一個基本功能的數據庫 2

Cell, Row, RowSet Class

簡單梳理下,每個Cell存type,size,和value;Row存一整行cell;RowSet存一序列的Row。具體在實現中還有很多細節需要注意,如typecheck, 確保每行列數相同,等等,這裡也一併從簡略過。定義了存儲方式和數據結構,具體數據讀取代碼如下:

數據庫內核雜談(一):一小時實現一個基本功能的數據庫 3

讀取

csvToRowSet和jsonToRowSet的實現只需要藉助第三方CSV和JSON的類庫就能實現,就不贅述代碼了。

這一節裡,我們定義了Cell, Row, RowSet的數據結構來存放從文件(CSV或JSON)中讀取的數據,並給出了示例代碼。

執行查詢

有了存儲和讀取,已經可以把數據從文件中讀取到內存,接下來就要支持用戶的查詢語句了。實現查詢就是去實現SQL語句中的各個功能模塊,比如排序(order by), 聚合(group by),多表聯合(join)等等。執行器會對每個功能模塊進行實現,甚至針對不同的數據分佈,會有多種方式的實現來提高讀取速度。現在,我們一起來討論一些常用的語言功能。

全表讀取(SELECT *)

其實,定義了RowSet的數據結構和實現了讀取文件的接口,我們的數據庫就已經支持全表讀取的SQL語句,示例如下:

SELECT * FROM student;

分頁語句(LIMIT)

一下子就能想到的分頁語句,用來限制輸出的數據行數:

數據庫內核雜談(一):一小時實現一個基本功能的數據庫 4

Limit Operator

一行代碼,不解釋了。抬走!

關係映射語句(PROJECTION)

關係映射的本質是對於輸入的RowSet的每一行(row), 通過各種標量計算,輸出一個新的數據行,再由這些行組成新的RowSet。見下圖示例:

SELECT id + 5, LEN(name) FROM student;

對從student表讀取的每一行數據,輸出一個新的數據行包含 id + 5 和 LEN(name)的cells。

Projection可以非常複雜,但有一條準則就是它不改變原有RowSet的基數(cardinality), 即新RowSet的行數和原來的相同。因此,無論映射邏輯多複雜,輸入一個Row,輸出一個Row。再复雜的計算,也是一比一步迭代產生。比如上述示例可以分解成下面這些操作來完成:對於每一行input row, id值加5,對name取length,最後去掉class和hobby兩列。歸根結底就是將復雜的運算拆分成原子操作然後一步一步地順序執行。我們可以定義如下兩個基本operator:RowComputeOperator根據定義的computeCellVal對input row計算一個新cell,並把這個cell加到原row的末尾。 SelectionOperator根據給定的indexes,生成一個僅包含指定index的新row。 Pseudo code如下:

數據庫內核雜談(一):一小時實現一個基本功能的數據庫 5

RowComputeOperator and SelectionOperator

RowComputeOperator裡面有需要定義computeCellVal,輸入是一個row,輸出一個新的cell。具體實現則根據具體語義來定。定義一個computeCellVal需要2個參數:1)運算作用在哪些cell上,假設限制只能作用在1個或2個cell上(2個以上可以用多個Operator嵌套);2)提供具體計算的操作,比如常見單元操作如len(), ceiling(), abs()或者常見的二元操作如±*/等等。

有了這兩個基本operator, 實現示例中的projection,我們定義3個operator即可:1)compute a new cell using “(id + 5)” 2) compute a new cell using “len(name)” 3 ) 用SelectionOperator選擇最後兩個新生成的cell。

實現整個projection的operator的pseudo code如下:

數據庫內核雜談(一):一小時實現一個基本功能的數據庫 6

Projection Operator

條件選擇語句(WHERE)

有了Projection,我們就可以實現下面的條件選擇語句(WHERE)了:

SELECT * FROM student WHERE class = 3;

實現想法很簡單,首先用Projection operator計算出filter condition的值(bool),然後filter by 這個cell即可。

數據庫內核雜談(一):一小時實現一個基本功能的數據庫 7

Filter Operator

排序語句(ORDER BY)

這裡,我給一個非常低效但很容易理解的實現:創建一個hashmap來存,然後對要sort的cell排序,根據cell順序取出原row組成新的rowSet輸出:

數據庫內核雜談(一):一小時實現一個基本功能的數據庫 8

Sort Operator

有讀者會問,如果排序語句是一個expression而不是單個column怎麼辦?比如下面的示例:

SELECT * FROM student ORDER BY id + 5 ASEC;

還記得我們前面實現的projection嗎?這裡把(id + 5)作為一個新的projection加入到Row中即可。

一起實現了4個Operator,看看有沒有什麼規律可循?所有定義的操作都是基於一個原則:輸入一個RowSet,然後輸出一個RowSet。並且,是一層一層循序漸進的迭代。對於數據的查詢操作,是從最初讀取表中的原始數據開始,根據給定的Operator序列對數據逐一進行操作;這一個Operator的輸出就是下一個operator的輸入。也就是說,給定一個SQL查詢語句,我們生成一序列Operator的tree,再依次執行,就能得到最終結果。現在來一起優化下代碼,把Operator的接口抽像出來,然後把剛才實現的operator全當成子類來實現。代碼如下:

數據庫內核雜談(一):一小時實現一個基本功能的數據庫 9

Unary Operator

有讀者會有疑問,基類為什麼叫UnaryOperator呢?先賣個關子。有了基類,我們可以根據SQL的語法功能實現相應的Operator。

聚合操作(AGGREGATION)

接著一起來實現聚合操作。 Aggregation分為兩大類,scalar-agg和multi-agg。 scalar-agg就是簡單的sum, avg, min, max等的數據聚合操作,最終返回一個數據行的結果集,實現代碼如下:

數據庫內核雜談(一):一小時實現一個基本功能的數據庫 10

Scalar-agg

每個AggOp接受一序列的cells,然後輸出聚合結果的cell。常見的AggOp如sum, max,min實現都很簡單,這邊就不贅述了。

multi-agg對應SQL中的GROUP By,如下圖示例:

SELECT class_room, COUNT(*) FROM student;

比scalar-agg複雜的地方就是先要把有相同值的group by columns(示例中為class_rom)的row合併起來,然後對合併後的rows做Scala-agg即可。代碼我就不貼啦,當留個小作業給大家。

SQL Operator Tree

有了實現基本語義的Operator,要實現一個完整的查詢語句,我們要做的就是把operator一層一層的累加起來,形成一個Operator tree,然後根據這個operator tree, 依次執行每一個operator即可。比如下面這個查詢語句:

select class, sum(id + len(name)) as c

from (

    select * from student where hobby = 'hiking' limit 10

)

group by class;

我們只要建立如下的Operator tree:

數據庫內核雜談(一):一小時實現一個基本功能的數據庫 11

sql operator tree

有沒有覺得挺神奇的!即使再复雜的查詢SQL都能這樣用基本的operator像搭樂高一樣搭建起來。

小結

至此,我們簡單的數據庫也實現得差不多啦。我看了下自己寫的pseudo code僅僅200多行,一個小時寫完也不算條件太苛刻。雖然數據結構冗餘,算法低效,但是麻雀雖小,五臟俱全!

來解釋前面賣的關子,為什麼基類定義為UnaryOperator?因為我們還有BinaryOperator。二元的操作是做什麼的呢?答案就是為了表與表的聯合(join)。有了Binary Operator,Operator的疊加就真正變成了一顆樹(二叉樹),這也是為什麼前文我們稱之為operator tree。本文就先不詳述如何實現Join Operator了,以後會有專門的章節來覆蓋。再講下去,肯定超過一個小時,讀者就更覺得我標題黨了。

最後給大家總結一下:

1)一個SQL的查詢語句,即便邏輯再复雜,也可以拆分成一個一個原子operator的疊加

2)把這些operator組建成一個operator tree,然後自底向上地依次執行,就能得到最終的查詢結果

3)你可能覺得真正的數據庫和我們在這搗鼓的很不一樣。如果有條件,可以在Mysql或者Postgres中運行”EXPLAIN SQL_STMT”來打印它們生成的operator tree,你會發現和我們生成的樹挺相似的

4)相信大家都非常熟悉用SQL做各種數據查詢,但可能從沒去想過底層是怎樣實現的。希望這篇博客對你有所幫助。正所謂,知其然,知其所以然!

下一篇,咱們深入聊聊存儲!

作者介紹:

顧仲賢,現任Facebook Tech Lead,專注於數據庫,分佈式系統,數據密集型應用後端架構與開發。擁有多年分佈式數據庫內核開發經驗,發表數十篇數據庫頂級期刊併申請獲得多項專利,對搜索,即時通訊系統有深刻理解,愛設計愛架構,持續跟進互聯網前沿技術。

2008年畢業於上海交大軟件學院,2012年,獲得美國加州大學戴維斯計算機碩士,博士學位;2013-2014年任Pivotal數據庫核心研發團隊資深工程師,開發開源數據庫優化器Orca;2016年作為初創員工加入Datometry,任首席工程師,負責全球首家數據庫虛擬化平台開發;2017年至今就職於Facebook任Tech Lead,領導重構搜索相關後端服務及數據管道, 管理即時通訊軟件WhatsApp數據平台負責數據收集,整理,並提供後續應用。