概述

页面管理模块中,很重要的一个功能是缓存页面的内容在内存中:

  • 读页面:如果页面已经在内存,就不需要到文件中读出页面内容。
  • 写页面:如果页面已经在内存,那么对页面的修改就只需要修改页面在内存中的数据即可,被修改了但是还没有落盘的页面,被称为“脏页面(dirty page)“。这样,多次对某个页面的修改,可能最后只需要一次落盘即可。当然,对页面的修改,如果在还没有落盘之前,系统就崩溃了,这种情况下应该如何处理,这就是“崩溃恢复”模块做的事情了。本节中,将专注在“页面缓存”这个子模块的实现。

既然要将页面缓存在内存中,就会涉及到几个功能:

  • 如何知道哪些页面已经被缓存在内存里了?
  • 缓存在内存中的页面如何组织管理?
  • 缓存页面使用的内存不够用时,应该如何处理?

我们首先来了解一下“页面缓存”模块的总体划分:

页面缓存功能的模块划分

按照上图的划分,页面缓存模块分为以下几部分:

  • 页面缓存管理器:实现了页面缓存的总体算法流程,以及提供对外的接口,但是具体到“页面缓存算法”的实现,则有赖于下面这个可用户定制的sqlite3_pcache_methods2。这部分功能在代码pcache.c中。
  • 页面缓存算法:用户可自己定制,只要实现sqlite3_pcache_methods2结构体中的接口即可。系统中的默认实现,在文件pcache1.c中。
  • 除此以外,还需要快速根据页面编号就能知道哪些页面已经被缓存的功能,这部分sqlite使用位图数据结构来实现,在文件bitvec.c中。

页面缓存管理器,核心功能就是维护脏页面链表,缓存页面的管理,诸如根据页面编号查找页面、淘汰页面算法等,都由“页面缓存算法”来维护。可以这样来简单的理解上面的功能划分:

  • “页面缓存管理器”:定义了管理页面缓存的接口、总体流程,维护管理目前在用的脏页面。
  • “页面缓存算法”:维护其它不在使用但还在内存中的页面,负责其淘汰、回收等实现。由“sqlite3_pcache_methods2”结构体实现,用户可以定制自己实现的“sqlite3_pcache_methods2”,系统也提供默认的实现。

两种页面的划分

简而言之,如果把当前在内存中的页面划分为以下两类,那么:

  • 当前在使用的页面:即与页面编号对应的页面,由“页面缓存管理器”维护。
  • 当前还未使用、但也在内存中的页面:即随时准备拿出来存储从磁盘中读出来的数据的页面,由“页面缓存算法”维护,比如淘汰、回收、复用等。

下面,就开始“页面缓存”这几部分功能的具体讲解。

管理页面

页面相关的数据数据结构

首先来看页面相关的数据结构,sqlite中使用PgHdr结构体来在内存中描述一个页面:

/*
** Every page in the cache is controlled by an instance of the following
** structure.
*/
struct PgHdr {
  sqlite3_pcache_page *pPage;    /* Pcache object page handle */
  void *pData;                   /* Page data */
  void *pExtra;                  /* Extra content */
  PCache *pCache;                /* PRIVATE: Cache that owns this page */
  PgHdr *pDirty;                 /* Transient list of dirty sorted by pgno */
  Pager *pPager;                 /* The pager this page is part of */
  Pgno pgno;                     /* Page number for this page */
#ifdef SQLITE_CHECK_PAGES
  u32 pageHash;                  /* Hash of page content */
#endif
  u16 flags;                     /* PGHDR flags defined below */

  /**********************************************************************
  ** Elements above, except pCache, are public.  All that follow are 
  ** private to pcache.c and should not be accessed by other modules.
  ** pCache is grouped with the public elements for efficiency.
  */
  i16 nRef;                      /* Number of users of this page */
  PgHdr *pDirtyNext;             /* Next element in list of dirty pages */
  PgHdr *pDirtyPrev;             /* Previous element in list of dirty pages */
                          /* NB: pDirtyNext and pDirtyPrev are undefined if the
                          ** PgHdr object is not dirty */
};

其中的信息,大部分在注释中已经自解释:

  • pPage:这个字段稍显复杂,后面展开详细解释。
  • pData,pExtra:pData指向了页面实际的内容,pExtra指向页面额外数据,大部分时候,后者的内容可以忽视。
  • pCache:页面缓存管理器对象指针。
  • pDirty:脏页面链表指针。
  • pPager:页面管理器对象指针。(注意和pCache进行区分,pCache是“页面缓存管理器”)。
  • pgno:存储该页面的页面编号。
  • flags:页面标志位,有如下几种,可以通过位操作来加上多个标志位:
    • PGHDR_CLEAN:干净的页面。
    • PGHDR_DIRTY:脏页面。
    • PGHDR_WRITEABLE:已经记录下来修改之前的页面内容,所以此时可以对内存中的页面内容进行修改了。
    • PGHDR_NEED_SYNC:将该页面内容写入数据库文件之前,需要sync journal文件中的页面内容。
    • PGHDR_DONT_WRITE:不需要写页面内容到磁盘。
    • PGHDR_MMAP:该页面内容是通过mmap到内存中的。
    • PGHDR_WAL_APPEND:页面内容已经添加到WAL文件中了。
  • nRef:页面引用计数。
  • pDirtyNext、pDirtyPrev:存储脏页面链表中前、后页面指针,如果该页面不是脏页面,则这两个字段未定义。

可以简略的总结该结构体中的内容,最重要的莫过于以下几项:

  • pData存储的页面内容,所谓的读、写页面内容实际上操作的是这个成员指向的内容。
  • pDirty、pDirtyNext、pDirtyPrev这几个成员维护的脏页面相关的指针。
  • flags维护的页面标志位,通过这些标志位来区分应该对页面进行什么操作。

内存中脏页面的组织

sqlite3_pcache_page数据结构

上面的PgHdr结构体中,还有第一个成员,即sqlite3_pcache_page类型的pPage指针没有讲解,这里展开解释。

前面概述部分提到,“页面缓存算法”的实现,是可以交给用户自定义的,这就带来一个问题:每个自定义的实现,内部实现的管理页面的结构体可能并不相同。于是,就要类似C++中的面向对象机制一样,先声明一个“页面”的基类,基类中定义最基础的成员变量,这样做之后有这样的好处:页面管理模块,所有的操作都能针对这个基类来进行,而不需要管具体实现中的差异。

在这里,这个基类就是成员sqlite3_pcache_page,其定义如下:

typedef struct sqlite3_pcache_page sqlite3_pcache_page;
struct sqlite3_pcache_page {
  void *pBuf;        /* The content of the page */
  void *pExtra;      /* Extra information associated with the page */
};

成员中的用途,注释中也写得挺清楚了:

  • pBuf:指向页面内容。
  • pExtra:保存页面的额外信息。

既然是“基类”,就要求每个子类都要有该基类的信息,实际上也是这样做的,比如“页面缓存算法”的默认实现中,其管理页面的结构体是PgHdr1(后面会展开解释这个结构体),其初始定义如下:

struct PgHdr1 {
  sqlite3_pcache_page page;      /* Base class. Must be first. pBuf & pExtra */
  ...
}

从注释可以看到,sqlite中要求所有实现页面缓存算法中管理页面的数据结构体,都要以sqlite3_pcache_page结构体开始做为第一个成员。

实际上,sqlite3_pcache_page结构体中,pExtra成员包括如下两部分:

  • 额外内容:由系统指定szExtra大小来指定这部分内容大小,简单起见,目前可以认为这部分为0。
  • PgHdr结构体:即前面讲解的页面缓存模块中描述一个页面的结构体大小。

读到这里,有可能把读者绕晕了,我们以代码和图示为引子详细看一下。

首先,创建一个“页面缓存算法”模块时,要调用sqlite3_pcache_methods2结构体中定义的xCreate函数指针来完成,其函数定义如下:

sqlite3_pcache *(*xCreate)(int szPage, int szExtra, int bPurgeable);

传入的第二个参数szExtra需要指定额外部分的内容大小,实际在调用时,这个参数的大小就是我们上面说的szExtra和PgHdr结构体大小之和(做了8字节对齐):

    sqlite3_pcache *pNew;
    pNew = sqlite3GlobalConfig.pcache2.xCreate(
                szPage, pCache->szExtra + ROUND8(sizeof(PgHdr)),
                pCache->bPurgeable

于是,“页面缓存模块”中要获取一个页面时,是通过sqlite3_pcache_methods2结构体中定义的xFetch函数指针来完成的,这个函数指针的定义是:

sqlite3_pcache_page *(*xFetch)(sqlite3_pcache*, unsigned key, int createFlag);

可以看到,这里返回的就是上面说的“基类”,即sqlite3_pcache_page结构体指针。而在内部的默认实现中,其实返回的是PgHdr1指针进行强制转换之后的结果,即sqlite3_pcache_page这一基类的子类,之所以能够做,完全是因为在PgHdr1结构体定义时,把sqlite3_pcache_page结构体成员放在第一个成员:

struct PgHdr1 {
  sqlite3_pcache_page page;      /* Base class. Must be first. pBuf & pExtra */
  ...
}

得到返回的sqlite3_pcache_page指针之后,就能通过其中的pExtra指针拿到PgHdr

PgHdr *sqlite3PcacheFetchFinish(
  PCache *pCache,             /* Obtain the page from this cache */
  Pgno pgno,                  /* Page number obtained */
  sqlite3_pcache_page *pPage  /* Page obtained by prior PcacheFetch() call */
){
  PgHdr *pPgHdr;

  pPgHdr = (PgHdr *)pPage->pExtra;
  // ...
}

总结起来,如下图所示:

sqlite3_pcache_page

页面所在的数据结构

缓存中的页面,可能存在于以下三种数据结构中:

  • 脏页面链表:该链表维护所有当前在使用的页面,由“页面缓存管理器”维护。
  • hash数组:作用是以页面编号为键来查询页面,由默认的“页面缓存算法”来维护。
  • LRU链表:越是常被访问的页面,在LRU链表中就越往前,从LRU链表中淘汰数据都是从链表尾部开始的,也是由默认的“页面缓存算法”来维护。

页面所在的三种数据结构

脏页面链表

这个页面链表叫“脏页面(dirty page)链表”实际上并不十分准确,这会让人误以为这个链表上的页面全都是脏页面,实际上是可能存在干净的页面的。更准确的说法,是当前系统在使用的页面,都维护在这个页面链表中。

操作这个链表的入口函数是pcacheManageDirtyList,其传入的参数一个是PgHdr类型的指针,另一个用于指定行为,有以下三种:

#define PCACHE_DIRTYLIST_REMOVE   1    /* Remove pPage from dirty list */
#define PCACHE_DIRTYLIST_ADD      2    /* Add pPage to the dirty list */
#define PCACHE_DIRTYLIST_FRONT    3    /* Move pPage to the front of the list */

pcacheManageDirtyList函数实现中,也是根据这个参数进行与操作判断来做不同的行为的:

pcacheManageDirtyList实现:
  如果 addRemove & PCACHE_DIRTYLIST_REMOVE:
    从链表上删除
  如果 addRemove & PCACHE_DIRTYLIST_ADD:
    添加到链表头

这里需要注意的是,参数PCACHE_DIRTYLIST_FRONT为3,而另外两个参数一个是1(删除)一个是2,所以当传入PCACHE_DIRTYLIST_FRONT的时候,按照上面的流程,就是首先从链表上删除,再放到链表头。

由于脏页面链表是由“页面缓存管理器”来管理的,所以描述页面的结构体与这个链表相关的数据结构,都在PgHdr上:

struct PgHdr {
  ...
  PgHdr *pDirtyNext;             /* Next element in list of dirty pages */
  PgHdr *pDirtyPrev;             /* Previous element in list of dirty pages */
                          /* NB: pDirtyNext and pDirtyPrev are undefined if the
                          ** PgHdr object is not dirty */
}; 

hash数组

为了快速根据页面编号,查找到该编号的页面是否已经加载到页面中,每个页面的数据还存在于一个hash数组中。

如前所述,这个数据结构由默认的“页面缓存算法”维护,所以与之相关的数据结构,都在结构体PgHdr1上:

struct PgHdr1 {
  ...
  PgHdr1 *pNext;                 /* Next in hash table chain */
};

hash数组的实现,与一般的实现并没有太大区别,这里就不展开说了。

LRU链表

当需要加载当前还不在内存中的页面时,需要首先分配出一块空间,用于保存从文件中加载的页面数据。如前所述,“页面缓存管理器”管理的是还在使用的页面,而“页面缓存算法”管理的是当前没有被使用的页面,所以这部分功能也是由默认的“页面缓存算法”来实现的,与之相关的数据结构,和hash数组的实现一样,也在结构体PgHdr1上:

struct PgHdr1 {
  ...
  PgHdr1 *pLruNext;              /* Next in LRU list of unpinned pages */
  PgHdr1 *pLruPrev;              /* Previous in LRU list of unpinned pages */
                                 /* NB: pLruPrev is only valid if pLruNext!=0 */
};

当需要从“没有被使用的页面”中,分配出来一个页面数据用于保存加载的页面时,就涉及到淘汰问题:如果一个页面虽然当前没有被使用,但是由于经常被访问,所以不应该淘汰这个页面,因为很有可能它马上又会被访问到,应该首先淘汰那些不常被访问的页面,用来加载页面数据。

维护这些信息的数据结构,就是LRU链表:在链表中越往前的数据,意味着被访问的越频繁;反之,淘汰都是从链表尾部开始。

pin和unpin操作

pinunpin操作,在默认的缓存算法中,是针对LRU链表而言的:一个页面数据,如果执行了pin操作,就是将这个页面从LRU链表上摘下来。而unpin操作则反之,将页面放入LRU链表。

为什么需要这两个操作?

再复习一下前面提到的分工:

  • 页面缓存管理器:负责维护在使用的页面。
  • 页面缓存算法:负责维护未使用的页面。

假设一个页面编号为N的页面,被访问时需要加载到内存,此时就会由“页面缓存管理器”加载到内存中,放入脏页面链表;而一旦访问完成,就会调用页面缓存算法的xUnpin函数指针执行unpin操作(实现页面缓存算法的sqlite3_pcache_methods2结构体在后面解释)。

在默认的缓存算法中,执行unpin操作,就是将页面放入LRU链表,并不会将页面从hash数组中删除,也就是说:unpin操作,并不妨碍这个能够以页面编号从hash数组中再次查到该页面的数据。

换言之,unpin操作是在“页面缓存算法”使用完毕某个页面时执行的,只是用来通知“页面缓存算法”:这个页面我已经用不上了,后续怎么处理,可以由“页面缓存算法”自行决定。

于是,对于那些经常被访问的页面,即便当前没有被使用,真正到需要它的时候,只要没有被淘汰出去分配给其他页面,就不再需要再次从文件中加载出来。

页面缓存管理器

页面缓存管理器的数据结构

页面缓存管理器,核心功能就是维护脏页面链表,页面缓存管理器的数据结构中最重要的莫过于以下几个成员:

struct PCache {
  PgHdr *pDirty, *pDirtyTail;         /* List of dirty pages in LRU order */
  PgHdr *pSynced;                     /* Last synced page in dirty page list */
  ...

  int (*xStress)(void*,PgHdr*);       /* Call to try make a page clean */
  void *pStress;                      /* Argument to xStress */
  sqlite3_pcache *pCache;             /* Pluggable cache module */
}

可以看到,有两个维护页面链表相关的指针:

  • 脏页面链表:由成员pDirty, pDirtyTail指向该链表的一头一尾。脏页面链表中,页面是按照LRU的顺序进行排列的,即:越靠近链表尾的页面最可能被淘汰。
  • 最后进行sync的页面指针:在脏页面链表中,pSynced始终指向最后一个已经进行sync操作的页面。

为什么需要多一个pSynced指针?因为在页面缓存紧张的时候,需要快速知道哪些页面已经sync了,这样的页面淘汰的代价最低,具体可以看函数sqlite3PcacheFetchStress的实现,该函数的大体流程是:

分为两步寻找可以淘汰的页面:
  首先在pSynced指针开始往前找不需要sync且引用计数为0的页面
  如果找不到就继续在脏页面链表中寻找引用计数为0的页面
  找到之后,调用注册的xStress进行淘汰操作

除了这几个和脏页面链表相关的数据结构之外,上面还列举出来了其他几个成员:

  • xStress和pStress:在页面缓存出现压力时,需要将页面淘汰同时进行清理,清理页面的操作最终由xStress函数指针来完成。
  • sqlite3_pcache:下面会提到,实现“页面缓存算法”的sqlite3_pcache_methods2结构体,其内部的xCreate函数指针最终会创建出一个sqlite3_pcache返回,后续调用页面缓存算法时,传入的都是这个返回的指针。

页面缓存算法结构体

页面缓存算法,需要实现sqlite3_pcache_methods2接口并且注册到系统中,来看sqlite3_pcache_methods2的定义:

typedef struct sqlite3_pcache_methods2 sqlite3_pcache_methods2;
struct sqlite3_pcache_methods2 {
  int iVersion;
  void *pArg;
  int (*xInit)(void*);
  void (*xShutdown)(void*);
  sqlite3_pcache *(*xCreate)(int szPage, int szExtra, int bPurgeable);
  void (*xCachesize)(sqlite3_pcache*, int nCachesize);
  int (*xPagecount)(sqlite3_pcache*);
  sqlite3_pcache_page *(*xFetch)(sqlite3_pcache*, unsigned key, int createFlag);
  void (*xUnpin)(sqlite3_pcache*, sqlite3_pcache_page*, int discard);
  void (*xRekey)(sqlite3_pcache*, sqlite3_pcache_page*, 
      unsigned oldKey, unsigned newKey);
  void (*xTruncate)(sqlite3_pcache*, unsigned iLimit);
  void (*xDestroy)(sqlite3_pcache*);
  void (*xShrink)(sqlite3_pcache*);
};

逐个解释:

  • iVersion:版本号。
  • pArg:参数。
  • xInit:初始化模块的函数指针,这在模块初始化时一次性调用即可。
  • xShutdown:停止模块的函数指针。
  • xCreate:创建一个“页面缓存算法”的指针sqlite3_pcache返回,注意这个函数里传入了页面大小、额外空间大小,这些都在上面有说明。后续的其他函数指针,传入的第一个参数都是这里返回的sqlite3_pcache指针。
  • xCachesize:返回当前cache大小。
  • xPagecount:返回页面数量。
  • xFetch:核心函数,根据传入的key在缓存中查找页面,如果没有找到则按照createFlag参数来决定后面的行为。
  • xUnpin:页面的引用计数为0时就会调用这个函数。
  • xRekey:表示把页面的key进行修改,这里key其实就是页面编号。
  • xTruncate:将所有页面编号>=iLimit的页面都释放,回收内存。
  • xDestroy:销毁前面xCreate函数返回的sqlite3_pcache指针。
  • xShrink:尽可能的回收内存。

需要说明的是:

  • xInit函数:完成初始化这个模块的工作。
  • xCreate:返回创建一个“页面缓存算法”的指针sqlite3_pcache,后续的所有操作,都使用这个指针。

而sqlite中,其实并没有定义sqlite3_pcache的具体结构,仅仅只是声明了这个类型,可以理解为是一个类似于void*这样的泛型指针:

/*
** CAPI3REF: Custom Page Cache Object
**
** The sqlite3_pcache type is opaque.  It is implemented by
** the pluggable module.  The SQLite core has no knowledge of
** its size or internal structure and never deals with the
** sqlite3_pcache object except by holding and passing pointers
** to the object.
**
** See [sqlite3_pcache_methods2] for additional information.
*/
typedef struct sqlite3_pcache sqlite3_pcache;