世界上最流行的数据库是什么？

Oracle? MySQL? PostGreSQL?

都不是，答案是SQLite。

你可能没听说过它，但是它就在你身边的：

每一台智能手机中（Android 和iOS）

每一台Mac电脑中

每一台Windows 10 电脑中

每一个主要的浏览器中（Chrome, Firefox,Safari）

大部分的机顶盒当中

每个PHP和Python安装目录中

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

……

不信的话可以在电脑中搜索一下 “*.db”，看看能发现多少个。

每个流行的软件都是为了解决一个痛点问题，SQLite也不例外。

时光回到2000年，Richard Hipp为美国海军的驱逐舰开发软件，这个软件要对船上所有的阀门进行管理和操作。

当时，美国海军使用的是IBM的Informix数据库，这个软件需要通过网络访问它来读取数据。

但是有时候Informix所在的服务器会挂掉，阀门管理软件就会报错：不能连接到服务器！

更糟糕的是，他们对这个数据库服务器没有任何控制权，结果不出意外，谁弹的报错对话框，谁背锅。

为了解决这个问题，Richard团队想了一招：将所有数据读入内存！

好在他们的程序不需要增、删、改数据，只要将数据全部读入内存，就万事大吉了。

此时，Richard脑中闪现出一个大胆的想法：既然如此，还要啥Informix呢？

直接从本地硬盘读取数据就得了！这样只要计算机能正常工作，程序就能正常运行。

这其实就是嵌入式数据库，数据库和用户程序位于同一台机器的同一个进程当中。

不过当时还没有这样的数据库，这时，一位同事提醒Richard：“那你为什么不自己写一个呢？”

当时纽特·金里奇和比尔·克林顿正在“打架”，所有政府合同都暂停执行，所以Richard失业了几个月。

没事儿可干的Richard决定把这个嵌入式数据库给写出来。

于是，SQLite诞生了！

SQLite第一版的提交历史记录

SQLite第一版其实也是个套壳数据库

就像今天TiDB使用RocksDB作为其存储引擎，SQLite的第一版也只不过是在GDBM——可谓是NoSQL的鼻祖——上套了个壳。SQLite第一版的README文件中这样写道：

SQLite: An SQL Database Built Upon GDBM

GDBM衍生自DBM，而DBM（DataBase Manager的缩写）是来自Unix的键值数据库（key-valuedatabase），支持通过主键快速访问数据，最初由计算机界的大佬Ken Thompson编写。

所以，我们可以把GDBM的数据库看作是存储在硬盘上的哈希表。

GDBM仅仅以代码库（library）的形式向用户提供一系列API，并不支持SQL语句。

虽然是套壳数据库，但这个壳套得可不简单。

上世纪90年代，编程语言界诞生了不少基于字节码的语言，也因此出现了各种虚拟机。

例如，Java有JVM，PHP有Zend Engine，Python和Ruby也有自己的虚拟机。

拥有丰富编译器经验的Richard也如法炮制，他也搞了虚拟机，将SQL语句转化为字节码，在虚拟机上执行。

下面我们就来梳理一下SQLite第一版的架构，看看它是怎么套壳GDBM的。

SQLite第一版的架构

SQLite采用了典型的分层架构，一条SQL语句依次经过

  • 用户接口（UI）层

  • 词法分析器（Tokenizer）层

  • 语法解析器（Parser）层

  • 字节码生成器（Code Generator）层

  • 虚拟机（虚拟数据库引擎〔Virtual DataBaseEngine〕）层

  • 数据库后端（DataBase BackEnd〔DBBE〕）层

最终到达GDBM数据库层，变为对GDBM数据库的CRUD（通过调用GDBM提供的API）。

这些层在下图中都用方框表示，方框内写有该层的名称，名称下方括号内是实现层的源代码文件。

以图中的INSERT INTO语句为例，首先，UI层将用户输入的这条SQL语句传递给Tokenizer（词法分析器）。

Tokenizer会将一条SQL语句分割为Token的序列（通过sqliteGetToken()函数），类似[INSERT,INTO, examp, VALUES, (, ‘Hello, World!’…]。

接下来由Parser（语法分析器）根据语法规则（如图中的cmd::= INSERT INTO…）解析来自Tokenizer的Token的序列，并调用与匹配的语法规则对应的处理函数，这里是INSERT语句的语法规则对应的处理函数sqliteInsert()。

值得一提的是，SQLite第一版中的词法分析器和语法分析器（叫做Lemon）都是Richard自己编写的，他从一开始就没有采用lex和yacc等成熟的现成工具，这或许是源于他对自由的极度渴望。

文章最后我们会聊聊Richard在软件世界中的生存态度，到时候就更能理解Richard为什么要重复造轮子了。

回到架构图中，在语法规则处理函数sqliteInsert()中（位于字节码生成器〔Code Generator〕层），SQL语句被翻译（通过sqliteVdbeAddOp()函数）成了如下图左侧黄色方框中的字节码（OpCode）（我这里进行了简化，实际的字节码要比这里的复杂一些）。

可以看到，此时一条INSERT语句被分解成为若干简单的指令：

Open examp——打开名为examp的数据表；

Integer 99——添加一个整型的数据项，值为99；

Put——向数据表中写入记录……

SQLite第一版的架构（续）

当虚拟机（也叫VDBE，VirtualDataBaseEngine，虚拟数据库引擎）接收到这一串指令后，就会根据指令的类型（是Open、是Put，还是……）调用对应的函数。

如对于Put这个指令，就需要调用sqliteDbbePut()来处理。

现在处理流程终于进入到了DBBE（DataBaseBackEnd，数据库后端）层，这里才是最贴近GDBM的那层壳。

既然Put指令（对应sqliteDbbePut()函数）要插入记录，那就调用gdbm_store()这个GDBM的API完成数据写入。

至此，SQLite第一版就处理完了一条INSERT语句，向examp表中插入了一条新纪录(“Hello,World!”, 99)。

从设计模式的角度看，DBBE层相当于接口，而GDBM相当于实现类；从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这个人。

世界上有这样一类人，他们在一小块土地上自己种植食物，生活完全靠自给自足，甚至不使用自来水、电、天然气等公共设施。

人们称他们为生存主义者（survivalist）或末日准备者（preppers）。

而Richard仿佛也是他们之中的一员，时刻都在为软件世界的“末日”做着准备：

要是现有的语法分析器不能满足我的需求怎么办？——那我自己写一个吧——于是有了Lemon。

要是版本控制系统不好用怎么办？——那我自己写一个吧——于是有了Fossil。

要是文本编辑器……——那我自己写一个吧。

在一档名为FLOSS Weekly的访谈节目的结尾（我搬运到了B站https://www.bilibili.com/video/BV1Hj411W7xc/?t=2944.1）

主持人问了Richard一个例行问题：“你最喜欢的编辑器是？”

“当然是我自己写的那个，哈哈哈”

为了管理SQLite的代码迭代，Richard还自己造了个叫做Fossil的版本控制系统。

更有意思的是，SQLite的源代码使用Fossil来管理，而Fossil又依赖SQLite来存储代码仓库的信息，这就产生了一个在后人看来类似先有鸡还是先有蛋的问题。

毫不夸张地说，除了C编译器和libc中的一些东西之外，SQLite基本上只依赖Richard自己构建的软件。

而这正是Richard所要的自由——自己编写的组件越多，就越自由，就越少受到束缚。

日本动画片《新世纪福音战士EVA》电视版的第26集也有一段对“自由”的描述，看过后可能会觉得绝对的自由会让人感到不安、寂寞、迷茫。

而Richard却坚定地认为，如果想要自由，就得自己动手。如果有人跟你说“让我们为你解决问题”，那你就要有所警惕，因为他们真正想说的是，“我们将会剥夺你的一些自由”。

Richard不想让别人控制自己的命运，他要牢牢掌握自己的命运，纵使会付出很多努力。