sqlite3.36版本 btree实现（四）- WAL的实现

《sqlite3.36版本 btree实现》系列文章：

• sqlite3.36版本 btree实现（零）- 起步及概述 - codedump的网络日志
• sqlite3.36版本 btree实现（一）- 管理页面缓存 - codedump的网络日志
• sqlite3.36版本 btree实现（二）- 并发控制框架 - codedump的网络日志
• sqlite3.36版本 btree实现（三）- journal文件备份机制 - codedump的网络日志
• sqlite3.36版本 btree实现（四）- WAL的实现 - codedump的网络日志
• sqlite3.36版本 btree实现（五）- Btree的实现 - codedump的网络日志

概述

前面两节，分别讲解了sqlite中写入事务时的并发控制框架，以及journal备份文件的实现机制。

回忆一下journal备份文件的实现：

• 每次一个新的写事务开始之前，要首先写journal文件的文件头。
• 写事务过程中，如果修改了哪个页面，在修改之前需要首先将这个页面的内容写入到journal文件中。
• 写事务完成后，在同步所有缓存中被修改的页面到数据库文件之前，要首先将journal文件中的所有修改同步到磁盘，然后再修改数据库文件。

可以看到，journal备份的整个流程都较为原始，性能不高，所以在sqlite 3.7.0版本（SQLite Release 3.7.0 On 2010-07-21，2010-07-21）中，引入了另一种备份机制：WAL（Write Ahead Log）。

本节首先介绍WAL的实现原理，然后再展开其具体的实现。

WAL工作原理

从前面journal的实现中可以看到，写入journal文件中的内容，是待修改页面修改之前的内容，而WAL则相反：被修改的页面内容首先写入到WAL中。

用sqlite官网的文字来说，WAL文件的定义是这样的：

The write-ahead log or “wal” file is a roll-forward journal that records transactions that have been committed but not yet applied to the main database.

即WAL文件中存储的是被修改但是还没有写入数据库文件的页面内容。

WAL整体的实现机制，分为以下几个流程：

• 对页面的修改，可以只写入到WAL文件中就认为完成，不必一定要落盘到数据库文件才能算完成，这个设定保证了WAL的修改操作比journal性能有很大的提升。
• 由于上面的这一点保证，同一时间的并发读操作，能继续读数据库中未修改的内容，极大提升了读并发的性能。
• 当然WAL也不能无限制的一直写下去，必须有一个机制，触发将保存在WAL中的页面内容写入回到数据库文件中，这个流程被称为checkpoint。

WAL相关文件结构

在工作原理部分，只会简单讲解WAL相关文件结构，具体的格式等细节留待下面的实现部分详细讲解。

WAL文件本身的格式很简单，有如下两部分组成：

• WAL文件头。
• 紧跟着文件头之后的，就是由修改之后的页面内容组成的页面内容数组。
• 最后，当事务被提交时，还会有一个特殊的WAL日志，标记这个事务提交了。

换言之，一个WAL中，可能先后存储了多个事务的写入。

由于WAL文件保存的修改页面的内容，同一个页面，可能在一次事务中被多次修改，如下所示：

WAL存储了四个页面数据，其中页面编号1被修改了两次。

如果在这个写操作完成之后，需要读这些页面的内容，都需要读到最新的内容。所以，WAL还有一个对应的WAL页面索引数据，这部分索引数据存储在内存中，作用是根据页面编号，知道该页面编号对应的最新内容，存储在WAL文件中的具体位置，以取得某个页面的最新页面内容；如果在这个内存索引中查不到的数据，都需要到数据库文件中读取。

checkpoint

随着WAL文件的增长，终究要将里面修改的内容同步到数据库文件中，这个流程被称为“checkpoint”。只要WAL文件被“checkpoint”，就可以从头开始写这个文件，避免文件的无限增大。

对于journal备份机制而言，只有两种操作：读和写；而对于WAL机制而言，实际有三种操作：读、写、checkpoint。这也是两种机制的主要区别之一。

并发的实现

前面提到了，WAL机制的一个优势在于：在写未完成之前，可以允许同时并发多个读操作，来看看这一点是如何做到的。

在每次读操作开始之前，都会记录下来当前最后提交事务的提交记录，这条记录被称为“end mark”。因为WAL会随着写操作的进行不断增加，通过读操作的“end mark”，就能知道对于这个读操作而言，页面内容应该以当前WAL内容为准，还是以数据库文件为准。

以下图为例来做个说明：

在上图中：

• WAL文件中先后记录了两个写事务，其中第一个写事务修改了页面编号1、2，已经提交完成；还有一个在进行还未完成的写事务，修改了页面编号1。
• 这时候，如果来了一个读事务，那么将记录下来最后一个完成事务的提交记录做为自己的“end mark”，即图中的浅蓝色的那个提交记录。
• 假设现在这个读事务，依次要读取页面编号1和2的页面，那么：
  • 到页面索引中查询页面1的位置，发现位置比自己的“end marker”更大，也就是说这个页面在上一次完成写事务之后，被当前还未完成的写事务修改了，于是并不能读WAL的内容，因为这部分内容对这个读操作来说还是未提交的，所以页面1需要到数据库文件中读取。
  • 到页面索引中查询页面2的位置，发现位置比自己的“end marker”更小，也就是在自己标记的写事务完成之后并未被修改过，于是可以读WAL中这个页面的内容。

可见，有了“end mark”这一标记位置之后，加上页面索引，任意数量的读操作都能快速判断自己应该读WAL文件还是数据库文件，写操作可以继续写，读和写之间并不会冲突，极大提升了读并发的性能。

同样要看到的是，由于只有一个WAL文件，同一时间之内，只能有一个写操作。即：sqlite的WAL模式，只能支持单写多读的模式。

读操作和checkpoint的联系

前面讲到了checkpoint以及读并发的实现，两者可以并发一起执行，但是某些时刻会有一些关联，影响系统的性能。

因为超过读操作“end mark”的页面，读操作需要到数据库文件中读取该页面内容，那么反过来，当checkpoint操作要将一个超过当前并发的任意读操作“end mark”的页面落到数据库文件中时，就必须等待这个读操作完成才能进行。

仍然以前面读并发的示意图来解释这个过程：

• checkpoint 页面编号2的内容到数据库文件时，该页面最后在WAL文件中的位置，并不比当前的任意读操作的“end mark“更大，所以checkpoint这个页面的内容到数据库文件时无需等待即可完成。
• 反过来，checkpoint 页面编号1的内容到数据库文件时，该页面最后在WAL文件中的位置，大于当前读操作的”end mark“，所以这个页面的内容就需要等待读操作完成才能进行下去。

换言之：一个执行很久的读操作，可能会影响同时在进行的checkpoint操作的执行。

被阻塞的checkpoint必须等待读操作完成才能继续执行，因此需要一些额外的信息来维护当前checkpoint执行的状态，这些具体的实现细节都会在下面实现环节的分析中涉及。

现在已经大体清楚WAL的原理了，下面来看具体的实现。

WAL的实现

sqlite中，可以使用PRAGMA journal_mode=wal设置页面备份机制为wal，这时候就会有三个与数据库相关的文件在同一个目录：

• 数据库文件，假设名字为X。
• WAL文件，名字为“X-wal”。
• wal索引文件，名字为“X-shm”。

WAL的文件格式

首先来看WAL文件的格式，分为两个部分：

• WAL文件头：一次写事务，对应一个WAL文件头。
• 除去文件头，每一页数据都是存储在“帧（frame）”里，每一帧又包括两部分数据：
  • 帧头部：描述存储的这一页数据的信息。
  • 页面数据：存储页面数据。

WAL文件头，只会在每次写事务中写入一次，而帧可能在一次写事务中多多个，取决于这一次写事务修改了多少页面。如下图：

上图中，依次存储了两次写事务的数据，其中第一次写了两帧数据，第二次写了一帧数据。

有了以上的概念，下面详细看WAL文件的结构。

WAL文件头格式

（引用自 Database File Format section 4.1）

其中的很多字段自有解释，其中多数涉及到页面内容的校验，后面再展开说。

WAL帧头部格式

（引用自 Database File Format section 4.1）

帧头部需要存储如下的信息：

• 0-4字节：页面编号。
• 4-8字节：对于提交记录而言，这4字节存储的是该事务提交之后，数据库文件的最大页面编号；其它的时候，这4字节为0。也就是说，这4字节大于0的时候，表示是一次事务的最后一次页面修改。

其它的字段，都跟页面的校验有关，接下来就看看这部分的实现。

页面内容校验算法

前面的格式中，无论是WAL文件头，还是WAL帧头部，都有以下的字段：

• 8字节的salt数据。
• 两组4字节的checksum数据。

校验时，只有满足以下条件的情况下才认为是正确的帧数据：

• 帧头部中的8字节的salt数据，和WAL头部的salt数据相同。
• 根据校验算法遍历页面数据计算出来的checksum，和帧头部的checksum数据相同。

第一部分salt数据，每次写事务生成一次，所以校验这个值可以认为校验这一帧数据是否和这次事务匹配；而第二部分的checksum数据，则会用来依次串起一次写事务的所有页面修改。

比如下面这个写事务流程：

• 第一次写页面，由于之前这个写事务没有写过页面，所以初始的checksum为0，以这个初始的checksum来计算这第一个页面的checksum，计算之后的值记录到这个页面的checksum，记为checksum_1。
• 第二次写页面，取上一次计算的checksum即checksum_1，来计算这第二个页面的checksum，记为checksum_2。
• 类似的，第N次写页面时，以上一次计算的checksum即checksum_n-1来做为计算的初始值计算。

这样，相邻页面之间的校验值就有了关联。

总结起来：

• salt：每次事务算一次随机值。
• checksum：满足以下以下条件：
  • checksum_0 = 0
  • checksum_n = F(checksum_n-1, 页面数据) ，其中函数F是根据初始校验值和页面数据计算出新校验值的函数。

校验页面的函数实现在walDecodeFrame中，而计算页面校验值的函数实现在walChecksumBytes中。

WAL页面索引

结构

前面分析WAL文件结构的时候，提到保存一页数据的内容被称为“帧（frame）”，帧的编号从1开始顺序递增，每一帧内容存储的页面内容可能会发生变化，如下图所示：

图中，依次有四帧页面数据，帧数与页面的对应关系依次是：(1,1)，(2,3)，(3,5)，(4,4)。假设随着运行，第一帧对应的页面1被写入了数据库，那么第一帧的空间就会被复用来存储别的页面的内容。

所以，WAL页面索引中，需要存储帧数与页面编号之间的对应关系，这样就能：

• 访问一帧的内容时，知道保存的是哪个页面的内容；
• 根据页面编号，能查到这个页面的最新数据保存在哪一帧中。

根据需要的这两份数据，定义了用于保存wal索引的数据结构：

struct WalHashLoc {
  volatile ht_slot *aHash;  /* Start of the wal-index hash table */
  volatile u32 *aPgno;      /* aPgno[1] is the page of first frame indexed */
  u32 iZero;                /* One less than the frame number of first indexed*/
};

其中：

• aHash：保存了根据页面编号查找iFrame帧数的hash数组数据。
• aPgno：保存了根据帧数查找页面编号的数据。
• iZero：保存了当前索引页面第一帧的帧数。

这么看来有一些抽象，我们以下图来做解释wal-index文件的结构：

如上图所示，其中：

• wal索引文件一页大小为32KB，需要注意的是：不要把wal索引文件的一页与数据库文件的一页搞混，两者并不一定相同，但是都为2的次方，数据库文件的一页可以编译期修改，但是wal索引文件的一页大小写死为32KB。
• 第一页相对有些特殊，因为最开始的136字节是wal索引文件头，所以相对的，剩下用来存储索引数据的空间就会变少一些。索引文件头的内容，留待后面再详细解释。
• 每一页存储的数据中，aPgno大小为4096（第一页只有4062，因为有头部用到的空间），aHash的大小为8192。

这几个常量，由下面这几个宏来定义：

// 每一页aPgno数组大小
#define HASHTABLE_NPAGE      4096                 /* Must be power of 2 */
// 查询时hash取模时的质数
#define HASHTABLE_HASH_1     383                  /* Should be prime */
// 每一页hash slot数组大小
#define HASHTABLE_NSLOT      (HASHTABLE_NPAGE*2)  /* Must be a power of 2 */

// 页面1实际能容纳的aPgno大小：HASHTABLE_NPAGE减去WALINDEX_HDR_SIZE使用的大小
#define HASHTABLE_NPAGE_ONE  (HASHTABLE_NPAGE - (WALINDEX_HDR_SIZE/sizeof(u32)))

// 一个wal索引页面的大小，为4096*4+8192*2 = 32KB
#define WALINDEX_PGSZ   (                                         \
    sizeof(ht_slot)*HASHTABLE_NSLOT + HASHTABLE_NPAGE*sizeof(u32) \
)

索引文件头结构

来看看索引文件头的结构，其整体大小为136字节，划分为三部分：

（引用自WAL-mode File Format section 2.1）

这总共136字节的数据，一共分为三个部分：

• 0-47字节：WAL索引头部，由结构体WalIndexHdr来描述。
• 48-95字节：还是一个由结构体WalIndexHdr描述的WAL索引头部。
• 96-136字节：由结构体WalCkptInfo描述的WAL checkpoint信息。

下面的表格，详细展示了这136字节中都有哪些字段。

（引用自WAL-mode File Format section 2.1）

下面就这里的一些重点字段做一下介绍。

为什么需要两个相同大小的WAL索引头部？

注意到0-47和48-95这两部分48字节的数据，都是同样类型的数据，都由WalIndexHdr结构体来描述。

这样设计的目的，是为了读写的时候数据校验。假设头48字节为h1，后48字节为h2。那么读操作的时候是先读h1再读h2，而写操作的时候则相反，先写h2再写h1。这样，如果在读操作的时候，读到这两部分内容并不一样，说明当前有写操作在进行。

读头部的实现见函数walIndexTryHdr：

static SQLITE_NO_TSAN int walIndexTryHdr(Wal *pWal, int *pChanged)
{
  u32 aCksum[2];              /* Checksum on the header content */
  WalIndexHdr h1, h2;         /* Two copies of the header content */
  WalIndexHdr volatile *aHdr; /* Header in shared memory */

  aHdr = walIndexHdr(pWal);
  memcpy(&h1, (void *)&aHdr[0], sizeof(h1)); /* Possible TSAN false-positive */
  walShmBarrier(pWal);
  memcpy(&h2, (void *)&aHdr[1], sizeof(h2));

  // 对比两个header，不相同就返回
  if (memcmp(&h1, &h2, sizeof(h1)) != 0)
  {
    return 1; /* Dirty read */
  }
  if (h1.isInit == 0)
  {
    return 1; /* Malformed header - probably all zeros */
  }
  // 对比校验值
  walChecksumBytes(1, (u8 *)&h1, sizeof(h1) - sizeof(h1.aCksum), 0, aCksum);
  if (aCksum[0] != h1.aCksum[0] || aCksum[1] != h1.aCksum[1])
  {
    return 1; /* Checksum does not match */
  }

  // 到了这里，就是判断是否发生过改变了
  if (memcmp(&pWal->hdr, &h1, sizeof(WalIndexHdr)))
  {
    *pChanged = 1;
    memcpy(&pWal->hdr, &h1, sizeof(WalIndexHdr));
    pWal->szPage = (pWal->hdr.szPage & 0xfe00) + ((pWal->hdr.szPage & 0x0001) << 16);
    testcase(pWal->szPage <= 32768);
    testcase(pWal->szPage >= 65536);
  }

  /* The header was successfully read. Return zero. */
  return 0;
}

mxFrame和nBackfill

mxFrame记录着当前WAL文件的最大帧数，而nBackfill记录着当前checkpoint操作进行到第几帧，即在nBackfill之前的帧数都已经被写入数据库文件了。

显然这两个值有如下关系：nBackfill<=mxFrame：

• nBackfill<mxFrame，checkpoint过程还未结束。
• nBackfill==mxFrame，checkpoint过程已经结束，这时候：
  • WAL文件中的所有页面已经被回填（backfill）到数据库文件中了；
  • 所有读页面的操作，都不再需要访问WAL文件，而是直接访问数据库文件；
  • 下一次再有写操作，可以从WAL的头部开始写。

实现

有了前面的准备，我们来看看这两种对应关系的查找是怎么做的。

索引页面的存储

前面分析到，一个wal索引页面的大小为32KB，这些数据是存储在Wal结构体中的：

struct Wal {
	// ...
	int nWiData;               /* Size of array apWiData */
	volatile u32 **apWiData;   /* Pointer to wal-index content in memory */
	// ...
}

其中：

• apWiData：存储页面指针的数组。
• nWiData：页面指针数组的大小。

根据帧数查询页面编号

首先来看根据帧数查询这一帧存储的是哪个页面的数据，即根据帧数查询页面编号的实现。

由于wal文件中，到了一定大小之后，就会执行“checkpoint”操作，所以帧数一定是有限的。即帧数满足以下的条件：

• 从0开始递增。
• 不会无限增大。

所以在aPgno中，就直接使用帧数来做为这个数组的索引。总结下来，添加一个帧数和页面之间对应关系的大体的步骤如下（函数walIndexAppend）：

• 首先根据帧数，知道在第几个索引页面中，也就是apWiData数组的第几个元素，这样就拿到这一帧对应在哪个32KB的数据。（函数walHashGet，另外函数walFramePage是根据帧数得到apWiData数组索引）。

rc = walHashGet(pWal, walFramePage(iFrame), &sLoc);

• 帧数减去这一页的iZero知道是这一页中的aPgno数组的索引：

  idx = iFrame - sLoc.iZero;
  

• 在hash数组中找到空位置存储页面编号：

    /* Write the aPgno[] array entry and the hash-table slot. */
    nCollide = idx;
    for(iKey=walHash(iPage); sLoc.aHash[iKey]; iKey=walNextHash(iKey)){
      if( (nCollide--)==0 ) return SQLITE_CORRUPT_BKPT;
    }

• 将两者的对应关系存储下来，即：向aPgno中存入页面编号，向aHash中存储帧数：

      sLoc.aPgno[idx] = iPage;
      AtomicStore(&sLoc.aHash[iKey], (ht_slot)idx);
  

下图展示了这个过程的大体示意：

举个例子来说明上面的流程，假设要存储的对应关系是帧数5000存储的是页面编号5：

• 根据帧数5000，算出这一帧的索引数据应该存储在第二个索引页面中，由此拿到这个页面的WalHashLoc指针。

• 再根据5000，减去这个页面的帧数起始位置4063，得到帧数偏移量为927，即这个帧在这个WalHashLoc->aPgno数组的位置是927，即idx=927。

• 再到WalHashLoc->aHash中，找到一个空的位置，这个空位置假设是iKey=101。

• 到了这里，位置都找到了，更新数据：

sLoc.aPgno[927] = 5;
AtomicStore(&sLoc.aHash[101], (ht_slot)927);

可以看到：

• 通过帧数找到aPgno是一个两次索引的过程：第一次根据帧数找到32KB页面，第二次再根据帧数找到在这一页中的帧数偏移量。
• 最后修改aHash是一次原子操作，因为其它地方可能同时在查询。

根据页面编号查询所在帧

前面分析了如何存储帧数到页面编号的对应关系，可以看到这一次更新是把两个对应关系一起更新的。也可以看到，根据帧数查找的流程实际还是相对简单的，就是两次索引：一次找到页面，再一次就是页面内的查找，原因在于：帧数是有限的。

但是页面就不是这样了，因为这里要存储的页面编号是数据库文件中的页面编号，并不知道当前数据库到底变到多大了，这样就不能按照前面的方式来两次索引。

我们来看看如何根据页面编号，知道这一页面是存储在哪一帧里的，即wal文件的帧数，这个过程在函数sqlite3WalFindFrame中。

• 拿到该读操作当前最大和最小帧数，根据这两个帧数得到对应的索引32KB页面。
• 从后往前遍历这些页面，每个页面中到WalHashLoc->aHash中，根据页面编号的hash值来查找。
• 这个流程一直到找到页面，或者全部遍历完毕为止。

从这个流程可以看到：查找页面对应帧数的流程，最坏的情况下可能遍历了所有索引页面，虽然其中的查找过程会根据页面编号的hash值来查找。于是一个重要的结论就出来了：WAL的实现，其中有一个缺点是，当WAL文件很大时，对应的索引页面也会很大，在索引中查找页面编号的流程就会变久。

锁的实现

数据结构

wal模式提供了以下4种锁，这4种锁从wal索引文件头部120字节处开始，每种锁占一个字节：

• WAL_WRITE_LOCK：写锁，写操作之前必须拿到写锁。
• WAL_CKPT_LOCK：checkpoint锁，在做checkpoint之前需要拿到这个锁。
• WAL_RECOVER_LOCK：恢复锁，在进行恢复操作之前要拿到这个锁。
• WAL_READ_LOCK：读锁，一共有五个读锁，但是作用不尽相同。

这四种锁，其中有五个读锁，一共加起来就是8个锁，定义如下：

// wal索引文件中锁的数量
#define SQLITE_SHM_NLOCK        8

// 写锁在所有锁中的偏移量
#define WAL_WRITE_LOCK 0
// 除了写锁以外的其他所有锁
#define WAL_ALL_BUT_WRITE 1
// checkpoint锁在所有锁中的偏移量
#define WAL_CKPT_LOCK 1
// 恢复锁在所有锁中的偏移量
#define WAL_RECOVER_LOCK 2
// 输入读锁索引，返回对应读锁在所有锁中的偏移量，因为读锁从3开始，所以+3
#define WAL_READ_LOCK(I) (3 + (I))
// 读索引的数量 = 所有锁数量 - 读锁起始位置3
#define WAL_NREADER (SQLITE_SHM_NLOCK - 3)

问题来了，为什么是索引文件头部120字节处开始的呢？从上面对wal索引文件的格式分析可知：索引文件开始是两个WalIndexHdr + 一个WalCkptInfo，而WalCkptInfo结构体定义如下：

struct WalCkptInfo
{
  u32 nBackfill;              /* Number of WAL frames backfilled into DB */
  u32 aReadMark[WAL_NREADER]; /* Reader marks */
  u8 aLock[SQLITE_SHM_NLOCK]; /* Reserved space for locks */
  u32 nBackfillAttempted;     /* WAL frames perhaps written, or maybe not */
  u32 notUsed0;               /* Available for future enhancements */
};

其中的aLock字段就是存储上面的这些锁的数组，把前面这些数据的大小加起来，一直到这个字段就正好是120，有宏定义为证：

/* A block of WALINDEX_LOCK_RESERVED bytes beginning at
** WALINDEX_LOCK_OFFSET is reserved for locks. Since some systems
** only support mandatory file-locks, we do not read or write data
** from the region of the file on which locks are applied.
*/
#define WALINDEX_LOCK_OFFSET (sizeof(WalIndexHdr) * 2 + offsetof(WalCkptInfo, aLock))

（引用自WAL-mode File Format）

加解锁操作

wal与前面的journal相比，少了很多其他类型的锁，wal只有两种类型的锁：shared共享锁，以及exclusive排它锁。对应的API有下面四个：

static int walLockShared(Wal *pWal, int lockIdx);
static void walUnlockShared(Wal *pWal, int lockIdx);
static int walLockExclusive(Wal *pWal, int lockIdx, int n);
static void walUnlockExclusive(Wal *pWal, int lockIdx, int n);

这里有几个细节，需要交待一下。

首先，其中传入的参数lockIdx，就是上面提到的几种锁的类型索引。

其次，代码中有walLockShared(pWal, WAL_WRITE_LOCK)这样的操作。对一个写锁加共享锁应该怎么理解？需要纠正的是，类似WAL_WRITE_LOCK这样的宏，只是表示这一字节用于什么操作，比如WAL_WRITE_LOCK用于写操作，即：

• 要拒绝其他写请求的情况下读数据时，就应该对WAL_WRITE_LOCK类型的锁加共享锁。
• 要开始写操作时，就应该对WAL_WRITE_LOCK类型的锁加排它锁。

其他类型的锁依次类推，即WAL_*_LOCK这类宏只是表示这一个字节的用途。

最后一个细节是，加共享锁时只能传入锁类型索引，而加排它锁的时候还能传入一个参数n，这是什么意思？

因为这些不同类型的锁，本质上就是wal索引共享文件上连续的字节，所以区别在于，共享锁一次只能对一个锁进行操作；而排它锁则可以一次多对多个锁进行操作。

比如

walLockExclusive(pWal, WAL_READ_LOCK(1), WAL_NREADER - 1);

这样就能把从1号读锁开始的所有读锁都加上排它锁。

再比如：

  iLock = WAL_ALL_BUT_WRITE + pWal->ckptLock;
  rc = walLockExclusive(pWal, iLock, WAL_READ_LOCK(0) - iLock);

这里的几个常量取值如下：

• ckptLock取值为0或者1。
• WAL_ALL_BUT_WRITE为1。
• #define WAL_READ_LOCK(I) (3 + (I))，所以WAL_READ_LOCK(0)为3。

于是：

• 如果ckptLock取值为0，表示这时候还没有加上了checkpoint的排它锁：
  • iLock为1，1为WAL_CKPT_LOCK这个类型的锁。
  • WAL_READ_LOCK(0) - iLock为2。
  • 这样，walLockExclusive(pWal, iLock, WAL_READ_LOCK(0) - iLock);就能把checkpoint和0号读锁都加上排它锁，这样就不会其他checkpoint操作。
• 如果ckptLock取值为1，表示这时候已经加上了checkpoint的排它锁：
  • iLock为2，2为WAL_RECOVER_LOCK这个类型的锁。
  • WAL_READ_LOCK(0) - iLock为1。
  • 这样，walLockExclusive(pWal, iLock, WAL_READ_LOCK(0) - iLock);就能把恢复加上排它锁，这样能进行恢复操作。

特殊的0号读锁

除此以外，还需要注意0号读锁很特殊，它表示读事务申请的共享锁，和WAL_WRITE_LOCK不冲突，读写可以完全并发进行，互不影响，但是不能和数据库同步操作和WAL-index文件恢复并发进行。0号读锁表示只从数据库读取页。

有了对锁的了解，可以接下来看各种操作的具体实现了。

读操作

进行读操作时，大体需要以下两个操作：

• 保存当前的aReadMark，因为这涉及到读页面的时候数据从哪里来的问题。
• 拿到对应的读锁。

下面分别讨论这两方面的内容。

readMark

首先来了解一下什么叫readMark，以及有什么作用。

回顾之前谈到wal文件以及wal索引文件的格式，有这么几个要点：

• 对于同一个页面编号的页面，可能会在wal文件存在不同时间的多次写入结果。这些多次写入结果里，如果所在的事务还未提交，那么这个修改应该对读操作还处于不可见的状态。wal文件头中使用mxFrame这个字段来存储当前最后完成的写事务的帧数，超过这个帧数的修改都认为还没有完成。
• wal索引保存着页面的最新修改的位置信息，这“最新修改”指的是已经提交的事务，并不包括还未提交的事务的修改。
• 读操作时，以页面编号先从wal索引中尝试读这个页面在wal中的位置信息：
  • 如果读成功，根据这个wal的位置信息，到wal文件中读取该页面。
  • 否则，该页面没有在wal中，到数据库文件中读取。

以下图为例来说明情况，为了简化说明，一个页面存储的一对KV的信息。

在上图中：

• 有三个写事务，其中：
  • 第一个事务已经完成，修改了值y=20，这个修改存在第一帧中。
  • 第二个事务也已经完成，修改了值x=1和y=2，这两个修改存在第二和第三帧中。
  • 第三个事务还在进行中，目前修改了值x=3，这个修改存在第四帧中，其余修改还在进行中。
• 根据上面的描述，那么wal索引中这几个维护位置信息的内容就是：
  • mxFrame=3，因为这是最后一个完成的写事务的最大帧数。
  • wal索引中：
    • x的位置在第四帧，但是需要注意这个值还并未提交，所以要区分不能读到未提交的值（read uncommitted），这在下面会展开说明。
    • y的位置在第三帧。注意到y有两个数据，但是取了已提交事务中最新的那次数据。
    • z在wal中没有，即在wal当前保存的所有事务中都没有修改到z，于是如果需要读取z的值，需要到数据库文件。
  • 在数据库文件中，x、y、z又是另外的三个值，因为这个时候，已提交事务的修改还在WAL文件中，并未写入数据库文件里面。

于是，当一个新的读操作开始的时候，会记录下来当时的mxFrame，这个值对于读操作而言，被称为readMark，保存在WalCkptInfo结构体的成员aReadMark数组中。有了这个值，当进行checkpoint操作的时候，就能判断当前是否需要等待读操作完成。这部分将在下面结合checkpoint流程继续讲解。

除此之外，readMark还有另一层含义：即当前已完成事务的最大帧数，所以当读事务去读一个页面的内容时，会首先到wal索引中，根据该页面的编号查询这个页面对应的帧数，有这几种可能：

• 没有找到：这说明当前wal文件中没有该页面的内容，要到数据库文件中查询。
• 找到了，假设这个帧数为iFrame，这又分为两种情况：
  • iFrame>readMark：这说明是这个读事务之后才进行的写操作，于是这个页面的内容还是不能从WAL文件中读取，仍然到数据库文件中读。这是因为如果从WAL中读取，可能读到的是还未提交的事务的数据。
  • iFrame<=readMark：这说明是在这个读事务之前的写操作，可以从WAL文件读这个页面的内容。

仍然以前面的图为例来说明情况，假设在上图的第三个写事务还在进行的时候，来了一个读事务，按照前面的解释，此时：

• 这个读事务的readMark=3。
• 假如这个读事务分别读了x、y、z这三个值，它需要到wal索引中查询这几个值是否在wal文件中，那么：
  • x：x的最新值在第四帧，大于readMark=3，说明是个发起读操作之后还未提交的写事务更新的，这就不能读wal的最新值，而要读数据库文件中的值，此时读出来的值为x=100。
  • y：y的最新值在第三帧，并不大于readMark=3，所以可以以wal的值为准，读出来y=2。
  • z：在wal索引中没有找到z，只能去数据库文件中查，读出来z=300。

再次说明的是，为了问题描述的简化，这里假设一个页面只存储了一对KV的值。

有了对readMark的初步了解，继续看读操作如何获得读锁。

读锁

前面已经提到，读锁的信息保存在WalCkptInfo的aLock成员中：

struct WalCkptInfo
{
	// ...
  u32 aReadMark[WAL_NREADER]; /* Reader marks */
  u8 aLock[SQLITE_SHM_NLOCK]; /* Reserved space for locks */
  // ...
};

在这里：

• aReadMark：用于存储每个读操作的readMark值，这个值已经在上面做了解释，这个数组的大小为WAL_NREADER，即每个reader一个readMark值。
• aLock：存储锁类型的数组，这些锁类型也在上面做了诠释。

当一个读操作来的时候，需要获得一个读锁，才能继续往下进行它的读操作，这个获得锁的流程，在函数walTryBeginRead中：

1. 调用walIndexReadHdr函数读取wal的索引文件头。
2. 由于WalCkptInfo信息存储在索引文件头中，于是可以接下来调用walCkptInfo函数拿到这部分信息。
3. 寻找当前可用的读锁，分为以下几步：
   1. 有了当前的WalCkptInfo信息，遍历其中的aReadMark数组，选出其中readMark最小的那个值，并且记录下这个最小值的索引i。这是因为readMark小的读操作，更有可能已经完成了读操作。
   2. 尝试调用walLockExclusive(pWal, WAL_READ_LOCK(i), 1)对上一步拿到的readMark数组索引加排他锁：
      1. 如果成功，说明这个读锁当前没有其它进程在用，可以退出循环了。
      2. 否则，就递增i索引对下一个读锁进行尝试，直到遍历完毕所有读锁。
   3. 到了这里，已经拿到一个可用的读锁了，调用walLockShared对这个读锁加共享锁。
4. 在前面的过程中，很可能有写操作在进行，所以在返回之前，最后判断一下wal 索引头数据是否发生了变化，如果发生了变化，前面的步骤就得重新来过，返回重试。

需要补充说明的是，函数walTryBeginRead在调用时，如果返回重试（WAL_RETRY）的话，调用者会将调用计数递增，当这个调用计数超过一个阈值时，再次调用时walTryBeginRead会休眠一下，超过100次则会报错不再尝试。

  // 尝试超过5次的情况下，要休眠一下
  if (cnt > 5)
  {
    int nDelay = 1; /* Pause time in microseconds */
    if (cnt > 100)
    {
      // 超过100次了，退出报错
      VVA_ONLY(pWal->lockError = 1;)
      return SQLITE_PROTOCOL;
    }
    if (cnt >= 10)
      nDelay = (cnt - 9) * (cnt - 9) * 39;
    sqlite3OsSleep(pWal->pVfs, nDelay);
  }

可以从加读锁的流程看到：

• sqlite的WAL机制，最大只能支持同时有WAL_NREADER个读操作并发。
• 加读锁的时候，如果因为写操作导致wal索引文件头发生了变化，将前功尽弃再次尝试。

写操作

写锁

拿到写锁的流程，对比上面拿到读锁的流程来说，就简单很多了，在函数sqlite3WalBeginWriteTransaction中：

1. 调用walLockExclusive(pWal, WAL_WRITE_LOCK, 1)拿到写锁的排它锁。
2. 同样也是检查是否wal索引头发生了变化，如果是则需要再次尝试。

而解写锁操作就在函数sqlite3WalBeginWriteTransaction。

这两个函数的实现都挺简单，就不展开阐述了。

写操作

真正将脏页面写入wal文件中的操作在函数sqlite3WalFrames中，该函数有几个比较重要的参数：

• PgHdr *pList：脏页面链表。
• int isCommit：为1的情况下，表示这是提交操作，即这个写事务的最后一次调用sqlite3WalFrames函数。

sqlite3WalFrames函数的实现也并不复杂，有这么几个事情：

• 拿到当前写wal的起始位置，从这个位置开始，遍历脏页面写入wal文件中。而这个起始位置，就是前面提到的mxFrame+1帧。
  • 但是这个过程中需要考虑到可能出现的覆盖情况，即：同一次写事务，对同一个页面有多次写操作，这种情况下，后面对同一个页面的写操作，不应该写到wal后面，而是覆盖前面的内容。
• 遍历脏页面链表，将脏页面写入wal文件之后，就需要根据最新的页面编号和wal文件帧数的对应关系，更新wal索引的内容。
• 最后，更新mxFrame的值为WAL文件当前的最大帧数。

还是以一个例子来说明这个流程。

如上图所示，精简了很多情况，假设从WAL文件的开头开始写脏页面了，图中的写事务一共写了三次页面：

• 写入y=200：这时候将这个内容写入WAL文件中的第一帧，更新wal索引中y页面的帧数为1，而此时x还没有内容。写完毕之后，更新mxFrame=1。
• 写入x=100：这时候将这个内容写入WAL文件中的第二帧，更新wal索引中x页面的帧数为2。写完毕之后，更新mxFrame=1。
• 写入y=101：写入时发现，同一个事务之前已经修改过y页面了，于是这一次并不把y=101的修改继续写到WAL文件结尾，而是覆盖第一帧中已经存在的y页面内容，同时索引数据也不需要更新：因为是覆盖操作，y页面的帧数并没有发生变化。同样的，由于没有修改WAL文件的最大帧数，mxFrame也没有修改。

页面校验值的计算

checkpoint

总体流程

有了前面读、写操作的了解，接着来了解一下checkpoint操作是如何实现的。

我们回顾一下checkpoint操作要完成的事情：由于wal日志中存储的，都是每次写事务被修改的页面，因此checkpoint操作就是将wal日志中被修改的页面写入数据库文件中。也是因为这个原因，因此checkpoint也被称为backfill（回填）操作。

从上面的读写流程的分析里看出：

• 同时能支持多个读事务，每个读事务都有一个readMark值，用来区分这个读操作读到在WAL中存储的某个页面时，是以wal的页面为准，还是应该到数据库文件中读取这个页面。
• 同时只能存在一个写事务，这个写事务没有完成之前，任何读事务不能读到它的数据，因为是未提交（uncommitted）的修改。

因此，在做checkpoint的时候，需要保证：

• 不能将未提交写事务的修改，回填到数据库文件中。
• 对于正在进行的读操作，不能将超过该读操作的readMark值的帧，回填到数据库文件中，需要等待读操作完成才能回填这部分数据。

第一点很好理解，因为未提交的写事务，可能只修改了一部分，如果在未提交这个写事务之前，就把这一部分回填到数据库文件中，会造成读出来的这部分数据驴头不对马嘴。比如一个写事务的修改，是将A账号的100转账到B账号上，于是这个写事务就涉及两个修改：

• A：扣除100。
• B：加上100。

如果这个事务当前只完成了上面的第一步修改，这个修改马上被回填到数据库文件中，这时候看到的就是A少了100，而B没有变化，这显然是不可接受的。

第二点的理解，要回到前面对readMark值的解释上：一个读操作开始之前，会记录一下当前已完成写事务的最大修改帧数做为自己的readMark，在后续的读操作中，从wal索引中查询一个页面编号，有以下几种可能：

• 没有找到，说明需要到数据库文件中查找该页面内容。
• 找到了，又需要区分两种情况：
  • 这个页面所在的帧数<readMark：说明这个页面在读操作开始之后再没有被修改了，可以以wal的内容为准。
  • 否则：说明这个页面在读操作之后被修改了，需要到数据库文件中查询被修改之前的值。

注意：上面的”这个页面在读操作之后被修改“条件，不仅包括这个修改对应的写事务没有被提交，也包括写事务已提交的情况。

即：readMark保证了，一个读事务绝对不能读到在这个读事务之后的任何修改。

由这个解释可以看到，当一个读操作判断一个页面的内容需要到数据库文件中读取时，需要读到的是这个读事务之前的修改。因此，checkpoint需要保证：不能将超过当前任何读操作的readMark值的帧数，回填其保存的页面到数据库文件中。

到了这里，基本可以确定一个checkpoint操作的流程了：

• 加checkpoint的排它锁，保证同时只能有一个checkpoint操作在进行。
• 算出当前最大可以回填到第几帧的数据，假设这个值保存在变量mxSafeFrame中，流程如下：
  • 初始时，取mxSafeFrame=mxFrame。
  • 遍历当前所有还在进行的读操作，取mxSafeFrame=min(mxSafeFrame, aReadMark)，即不能超过任何一个在进行的读操作的readMark值。
• 计算出来了最大回填帧数，可以实际进行回填操作了：遍历当前的wal文件，将所有帧数小于等于mxSafeFrame的修改都回填到数据库文件中

以上是checkpoint流程的总体描述，其中涉及的主要函数是：

• sqlite3WalCheckpoint：checkpoint操作的入口函数，负责加checkpoint排它锁，然后继续调用下面的walCheckpoint进行实际的回填操作。

• walCheckpoint：执行checkpoint操作。

想了解更多细节的读者可以自行阅读。

不同的checkpoint模式

上面只是了解了checkpoint的大体流程，但是不同的checkpoint模式又有区别，有如下的宏来进行区分：

#define SQLITE_CHECKPOINT_PASSIVE  0  /* Do as much as possible w/o blocking */
#define SQLITE_CHECKPOINT_FULL     1  /* Wait for writers, then checkpoint */
#define SQLITE_CHECKPOINT_RESTART  2  /* Like FULL but wait for for readers */
#define SQLITE_CHECKPOINT_TRUNCATE 3  /* Like RESTART but also truncate WAL */

SQLITE_CHECKPOINT_PASSIVE

这个模式下，不会等待读写操作完成，而是基于现有的数据，尽可能将安全的帧回填到数据库文件中。

可以看到，这种模式更接近于一种”步进（step）“的模式：每次回填一部分数据，回填不完就直接返回不再进行。所以，需要某些变量来保存当前的回填进度，这个值保存在WalCkptInfo.nBackfill，所以回填还没有结束的条件也就是：pInfo->nBackfill < pWal->hdr.mxFrame。

SQLITE_CHECKPOINT_FULL

这个模式下，checkpoint操作会等待写操作完成，才继续进行回填操作，而在回填过程中也不再允许有新的写操作进行。

SQLITE_CHECKPOINT_RESTART

对比SQLITE_CHECKPOINT_FULL模式，这一个模式更进了一步：等待所有读操作完成才开始回填操作，同样的，在checkpoint过程中除了不能有写操作还不能有读操作。

SQLITE_CHECKPOINT_TRUNCATE

这一个模式对比SQLITE_CHECKPOINT_RESTART又更近了一步，在回填完毕之后，将截断WAL文件，这样后面新来的wal的写操作，将从wal文件的开始位置开始写。我们前面提到，在wal文件中查找一个页面时，跟wal文件的大小成正比，所以回填完毕截断wal文件重新开始写，会加速后面的查询操作。

错误恢复

以上已经把wal的读、写、checkpoint流程都了解了，最后了解一下wal的错误恢复是如何实现的。

区分几种情况下面的出错崩溃，以及这些情况下都如何恢复的：

• 写事务进行时出错崩溃：这种情况下，显然wal中存储了一部分这个写事务的修改，崩溃恢复时校验后会发现这部分的修改不完全，于是会将这部分修改截断，而数据库文件，根据前面checkpoint流程的讲解，并不会回填还未提交的写事务的修改，所以数据库文件并未损坏。
• 当前没有任何写事务，在进行checkpoint过程中崩溃：在进行checkpoint时，不允许同时并发有写操作。于是这种情况下，wal文件中保存的数据，都是完整的写事务修改数据。启动后校验wal文件发现内容都是对的，于是遍历wal文件，首先将当前wal文件中的内容全部回填至数据库文件中再启动即可。

总结

最后对wal机制做一个简短的总结：

• 与journal备份机制不同的是：journal备份的是修改之前的页面内容，而wal存储的是修改后的内容。
• 于是，wal中可能存储了同一个页面的多次修改结果，因为不同的事务、甚至相同的事务，都有可能修改了同一个页面，而每一次修改都要将修改结果存储wal文件。
• wal文件中，存储一个页面内容的单位是”帧（frame）“，一帧存储一个页面，而反过来一个页面可能先后被存储在不同帧的内容中。于是就需要wal索引数据：
• wal索引需要存储两类数据：一个帧存储的是哪个页面的数据，以及某个页面最新的数据存储在哪一帧。
• 完成一次写操作，wal只需一次sync操作（sync wal文件），journal需要两次（sync journal文件一次，将页面缓存写入数据库文件之后sync数据库文件一次），因此wal的写性能更高。
• wal支持一写多读的并发，但是journal在写的时候不支持同时读数据。
• 有两个重要的变量来保证并发读时不会读到读操作开始之后的修改：mxFrame保存的是当前最提交的写事务写的最大帧数；每个读操作还保存了一个readMark值，存储的是读操作开始时的mxFrame值。
• checkpoint操作，又称为回填（backfill）操作，用于将wal文件的内容同步到数据库文件中，它需要前面的mxFrame和readMark来保证回填操作的正确性。回填操作会影响同时在进行的读、写操作。

参考资料

• Write-Ahead Logging
• WAL-mode File Format
• WAL文件格式见：Database File Format中“4. The Write-Ahead Log”这一小节内容。
• checkpoint中几种模式的解释：Checkpoint a database
• SQLite分析之WAL机制_岩之痕-CSDN博客_sqlite wal
• SQLite3源码学习（31） WAL日志的锁机制_test-CSDN博客