世界上最流行的數(shù)據(jù)庫是什么？

Oracle? MySQL? PostGreSQL?

都不是，答案是SQLite。

你可能沒聽說過它，但是它就在你身邊的：

每一臺智能手機中（Android 和iOS）

每一臺Mac電腦中

每一臺Windows 10 電腦中

每一個主要的瀏覽器中（Chrome, Firefox,Safari）

大部分的機頂盒當中

每個PHP和Python安裝目錄中

很多流行的桌面應用(微信、QQ、 DropBox、 Skype、iMessage、WhatsApp、 Adobe Acrobat Reader....)

......

不信的話可以在電腦中搜索一下 “*.db”，看看能發(fā)現(xiàn)多少個。

每個流行的軟件都是為了解決一個痛點問題，SQLite也不例外。

時光回到2000年，Richard Hipp為美國海軍的驅逐艦開發(fā)軟件，這個軟件要對船上所有的閥門進行管理和操作。

當時，美國海軍使用的是IBM的Informix數(shù)據(jù)庫，這個軟件需要通過網(wǎng)絡訪問它來讀取數(shù)據(jù)。

但是有時候Informix所在的服務器會掛掉，閥門管理軟件就會報錯：不能連接到服務器！

更糟糕的是，他們對這個數(shù)據(jù)庫服務器沒有任何控制權，結果不出意外，誰彈的報錯對話框，誰背鍋。

為了解決這個問題，Richard團隊想了一招：將所有數(shù)據(jù)讀入內存！

好在他們的程序不需要增、刪、改數(shù)據(jù)，只要將數(shù)據(jù)全部讀入內存，就萬事大吉了。

此時，Richard腦中閃現(xiàn)出一個大膽的想法：既然如此，還要啥Informix呢？

直接從本地硬盤讀取數(shù)據(jù)就得了！這樣只要計算機能正常工作，程序就能正常運行。

這其實就是嵌入式數(shù)據(jù)庫，數(shù)據(jù)庫和用戶程序位于同一臺機器的同一個進程當中。

圖片

不過當時還沒有這樣的數(shù)據(jù)庫，這時，一位同事提醒Richard：“那你為什么不自己寫一個呢？”

當時紐特·金里奇和比爾·克林頓正在“打架”，所有政府合同都暫停執(zhí)行，所以Richard失業(yè)了幾個月。

沒事兒可干的Richard決定把這個嵌入式數(shù)據(jù)庫給寫出來。

于是，SQLite誕生了！

SQLite第一版的提交歷史記錄

SQLite第一版其實也是個套殼數(shù)據(jù)庫

就像今天TiDB使用RocksDB作為其存儲引擎，SQLite的第一版也只不過是在GDBM——可謂是NoSQL的鼻祖——上套了個殼。SQLite第一版的README文件中這樣寫道：

SQLite: An SQL Database Built Upon GDBM

GDBM衍生自DBM，而DBM（DataBase Manager的縮寫）是來自Unix的鍵值數(shù)據(jù)庫（key-valuedatabase），支持通過主鍵快速訪問數(shù)據(jù)，最初由計算機界的大佬Ken Thompson編寫。

所以，我們可以把GDBM的數(shù)據(jù)庫看作是存儲在硬盤上的哈希表。

GDBM僅僅以代碼庫（library）的形式向用戶提供一系列API，并不支持SQL語句。

雖然是套殼數(shù)據(jù)庫，但這個殼套得可不簡單。

上世紀90年代，編程語言界誕生了不少基于字節(jié)碼的語言，也因此出現(xiàn)了各種虛擬機。

例如，Java有JVM，PHP有Zend Engine，Python和Ruby也有自己的虛擬機。

擁有豐富編譯器經(jīng)驗的Richard也如法炮制，他也搞了虛擬機，將SQL語句轉化為字節(jié)碼，在虛擬機上執(zhí)行。

下面我們就來梳理一下SQLite第一版的架構，看看它是怎么套殼GDBM的。

SQLite第一版的架構

SQLite采用了典型的分層架構，一條SQL語句依次經(jīng)過

• 用戶接口（UI）層 
• 詞法分析器（Tokenizer）層 
• 語法解析器（Parser）層 
• 字節(jié)碼生成器（Code Generator）層 
• 虛擬機（虛擬數(shù)據(jù)庫引擎〔Virtual DataBase Engine〕）層 
• 數(shù)據(jù)庫后端（DataBase BackEnd〔DBBE〕）層

最終到達GDBM數(shù)據(jù)庫層，變?yōu)閷DBM數(shù)據(jù)庫的CRUD（通過調用GDBM提供的API）。

這些層在下圖中都用方框表示，方框內寫有該層的名稱，名稱下方括號內是實現(xiàn)層的源代碼文件。

SQLite第一版的架構

以圖中的INSERT INTO語句為例，首先，UI層將用戶輸入的這條SQL語句傳遞給Tokenizer（詞法分析器）。

Tokenizer會將一條SQL語句分割為Token的序列（通過sqliteGetToken()函數(shù)），類似[INSERT,INTO, examp, VALUES, (, 'Hello, World!'...]。

接下來由Parser（語法分析器）根據(jù)語法規(guī)則（如圖中的cmd::= INSERT INTO...）解析來自Tokenizer的Token的序列，并調用與匹配的語法規(guī)則對應的處理函數(shù)，這里是INSERT語句的語法規(guī)則對應的處理函數(shù)sqliteInsert()。

值得一提的是，SQLite第一版中的詞法分析器和語法分析器（叫做Lemon）都是Richard自己編寫的，他從一開始就沒有采用lex和yacc等成熟的現(xiàn)成工具，這或許是源于他對自由的極度渴望。

文章最后我們會聊聊Richard在軟件世界中的生存態(tài)度，到時候就更能理解Richard為什么要重復造輪子了。

回到架構圖中，在語法規(guī)則處理函數(shù)sqliteInsert()中（位于字節(jié)碼生成器〔Code Generator〕層），SQL語句被翻譯（通過sqliteVdbeAddOp()函數(shù)）成了如下圖左側黃色方框中的字節(jié)碼（OpCode）（我這里進行了簡化，實際的字節(jié)碼要比這里的復雜一些）。

可以看到，此時一條INSERT語句被分解成為若干簡單的指令：

Open examp——打開名為examp的數(shù)據(jù)表；

Integer 99——添加一個整型的數(shù)據(jù)項，值為99；

Put——向數(shù)據(jù)表中寫入記錄……

SQLite第一版的架構（續(xù)）

當虛擬機（也叫VDBE，Virtual DataBaseEngine，虛擬數(shù)據(jù)庫引擎）接收到這一串指令后，就會根據(jù)指令的類型（是Open、是Put，還是……）調用對應的函數(shù)。

如對于Put這個指令，就需要調用sqliteDbbePut()來處理。

現(xiàn)在處理流程終于進入到了DBBE（DataBase BackEnd，數(shù)據(jù)庫后端）層，這里才是最貼近GDBM的那層殼。

既然Put指令（對應sqliteDbbePut()函數(shù)）要插入記錄，那就調用gdbm_store()這個GDBM的API完成數(shù)據(jù)寫入。

至此，SQLite第一版就處理完了一條INSERT語句，向examp表中插入了一條新紀錄("Hello,World!", 99)。

從設計模式的角度看，DBBE層相當于接口，而GDBM相當于實現(xiàn)類；從MySQL架構的角度看，DBBE層相當于MySQLServer層，而GDBM相當于MyISAM或InnoDB，是一種Pluggable Storage Engine。

也許Richard一開始就想到了不能在GDBM一棵樹上吊死，底層的存儲引擎應該是可以替換的。

果然，到了2001年，Richard就決定干掉GDBM了。

他從書架上取出高德納（Donald Knuth）的巨著The Art ofComputer Programming（《計算機程序設計藝術》），用B樹替代掉了GDBM。

用B樹替代GDBM的提交記錄

B樹替代GDBM后，README文件的diff

“末日準備者”Richard

最后我們來聊一聊Richard這個人。

世界上有這樣一類人，他們在一小塊土地上自己種植食物，生活完全靠自給自足，甚至不使用自來水、電、天然氣等公共設施。

人們稱他們?yōu)樯嬷髁x者（survivalist）或末日準備者（preppers）。

而Richard仿佛也是他們之中的一員，時刻都在為軟件世界的“末日”做著準備：

要是現(xiàn)有的語法分析器不能滿足我的需求怎么辦？——那我自己寫一個吧——于是有了Lemon。

要是版本控制系統(tǒng)不好用怎么辦？——那我自己寫一個吧——于是有了Fossil。

要是文本編輯器……——那我自己寫一個吧。

在一檔名為FLOSS Weekly的訪談節(jié)目的結尾（我搬運到了B站??https://www.bilibili.com/video/BV1Hj411W7xc/?t=2944.1）

主持人問了Richard一個例行問題：“你最喜歡的編輯器是？”

“當然是我自己寫的那個，哈哈哈”

為了管理SQLite的代碼迭代，Richard還自己造了個叫做Fossil的版本控制系統(tǒng)。

更有意思的是，SQLite的源代碼使用Fossil來管理，而Fossil又依賴SQLite來存儲代碼倉庫的信息，這就產(chǎn)生了一個在后人看來類似先有雞還是先有蛋的問題。

毫不夸張地說，除了C編譯器和libc中的一些東西之外，SQLite基本上只依賴Richard自己構建的軟件。

而這正是Richard所要的自由——自己編寫的組件越多，就越自由，就越少受到束縛。

日本動畫片《新世紀福音戰(zhàn)士EVA》電視版的第26集也有一段對“自由”的描述（??https://www.bilibili.com/video/BV1yK411b7AT/），看過后可能會覺得絕對的自由會讓人感到不安、寂寞、迷茫。

而Richard卻堅定地認為，如果想要自由，就得自己動手。如果有人跟你說“讓我們?yōu)槟憬鉀Q問題”，那你就要有所警惕，因為他們真正想說的是，“我們將會剝奪你的一些自由”。

Richard不想讓別人控制自己的命運，他要牢牢掌握自己的命運，縱使會付出很多努力。

（完）

本文來自“胡譯胡說” 的投稿。

如需轉載，請通過作者微信公眾號coderising獲取授權。