架构 (architecture)

三个子系统,8 个独立模块

接口 (Interface)

ODBC/JDBC 最终是 SQLite C API 调用

编译器 (Compiler)

分词器(Tokenizer)和分析器 (Parser) 检查SQL,转为底层能更方便处理的分层的数据结构: 语法树

语法树 > 代码生成器 (code generator) > 针对 SQLite 的汇编代码 > 虚拟机 (Virtual Machine) 执行

虚拟机 (Virtual Machine)

架构最核心部分,或叫虚拟数据库引擎 (Virtual Database Engine,VDBE),解释执行字节代码

VDBE 由 128 个opcodes 构成

每条指令完成特定数据库操作 (如打开一个表的游标) 或者为这些操作栈空间的准备 (比如压入参数)

总之,所有的这些指令都是为了满足 SQL 命令的要求

后端 (Back-End)

由 B-tree,页缓存 (page cache,pager) 和操作系统接口 (即系统调用) 构成

B-tree 和 page cache 共同对数据进行管理

B-tree 索引维护着各个页面之间的复杂的关系,便于快速找到所需数据

pager 通过 OS 接口在 B-tree 和 Disk 之间传递页面


API

  • 核心 API

基本数据库操作:连接数据库,处理 SQL,遍历结果集

实用函数,如字符串转换,操作控制,调试和错误处理

  • 扩展 API

自定义 SQL 函数去扩展 SQLite

SQLite 3新特点

  1. 并发性能。锁升级模型 (lock escalation model),解决第二版的写进程饿死的问题 (DBMS 必须面对的问题)

    保证写进程先来先服务得到排斥锁 (Exclusive Lock)。甚至,写进程通过把结果写入临时缓冲区 (Temporary Buffer),可以在得到排斥锁之前就能开始工作。对于写要求较高的应用,性能可提高 400%

  2. 表用 B + 树,大大提高查询效率

  3. 存储模型。第二版只支持文本模型,扩展到支持 5 种本地数据类型

总之灵活性,特点和性能方面有很大的改进

主要数据结构 (The Principal Data Structures)

1

编程需要知道三个主要方面:API, 事务 (Transaction) 和锁 (Locks)

B-tree 和 pager 不是 API 的一部分,在事务和锁上起着关键作用


  • Connections 和 Statements

一个连接 (Connection) 代表在一个独立的事务环境下的一个连接 A (connection represents a single connection to a database as well as a single transaction context)

每一个 statement 都和一个 connection 关联,通常表示一个编译过的 SQL 语句,在内部,它以 VDBE 字节码表示

Statement 包括执行一个命令所需要一切,包括保存 VDBE 程序执行状态所需的资源,指向硬盘记录的 B - 树游标,以及参数等等

  • B-tree 和 pager

一个 connection 可以有多个 database 对象 — 一个主要的数据库以及附加的数据库,每一个数据库对象有一个 B-tree 对象,一个 B-tree 有一个 pager 对象 (不是面向对象的 “对象”)

Statement 最终都是通过 connection 的 B-tree 和 pager 从数据库读或者写数据,通过 B-tree 的游标 (cursor) 遍历存储在页面 (page) 中的记录

游标在访问页面之前要把数所从 disk 加载到内存,而这就是 pager 的任务

B-tree 需要的任何页面都会请求 pager 从 disk 读取数据,然后把页面 (page) 加载到页面缓冲区 (page cache),之后,B-tree 和与之关联的游标就可以访问位于 page 中的记录了

如果 cursor 改变了 page,为了防止事务回滚,pager 必须采取特殊的方式保存原来的 page

总的来说,pager 负责读写数据库,管理内存缓存和页面(page),以及管理事务,锁和崩溃恢复

总之,关于 connection 和 transaction

  1. 对数据库的任何操作,一个连接存在于一个事务下
  2. 一个连接决不会同时存在多个事务下

1

#include <stdio.h>
#include <stdlib.h>
#include "sqlite3.h"

#include <string.h>

int main(int argc, char **argv)
{
    int rc, i, ncols;
    sqlite3 *db;
    sqlite3_stmt *stmt;
    char *sql;
    const char *tail;
    // 打开数据
    rc = sqlite3_open("foods.db", &db);

    if(rc) {
        fprintf(stderr, "Can't open database: %s\n", sqlite3_errmsg(db));
        sqlite3_close(db);
        exit(1);
    }
    
    sql = "select * from episodes";
    // 预处理
    rc = sqlite3_prepare(db, sql, (int)strlen(sql), &stmt, &tail);

    if(rc != SQLITE_OK) {
        fprintf(stderr, "SQL error: %s\n", sqlite3_errmsg(db));
    }
    
    rc = sqlite3_step(stmt);
    ncols = sqlite3_column_count(stmt); 

    while(rc == SQLITE_ROW) {
        
        for(i=0; i < ncols; i++) {
            fprintf(stderr, "'%s' ", sqlite3_column_text(stmt, i));
        }

        fprintf(stderr, "\n");

        rc = sqlite3_step(stmt);
    }
    // 释放 statement
    sqlite3_finalize(stmt);
    // 关闭数据库
    sqlite3_close(db);

    return 0;    
}

事务 (Transaction)

事务的周期 (Transaction Lifecycles)

程序与事务之间有两件事值得注意

  1. 哪些对象在事务下运行——直接与 API 有关
  2. 事务的生命周期,什么时候开始,结束及在什么时候开始影响别的连接(对于并发性很重要)

一个连接(connection)可包含多个 (statement),而且每个连接有一个与数据库关联的 B-tree 和一个 pager

Pager 在连接中重要,管理事务、锁、内存缓存以及负责崩溃恢复 (crash recovery)

写操作时:在任何时候,只在一个事务下执行一个连接。回答了第一个问题

一般一个事务的生命和 statement 差不多,也可以手动结束它。默认自动提交,也可BEGIN..COMMIT 手动提交

锁的状态 (Lock States)

锁对于实现并发访问很重要,SQLite 锁实现相对较简单

通常持续时间和事务一致。一个事务开始,它会先加锁,事务结束,释放锁

但是系统在事务没有结束的情况下崩溃,下一个访问数据库的连接会处理这种情况

SQLite 有 5 种不同状态的锁,连接(connection)任何时候都处于其中的一个状态

相应的状态以及锁的生命周期

  • 事务可在 UNLOCKED(默认),RESERVED 或 EXCLUSIVE 三种状态下开始
  • 白色框中的 UNLOCKED, PENDING, SHARED 和 RESERVED 可在数据库同时存在
  • 灰色的 PENDING 开始,事情就变得严格起来,意味着事务想得到排斥锁 (EXCLUSIVE)(注意与白色框中的区别)

虽然锁有这么多状态,但是从体质上来说,只有两种情况:读事务和写事务

读事务 (Read Transactions)

SELECT 执行时锁状态变化过程非常简单:

连接执行 select 语句,触发一个事务,从 UNLOCKED 到 SHARED,事务 COMMIT 时,又回到 UNLOCKED

伪代码

db = open('foods.db')
db.exec('BEGIN')
db.exec('SELECT * FROM episodes')
db.exec('SELECT * FROM episodes')
db.exec('COMMIT')
db.close()

显式使用 BEGIN 和 COMMIT,两个 SELECT 命令在一个事务下执行

第一个 exec() 执行时,connection 处于 SHARED,然后第二个 exec() 执行,当事务提交时,connection 又从 SHARED 回到 UNLOCKED 状态

UNLOCKED→PENDING→SHARED→UNLOCKED

如果没有 BEGIN 和 COMMIT 两行时如下

UNLOCKED→PENDING→SHARED→UNLOCKED→PENDING→ SHARED→UNLOCKED

写事务(Write Transactions)

如 UPDATE。和读事务一样,也会经历 UNLOCKED→PENDING→SHARED,但接下来却是灰色的 PENDING

The Reserved States

当一个连接(connection)向数据库写数据时,从 SHARED 状态变为 RESERVED 状态,如果它得到 RESERVED 锁,也就意味着它已经准备好进行写操作了

即使它没有把修改写入数据库,也可以把修改保存到位于 pager 中缓存中(page cache)

连接进入 RESERVED 状态,pager 就开始初始化恢复日志(rollback journal)

RESERVED 状态下,pager 管理着三种页面:

  • Modified pages:包含被 B - 树修改的记录,位于 page cache 中
  • Unmodified pages:包含没有被 B-tree 修改的记录
  • Journal pages:这是修改页面以前的版本,这些并不存储在 page cache 中,而是在 B-tree 修改页面之前写入日志

Page cache 非常重要,正是因为它的存在,一个处于 RESERVED 状态的连接可以真正的开始工作,而不会干扰其它的(读)连接。所以,SQLite 可以高效的处理在同一时刻的多个读连接和一个写连接

The Pending States

当一个连接完成修改,就真正开始提交事务,执行该过程的 pager 进入 EXCLUSIVE 状态。从 RESERVED 状态,pager 试着获取 PENDING 锁,一旦得到,就独占它,不允许任何其它连接获得 PENDING 锁(PENDING is a gateway lock)

既然写操作持有 PENDING 锁,其它任何连接都不能从 UNLOCKED 状态进入 SHARED 状态,即没有任何连接可以进入数据(no new readers, no new writers)。只有那些已经处于 SHARED 状态的连接可以继续工作。而处于 PENDING 状态的 Writer 会一直等到所有这些连接释放它们的锁,然后对数据库加 EXCUSIVE 锁,进入 EXCLUSIVE 状态,独占数据库 (讨论到这里,对 SQLite 的加锁机制应该比较清晰了)

The Exclusive State

EXCLUSIVE 状态下,主要的工作是把修改的页面从 page cache 写入数据库文件,这是真正进行写操作的地方

pager 写入 modified pages 之前,它还得先做一件事:写日志

它检查是否所有的日志都写入了磁盘,而这些通常位于操作的缓冲区中,所以 pager 得告诉 OS 把所有的文件写入磁盘,这是由程序 synchronous(通过调用 OS 的相应的 API 实现) 完成的

日志是数据库进行恢复的惟一方法,所以日志对于 DBMS 非常重要。如果日志页面没有完全写入磁盘而发生崩溃,数据库就不能恢复到它原来的状态,此时数据库就处于不一致状态。日志写入完成后,pager 就把所有的 modified pages 写入数据库文件。接下来就取决于事务提交的模式,如果是自动提交,那么 pager 清理日志,page cache,然后由 EXCLUSIVE 进入 UNLOCKED。如果是手动提交,那么 pager 继续持有 EXCLUSIVE 锁和保存日志,直到 COMMIT 或者 ROLLBACK

总之,从性能方面来说,进程占有排斥锁的时间应该尽可能的短,所以 DBMS 通常都是在真正写文件时才会占有排斥锁,这样能大大提高并发性能


内核

虚拟机(Virtual Machine)

VDBE 是 SQLite 的核心,上层模块和下层模块都是本质上都是为它服务的

它通过底层的基础设施 B+Tree 执行由编译器(Compiler)生成的字节代码(为了进行查询,读取和修改数据库而专门设计)

VM 执行的原理:一个包含大量 switch 语句的 for 循环,每一个 switch 语句实现一个特定的操作指令

Back-end(后端)

B-tree 和 Pager

B-Tree 得 VDBE 可在 O(logN) 下查询,插入和删除数据, O(1) 下双向遍历结果集

B-Tree 不直接读写磁盘,仅维护着页面 (pages) 之间的关系

B-TREE 需要页面或者修改页面时,调用 Pager

修改页面时,pager 保证原始页面首先写入日志文件,当它完成写操作时,pager 根据事务状态决定如何做

数据库文件格式(Database File Format)

索引用 B-tree,表用 B+tree

B+tree 所有叶子节点包含了全部关键字信息,而且可以有两种顺序查找

B-tree 更适合用来作索引

页面重用及回收 (Page Reuse and Vacuum)

SQLite 用空闲列表 (free list) 进行页面回收

一个页面的所有记录都被删除时,就被插入到该列表

运行 VACUUM 命令时,清除 free list,数据库缩小,本质上它是在新的文件重新建立数据库,而所有使用的页在都被拷贝过去,而 free list 却不会,结果就是一个新的,变小的数据库

当autovacuum 开启时,SQLite 不会使用 free list,而且在每一次 commit 时自动压缩数据库


Page Cache 之事务处理

初始状态(Initial State)

当一个数据库连接第一次打开时,最右边Disk表示保存在存储设备中的内容

每个方框代表一个扇区

蓝色的块表示这个扇区保存了原始数据

中间区域是 os 磁盘缓冲区

开始的时候,这些缓存是还没有被使用,这些方框是空白的

左边区域显示 SQLite 用户进程的内存。数据库连接刚刚打开,所以还没有任何数据记录被读入,所以这些内存也是空的

获取读锁 (Acquiring A Read Lock)

写之前必须先从数据库中读取相关信息。如,插入时,从 sqlite_master 表(数据字典)中读取数据库模式),以便编译器对 INSERT 语句进行分析,确定数据插入的位置

读操作前必须先获取数据库的共享锁 (shared lock),共享锁允许两个或更多的连接在同一时刻读取数据库。但是共享锁不允许其它连接对数据库进行写操作

shared lock 在 os 磁盘缓存,而非磁盘

文件锁的本质只是 kernel 数据结构,os 崩溃或掉电时,这些内核数据也会随之消失

读取数据

一旦得到 shared lock,就可以进行读操作

数据先由 OS 从磁盘读取到 OS 缓存,然后再由 OS 移到用户进程空间

一般数据库文件分为很多页,一次读操作只读取一小部分页面

从 8 个页面读取 3 个页面

获取 Reserved Lock

数据修改前,先要获取数据库文件的 Reserved Lock

Reserved Lock 和 shared lock 相似之处在于,都允许其它进程对数据库文件进行读操作

Reserved Lock 和 Shared Lock 可以共存,但是只能是一个 Reserved Lock 和多个 Shared Lock——多个 Reserved Lock 不能共存

所以,在同一时刻,只能进行一个写操作

Reserved Lock 意味着当前进程 (连接) 想修改数据库文件,但是还没开始修改操作,所以其它的进程可以读数据库,但不能写数据库

创建恢复日志 (Creating A Rollback Journal File)

写前先要创建一个单独的日志文件,然后把要修改的页面的原始数据写入日志

回滚日志包含一个日志头 (图中的绿色)——记录数据库文件的原始大小

所以即使数据库文件大小改变了,仍知道数据库的原始大小

OS 的角度来看,一个文件创建时,大多数 OS(Windows,Linux,Mac OS X) 不会向磁盘写入数据,新创建的文件此时位于磁盘缓存中,之后才会真正写入磁盘

如图,日志文件位于 OS 磁盘缓存中,而不是位于磁盘