SQLite--OS

自底向上看sqlite的时候发现自己欠缺和遗忘了好多知识（尤其是操作系统）。如果能把这个sqlite的系列都写完的话，在操作系统上，尤其是文件和内存管理上能有不少的知识复习和提升 :)。

简述

本文主要讲述Sqlite的最底下那层，也就是OS-Interface(后面我们统一叫os层)的原理和实现。

从接口上来看，OS层主要是对上层屏蔽了不同操作系统下的文件操作实现。OS层提供了统一的以sqlite3Os为前缀的接口方法给上层，实现了包括文件读写，文件创建/删除，sqlite文件锁，以及一些与系统实现相关的Util类操作，例如sqlite3OsSleep、sqlite3OsCurrentTimeInt64等等。这些接口方法都在os.h的头文件中声明了。

OS层主要实现了文件操作，锁，以及共享内存，三大块的内容。共享内存可以看这篇文章。本文就从另外两个角度去看OS是如何提供平台无关的接口。而其中锁是本层的一个核心功能，SQLite的多线程乃至跨进程的并发读写很大程度上就是依赖了这个锁的实现。

一般在移动设备上（尤其是iOS）多进程读写文件在操作系统层面上就被禁止了，所以有些框架（WCDB）为了减少一些文件锁带来的读写性能开销，直接把文件锁禁用了，打开即独占。

初始化

os层还有一个别的名字，叫vfs（virtual file system）。sqlite在很多地方都使用了插件化和模块化的设计，例如cache，extension…还有就是这里的vfs。

在sqlite最早初始化的时候会调用sqlite3_os_init()方法，这个方法除了测试一下malloc方法之外，剩下的就是初始化vfs了。

函数原型

1	int sqlite3_os_init(void);

sqlite是跨平台组件，实现大体上都差不太多，这里我们只看unix的实现，如果不同平台实现差别较大的地方，我们再另外提及。

文件

文件结构

Sqlite从OS层向外暴露的是sqlite3_file这个数据结构，标识了一个数据库文件。而这个sqlite3_file更多的可以理解为一个接口，它抽象出了很多vfs的方法。而不同平台下的vfs会有不同的文件数据结构，例如unixFile就是在Unix系统下的一个vfs实现。

在unixFile这个数据结构内存储了很多这个文件当前的属性。UnixFile，sqlite3_file 这些数据结构是相对于连接而言的，也就是说，不同的连接持有的是不同的file对象，可以对应到操作系统中的文件描述符。

文件inode

在Unix中，对于同一个数据库文件或者是同一个数据库文件的不同连接（软连接或硬连接），在sqlite3中可以多次打开，他们也是不同的file对象。对于这个情况，Unix的vfs针对file node也做了管理。

每个打开的文件都会有一个文件描述符与之对应，但是在操作系统中，文件的实际索引是由inode来决定的。同一个文件或者文件链接打开多次，会有不同的文件描述符，但是文件的实际索引不变。

unixInodeInfo这个数据结构描述了unix中一个文件的实际索引信息。unixFile和unixInodeInfo是多对一的关系。unixInodeInfo中会有一个nRef变量来记录当前还有多少个文件描述符(unixFile)，在持有这个文件索引。每打开一次文件nRef++，关闭一次nRef–。另外在关闭一个已打开的文件描述符的时候，Sqlite不会立即关闭。在unixInodeInfo中用一个链表UnixUnusedFd描述了当前文件索引下，不再使用的文件描述符。以便再次打开该数据库。当nRef降至0时，Sqlite才会真正关闭数据库文件。

数据结构

/*
 * 标识UNIX的文件索引,对所有持有这个InodeInfo的UnixFile做了引用计数
 */
struct unixInodeInfo {
  struct unixFileId fileId;       /* The lookup key */
  sqlite3_mutex *pLockMutex;      /* Hold this mutex for... */
  int nShared;                      /* Number of SHARED locks held */
  int nLock;                        /* Number of outstanding file locks */
  unsigned char eFileLock;          /* One of SHARED_LOCK, RESERVED_LOCK etc. */
  unsigned char bProcessLock;       /* An exclusive process lock is held */
  UnixUnusedFd *pUnused;            /* Unused file descriptors to close */
  int nRef;                       /* Number of pointers to this structure */
  unixShmNode *pShmNode;          /* Shared memory associated with this inode */
  unixInodeInfo *pNext;           /* List of all unixInodeInfo objects */
  unixInodeInfo *pPrev;           /*    .... doubly linked */
};

在Sqlite中有一个全局变量 static unixInodeInfo *inodeList = 0; 用一个双向链表记录了，当前进程内打开的所有文件索引。

锁

POSIX设计的锁做不到在同一个进程内不同线程之间互斥。因为按照POSIX的设计，文件锁的最小粒度是进程，所以只要
在同一个进程内，不同线程的锁，是可以相互覆盖的。

举个例子，如果线程AB在同一个进程内，线程A先请求了某个文件某个区域的写锁，这个时候，线程B如果再去请求同一个区域的写锁的时候，是可以成功的。因为锁分配的最小单位是进程。

另外，对于不同的文件描述符，但是是同一个文件索引，操作系统在对文件加锁的时候，是会对实际的文件（文件索引）加锁，而不是硬链接或者软链接。

举个例子，如果一个文件有两个软链接，在同一个进程内分别对这两个软链接指向的文件进行锁操作的时候，操作的实际是同一个文件。

根据上面的问题描述，那么Sqlite 如果想要实现多线程操作一个文件，必然需要实现多线程下的文件锁互斥。也就是说Sqlite需要在进程内，把锁的粒度控制在线程上。
当关闭文件的时候，操作系统会释放掉当前进程在改文件上的所有锁。所以还需要管理进程内对每个文件的锁，所有线程都释放锁的时候，才会真正释放进程对文件的锁。

Sqlite 锁的设计

与简单的读写锁不同，Sqlite内部有5种锁状态：UNLOCKED,SHARED,RESERVED,PENDING,EXCLUSIVE。这5个锁的状态是存储在inode的eFileLock上。

UNLOCKED:这个没有什么疑问，就是没有加锁的状态，任何文件初始状态都是这个。
SHARED:共享锁，也叫读锁，如果想要读一个文件，那么这个文件的锁级别必须至少是SHARED。同一个文件上的共享锁可以存在多个。共享锁是所有锁的第一步，想要获取任何高级别的锁，必须要先获取共享锁。
RESERVED:保留锁，保留锁是用来过渡想要从共享锁提升到高级锁的一个暂度期。在这个锁的状态下，可以继续有新的共享锁出现。
PENDING:未决锁，这个锁表示，当前连接马上要写数据库了。但是也不能把所有读锁都剥夺，这样会有问题。所以在这个级别的锁下，可以保持现有的锁。但是不能有新的共享锁了。
EXCLUSIVE:排它锁，在排它锁下，只有当前这个连接可以读写数据库。这个锁的级别最高。

在os层有5个类型的锁，但是os暴露出来的只有4个类型。其中的PENDING，是os的内部锁。

接下来我们详细看下锁升降级的两个函数，理解Sqlite是如何设计锁的。

锁的结构

简单画了一张图，描述了单个文件下的不同文件锁状态。

解释一下图，绿色表示读锁，红色表示写锁。

从上到下，依次是:Shared锁，Shared->Reserved锁，Shared->Reserved->Pending锁，Shared->Pending锁，Shared->Reserved->Pending->Exclusive锁，Shared->Pending->Exclusive锁。这些锁的转换下文会细说。

1GB:
因为在Windows上锁是强制性的，加锁区间不能存储数据。所以这个区间必然不能被分配为一个page。page的大小是[512,32768]，为了让这个锁的区间可以在一个page内，所以整个锁的区间大小为512 bytes。
SharedBytes:
在Win95/98/ME上，操作系统没有提供读写锁，因此，在shared byte上写并行会存在问题。sqlite把这块区域放大到510字节，每次加读锁的时候，从510个字节中随机取一个。有概率会失败，但毕竟这也算是一个曲线救国的方案吧。
图中描述的是文件锁，文件锁的状态实际是存储在file的inode中（unixInodeInfo）。

锁的升级

1
2

//os.h 中声明了这个方法，用来给外部调用，第一个参数是抽象文件对象，第二个参数是锁的级别，即上面提到4种锁的枚举值。
int sqlite3OsLock(sqlite3_file*, int);

锁的状态转换：

UNLOCKED -> SHARED
从未加锁状态转换到共享锁读锁：

如果当前文件描述符对应的文件索引已经持有了共享锁或者保留锁，那么就只需要在InodeInfo上增加nShared、nLock的计数，并修改文件描述符内文件的锁状态即可。否则就会走下面的加锁流程：
1. 在pending byte位上加读锁
2. 在所有的SHARED_BYTES上加读锁
3. 移除掉pending byte位上的读锁
SHARED -> RESERVED
从共享读锁升级到保留锁：
1. 当前已经持有共享锁，直接在保留锁位上加写锁
SHARED -> (PENDING) -> EXCLUSIVE
从共享读锁直接升级到排他锁：
1. 如果当前InodeInfo持有的锁不是Pending，那么先在pending上加写锁
2. 如果InodeInfo上还有其他共享读锁（nShared>1），那么直接返回SQLITE_BUSY。此时InodeInfo和unixFile持有的都是Pending锁，不会回滚Pending锁。
3. 把所有的SHARED_BYTES上加写锁。
RESERVED -> (PENDING) -> EXCLUSIVE
从保留锁升级到排他锁：
1. 与上一个步骤一样。
PENDING -> EXCLUSIVE
从未决锁升级到排他锁：
1. 直接尝试 SHARED -> (PENDING) -> EXCLUSIVE的步骤 3

其他说明：

unlocked状态只能升级到shared状态，也就是说，锁状态必须从共享读锁开始向上升级。
Sqlite不接受直接请求pending锁，也就是Pending锁只是内部使用。
SQLITE_BUSY:
当前文件描述符持有的锁与文件索引实际持有的状态不一致时（即文件实际锁状态级别高于文件描述符的锁的状态，即文件实际锁状态至少为共享锁）
a. Inode 实际锁 >= pending时，即表示有其他线程等待写入文件，当前文件描述符请求任何锁失败（因为pending的时候不允许有shared）。
b. Inode 实际锁 < pending时，请求的锁 > shared时（即保留锁和排它锁），请求锁返回失败。

对于面向OS接口而言，没有PENDING->EXCLUSIVE这个升级过程，因为PENDING锁是不会以一个独立的锁的状态存在。而是在一个文件因为还有正在读的进程，而尝试加写锁失败的时候，此时unixFile才会停滞于Pending锁状态，等待下一次的加锁重试。

锁的降级

1 2	// 降低锁的级别 int sqlite3OsUnlock(sqlite3_file*, int);

其中第二个参数只能是 SHARE_LOCK 或者 NO_LOCK…换句话说，文件描述符持有的锁只能降低为读锁或者无锁。

分两种情况讨论：

降级为无锁：
1. 将pending + reserved + shared_size 全部降为 UNLOCK
2. 文件索引Inode上的 nShared– 以及 nLock–
降级为共享读锁：

降级到读锁的时候稍微麻烦一点。理论上来说和无锁应该一样，把pending+reserved全部降为UNLOCK，shared_size降为读锁即可。但是，在某些BSD 的NFS上会出现某个区间写锁降到读锁的时候会出现失败的bug。

Sqlite针对上面的情况，做了兼容：在此类操作系统上，先把(shared_size - 1)个bytes降为无锁，然后再把这些bytes升级为读锁，最后把剩下的最后一个byte降为无锁。这样避免了在从写锁降到读锁的时候，出现竞争条件的问题。