SQLite 的第一版不过是在 GDBM 上套了个壳

2024-04-02
北京
本文字数：3414 字
阅读完需：约 11 分钟

今天，SQLite 可谓是部署范围最广、安装次数最多（据说安装量排名世界第二）的数据库引擎。从平凡的 CRUD 项目到著名的 App，从浏览器到操作系统，从手机到 IoT，到处都能看到 SQLite 的身影。而 SQLite 的诞生过程却很偶然。

时光倒回到 2000 年，那时还没有维基百科，人们无法询问 Google 如何写一个数据库。SQLite 的作者 D. Richard Hipp 失业在家，凭借着之前构建编译器的经验，实现了一个不需要服务器的数据库引擎。这就是 SQLite 的第一版。

图 1 SQLite 的作者 D. Richard Hipp（美国 1961-04-09～）

SQLite 第一版的诞生过程

Richard 曾带领团队为一艘全副武装的战列舰开发程序。他们的程序依赖一个不太可靠的 Informix 数据库服务器。这个数据库服务器正常运行时倒是没有问题，但一旦宕机，就会导致他们的程序无法正常运行，同时还会弹出一个对话框，上面写着“Can’t connect to database server”（无法连接数据库服务器）。更糟糕的是，他们对这个数据库服务器没有任何控制权，结果不出意外，谁弹的报错对话框，谁背锅。

为了提升程序的可靠性，Richard 团队先将所有数据读入内存，好在他们的程序不需要增、删、改数据，所以只要将数据全部读入内存，就万事大吉了。此时，Richard 脑中闪现出一个大胆的想法：既然如此，为什么还需要数据库服务器呢？为什么不能直接从硬盘取数据呢？如果直接从硬盘读数据，那只要计算机能正常运行，程序就能正常运行。

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

此言一出没过多久，因项目被终止，Richard 失业了。但也是时候开始造数据库了。

“咔嚓一个大雷，我的妈呀”，SQLite 诞生了。

图 2 SQLite 第一版的提交历史记录 https://sqlite.org/src/timeline?a=2000-05-01

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

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

SQLite: An SQL Database Built Upon GDBM

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

不过 GDBM 实际上只是一个数据库引擎，仅以代码库（library）的形式向用户提供一系列 API，并不支持 SQL 语句。我们可以将 GDBM 的数据库看作是存储在硬盘上的哈希表。

虽然是套壳数据库，但这个壳套得可不简单。由于有构建编译器的经验，Richard 将每个 SQL 语句都翻译为一个“程序”，这个程序是使用类似某种汇编语言（姑且称为 SQL 字节码）编写的，为此他又编写了一个编译器，将 SQL 语句转化为字节码，以及一个能够解析执行 SQL 字节码的虚拟机。

上世纪 90 年代的确诞生了不少基于字节码或 OpCode 的语言，也因此出现了各种虚拟机。Java 有 JVM，PHP 有 Zend Engine，Python 和 Ruby 也有自己的虚拟机。但现在看来，谁能想到还有人把 SQL 也编译成字节码放到虚拟机上执行，而 Richard 当年就是这么做的。

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

SQLite 第一版的架构

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

用户接口（UI）层 →
词法分析器（Tokenizer）层 →
语法解析器（Parser）层 →
字节码生成器（Code Generator）层 →
虚拟机（虚拟数据库引擎〔Virtual DataBase Engine〕）层 →
数据库后端（DataBase BackEnd〔DBBE〕）层

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

这些层在下图中都用方框表示，方框内写有该层的名称，名称下方括号内是实现层的源代码文件（第一版的代码仓库 https://www.sqlite.org/src/tree?ci=e8521fc10dcfa02f）。

图 3 SQLite 第一版的架构

以图中的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()函数）成了如图 4 左侧黄色方框中的字节码（OpCode）（我这里进行了简化，实际的字节码要比这里的复杂一些），可以看到，此时一条 INSERT 语句被分解成为若干简单的指令：Open examp——打开名为examp的数据表；Integer 99——添加一个整型的数据项，值为99；Put——向数据表中写入记录……

图 4 SQLite 第一版的架构（续）

当虚拟机（也叫 VDBE，Virtual DataBase Engine，虚拟数据库引擎）接收到这一串指令后，就会根据指令的类型（是Open、是Put，还是……）调用对应的函数。如对于Put这个指令，就需要调用sqliteDbbePut()来处理。

现在处理流程终于进入到了 DBBE（DataBase BackEnd，数据库后端）层，这里才是最贴近 GDBM 的那层壳。既然Put指令（对应sqliteDbbePut()函数）要插入记录，那就调用gdbm_store()这个 GDBM 的 API 完成数据写入。从设计模式的角度看，DBBE 层相当于接口，而 GDBM 相当于实现类；从 MySQL 架构的角度看，DBBE 层相当于 MySQL Server 层，而 GDBM 相当于 MyISAM 或 InnoDB，是一种 Pluggable Storage Engine。也许 Richard 一开始就想到了不能在 GDBM 一棵树上吊死，底层的存储引擎应该是可以替换的。

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

SQLite 的创造者 Richard

最后我们来谈一谈 SQLite 的创造者 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 集也有一段对“自由”的描述（🎬https://www.bilibili.com/video/BV1yK411b7AT/），看过后可能会觉得绝对的自由会让人感到不安、寂寞、迷茫。而 Richard 却坚定地认为，如果想要自由，就得自己动手。如果有人跟你说“让我们为你解决问题”，那你就要有所警惕，因为他们真正想说的是，“我们将会剥夺你的一些自由”。Richard 不想让别人控制自己的命运，他要牢牢掌握自己的命运，纵使会付出很多努力。

时间来到 2001 年，Richard 又解除了一层枷锁。他从书架上取出高德纳（Donald Knuth）的巨著 The Art of Computer Programming（《计算机程序设计艺术》），用 B 树替代掉了 GDBM。