SQLite系统构架及虚拟机分析

摘  要： 就目前广泛使用的轻量级数据库SQLite的构架进行分析，特别是对其中的虚拟数据库引擎（VDBE）做了原理性的剖析，并结合实例，展示了SQLite的应用及SQLite内部VDBE指令程序的运行方式。
关键词： SQLite；构架；VDBE；虚拟机

    SQLite是遵守ACID的轻量级关系型数据库管理系统，完全免费、开源，无需任何配置也无需任何安装程序[1]。它广泛应用在各种嵌入式系统中，在iOS和Android等系统中都是集成在各自的库中。
    虚拟机是当前比较流行的一种软件构架，特别是在解释性编程语言领域。在安全领域，虚拟机也被用于实现软件的加密，是公认的一种非常高效且实用的技术手段。SQLite用较小规模的代码用C语言实现了一个程序虚拟机，提高了代码的独立性，降低了耦合性，同时保持了很高的效率。
1 SQLite数据库构架
    图1所示为SQLite系统的总体构架图[2]。整体上SQLite可以分为前端和后端：前端负责从用户数据到平台不相关的指令的转换；后端处理数据流，深入到具体数据库数据在磁盘上的操作，这些数据是和平台相关的。SQLite的平台无关性通过其内部实现的虚拟数据库引擎VDME（Virtual Database Engine)来完成，总地来说，就是将SQL语句先翻译成一种专门设计的语言，然后下层再调用平台相关的系统API接口，完成相应的功能。

    SQLite的源代码由96个C语言文件（.c和.h）组成，在编译之前会由Makefile生成一个完整的文件，即为可以在官方网站上下载的sqlite3.c和sqlite3.h等文件，然后编译形成所需要的库或者可执行文件。
    图1给出了SQLite的主要模块及相互之间的关系，以下将分别介绍各个部分的功能。
    (1)接口（Interface)
    SQLite库提供的对外不调用的接口大多数都在main.c、legacy.c和vdbeapi.c中，其他一些散布在源代码的不同部分。对接口的查询可以在文档中找到详细的介绍。为了避免命名上的冲突，所有外部可以调用的接口都以sqlite3_开头[3]。
    (2)SQL编译器（SQL Compiler)
    这是一个比较完整的编译器构架，分别完成词法分析、语法分析和中间代码生成。词法分析器(Tokenizer)由C语言实现，包含在tokenize.c中；语法分析器(Parser)由Lmon LALR(1)生成，和YACC/BISON类似，不兼容，但是生成的代码是可重入且线程安全的，代码包含在parse.c中；代码生成器（Code Generator）生成虚拟机执行的中间代码，包含的文件相对较多，例如select.c、update.c等，大多和SQL命令同名对应。
    (3)虚拟机VM（Virtual Machine）
    代码生成器生成的中间代码会通过VM执行。这部分后面会有更详细的分解。
    (4)B-Tree（B-树）
    数据库在磁盘上的操作都是通过B-树的，对应于数据库中的每一个表或者索引都会有相应的B-树。实现和接口分别在btree.c和btree.h中[4]。
    (5)页缓存（Page Cache）
    数据的读写都以Chunk为单位进行，这样可以提高效率。页缓存负责这部分工作，同时提供了回滚（rollback）等功能，并对数据库文件进行管理。实现和接口分别在pager.c和pager.h中。
    (6)系统接口（OS Interface）
    SQLite提供了一个系统抽象层，定义在os.h中。每个支持的平台有自己对应的实现文件，例如os_uinx.c和os_win.c(及相应的头文件os_unix.h和os_win.h)。
    (7)功能和测试（Utility和Test Code）
2 VDBE框架及关键源码分析
    虚拟数据库引擎VDBE(Virtual Database Engine)居于SQLite数据库的核心部分。从整个SQLite的构架可以看出，它处在整个系统的中间部分：前端代码完成对SQL语言的编译，相当于简化版本的一个编译器；后端完成物理上的操作，即利用B-Tree和Pager对物理硬盘上的数据进行实际的操作。VDBE完成了这个层次上的抽象链接。
    整个虚拟数据库引擎（VDBE）由若干个C语言文件组成，主题实现都包含在了vdbe.c（vdbe.h）中。vdbeInt.h定义了VDBE内部使用的各种结构和函数原型。vdbeaux.c实现了VDBE内部和整个SQLite构建VDBE程序需要的其他功能性函数代码。vebeaip.c包含了供外部接口函数(SQLite库外的应用程序，如sqlite3_bind系列函数)使用的一些结构。vdbemen.c 实现了在vdbe的存储管理。
    对于用户的SQL语句，编译器会生成一个虚拟机实例。虚拟机实例在内部和外部是不同的。对内看到的是一个vdbe结构的实例，这个结构定义在vdbeInt.h中，代码如下：
    struct Vdbe {
    sqlite3 *db;        /* 数据库连接 */
    Op *aOp;            /* 保存虚拟机的空间 */
    …                /* 其他指令 */
    int nOp;            /* 生成的指令的条数 */
    char *zSql;        /* SQL语句 */
    …                /* 其他指令 */
    SubProgram *pProgram;  /* 虚拟机使用的其他子程序，
链表 */
    };
    一个虚拟机实例可以有多个子程序，每个子程序可以由多条指令组成。下面是子程序的结构：
    struct SubProgram {
    VdbeOp *aOp;            /* 指令 */
    int nOp;                /* 指令条数 */
    int nMem;            /* 需要的内部空间 */
    int nCsr;                /* 需要的游标 */
    void *token;            /* 循环触发时需要的id */
    SubProgram *pNext;    /* 链表的下一个 */

    };
    现在的SQLite有142条操作指令，都定义在opcodes.h中，在vdbe.c中有相应的源代码，将解析一些指令作为代表，详细的技术文档可以查看官方文档。所有的指令大概可以分为3类：
    （1）数据操作：包含算术、逻辑运算、字符串操作等；
    （2）数据管理：主要关于内存和磁盘的操作。内存上如栈(stack)操作、数据的传送等，磁盘操作主要是B-Tree和Pager模块，包括打开及操作游标、事务的开始与结束等；
    （3）控制流：指令的跳转。
    SQL语句在生成VDBE程序后，每条指令包含了一个操作码(opcode)和至多5个操作数（operands:P1、P2、P3、P4和P5)。其中：
    （1）P1、P2、P3都是32 bit的带符号整数，它们通常引用的是寄存器。
    （2）P2在所有的有跳转功能的指令中表示目的地址。例如上面的第2条指令将会跳转到第10条指令，然后顺序执行。
    （3）P4可以是32 bit或者64 bit的带符号整型数据、字符串、BLOB数据(二进制大对象)、函数指针等其他多样的对象。
    （4）P5通常是无符号的字符，充当的是标识位。
    在SQLite的VDBE内部，所有的指令都是VdbeOp结构的一个实例(定义在vdbe.h中)，结构的定义也主要是这5个操作数。
    struct VdbeOp {
    u8 opcode;    /* 操作码类型 */
    …            /* 其他数据接口 */
    signed char p4type;    /* p4 的类型 */
    u8 p5;        /* p5是无符号字符型 */
    int p1;        /* 操作数1 */
    int p2;        /* 操作数2，通常是跳转指令的目的 */
    int p3;        /* 操作数3 */
    union { /* ... */ } p4;        /* p4 是一个联合，
可以有不同的类型 */
    …            /* 其他数据接口 */
};
    由代码生成器生成的程序交由VM执行。sqlite3_step()会触发内部vdbe解释生成的vdbe指令。指令的执行在如下的函数中进行(SQLITE_PRIVATE 即为static关键字)，此处去掉了烦琐的细节，只展示其中的关键结构和一个指令的执行。
    SQLITE_PRIVATE int sqlite3VdbeExec(
        Vdbe *p                /* VDBE 实例 */
    ) {
        int    pc;                /* 程序计数器 */
        Op    *aOp = p->aOp;    /* 得到所有的指令 */
        Op    *pOp;            /* 当前指令 */
        int    rc=    SQLITE_OK;    /* 返回值 */
        sqlite3* db = p->db;    /* 数据库连接实例 */
        u8 encoding = ENC(db);/* UTF-8编码 */
        …                /* 其他初始化代码 */
        switch ( pOp->opcode )    {    /* 在此之后就是一个
非常大的case代码
            case OP_Goto: {
                CHECK_FOR_INTERRUPT;
                pc=pOp->p2-1;/* 调整程序计数器 */
                break;
            }
            …    /* 其他的case指令 */
        }
        …        /* 其他指令 */
    }
    这个函数是整个VDBE的核心执行函数，虽然重要，但是代码的原理非常简单，就是一系列的switch-case语句。在相应的case情况下，会执行相应的底层代码，进行数据库的磁盘操作。
3 实验
3.1 数据库编程接口
    SQLite的编程模型比较简单，下面的例子给出了一个基本的框架。
    #include "sqlite3.h"
    #include <stdlib.h>
    int main(int argc, char **argv)
    {
        char        *file = "./test.db";/* 数据库文件 */
        sqlite3    *db = NULL;    /* 数据库连接实例 */
        int        rc = 0;        /* 返回值 */
        sqlite3_initialize();        /* 初始库 */
        rc= sqlite3_open_v2(file, &db,
SQLITE_OPEN_READWRITE, NULL);
        /* 准备SQL语句，生成VDBE程序 */
        sqlite3_stmt    *stmt = NULL:
        rc=sqlite3_prepare_v2(db, "SELECT * FROM FILM",
 -1, &stmt, NULL);
            if (rc != SQLITE_OK) exit(-1);
        while (sqlite3_step(stmt) == SQLITE_ROW) {
            const char *data = (const char*)
sqlite3_column_text(stmt, 0);
            printf("%sn", data data:"[NULL]");
        }
        sqlite3_finalize(stmt);
        sqlite3_close(db);            /* 关闭 */
        sqlite3_shutdown();            /* 释放资源 */
    }
    在上面的例子中，使用了sqlite3_prepare_v2()和sqlite3_
step()函数，这是和内部的虚拟机联系非常紧密的两个函数，也是了解SQLite虚拟机的两个点。sqlite3_prepare_v2()完成的是将SQL语句提交给SQL编译器，编译成VDBE指令程序，sqlite3_step()将驱动VDBE执行指令程序。
    从应用上来说，这仅仅是最简单的数据库应用框架，更多的接口信息可以查看官方的文档。
3.2 VDBE程序分析
    在官方提供的下载中，有编译好的命令行可执行程序，可以作为完全的SQLite数据库管理工具。同时，它也考虑了一些Debug和Test功能，可以利用它们深入了解SQLite的内部机制。可以利用SQLite命令行程序中的explain命令查看由代码生成器生成的中间代码的形式，这只需要在相应的SQL代码前面加上explain就可以了。如以搜索的命令行显示（如图2所示，箭头表示实际执行顺序）：
    图2中，“addr”列是虚拟机的地址编号，并不是指令执行的顺序，由于跳转指令的存在，用箭头标示出了指令运行的实际顺序，也可以在SQLite编译时指定相应的选项，然后利用指令“pragma vdbe_trace=on;”详细地看到指令的运行过程和堆栈的变化情况。

    指令0～指令12都是对SQLite数据库内部的准备：由指令1跳转到指令10，指令10（Transaction）开始一个事务，指令11（VerifyCookie）在执行一个指令前检查数据库模式是否发生了变化，当发生了变化时要重置，指令12（TableLock）将要读的数据库表锁起来，指令13（Goto）跳转到指令2。
    从指令2开始是实际的对数据库的操作了。指令2(OpenRead)会打开一个数据库表的只读游标，P1作为这个游标的标志，P2是打开的数据库表的根页（root page），P3==0表明是主数据库，P4表明数据库有两列，P5说明是以P2的值作为根页。（OpenRead指令的各个操作数还可以有其他含义，这里只是针对这条SQL语句的解释，请查看技术文档。)指令3(Rewind)～指令7(Next)完成了对所有查询数据的遍历。指令8(Close)关闭游标，指令9（Halt）结束这个VDBE程序。
    VDBE对上层提供的就是这样的接口，而对下层将是调用相应的接口实现相应的功能，并由此完成模块上的解耦合。
    由VDBE的定义、代码分析及以上的实验，可以总结出SQLite的整体构架：
    外部调用SQLite接口函数sqlite3_prepare(), SQL语句通过SQL编译器生成对应的VDBE指令程序；
    内部调用sqlite3_step()驱动，内部执行sqlite3VdbeEx-
ec()，switch-case语句执行相应指令。底层通过B-Tree和Pager实现对磁盘数据库文件的管理，如图3所示。
    在实际应用中，可以设计一个面向应用的指令集，利用程序虚拟机设计中间抽象层，提高平台通用性。同时程序虚拟机也为语言虚拟机、系统虚拟机及安全沙盒等技术提供了技术基础。

参考文献
[1] OWENS M.The definitive guide to SQLite[M].Apress，2006.
[2] KREIBICH J A.Using SQLite[M].O'Reilly Media，2010.
[3] 李蔚，陈亚峰.嵌入式数据库SQLite及其应用研究[J].沿海企业与科技，2010(10)：45-47.
[4] 杜国祥，石俊杰.SQLite嵌入式数据库的应用[J].电脑编程技巧与维护，2010(14)：43-46.