嵌入式数据库SQLite上多版本并发控制的设计与实现

景子奇，邹兆年

（哈尔滨工业大学计算机科学与技术学院，哈尔滨 150001）

0 引言

SQLite［1］是当今非常流行的轻量级开源关系数据库管理系统（Relational DataBase Management System，RDBMS）。与Oracle、MySQL、PostgreSQL 等主流RDMBS 不同，SQLite 是一个嵌入式RDBMS。嵌入式数据库体积非常小，系统资源占用非常低，可以运行于手机等终端设备，使用时不需要运行独立的数据库引擎，可与应用一同编译［2］。SQLite 支持大部分SQL92 标准，支持满足ACID（Atomicity-Consistency-Isolation-Durability）特性（即原子性、一致性、隔离性和持久性）的事务，可以运行在Unix、Linux、Windows、MacOS 等诸多主流操作系统上，并支持C、Java、PHP、Tcl、C#等众多计算机程序设计语言［3］。SQLite 是用ANSI C 语言编写的，自身完全独立，无需依赖任何外部函数库。SQLite 的整个数据库（包括数据库模式定义、表和索引）都存储在宿主机上的单一文件中，便于数据库和应用程序的迁移。由于上述优点，SQLite 目前已在移动应用开发中占据了相当大的市场份额［4］，并在气象观测［5］、矿业［6］、航空航天［7］等领域得到了广泛应用。

SQLite 提供了对ACID 事务的完整支持。由于SQLite 的嵌入式特点，SQLite 仅支持数据库级别的事务并发，允许同一时刻有多个读事务并发执行，但任何时刻最多只允许一个写事务执行，并且读事务和写事务之间可能存在冲突。在事务并发控制方面，SQLite 采用了两阶段锁（two-Phase Locking，2PL）并发控制协议，通过对操作系统提供的文件锁进行包装，实现了数据库粒度的锁。此外，SQLite 提供了journal 日志机制，可用于故障恢复，无需额外编写故障恢复模块［8］。SQLite 的并发控制方法任意时刻只允许有一个正在执行的写事务，因此无法实现多个写事务的并发执行。另一方面，由于锁的粒度为数据库级，因此即使两个并发执行的读写事务分别读写不同的数据表，它们仍然会发生冲突。

多版本并发控制（Multi-Version Concurrency Control，MVCC）［9］是当今RDBMS 中非常流行的事务管理方法。在使用MVCC 的RDBMS 中，关系的每个元组都有多个版本（version），每个版本带有一个时间戳（timestamp），版本越新，其时间戳越大。MVCC 实现了并发事务之间的快照隔离（snapshot isolation），保证每个事务在读数据库时读到的是事务开始时的数据库实例（即快照）。因此，在支持MVCC 的RDBMS 中不存在读写冲突（read-write conflict），即当一个写事务和一个读事务并发执行时，读事务会读取它应该读的数据库版本，写事务会写入新版本的元组，因此两个读写事务之间不存在冲突。尽管在支持MVCC 的RDBMS 中不存在读写冲突，但写写冲突（write-wirte conflict）仍然存在。

为了提高SQLite 处理并发读事务和写事务的能力，本文设计并实现了SQLite 上的MVCC。该设计利用SQLite 现有的锁机制与执行结构，通过修改数据库文件头与记录格式来确定数据的可见性，并改写SQLite 内置虚拟机的操作序列完成MVCC 的执行。在大量数据上进行了实验，验证了在SQLite 上实现MVCC 可以有效提高数据库上读写事务的并发性。

1 预备知识

1.1 SQLite的体系结构

与MySQL、PostgreSQL 等主流RDMBS 不同，SQLite 具有一个精致的、模块化的体系结构，并采用了一些独特的方法来管理关系数据库。SQLite 包含3 个子系统和8 个独立的模块，这些模块可以分为两部分：前端解析系统和后端处理引擎。SQLite 的体系结构如图1 所示。

图1 SQLite的体系结构Fig.1 Architecture of SQLite

SQLite 的前端部分由分词器、语法分析器和代码生成器构成，作用是将SQL 语句转换为SQLite 虚拟机上可以执行的字节码（opcode）序列。SQLite 的后端主要负责处理SQLite 数据库文件的存储与读写，主要由B-树、页缓存（pager）和操作系统接口三部分构成，其中B-树的作用是对文件页面中的元组进行索引；页缓存的作用是通过操作系统接口在B-树和磁盘之间传递页面。

SQLite 的核心是虚拟机VDBE（Virtual DataBase Engine）。在SQLite 执 行SQL 语句时SQLite 的前端 首先将SQL 语句转换为虚拟机上可以执行的字节码序列，然后启动虚拟机执行字节码，完成SQL 语句的执行。在执行字节码的过程中，虚拟机通过SQLite 后端的B-树模块读写数据库中的元组。

SQLite 支持ACID 事务，它使用库级锁来协调并发事务。SQLite 支 持4 种类型的锁：SHARED 锁、RESERVED 锁、PENDING 锁和EXCLUSIVE 锁。表1 展示了这4 种类型锁的相容性。在事务执行过程中，读操作在读数据库对象时须获得SHARED 锁，写操作在修改未提交时须获得RESERVED 锁来阻止其他写事务启动。写事务在内存中完成写操作时，必须先获取PENDING 锁来阻止新的读事务启动，并在所有已启动的读事务提交后获取EXCLUSIVE锁，将修改写入磁盘。

表1 SQLite中不同类型锁之间的相容性Tab.1 Compatibility of mutex in SQLite

1.2 多版本并发控制

多版本并发控制（MVCC）提出于20 世纪70 年代末，尽管时间久远，但仍是当前最流行的事务管理方案，几乎被当今所有RDBMS 采用。

1.2.1 MVCC协议

MVCC 协议保证事务访问到的数据库内容等同于该事务启动时已提交的数据库内容（即一致性快照）。因此，MVCC 允许一个事务T在另一个并发事务T′更新对象X 时读取X 的旧版本，使这两个X 上的读写操作不冲突。尽管MVCC 避免了读写冲突，但并发事务的写写冲突仍然存在，需要采取特殊的手段来解决。根据解决手段的不同，MVCC可分为使用事务标识符（TID）标注元组可用性的MVTO（Multi-Version Timestamp Ordering）、使用乐观锁协议的MVOCC（Multi-Version Optimistic Concurrency Control）［10］和使用两阶段锁协议的MV2PL（Multi-Version Two-Phase Locking）。图2 展示了三种协议下元组的格式。

图2 三种MVCC协议下元组的格式Fig.2 Tuple formats under three MVCC protocols

MVTO 是最初的MVCC，它使用事务的TID 来预计算事务的序列化顺序。当事务T 对一条逻辑元组执行读操作时，DBMS 将搜索TID 位于元组begin-ts 和end-ts 字段范围之间的版本，MVTO 从不允许事务读取未提交的版本。在MVTO中，事务执行写操作先需要持有写锁（锁有版本号），并将元组的txn-id 设置为事务的TID，且总是在元组的最新版本上进行写操作。

在MVOCC 中，事务在执行读写操作时无需获得锁，而是在提交前进行验证，验证通过后将更新过的对象写入磁盘。在MVOCC 中，事务的执行过程分为读、验证和写入3 个阶段，仅在写入时短暂持有锁。

MVP2L 使用2PL 来解决写写冲突，同时用read-cnt 表示同时在读该版本的事务数量，将read-cnt 视为共享锁，txn-id视为排他锁。

MVTO 和MV2PL 由于在读元组时修改了元组的头部，可能会使其他事务中止，而MVOCC 不会使事务中止，但是验证和回滚代价较大。为了解决这个问题，有研究将事务使用链表串联起来，并根据时间戳进行快速验证［11］。

1.2.2 数据版本的存储与检索

MVCC 设计中另一个重要的问题是数据版本的存储与检索。在版本存储方面，主要有Append-only、Time-travel 和Delta 三种方法［12］。

Append-only 方法将元组的所有版本都存储在同一个存储空间中，并用单向链表将元组的不同版本连接起来。根据单向链表的方向是从新版本到旧版本，还是从旧版本到新版本，又可将该方法分为N2O（Newest-To-Oldest）方法和O2N（Oldest-To-Newest）方 法。Append-only 方法已用于PostgresSQL 等数据库管理系统［13］中。

Time-Travel 方法将旧版本存放在单独的表中，主表中只存储最新版本［14］。该方法好处是索引始终指向元组的最新版本，省去了事务在更新元组时维护数据库索引的开销，并且非常适合于那些需要访问元组最新版本的查询。

Delta 方法仅在额外的存储空间中存储元组版本的变化，这样做能够降低写事务的开销，但读事务需要通过计算才能得到所需版本的元组，开销较大，不适合于读密集型事务。作为MySQL 默认存储引擎的InnoDB 便采取这种做法［15］。

1.2.3 垃圾回收

存储各个版本的数据需要消耗大量存储空间，必须在存储资源耗尽前将无用的版本删除，以回收存储空间。垃圾回收的过程分为3 步：1）检测无用的过期版本，其中过期版本是指无效的版本（即由中止事务创建的版本）或对任何活跃事务都不可见的版本。2）删除过期的版本以及和它们有关的关联链和索引链接。3）回收存储空间。

垃圾回收又分为元组级垃圾回收和事务级垃圾回收［12］。元组级垃圾回收是在执行查询时会定期扫描过期的元组版本，删除这些版本，从而实现垃圾回收。事务级垃圾回收则是按照事务的维度，要求记录r/w set，这样可以把不用的事务所创建的版本都过滤掉［16］。

1.2.4 索引

索引可以使用逻辑指针和物理指针两种方式实现。物理指针只适用于append-only 版本存储方法，因为该方法将全部版本存储在同一个表中，所有索引都可以指向这些版本。当更新表中的元组时，DBMS 会将新创建的版本插入到所有二级索引中。在这种方式下，DBMS 可以在二级索引上查找元组，而无需将次关键字与所有索引版本进行比较。MemSQL 和Hekaton 等多个支持MVCC 的DBMS 都采用了这种方案。使用逻辑指针的主要思想是使用固定的逻辑标识符来标识元组，该标识符对于索引中的相同元组是不变的。DBMS 只需使用一个间接层，将元组的标识符映射到其版本链的头部。该方法的优点是当元组被修改时，不必更新所有索引，使索引项指向新的物理位置。该方法只需修改间接层中的映射条目即可。但是由于索引没有指向确切的版本，DBMS 必须从元组版本链的头部开始遍历版本链从而找到可见的版本，查找效率较低，但比较适合于写密集型事务。

1.3 事务的隔离级别

不同的事务同时对一个数据库进行操作便构成了并发，并发事务的操作交叉执行，可能会相互干扰，影响事务之间的隔离性。根据事务中的操作是否修改了数据库的内容，事务被分为读事务与写事务。如果数据库上仅执行读事务，则读事务之间不会相互干扰；然而，当写事务与其他事务同时执行时，则可能会出现一些异常问题。解决这些异常问题的方法称为并发控制。人们总结出了事务并发执行时产生的几种常见的异常问题：脏读、不可重复读和幻读。

脏读（dirty read）是指事务读到了其他未提交事务写的数据。若未提交的事务进行了回滚，则引发了脏读。不可重复读（unrepeatable read）是指如果事务已读过的数据被其他事务修改了，该事务再次读该数据时与前一次读到的内容不一致。幻读（phantom read）是指当事务多次执行相同的查询时，后面操作因涉及其他事务写入的新数据，导致相同的查询返回不同的结果。

根据上述3 种异常问题是否会在事务并发执行过程中出现，可将事务的隔离性划分成如表2 所示的不同级别。并发控制的设计目标就是在保证一定的隔离级别的前提下尽可能提高系统的并发性能［17］。

表2 不同隔离级别的划分依据Tab.2 Division rules of different isolation levels

2 SQLite多版本并发控制的设计

本章介绍本文提出的SQLite 上的MVCC 设计方案。

2.1 设计目标

本节从多个方面分析SQLite 的设计方案，并提出SQLite上MVCC 的设计目标。

1）在数据库存储方面，为了便于数据库和应用程序的迁移，SQLite 将整个数据库存储在单个文件中。在设计SQLite的MVCC 时仍将数据库存储在单个文件中，并沿用SQLite 的文件组织方式，即一切数据页均为B 树节点。MVCC 中，需要存储一个元组的不同版本。在本设计中将一个表中的新旧版本的元组存储在该表中。

2）在并发控制方面，出于移植性的考虑，SQLite 的锁机制基于文件锁实现，其粒度为库级。一旦数据库被某个事务加上了排他锁，则整个数据库无法被任何其他事务并发访问。为保证可移植性，在进行设计MVCC 时应沿用SQLite 的锁机制，故多个写事务无法并发执行。因此，本文的MVCC设计方案只支持读事务与读事务的并发执行以及读事务与写事务的并发执行，而不支持多个写事务的并发执行。

3）与其他RDBMS 不同，SQLite 并不记录系统内的活跃（active）事务，因此无法从数据库的角度知道系统内有哪些事务正在执行。这使得无法根据活跃事务来划分数据库版本，也无法通过为事务分配自增ID 的方式进行版本控制。由于本文的MVCC 设计中不考虑写-写事务的并发，因此数据库在逻辑上被已提交的写事务划分为不同的独立状态，可以使用已提交的写事务将数据库划分为不同版本，并用单调递增的版本号进行标记。下文中提到的版本号均指以该方法指定的版本号。

4）在隔离性方面，SQLite 支持的隔离级别为可串行化（serializable）与读未提交（read uncommitted），其中读未提交隔离级别仅提供给同一进程内不同线程间的并发事务。在本文的MVCC 设计中，只考虑可串行化隔离级别。

2.2 MVCC协议

本节介绍SQLite 上MVCC 协议的具体设计。

数据库版本的表示 根据2.1 节介绍的设计思路，本设计中根据已提交的写事务将数据库划分成不同的版本。数据库的初始版本号为0。每当一个写事务提交，数据库的版本号增加1。在实现中在SQLite 数据库文件的头部记录数据库当前的版本号。每个版本的数据库由该版本的全体元组构成。为了记录元组的版本，在每条元组的头部增加了3 个字段：T_START、T_END 和CID，其中T_START 代表该元组创建时数据库的版本号，T_END 代表该元组结束时数据库的版本号，CID 代表该元组版本在同一事务中被创建的顺序。

数据可见性规则 由于数据库存在多个版本，MVCC 规定一个事务只能看见该事务启动前最后一个写事务提交后数据库的状态（即一致性快照）。为了实现上述可见性，基于上面介绍的数据库版本表示方法定义了如下数据可见性规则。设t是数据库中的一条元组，使用T_START（t）、T_END（t）和CID（t）分别表示t的T_START、T_END 和CID 字段的值。设T是一个事务，使用TID（T）表示T启动时数据库的版本号。对于T中的第i个操作，根据以下3 条规则来判定元组t是否对该操作可见。

规则1 如果T是读事务且T_START（t）≤TID（T）≤T_END（t），则t对T的第i个操作可见。

规则2 如果T是写事务且T_START（t）≤TID（T）＜T_END（t），则t对T的第i个操作可见。

规则3 如果T是写事务且T_START（t）=TID（T）+1，TID（T）＜T_END（t），CID（t）＜i，则t对T的第i个操作可见。

只要上述规则之一满足，则t对T的第i个操作可见。

2.3 数据更新操作

在MVCC 协议下，数据更新不再是SQLite 采用的原地更新（in-place update），而是维护数据的版本。下面介绍MVCC协议下的数据更新操作。

插入（INSERT）操作 INSERT 操作用于向数据库中插入新的元组。设事务T的第i个操作准备插入一条新元组，该元组的全部属性值为val，T的TID 为TID（T）。该操作将在表中插入一条新的元组t，其中T_START（t）=TID（T）+1，T_END（t）=∞，CID=i，t的属性值为val。根据2.2 节介绍的可见性规则，新插入的元组t对事务T后续操作可见。图3 中展示了INSERT 操作的过程，其中执行INSERT 操作的事务的TID 为1，该INSERT 操作是该事务的第0 个操作，新插入元组的属性值为b。

图3 INSERT操作的执行过程Fig.3 Execution process of INSERT operation

删除（DELETE）操作 DELETE 操作用于删除数据库中的元组。在MVCC 下，该操作不会在物理上删除元组，而是修改该元组可见版本的T_END 字段，设置其可见的结束时间。设事务T准备删除一条元组，t是T当前可见的元组版本，T的TID 为TID（T）。DELETE 操作将T_END（t）设置为TID（T）。根据2.2 节介绍的可见性规则，t对T不再可见，从而在逻辑上删除了t，然而对于某些早于T启动的事务，t仍然可见。图4 展示了DELETE 操作的过程，其中执行DELETE 操作的事务的TID 为2，rowid=0 的元组是该事务可见的待删除元组版本。

图4 DELETE操作的执行过程Fig.4 Execution process of DELETE operation

更新（UPDATE）操作 UPDATE 操作用于修改数据库中的元组。在MVCC 下，该操作不会原地修改元组，而是先执行DELETE 操作，删除该元组；再执行INSERT 操作，插入更新后的元组。图5 展示了UPDATE 操作的过程。设执行UPDATE 操作的事务的TID 为2，该INSERT 操作是该事务的第1 个操作，该事务准备将rowid=0 的元组的值a修改为b。该事务首先执行DELETE 操作，将rowid=0 的元组的T_END字段设置为2；然后执行INSERT 操作，插入rowid=2 的元组。

图5 UPDATE操作的执行过程Fig.5 Execution process of UPDATE operation

2.4 事务的执行流程

由于本文的MVCC 设计允许读-写事务并发，但不允许写-写事务并发，因此需要对SQLite 的事务执行流程进行重新设计。图6 展示了MVCC 下一个事务的执行流程（这里未使用检查点）。在事务执行过程中，系统使用SHARED 与RESERVED 两种类型的锁来控制并发。写事务通过持有RESERVED 锁来阻止其他写事务的执行，但并不会影响读事务的启动和提交。

图6 事务的执行流程Fig.6 Flowchart of transaction execution

事务的提交发生在commit 或end 语句执行时。如果提交的事务为写事务，则SQLite 会将该事务修改过的数据写入数据库文件中。如2.3 节所述，写事务在执行写操作时需要用到该事务的TID。在写数据库文件时需要判断当前写事务的TID 是否已经被其他已提交的事务使用过。进行该检查的理由如下：即使当前写事务已经获得了RESERVED 锁，使得其他事务无法升级到写事务，然而在该写事务提交后，其他访问该版本数据的事务仍可以获得RESERVED 锁并尝试提交。如果这种情况发生，两个提交的写事务提供的TID可能相同，因而无法正确划分数据版本。由于上述原因，在写事务提交前必须进行版本检查，只有写事务的TID 大于当前已提交的数据库版本，写事务才能成功提交，否则写事务回滚（rollback）。该方法可以保证数据库版本的唯一性。

2.5 并发事务的隔离级别

基于2.2～2.4 节的内容，给出本文提出的MVCC 设计方案下并发事务的隔离级别的分析。

定理1在本文提出的MVCC 设计方案下并发事务的隔离级别为可串行化（serializable）。

证明 根据可串行化隔离级别的定义，只需证明基于本文的MVCC 设计，并发事务不会产生脏读（dirty read）、不可重复读（unrepeatable read）和幻读（phantom read）。

1）无脏读。由SQLite 事务模型可知，未提交的事务不会将任何修改过的数据写入数据库文件中，因此任何事务读到的数据一定是已提交事务写入的版本，故不会产生脏读。

2）无不可重复读。设t是事务T1 可见的元组版本，根据可见性规则，有T_START（t）≤TID（T1）≤T_END（t）。设事务T2 对t进行了修改，则根据2.3 节介绍的UPDATE 操作，T2首先将T_END（t）设置为TID（T2），其中TID（T1）≤TID（T2）。根据2.2 节中的可见性规则，t仍然对T1 可见。然后，T2 插入一个新的元组版本t′，且T_START（t′）=TID（T2）+1。根据2.2 节中的可见性规则，t′对T1 不可见。T1 可见的仍然是t，故不会产生不可重复读。

3）无幻读。由于系统使用了库级锁，同一时刻只允许一个写事务执行，因此写事务插入的新元组的版本号一定大于当先所有读事务的TID。由可见性规则1 可知，这些新元组对任何读事务均不可见，因此不会发生幻读。

2.6 索引

索引用于对表中的元组进行快速查找。如果表被更新，则该表上的索引也要被更新。SQLite 中索引与表的格式相同，因此在MVCC 下，B+树索引叶节点中的索引项也记录着对应元组的T_START、T_END 和CID 字段的值。下面介绍如何在MVCC 下对索引进行查找和更新。

查找索引项 在索引上进行查找时，除了根据给定的索引键值进行查找外，还需要对查找到的索引项进行可见性检查，确保事务可见的索引与事务可见的数据库一致性快照是一致的。值得注意的是，在一个事务查找索引项的过程中，另一个事务可能同时更新了索引，导致B 树叶节点发生分裂。这有可能导致叶节点中信息与缓存中的父节点中的信息不一致，从而查不到索引项。为了解决该问题，需要保证在查找索引项的过程中B 树页面的版本没有发生变化。如果B 树页面的版本发生了变化，则需要终止本次索引查找并重新启动索引查找操作。

插入索引项 当一条新元组被插入表中时，需要向该表上每个索引中插入相应的索引项。索引项的T_START、T_END 和CID 字段的值分别与新元组这3 个字段的值相同。

删除索引项 当表中元组被删除时，索引中与该元组对应的索引项并不会被物理上删除，而是修改该索引项的T_END 字段，以改变该索引项的可见性。修改方法与2.3 节介绍的DELETE 操作修改元组T_END 字段的方法相同。

更新索引项 如2.3 节所述，当更新表中元组时，采取先执行DELETE 操作再执行INSERT 操作的方式。相应地，还要在每个索引上先删除索引项，再插入更新后的索引项。删除和插入索引项的方法均已在前面介绍过。

2.7 旧版本数据回收

当数据库长时间运行后，会积累大量旧版本数据。旧版本数据对新启动的事务不可见，因此不会被新事务访问。然而，所有版本的数据均存储于同一个SQLite 数据库文件中，这会导致文件过大，严重降低系统性能。因此，MVCC 设计必须为SQLite 设计旧版本数据回收方法。

为SQLite 设计旧版本数据回收方法主要面临两个困难：1）现有基于MVCC 的RDBMS 采用多种方法（如版本链、undo日志）来记录元组版本之间的关系，但受限于SQLite 的现有设计，无法在不大量改变SQLite 的前提下采取类似的方法来加速查询符合当前事务可见性的数据。2）SQLite 并不记录系统内的活跃事务，因此无法从数据库的角度判断元组的某个版本是否还在被某个活跃的读事务读取，因而无法主动清除数据库中的旧版本数据。

设计提供了下面的旧版本数据回收方法。首先，SQLite是一种嵌入式数据库，可以和应用程序的代码一起编译，用户可以在应用程序中记录系统内的活跃事务。然后，当系统内没有活跃事务时，SQLite 可以启动旧版本数据清理。具体过程如下：首先，阻止任何新事务启动。然后，打开数据库中所有的表，逐条扫描表中每条元组，使用所有最新版本的可见数据创建新的数据库。当新数据库创建完成后，用新数据库替换原有的数据库。

3 实验与结果分析

3.1 实验设置

本文在SQLite 3.34.0 上实现了MVCC，并在Visual Studio 2019 中使用nmake 指 令执行SQLite 的Makefile.msc 文件，将实现了MVCC 的SQLite 编译为动态链接库。后文将实现了MVCC 的SQLite 称为SQLite-MVCC。实验测试程序用C++语言编写，并用Visual Studio 2019 编译。实验测试程序在多个线程内打开SQLite-MVCC，并在事务中使用SQL 语句进行一系列操作。实验所使用的计算机的配置如下：Intel Core i7-7700 处理器（4 核，2.8 GHz），16 GB 内存，120 GB 硬盘（读取速度为546 MB/s），运行Windows 10 操作系统。

实验在1 个随机生成的表上进行。表中含有INT、TEXT、BLOB 和DOUBLE 类型的 属性各1 个，其 中INT 和DOUBLE 类型的属性值为随机数，TEXT 和BLOB 类型的属性值由随机生成的短序列拼接而成。元组长度在设定值的±2 B 内变动。实验中预设的元组长度分别为10 B、50 B 和20 B，用于反映不同应用情境下的数据。为使实验数据在图表中能合理显示，将上述3 种元组长度下的表中元组数分别设置为50 万条、20 万条和10 万条。

3.2 非并发情况下数据写操作的性能

本文首先在非并发情况下对SQLite-MVCC 上INSERT、DELETE 和UPDATE 操作与SQLite 上对应操作的执行时间进行了实验对比。图7 展示了实验结果。

图7（a）对比了SQLite 和SQLite-MVCC 上INSERT 操作的执行时间。实验中使用INSERT 语句分别在SQLite 和SQLite-MVCC 上依次插入50 万条元组，每条语句插入1 条元组，然后测试插入操作的平均执行时间。实验结果显示，SQLite 和SQLite-MVCC 上插入1 条元组的平均执行时间接近。但由于SQLite-MVCC 中的元组增加了T_START、T_END和CID 字段，比SQLite 中的元组略长，故SQLite-MVCC 上的插入操作略慢于SQLite 上的插入操作，但总体差异不大。

图7（b）对比了SQLite 和SQLite-MVCC 上DELETE 操作的执行时间。实验中使用DELETE 语句分别在SQLite 和SQLite-MVCC 上删除50 万条元组，并测试删除1 条元组的平均执行时间。实验结果显示，SQLite 和SQLite-MVCC 上删除操作的平均执行时间接近，因为SQLite 和SQLite-MVCC 均采用修改元组头部的方式实现数据删除，区别仅在于SQLite 修改元组的前4 个字节，而SQLite-MVCC 修改3 个字节长的T_END 字段，因此二者性能接近。

图7（c）对比了SQLite 和SQLite-MVCC 上UPDATE 操作的执行时间。实验方法与测试DELETE 操作时类似。实验结果显示，SQLite-MVCC 上UPDATE 操作的平均执行时间显著高于SQLite 上UPDATE 操作。这是因为SQLite 进行原地更新，只需修改元组的属性值即可，而SQLite-MVCC 需要先执行1 次DELETE 操作，再执行1 次INSERT 操作。因此，SQLite-MVCC 上UPDATE 操作在理论上要比SQLite 上UPDATE 操作多花费1 倍以上的时间，实验结果验证了这一点。另外，SQLite-MVCC 执行过程中沿着B+树叶节点遍历新插入的元组，即使元组不可见，也要被读取1 次并进行可见性判断，从而花费更多额外的时间。

图7 非并发情况下写操作性能的对比Fig.7 Performance comparison of non-concurrent write operations

综上所述，除UPDATE 外，SQLite-MVCC 上各项操作的时间性能比SQLite 上略有下降，但在可接受的范围内。受实现方法的影响，SQLite-MVCC 上更新操作的时间性能下降较多，因此更新元组数量较多的事务不适于使用SQLite-MVCC。

3.3 非并发情况下数据读操作的性能

本文还在非并发情况下对SQLite和SQLite-MVCC 的数据读取性能进行了实验对比。实验分别在元组长度为10 B 和200 B 的2 个随机生成的表上进行，查询语句的选择谓词的选择度约为0.1%，并在2 个表上各执行了100 次查询，测试100次查询的总体执行时间。图8展示了实验结果。如图8（a）所示，当元组长度为10 B 时，SQLite-MVCC 处理1 个查询的时间要比SQLite 多15%～20%。这是因为读取元组中的版本信息并进行元组的可见性判断耗费了额外的时间。如图8（b）所示，当元组长度为200 B 时，SQLite 和SQLite-MVCC 的查询执行时间的差异在5%以内，基本可以忽略。

图8 非并发情况下读操作性能的对比Fig.8 Performance comparison of non-concurrent read operations

3.4 并发情况下数据库的性能

接下来，在并发情况下对SQLite 和SQLite-MVCC 的性能进行了实验比较。实验中通过设置系统内的并发线程数来调整系统的并发度。

该部分实验首先测试了SQLite 和SQLite-MVCC 在不同并发线程数下的吞吐量，其中吞吐量使用系统每秒钟处理的事务数来衡量。图9 展示了实验结果。在该实验中，同类事务的执行时间基本相同，不存在因随机性而导致的执行时间偏差。实验结果表明，在相同线程数下，SQLite-MVCC 的吞吐量高于SQLite。这表明SQLite-MVCC 的读-写事务并发设计提高了系统的并发性。然而，随着线程数的增加，SQLite-MVCC 相较SQLite 的并发性能优势逐渐下降，主要原因如下：

图9 不同线程数下系统的吞吐量Fig.9 System throughput under different numbers of threads

1）线程数的增加导致了并发事务发生冲突的概率下降。当线程数为2 时，约有55%的事务发生冲突；而当线程数为6时，仅有5%左右的事务发生冲突。这是因为SQLite-MVCC不持支写-写事务并发，系统中最多只有1 个线程能够进行写操作。随着线程数的增加，读事务在全体并发事务中的占比提高，写事务的CPU 资源占用率下降，从而导致写事务的提交变得缓慢，致使并发事务发生冲突的概率下降。

2）3.3 节的实验表明，SQLite-MVCC 执行读事务的效率略低于SQLite，因此当线程数增加，读事务占比提高时，吞吐量提升的速度会下降。此外，SQLite-MVCC 更容易使CPU 到达性能瓶颈，从而导致吞吐量随线程数的增加其增长的速度放缓。

本文对并发状态下SQLite-MVCC 和SQLite 执行相同工作量的事务时所用的时间进行了实验对比。图10 展示了实验结果。图10 结果反映在各种线程数下，SQLite-MVCC 的执行时间均少于SQLite。这是由于SQLite-MVCC 支持读-写事务并发，在实际执行事务时总是可以提前完成写事务，使整体效率变高。该实验结果表明，在实际的有限任务工作负载下，SQLite-MVCC 的并发性显著优于SQLite。

图10 不同线程数下完成固定事务所需的时间Fig.10 Time cost for handling same transactions using different numbers of threads

数据集的大小对数据库系统的性能有内在影响，本文通过实验对此进行了测试。图11 展示了元组长度对数据库大小的影响。从实验结果来看，在相同的元组长度下，SQLite-MVCC 数据库比SQLite 数据库大，这是因为SQLite-MVCC 元组头部包含额外的版本信息，占用了更多的空间。但是随着元组长度的增大，版本信息所占的空间比例越来越低，对数据库大小的影响越来越不明显。图12 展示了在不同的元组长度下SQLite-MVCC 相较SQLite 的并发性能提升比例。可见，随着元组长度的增加，SQLite-MVCC 的并发性能提升越来越大，因为SQLite-MVCC 处理版本信息的开销在总开销中所占的比例越来越低，总性能提升。在实际使用数据库时，URL、TEXT、BLOB 等类型数据的长度一般在50 B 以上，此时SQLite-MVCC 有着不错的表现，并且此时存储元组头部的版本信息所消耗的存储空间基本可以忽略不计。

图11 元组长度对数据库大小的影响Fig.11 Influence of tuple length on database size

图12 不同元组长度下SQLite-MVCC并发性能的提升Fig.12 Concurrent performance improvement of SQLite-MVCC under different tuple lengths

基于以上实验结果可知，SQLite-MVCC 相较SQLite 并发性能有所提高，并具有一定实际意义，且在一定范围内并发事务中写事务比例越高性能提升越大，该方法更适合写事务占比高的并发场合使用。此外，当有长读取事务执行时也可考虑使用该方法提高数据库性能。

4 结语

本文为SQLite 设计了支持可串行化隔离级别的MVCC协议，并实现了支持MVCC 的SQLite，使SQLite 上并发的读事务和写事务不会冲突，有效提高了SQLite 处理并发事务的能力，为研究如何提高SQLite 的并发性能提供了一种新的技术思路。后续还可以从以下几个方面进行深入研究：1）将MVCC 与其他方法（如多粒度锁）相结合，进一步提高系统的并发性能，并解决目前写事务和写事务无法并发执行的问题。2）设计更符合MVCC 的编译器与字节码，使系统可以跳过不可见的元组，进一步提高系统性能。3）设计更加高效的旧版本数据回收机制。