如何自己實現一個關係型資料庫？

01-15

如題，最近一個同事突發奇想想要自己做一個關係型的資料庫。功能可以不夠完善，但是可以識別sql語句，實現增刪查改。有沒有什麼好的資料推薦，因為我發現網上搜素到的資料庫都是mysql里的一個資料庫，不是整個DB，或者說是我名稱用的不對？Anyway，他想純用python實現，不知道是否有可行性？實現資料庫需要掌握哪些知識？底層功能的邏輯劃分是怎樣的？

最近在做的畢業設計就是做一個非常簡單的關係型資料庫，用Rust，目前已完成大部分模塊。代碼質量一般般，有興趣就看看吧，GitHub - doyoubi/Blastoise: tiny relational database

實現了 sql parser，語義檢查，生成簡單的執行計劃，內存池，持久化。我想基本符合題目的要求了。

不過，其實我真不推薦做這個。贊同輪子哥的說法，關係型資料庫裡面重要的內容是保證一致性和性能優化。只是簡簡單單造一個雛形，其實挺浪費時間，收穫也不大。有時間還是應該多看資料。

不過還是貼一下做一個簡單關係型資料庫的資料吧。

How does a relational database work

《Database System Implementation》

https://web.stanford.edu/class/cs346/2015/

第三個是斯坦福的課程，在github上搜redbase能找到學生上傳的完整代碼。

都答偏了啊。

關係型資料庫的奧義就在於實現索引、transaction、回滾，還有斷電保護（

見《資料庫系統概念》

對外數據模型為關係型資料庫，內部的實現主要分成兩大類，一類是disk-based，比如mysql，postgres，一類是memory based，後者包括MemSQL，SAP HAHA，OceanBase。看題目的意思指的是前者。這裡說一個disk-based的關係型資料庫涉及多少東西。

上世紀70/80年代內存不大，數據不能都放在內存里，大部分數據都存在磁碟上，讀數據也需要從磁碟讀，然而讀寫磁碟太慢了，所以就在內存里做了一個buffer pool，將已經讀過的數據緩存到buffer pool中，寫的時候也是寫到buffer pool中就返回，buffer pool的功能就是管理數據在磁碟和內存的移動。在buffer pool中數據的管理單位是page。page大小一般幾十KB。一般都可以配置。如果buffer pool中沒有空閑的page，就需要將某一個page提出buffer pool，如果它是dirty page，就需要flush到磁碟，這裡又需要一個LRU演算法。一個page包含多條記錄，page的格式需要設計用來支持變長欄位。如果這時宕機了，buffer pool中的數據就丟了。這就需要REDO log，將對數據的修改先寫到redo log中，然後寫buffer pool，然後返回給客戶端，隨後，buffer pool中的dirty page會被刷到數據文件中(NO FORCE)。那麼重啟的時候，數據就能從redo log中恢復。REDO log還沒刷完就刷數據到磁碟可以加快寫入速度，缺點就是恢復的時候需要回放UNDO log，回滾一些還沒有提交的事務的修改。寫log又分為邏輯log和物理log，還有物理邏輯log。簡單說邏輯log就是記錄操作，比如將某個值從1改成2.而物理log記錄具體到record的位置，例如某個page的某個record的某個field，原來的值是多少，新值是多少等。邏輯log的問題是並發情況下不太好恢復成一致。物理log對於某些操作比如create table又過於瑣碎，所以一般資料庫都採用混合的方式。為了跟蹤系統中各種操作的順序，這就需要為log分配id，記做LSN(log sequence number)。系統中記錄各種LSN，比如pageLSN, flushedLSN等等。為了加快宕機恢復速度，需要定期寫checkpoint，checkpoint就是一個LSN。

以上ACID里的C和D有關。下面說A和I，即原子性和隔離性。

這兩個性質通過concurrency control來保證。隔離級別有很多種，最開始有4種，從低到高read uncommitted, read committed, repeatable read, serializable。serializable就是多個事務並發執行的結果和某種順序執行事務的結果相同。除了serializable，其他都有各種問題。比如repeatable read有幻讀問題(phantom)，避免幻讀需要gap lock。read committed有幻讀和不可重複讀問題。後來又多了一些隔離級別，比如snapshot isolation，snapshot isolation也有write skew問題。早期，並發控制協議大多是基於兩階段鎖來做的(2PL)，所以早期只有前面提到的四種隔離級別，後來，又出現一類並發控制協議，統稱為Timestamp Ordering，所以又多了snapshot isolation等隔離級別。關於隔離級別，可以看看這篇論文 http://research.microsoft.com/pubs/69541/tr-95-51.pdf。2PL需要處理deadlock的問題。

Timestamp Ordering大體的思想就是認為事務之間衝突不大，不需要加鎖，只在commit的時候check是否有衝突。屬於一種樂觀鎖。

Timestamp Ordering具體來說包括多種，最常見的MVCC就是這類，還有一類叫做OCC(optimistic concurrency control)。MVCC就是對於事務的每次更新都產生新的版本，使用時間戳做版本號。讀的時候可以讀指定版本或者讀最新的版本。幾乎主流資料庫都支持MVCC，因為MVCC讀寫互相不阻塞，讀性能高。MySQL的回滾段就是用來保存老的版本。MVCC需要有後台線程來做不再需要的版本的回收工作。Postgres的vacuum就是做這事的。OCC和MVCC的區別是，OCC協議中，事務的修改保存在私有空間(比如客戶端)，commit的時候再去檢測衝突，通常的做法是事務開始時看一下自己要修改的數據的最後一次修改的時間戳，提交的時候去check是否這個時間戳變大了，如果是，說明被別人改過了，衝突。衝突後可以回滾或者重試。

上面這些搞定了就實現了資料庫的核心，然後為了性能，需要index，通常有兩種，一種支持順序掃描B+Tree,還有一種是Hash Index。單條讀適合用Hash Index,O(1)時間複雜度，順序掃描只適合用B+Tree，O(logN)複雜度。然後，有些查詢只需要掃描索引就能得到結果，有些查詢直接掃描數據表就能得到結果，有些查詢可以走二級索引，通過二級索引找到數據表然後得到結果。。具體用哪種方式就是優化器的事了。

再外圍一些，關係型資料庫自然需要支持SQL了，由SQL變成最後可以執行的物理執行計劃中間又有很多步，首先SQL通過詞法語法分析生成抽象語法樹，然後planner基於這棵樹生成邏輯執行計劃，邏輯執行計劃的生成通常涉及到等價謂詞重寫，子查詢消除等邏輯層面的優化技術，優化的目的當然是性能。比如等價謂詞重寫，用大於小於謂詞消除like，between .. and..等不能利用索引的謂詞。下一步是邏輯執行計劃生成物理執行計劃，物理執行計劃樹每個節點是一個operator，operator的執行就是實實在在的操作，比如掃表的operator，filter opertor。一個邏輯執行計劃通常可以有多個物理執行對應，選擇哪個就涉及到物理執行計劃優化，這裡涉及到經典的cost model，綜合考慮內存,CPU, I/O,網路等。最典型的，三表join，從左到右還是右到左，使用hash join，還是sort merge join等。關於查詢優化器可以參考這本書資料庫查詢優化器的藝術：原理解析與SQL性能優化

可以看出，要實現一個disk-based關係型資料庫系統非常複雜，想看代碼的話直接看postgres吧

先寫這些，以後慢慢補充。。。

說起來最近在做的就是在KV資料庫（比如Redis）裡面提供一定的事務性的模塊。KVDB具有高性能的按Key的讀寫功能，但是通常不同Key的數據之間是有關聯的，我們希望能一次讀寫多個Key，而且保證讀寫的數據之間是一致的。

舉個例子來說，我們有A、B兩個Key，裡面對應的值是a, b。某個操作會同時將a和b的值各自遞增1。如果寫邏輯只是簡單去分別遞增兩個值，讀邏輯只是去各自讀一次相應的值，並發執行的情況下就會出現這樣的情形：

過程1寫入A = a + 1 ;

過程2讀取了A；

過程2讀取了B；

過程1寫入了B = b + 1

結果過程2讀取到的結果是(a +1, b)，是過程1寫入的一個中間結果。這個就破壞了過程的事務性。要使任何時候中間過程都不會被讀出來，就必須要有一定的機制來保證寫入是一次寫入，讀取是一次讀取。在Redis當中通常可以用MGET，MSET還有WATCH/MULTI/EXEC的方法來實現。

前面的是個簡單的例子，我們已經提前知道了A、B兩個Key，但是設想下面這個例子：

有一個Key記作C，C裡面的數據存儲了另一個Key記作D，我們需要同時讀取出C的數據和D的數據。注意到我們在讀取C的值之前是沒法知道D這個Key是什麼的，但是一旦我們讀取出C的值之後，在我們讀取D的值之前，C的值就可能已經過期了。比如說一個過程刪除了D，創建了E，同時將C指向了E，記作過程1，而過程2讀取了C以及C指向的Key的值，就會出現這樣的情況：

過程2讀取C，C指向D；

過程1刪除D，創建E，將C指向E；

過程2讀取D，D已經被刪除

於是過程2讀取到了不連續的結果，這個結果是個中間過程產生的。跟前一種情況不同，這一次我們不能用MGET同時讀取C和D的值，因為讀取C之前我們不知道D的Key。有兩種方法解決這個問題：

1. 讀取C的同時，將C鎖起來，防止別人修改C（這也是MySQL的做法）

2. 我採用的辦法：

讀取C，發現C指向D；

同時讀取C和D。重新判斷C的值，如果C仍然指向D，結束；否則重複這一過程，直到達成一致。

後一種方法沒有加鎖的開銷，但是會增加額外的讀取，如果數據頻繁被修改的話讀取的開銷增加會更大，適用於每個Key裡面值比較小，而且修改遠遠比讀取次數少的情況。

（對於Redis，還有一種方法是使用Lua Script，但是局限性比較大，而且不適用於Redis以外的KVDB）

按 @vczh 答案中的「實現索引、transaction、回滾，還有斷電保護」四點來說，斷電保護這個是底層存儲的能力，通常非關係型資料庫也支持；索引主要是數據結構的問題，如果把索引也看作是自動生成的數據的話，如果我們能實現後一種情況下的事務性，實現一個索引並不困難，既然值可以隨意引用其他Key而且能保證事務性，那麼用KVDB實現一個B樹也只是編程複雜度的問題；回滾我認為並不是一個真正的功能，通常說回滾其實是事務性的一部分，也就是事務在整體寫入之前可以撤銷，這其實跟事務的原子性是一體的，只是個實現問題。最根本的來說，關係型資料庫要實現的是讀寫的事務性。注意事務性並不代表顯示支持TRANSACT這樣的語句，實際上任何一句UPDATE、INSERT、DELETE都包含事務性，比如UPDATE同時寫入多行，其他的SELECT並不可以讀取出一部分行被UPDATE而另一部分沒有被UPDATE的結果；INSERT、DELETE通常伴隨著主鍵衝突檢查、索引更新的過程，這也要求很強的事務性。

至於SQL解析，那個說實話是最最沒有用的部分，如果不是想要實現一個SQL兼容的資料庫產品的話。如果你的需求真的是SQL兼容的，為什麼不直接用MySQL呢？大部分情況下我們需要的都是跟SQL功能不太一樣的，比如說非結構化數據的存儲，比如說可分區，這些天生就跟SQL用法不一樣了，一般沒必要去實現這玩意。

寫java的可以看看h2，語法和mysql高度一致，而且就是一個jar包，要調試比sqllite方便。

理論可以結合資料庫系統實現，也不一定要啃英文版，中文版翻譯的也不錯。

最近一個禮拜的morning paper就講 Database, Techiques Everyone Should Know, 引用小紅書第三章

(Database) Techiques Everyone Should Know

Readings in Database Systems, 5th Edition

沒有人提如何實現sql么?

可以看看 LEMON語法分析生成器

這本書對應的源代碼就是sqlite源碼中的lemon.c, 這是個LALR(1)的parser generator, 也就4000行左右。

2016年5月25日更新

距離我寫的第一個原始資料庫，過了近三年

我真的自己造了個資料庫基於協程和非同步IO的NoSQL資料庫AsyncDB正式發布 - 林誠的文章 - 知乎專欄

-------------------------------------------------------

題主的問題，一下把我的思緒拉到了幾年前

以前，我是這麼寫的，那時候，我還在讀會計，對於編程一竅不通

以下是Python偽代碼：

import pickle

my_db = {} db_file = open("db") pickle.dump(my_db, db_file) pickle.load(my_db, db_file)

一看，就知道，所謂對於資料庫的操作，其實就是對Python內存中Dict的操作。

我需要在開始程序的時候load dict，然後退出之前重新dump一遍dict

你能說這不是資料庫么？我又確實實現了對於數據持久化，雖然具體實現萌得一比。

後面還有更萌的，我看到了這個問題 python中的pickle問題? - 編程

那個題主，似乎在尋找一個「智能」的Pickle，類似SQL資料庫

我就在思考，究竟要怎麼樣，才能高效地存儲數據？

儘管那時候，我對空間複雜度，時間複雜度，沒有任何概念，但我隱約能感覺，我的第一版程序，非常的浪費資源。

首先，我開程序，要把資料庫遍歷了一遍，關程序，又把資料庫寫了一遍，而且所有的資料庫內容，都要載入在內存中的Dict中。從數學上分析，大量的數據，你是用不到的，放在硬碟就好了。因為硬碟空間大，這樣我就可以存儲超過我內存上限的數據了。

在沒有任何書籍的指導下，我一邊讀著煩人的會計，背著守則；一邊，對著電腦，不禁沉思，究竟有沒有辦法？有，那就是索引。

我把資料庫分成了2部分，1個文件存Index，1個文件存Value。

db_index_file = open("db_index") my_db_index = pickle.load(db_index_file) my_db_index[key] = value_position = (start_position, stop_position)

my_db = open("db") my_db.seek(start_position) value = pickle.loads(my_db.read(stop_position - start_position))

這樣內存只要存Index就好了，每次開關程序載入和寫入Index文件

增改時，新內容寫在Value文件里，得到這段數據在硬碟中開頭和結尾的位置，然後修改內存中的Index

但我又發現一個問題，如果我的Value是一個長List，我單獨對這個List的增刪改，整個List就要重寫。有沒有辦法，讓我能對這個資料庫的一個值為List的項單獨增刪改呢？

也是有的。

索引可以變成是多段的。一個Key對應的Value地址可以是多個的，取值就是把多個地址的值並在一起。

my_db_index[key_of_a_list] = value_positions = [(start_position, stop_position), (start_position, stop_position) ...]

舉個例子，

如果刪除的是List的頭或者尾項目，地址還是只有1個，刪除的中間的項目，原地址會分成2個

增改同理

後面，我又發現一個大問題，我這設計不具有任何「ACID」特性（那時候還不知道叫這），一旦程序中途crash了，數據就全丟了。雖然我的Value是實時更新的，但Index只有在開始運行和結束的時候會寫回。

這時候，資料庫被我分成了3部分，多了一個文件專門裝日誌。

每當資料庫收到一個指令，這個指令，就會被寫入日誌文件。

如果，程序正常關閉，日誌文件會被清空。

如果，程序崩潰了，下次啟動，資料庫會先檢測，日誌文件是不是空的，如果非空，就把日誌文件裡面記載的所有命令按順序執行一遍，就能還原崩潰前數據是啥樣的了；日誌為空，正常啟動。

那時候，我還不知道Git，代碼就直接寫在那個回答里了，有興趣可看看。不要在任何正式場合使用，我寫的時候從來沒有詳細測試過，只是用著沒錯就用下去了。

再後來，知道了演算法分析，我就發現這設計中巨大的缺陷，題主你把缺陷補上，再加上一個SQL語句解釋器就是真正可用的資料庫了。

我發現什麼缺陷？

主要有2個

Key和Value，全都是動態的。

拜Python的動態特性所賜，我當時理所當然地認為，所有的值都應該是動態變長的，直到我學了C。計算機的底層是定長的，32位int，64位的long。為了給我的資料庫的動態特性打補丁，不可避免，索引將會非常碎片化。

比如，說好這個column是int，那全都是int，刪除的時候，能直接計算出位置，擦除寫入就好了。

找第n個Item，尋找速度是O(1)，而我的是O(n)，必須遍歷所有的地址，然後一個一個找。

一個高效的資料庫，必然是靜態類型的。

索引的演算法非常的幼稚

資料庫索引，我相當於用的是Python內置的Hash演算法。但為了海量數據存儲，速度並不是那麼重要，重要的是硬碟和內存佔用，紅黑樹是合適得多的演算法，MySQL採用的是更優的B+-Tree。

對著演算法書，寫一個，應該也是問題不大。

至此，一個幼稚版的資料庫就完成了。

^_^先寫一個並發控制子系統。裡面要提供各種各樣的閂鎖。包括具有不同相容性矩陣的，有優先隊列或者沒有的，能指數後退或者不能的，全局可追蹤的或者不可追蹤的，等等等等。

然後寫一個存儲管理子系統。在這裡你可以決定你的資料庫的外存布局。比如一個表可不可以分開幾個文件存，有沒有區的概念，有沒有段的概念，有沒有表空間的概念，它們之中誰是定長的，誰是可變長的，誰是空間申請單位，誰是空間調度單位。決定好了開始設計頁區段表空間格式，它們的描述符格式，然後用頁頭，頁記錄，頁尾有的沒的串一起。設計好了開始決定這個子系統有哪些內存對象，至少要有一個存儲管理器用來初始化，分配或者調度存儲單元，至少還要提供一堆方法來決定怎麼把二進位數據變成有意義的數據，比如讀一個ushort, 寫一個uint64等等。

之後就要開始寫一個緩衝區管理子系統(假設你做的不是一個內存資料庫)。先弄明白什麼是一個block，一個page, 一個frame。這些都是你的類。然後寫一個緩衝池，再寫一個緩衝區管理器。緩衝池規定數據在內存上的布局，緩衝區管理器就是這個系統的介面了，可以回應一個頁的申請，並實現你最心儀的頁替換策略。

再之後要寫一個日誌系統。先想好你是要用shadow page日誌啊，還是ARIES演算法日誌啊。假設用後者，於是你就失去了強制寫，並採用偷幀的技術。這樣你要設計redo日誌的格式，並使你的日誌記錄種類可擴展，因為不一定什麼時候你就會需要一種新的日誌記錄。如果想讓你的系統更穩健，看看需不需要組日誌(一組日誌記錄要麼都重做要麼都不重做)。如果想讓你的系統更高效，看看需不需要mvcc。要的話還得再加入undo日誌，並設計格式。下面你要設計日誌記錄粒度。全物理日誌？全邏輯日誌？物理邏輯日誌。總之，邏輯的成分越多，系統設計越複雜(比如糟糕的部分寫怎麼處理)。最後跟存儲管理系統要個地方物化日誌，再管緩衝區管理系統要個地方用來調度日誌頁。

接下來要寫一個鎖系統。先想好你的系統是表級鎖還是頁級鎖還是行級鎖。前兩個最自然，直接用fix number什麼的就搞定，最後一個你要有用來表示行鎖的額外數據結構。每個行一個鎖實例？每個頁共用一坨鎖實例？之後去這個鎖表，用來統一申請釋放鎖。最後再決定如何解決死鎖，超時拋出異常？依賴圖分析？

再接下來要寫一個事務子系統。它無非就是提供了一些方法確保各種操作正確地使用了二階段鎖，正確地寫了日誌，正確地回滾。但是這個系統的架構由"各種操作"的多樣性決定。相比堆文件，對b+樹組織的記錄文件中記錄的增刪改查就要極大複雜化日誌寫入過程。相比定長記錄文件，對可變長記錄的增刪改查又是another story。

還有元數據管理子系統，記錄(索引)子系統。以上這些組成了一個存儲引擎。題主還想要的額外的東西分別是: SQL lexer, SQL parser, SQL planner, SQL optimizer。以上又構成了一個SQL compiler。最後再來個Server/Client Module 用來控制許可權，提供API，估計就差不多了。

至於後面那些組件的概要，等我找來時間再寫吧。

(補充一下，用Python寫，第一個子系統就是個問題，你頂多能用acquire_lock() 找出來一個沒有隊列(似乎有個wait參數可以指定要不要線程等待，所以也許是有隊列的，細節我忘了，囧)的自旋鎖。但是資料庫要求自旋次數可自定義，還要有優先隊列來讓線程睡眠。另外，凡是有GC的語言，緩衝區都不受你控制。因為頁被踢出後，並不代表它被析構，萬一代碼沒寫好，GC一直以為它有用，不就成內存泄漏了。)

你可以看看有個姜啥寫的mysql解析，對資料庫底層做了分析。具體的名字記不清了，讀書的時候圖書館看到的，隨便翻了翻還挺不錯。自己搜一下吧。

java的話，有derby可以參考。

關係資料庫功能繁雜，性能苛刻，除非是原型或demo，一個真正的關係資料庫幾乎都是在磨礪出來的：OceanBase用了6年多的時間才取代Oracle成為了支付寶的賬務等資料庫。當然只是做一個實驗室內的關係資料庫原型是可以的。

github一定有開源資料庫

一個成熟的資料庫的實現難度不低於實現一個成熟的操作系統。練手可以拿UWisconsin Madison的教學用MiniBase試試。

作為一個oracle碼農，，本來覺得oracle db慢又難用的要死比sql server不知道low到哪裡去了。。。看到大大們的回復頓覺人生又充滿了希望

(逃

這種底層的東西，還是用C/C++比較好。

python這種語言，做個二進位讀寫還得慢慢用struct來拼。。。

另外，和mysql毫無關係的關係型資料庫當然有啊，著名的sqlite就是啊。

先看資料庫系統全書，然後考慮：

1.存儲結構和索引結構，

2.支持的sql子集，

3.實現存儲的讀寫處理，以及擴容

4.實現sql引擎，關係處理，並與存儲集成

5.實現redo undo日誌，savepoint

6.實現隔離級別和事務，控制並發

7.看情況實現網路操作部分、命令行工具和jdbc之類的驅動

可以參考sqlite或derby，特別是早期版本的derby，代碼量不是很大

可以看一下這個 pingcap/tidb · GitHub

實現簡單的sql增刪改查應該可以用python實現的。不過語言只是工具，原理才是根本，我覺得了解簡單的DB結構還是必要的。

1. 資料庫文件的組織形式，包括數據文件和索引文件。一種是將數據，索引分離存儲（MyISAM），另一種資料庫文件本身就是按B+樹組織的，也就是數據和索引是同個文件（InnoDB）。

2. 資料庫文件的結構：一般按page或block組織，一個block 4k大小。SQLite的數據表就是由一個或多個page構成。

3. 資料庫系統結構：可以參照SQLite的系統結構，將系統分為Front-end前端，和Back-end（後端）。

Front-end：SQL的解析器，將輸入的sql命令進行tokenize，然後對sql語法進行parse，轉化為內部命令格式（後端調用）。

Back-end：要負責catalog的管理，增刪改查record時要建立index，也就涉及page/buffer管理。

4. 具體實現：如果不考慮事務，並發，複雜的sql操作，可以參考下面的實現模塊。

from github：halfvim/MiniDB · GitHub我也是參照上面的大神的代碼，目前在嘗試寫一個簡單的資料庫，不過我是用C++寫的。可以交流交流。

chenbjin/BeetleDB · GitHub

我也在自己寫一個資料庫，目前只基本完成了存儲引擎部分。

個人感覺「事務」功能的實現才是重點和難點，原子性（Atomicity）、一致性（Consistency）、隔離性（Isolation）、持久性（Durability），這些直接影響效率。

上層的SQL解析其實不是很重要，只是個介面而已。

所以我覺得實現步驟應該是這樣的：

實現分頁存儲、緩存
操作日誌、事務回滾
實現事務隔離、MVCC
數據索引
SQL解析、查詢計劃
網路複製同步