SQLite剖析之体系结构

1.通过官方的SQLite架构文档,理清大体的系统层次:Architecture of SQLite
2.阅读SQLite Documentation中Technical/Design Documentation章节(根据所在层次阅读代码,对应章节描述进行理解。)
应用层角度,从API(List Of SQLite Functions)角度切入,掌握API文档中所有参数的使用。
3.下载源码包sqlite-src-*.zip,在其src目录下包含了所有源码文件。注意若要编译SQLite库则下载单一文件版本sqlite-amalgamation-*.zip。

架构(architecture)

SQLite采用了模块的设计,它由三个子系统,包括8个独立的模块构成。

1.接口(Interface)
接口由SQLite C API组成,也就是说不管是程序、脚本语言还是库文件,最终都是通过它与SQLite交互的(我们通常用得较多的ODBC/JDBC最后也会转化为相应C API的调用)。
2.编译器(Compiler)
在编译器中,分词器(Tokenizer)和分析器(Parser)对SQL进行语法检查,然后把它转化为底层能更方便处理的分层的数据结构—语法树,然后把语法树传给代码生成器(code generator)进行处理。而代码生成器根据它生成一种针对SQLite的汇编代码,最后由虚拟机(Virtual Machine)执行。
3.虚拟机(Virtual Machine)
架构中最核心的部分是虚拟机,或者叫做虚拟数据库引擎(Virtual Database Engine,VDBE)。它和Java虚拟机相似,解释执行字节代码。VDBE的字节代码由128个操作码(opcodes)构成,它们主要集中在数据库操作。它的每一条指令都用来完成特定的数据库操作(比如打开一个表的游标)或者为这些操作栈空间的准备(比如压入参数)。总之,所有的这些指令都是为了满足SQL命令的要求(关于VM,后面会做详细介绍)。
4.后端(Back-End)
后端由B-树(B-tree),页缓存(page cache,pager)和操作系统接口(即系统调用)构成。B-tree和page cache共同对数据进行管理。B-tree的主要功能就是索引,它维护着各个页面之间的复杂的关系,便于快速找到所需数据。而pager的主要作用就是通过OS接口在B-tree和Disk之间传递页面。

SQLite的体系结构

下图是一个体系结构图,显示了SQLite的主要组件以及各组件之间是如何相互关联的。

在内部,SQLite由以下几个组件组成:内核、SQL编译器、后端以及附件。SQLite通过利用虚拟机和虚拟数据库引擎(VDBE),使调试、修改和扩展SQLite的内核变得更加方便。所有SQL语句都被编译成易读的、可以在SQLite虚拟机中执行的程序集。SQLite支持大小高达2 TB的数据库,每个数据库完全存储在单个磁盘文件中。这些磁盘文件可以在不同字节顺序的计算机之间移动。这些数据以B+树(B+tree)数据结构的形式存储在磁盘上。SQLite根据该文件系统获得其数据库权限。

1、公共接口(Interface)
SQLite库的大部分公共接口由main.c, legacy.c和vdbeapi.c源文件中的函数来实现,这些函数依赖于分散在其他文件中的一些程序,因为在这些文件中它们可以访问有文件作用域的数据结构。sqlite3_get_table()例程在table.c中实现,sqlite3_mprintf()可在printf.c中找到,sqlite3_complete()则位于tokenize.c中。Tcl接口在tclsqlite.c中实现。SQLite的C接口信息可参考http://sqlite.org/capi3ref.html。
为了避免和其他软件的名字冲突,SQLite库的所有外部符号都以sqlite3为前缀,这些被用来做外部使用的符号(换句话说,这些符号用来形成SQLite的API)是以sqlite3_开头来命名的。

2、词法分析器(Tokenizer)
当执行一个包含SQL语句的字符串时,接口程序要把这个字符串传递给tokenizer。Tokenizer的任务是把原有字符串分割成一个个标识符(token),并把这些标识符传递给解析器。Tokenizer是用手工编写的,在C文件tokenize.c中。
在这个设计中需要注意的一点是,tokenizer调用parser。熟悉YACC和BISON的人们也许会习惯于用parser调用tokenizer。SQLite的作者已经尝试了这两种方法,并发现用tokenizer调用parser会使程序运行的更好。YACC会使程序更滞后一些。

3、语法分析器(Parser)

语法分析器的工作是在指定的上下文中赋予标识符具体的含义。SQLite的语法分析器使用Lemon LALR(1)分析程序生成器来产生,Lemon做的工作与YACC/BISON相同,但它使用不同的输入句法,这种句法更不易出错。Lemon还产生可重入的并且线程安全的语法分析器。Lemon定义了非终结析构器的概念,当遇到语法错误时它不会泄露内存。驱动Lemon的源文件可在parse.y中找到。
因为lemon是一个在开发机器上不常见的程序,所以lemon的源代码(只是一个C文件)被放在SQLite的”tool”子目录下。 lemon的文档放在”doc”子目录下。

4、代码生成器(Code Generator)

语法分析器在把标识符组装成完整的SQL语句后,就调用代码生成器产生虚拟机代码,以执行SQL语句请求的工作。代码生成器包含许多文件:attach.c, auth.c, build.c, delete.c, expr.c, insert.c,pragma.c, select.c, trigger.c, update.c, vacuum.c和where.c。这些文件涵盖了大部分最重要、最有意义的事情。expr.c处理SQL中表达式的代码生成。where.c处理SELECT、UPDATE和DELETE语句中WHERE子句的代码生成。文件attach.c, delete.c, insert.c, select.c, trigger.c, update.c和vacuum.c处理同名SQL语句的代码生成(这些文件在必要时都调用expr.c和where.c中的例程)。所有其他SQL语句的代码由build.c生成。文件auth.c实现sqlite3_set_authorizer()的功能。

5、虚拟机(Virtual Machine)

代码生成器生成的代码由虚拟机来执行。关于虚拟机更详细的信息可参考http://sqlite.org/opcode.html。总的来说,虚拟机实现一个专为操作数据库文件而设计的抽象计算引擎。它有一个存储中间数据的存储栈,每条指令包含一个操作码和不超过三个额外的操作数。
虚拟机本身被完整地包含在一个单独的文件vdbe.c中,它也有自己的头文件,其中vdbe.h定义虚拟机与SQLite库其他部分之间的接口,vdbeInt.h定义虚拟机私有的数据结构。文件vdbeaux.c包含被虚拟机使用的一些工具,和被库的其他部分用来构建VM程序的一些接口模块。文件vdbeapi.c包含虚拟机的外部接口,例如sqlite3_bind_…族的函数。单独的值(字符串、整数、浮点数、BLOB对象)被存储在一个叫Mem的内部对象中,在vdbemem.c中可找到它的实现。
SQLite使用回调风格的C语言程序来实现SQL函数,每个内建的SQL函数都用这种方式来实现。大多数内建的SQL函数(例如coalesce(), count(), substr(), 等等)可在func.c中找到。日期和时间转换函数可在date.c中找到。

6、B-树(B-Tree)
一个SQLite数据库使用B-树的形式存储在磁盘上,B-树的实现位于源文件btree.c中。数据库中的每个表和索引使用一棵单独的B-树,所有的B-树存放在同一个磁盘文件中。文件格式的细节被记录在btree.c开头的备注里。B-树子系统的接口在头文件btree.h中定义。

7、页面高速缓存(Page Cache)
B-树模块以固定大小的数据块形式从磁盘上请求信息,默认的块大小是1024个字节,但是可以在512和65536个字节之间变化。页面高速缓存负责读、写和缓存这些数据块。页面高速缓存还提供回滚和原子提交的抽象,并且管理数据文件的锁定。B-树驱动模块从页面高速缓存中请求特定的页,当它想修改页面、想提交或回滚当前修改时,它也会通知页面高速缓存。页面高速缓存处理所有麻烦的细节,以确保请求能够快速、安全而有效地被处理。
页面高速缓存的代码实现被包含在单一的C源文件pager.c中。页面高速缓存子系统的接口在头文件pager.h中定义。

8、OS接口
为了在POSIX和Win32操作系统之间提供移植性,SQLite使用一个抽象层来提供操作系统接口。OS抽象层的接口在os.h中定义,每种支持的操作系统有各自的实现:Unix使用os_unix.c,Windows使用os_win.c,等等。每个特定操作系统的实现通常都有自己的头文件,如os_unix.h, os_win.h等。

9、实用工具(Utilities)
内存分配和字符串比较函数位于util.c中。语法分析器使用的符号表用Hash表来维护,其实现位于hash.c中。源文件utf.c包含Unicode转换子程序。SQLite有自己的printf()实现(带一些扩展功能),在printf.c中,还有自己的随机数生成器,在random.c中。

10、测试代码(Test Code)
如果你计算回归测试脚本,超过一半的SQLite代码将被测试。主要代码文件中有许多assert()语句。另外,源文件test1.c通过test5.c和md5.c实现只用于测试目的的一些扩展。os_test.c后端接口用来模拟断电,以验证页面高速缓存的崩溃恢复机制。

SQLite Version3.3.6源代码文件结构

文件名称 大小byte 备注
API main.c 35414 SQLite Library的大部分接口
legacy.c 3734 sqlite3_exec的实现
table.c 5464 the sqlite3_get_table() and sqlite3_free_table()的实现,它们是sqlite3_exec的包装
preprare.c 17983 主要实现sqlite3_prepare()
分词器部分(Tokenizer) tokenize.c 14495 分词器的实现
语法分析器部分(Parser) parser.c 116917 分析器的实现,由Lemon实现
parser.h 6847 分析器内部定义的关键字
代码生成器(Code Generator) update.c 23878 处理UPDATTE语句
delete.c 21978 处理DELETE语句
insert.c 62026 处理INSERT语句
trigger.c 29065 处理TRIGGER语句
attach.c 15941 处理ATTACHT 和DEATTACH语句
select.c 112084 处理SELECT语句
where.c 75826 处理WHERE语句
vacuum.c 11005 处理VACUUM语句
pragma.c 34289 处理PRAGMA命令
expr.c 73963 处理SQL语句中的表达式
auth.c 7496 主要实现sqlite3_set_authorizer()
analyze.c 13149 实现ANALYZE命令
alter.c 18414 实现ALTER TABLE功能
build.c 104052 处理以下语法:CREATE TABLE, DROP TABLE, CREATE INDEX,DROP INDEX,creating ID lists,BEGIN TRANSACTION,COMMIT,ROLLBACK
func.c 34335 实现SQL语句的函数语句
date.c 24031 与日期和时间转换有关的函数
虚拟机(Virtual Machine) vdbeapi.c 23300 虚拟机提供上层模块调用的API实现部分
vdbe.c 143552 虚拟机的主要实现部分
vdbe.h 5309 定义了VDBE的接口,VdbeOp结构体(代表一条指令)
vdbeaux.c 58741 Vdbe.h的接口的实现
vdbeInt.h 17595 Vdbe.c的私有头文件,定义了VDBE常用的数据结构:Cursor——虚拟机中使用的游标, Mem——vdbe在内部把所有的SQL值当作一个Mem数据结构来处理,Vdbe——虚拟机数据结构
vdbemem.c 26375 操作”Mem”数据结构的函数
vdbefifo.c 2927
B-Tree部分 btree.h 5260 头文件,定义了B-tree提供的操作接口
btree.c 215570 B-Tree部分的主要实现,并定义了以下数据结构:Btree——Btree handler,BtCursor——使用的游标, BtLock——锁, BtShared——包含了一个打开的数据库的所有信息,MemPage——文件在内存存放在该数据结构中,aCellInfo
OS Interface部分 os.h 18355 定义了为上层模块提供的操作函数,并定义了以下数据结构:
OsFile——描述一个文件
IoMethod——OsFile所支持的操作函数(对所有架构都适用的OS Interface)
os.c 2866 对IoMethod中的函数的包装
os_win.c 42975 Windows平台下的OS Interface
os_unix.c 60831 Unix平台下的OS Interface
os_os2.c 28451 OS2平台下的OS Interface
其它部分 utf.c 20891 与UTF编码有关的函数
util.c 43575 一些实用函数,比如:
sqlite3Malloc(),sqlite3FreeX()
sqlite3.h 63873 SQLite的头文件,定义了提供给应用使用的API和数据结构。
sqliteInt.h 78886 定义了SQLite内部使用的接口和数据结构
printf.c 29556 主要实现与printf有关的函数
random.c 3078 随机数生成
hash.c 11896 SQLite使用的hash表
hash.h 4033 Hash 表头文件