英文原文

SQLite

本文里蛀蜜，我們將會通過SQLite的一個早期版本來討論一下數(shù)據(jù)庫實現(xiàn)的一些架構(gòu)細節(jié)

簡介

????數(shù)據(jù)庫是軟件系統(tǒng)里很重要的一個組成部分投蝉，它主要用來高效地存儲和讀取數(shù)據(jù)硬纤。本文里，我們將會通過SQLite的一個早期版本來討論一下數(shù)據(jù)庫實現(xiàn)的一些架構(gòu)細節(jié)。

????SQLite是一個小型數(shù)據(jù)庫軟件，但是它被廣泛地用在成千上萬的軟件系統(tǒng)和硬件設(shè)備里篇恒。它是在2000年8月份被D.Richard Hipp發(fā)明的。SQLite是一個高性能的，輕量級的關(guān)系型數(shù)據(jù)庫系統(tǒng)。如果你想在代碼層面學(xué)習(xí)數(shù)據(jù)庫的內(nèi)部實現(xiàn)的話阻课，SQLite是眾多開源數(shù)據(jù)庫里最好的選擇限煞，它的文檔很多，而且代碼的可讀性非常高旺上。但是，如果去閱讀最新版本的SQLite的代碼的話，就顯得比較困難了，因為它包含了很多新的特性卒煞。另外乖订，為了便于理解數(shù)據(jù)庫的實現(xiàn)原理扛点，你需要熟悉數(shù)據(jù)結(jié)構(gòu)眠饮，了解計算原理以及操作系統(tǒng)原理寨蹋。

????在這里，我們會使用SQLite 2.5.0版本。你可以在GitHub上找到SQLite的一個簡單實現(xiàn)。另外嗦枢，這個代碼倉庫里有SQLite 2.5.0版本的代碼殖演，可以拿來參考丸相。

為什么需要數(shù)據(jù)庫座硕？

????使用純文件的方式來存儲和讀取數(shù)據(jù)是效率比較低的。數(shù)據(jù)庫會通過合適的方式來組織數(shù)據(jù)，這樣的話，數(shù)據(jù)的讀取和寫入都會比較快年局。數(shù)據(jù)可以是結(jié)構(gòu)化的，半結(jié)構(gòu)化的或者完全非結(jié)構(gòu)化的。根據(jù)存儲的數(shù)據(jù)類型验庙，數(shù)據(jù)結(jié)構(gòu)可以分為以下幾類：

1. 關(guān)系型數(shù)據(jù)庫：常用的數(shù)據(jù)庫搏恤，基于表結(jié)構(gòu)的熟空。數(shù)據(jù)表之間可以有關(guān)聯(lián)關(guān)系。這種數(shù)據(jù)庫可以用SQL語言來操作數(shù)據(jù)息罗。
2. 鍵-值數(shù)據(jù)庫：通過鍵-值對來存儲數(shù)據(jù)掂咒。數(shù)據(jù)可以通過指定的鍵來讀取。內(nèi)存數(shù)據(jù)庫大多都是這種類型的數(shù)據(jù)庫迈喉。
3. 對象數(shù)據(jù)庫绍刮。數(shù)據(jù)結(jié)構(gòu)更像一個對象而不是一個表。
4. 圖數(shù)據(jù)庫：圖數(shù)據(jù)庫存儲的是節(jié)點和邊挨摸，常用于數(shù)據(jù)挖掘和社交媒體應(yīng)用录淡。

SQLite 數(shù)據(jù)庫架構(gòu)

????SQLite數(shù)據(jù)庫架構(gòu)可以分為兩個部分，分別叫做內(nèi)核（core）和后臺（backend）油坝。內(nèi)核部分包含接口，分詞器刨裆，解析器澈圈，代碼生成器和虛擬機，它負責(zé)生成數(shù)據(jù)庫事務(wù)的執(zhí)行指令帆啃。后臺包含B-tree瞬女，頁（Pager）以及用來讀取文件的操作系統(tǒng)接口。分詞器努潘，解析器和代碼生成器合起來成為編譯器诽偷，它負責(zé)生成在虛擬機上執(zhí)行的指令坤学。

從哪里開始？

????了解一個數(shù)據(jù)庫的架構(gòu)报慕，你需要有以下預(yù)備知識：

1. 熟悉數(shù)據(jù)結(jié)構(gòu)和算法深浮。特別是B-tree，鏈表眠冈，哈希表等數(shù)據(jù)結(jié)構(gòu)飞苇。
2. 對計算機系統(tǒng)結(jié)構(gòu)（computer architecture）有一定的了解。例如文件是如何從磁盤里進行讀寫的蜗顽，分頁系統(tǒng)以及緩存是如何工作的布卡。
3. 一些計算原理的知識，例如有限自動機以及正則表達式雇盖。

SQLite 架構(gòu)

image

虛擬文件系統(tǒng)VFS（Virtual File System)

????在Unix和Windows兩種系統(tǒng)中忿等，文件訪問的方式是不同的。對此崔挖，VFS提供了與操作系統(tǒng)無關(guān)的通用API贸街。這套API里包含了文件的打開，讀取虚汛，寫入和關(guān)閉這些功能匾浪。以下是VFS里里用來讀取和寫入文件的API。

    Create a connection to file to read write 
    zFilename : file name 
    id : file pointer 
    pReadonly : read or write 
    */
    int sqliteOsOpenReadWrite(const char *zFilename, OsFile *id,int *pReadonly);

    Acqure the lock to read file. This function should be 
    called before caling to any file read function. 
    Return 0 if success
    id : file pointer 
    */
    int sqliteOsReadLock(OsFile *id);

    Get the write lock to write into a file. This function should called before
    doing any write operation into the file system.
    Return 0 if success
    id : file pointer
    */
    int sqliteOsWriteLock(OsFile *id);

    Move to the given number of offest to read or write into the file
    */
    int sqliteOsSeek(OsFile *id, int offset);

`/* 
Read amt bytes from the file with offset pointed by sqliteOsSeek
*/
int sqliteOsRead(OsFile *id, void *pBuf, int amt);`

`/* 
Write amt bytes from the pBuf into the file
*/
int sqliteOsWrite(OsFile *id, const void *pBuf, int amt);`

????首先卷哩，你可以通過sqliteOpenReadWrite函數(shù)來打開一個文件蛋辈。它會返回一個文件指針，你可以用這個指針來進行文件的讀寫操作将谊。接下來冷溶，如果要進行讀寫的話，就需要先獲取相應(yīng)的鎖尊浓。對于只讀操作逞频，只獲取讀鎖。對于事務(wù)而言栋齿，無論是讀寫苗胀，都需要獲取寫鎖。

????讀寫文件的尋址操作可以通過給sqliteOsSeek函數(shù)傳入指定的位移來完成瓦堵。文件位移是一個整數(shù)基协，它表示要讀寫的位置距離文件起始處的字節(jié)數(shù)。

頁（Pager）

????頁是數(shù)據(jù)庫在文件系統(tǒng)里的數(shù)據(jù)存儲的最小單元菇用。它是數(shù)據(jù)庫從磁盤讀取數(shù)據(jù)的最小單位澜驮，當(dāng)數(shù)據(jù)庫需要加裝數(shù)據(jù)的時候，它會一次性讀取整個頁的數(shù)據(jù)惋鸥。如果被加載的頁被訪問比較頻繁的話杂穷，它就會被保存在數(shù)據(jù)庫引擎的緩存里悍缠。頁都會被編號，起始號是1耐量。第一頁被稱為根頁飞蚓，而且一個頁的大小是固定的。

    Open pager with the given file name
    */
    int sqlitepager_open(Pager **ppPager,const char *zFilename,int nPage,int nEx);

    Get page specified by the page number
    */
    int sqlitepager_get(Pager *pPager, Pgno pgno, void **ppPage);

    Start to write data into a page specified in pData
    */
    int sqlitepager_write(void *pData);

    Commit page changes into the file
    */
    int sqlitepager_commit(Pager*);

    Close the connection to the file
    */
    int sqlitepager_close(Pager *pPager);

Btree

????Btree是一個用來存儲數(shù)據(jù)的樹狀數(shù)據(jù)結(jié)構(gòu)拴鸵。最簡單的Btree是二叉樹（Binary tree）玷坠。數(shù)據(jù)庫使用Btree來保存索引，用以提高其性能劲藐。Btree的每個節(jié)點都會保存一列用來進行索引的值八堡。而且你可以為數(shù)據(jù)表的每一列都創(chuàng)建一個Btree索引。每個Btree都包含一個根節(jié)點聘芜，它是搜索的起始點兄渺。

“游標(biāo)（Cursor）”是用來標(biāo)識Btree里的一條記錄的一個特殊指針。游標(biāo)通過頁碼（page id）和位置（offset）來索引一個數(shù)據(jù)記錄汰现。SQLite通過master_table這個表來存儲數(shù)據(jù)表元數(shù)據(jù)挂谍，并且master_table的數(shù)據(jù)是存放在數(shù)據(jù)庫的第一個數(shù)據(jù)頁里。

    Open file connection to a page file name specified by zFileName with 
    nCache size cache
    */
    int sqliteBtreeOpen(const char *zFilename, int mode, int nCache, Btree **ppBtree)

    Start transaction. This function should called before any btree modification 
    operations
    */
    int sqliteBtreeBeginTrans(Btree *pBt)

    Insert key pKey with nKey byte and value pData with nData byte put 
    into the Btree
    */
    int sqliteBtreeInsert(BtCursor *pCur, const void *pKey, int nKey, 
      const void *pData, int nData)

    Write data into the file
    */
    int sqliteBtreeCommit(Btree *pBt)

    Move cursor to the matching pKey with nKey bytes
    */
    int sqliteBtreeMoveto(BtCursor *pCur, const void *pKey, int nKey, int *pRes)

VDBE（虛擬數(shù)據(jù)庫系統(tǒng)瞎饲，Virtual Database Engine）

????虛擬數(shù)據(jù)庫系統(tǒng)（VDBE）是一個可以運行代碼生成器生成的指令的虛擬機口叙。包括insert，delete嗅战，update妄田，select在內(nèi)的SQL指令都會被轉(zhuǎn)換成一系列指令，然后這些指令都會在虛擬機上運行驮捍。每個指令包含三個輸入?yún)?shù)疟呐，分別是p1，p2和p3东且。你可以把它們看著是函數(shù)的輸入?yún)?shù)類似启具。

????以下是我為下面這個select語句構(gòu)造的執(zhí)行指令棧。PC是程序計數(shù)器的指令id珊泳。SQLite中比較有趣的一點是鲁冯，你可以通過在SQL語句前面加上explain命令來獲取該SQL對應(yīng)虛擬數(shù)據(jù)庫系統(tǒng)（VDBE）的指令。

explain select * from foo;

編譯器

????分詞器隘竭，解析器以及代碼生成器組合起來就是編譯器塘秦，它可以生成在虛擬數(shù)據(jù)庫引擎（VDBE）上執(zhí)行的指令。分詞器通過掃描SQL語句來生成一系列的標(biāo)識符（Token）动看。然后尊剔，再校驗語法并生成語法樹（parse tree）。最后菱皆，代碼生成器將語法樹轉(zhuǎn)換成一段SQLite指令的小程序须误。

結(jié)論

????SQLite是一個簡單，輕量級仇轻，高性能的關(guān)系型數(shù)據(jù)庫京痢，它被廣泛用于軟件系統(tǒng)設(shè)計。早期版本的SQLite的實現(xiàn)架構(gòu)簡單篷店，并且代碼可讀性非常高祭椰。頁提供了一種將文件讀取封裝成對固定大小數(shù)據(jù)塊進行操作的抽象層。Btree提供了在內(nèi)存里高效存儲和訪問數(shù)據(jù)的途徑船庇。最后吭产，當(dāng)SQL被加載到SQLite數(shù)據(jù)庫的時候，會被轉(zhuǎn)換成SQLite機器碼并在虛擬數(shù)據(jù)庫系統(tǒng)（VDBE）上執(zhí)行鸭轮。最終結(jié)果會通過API返回給用戶臣淤。