sqlite3.36版本 btree实现（一）- 管理页面缓存

2021-12-17
15分钟阅读时长
存储 , 存储引擎
sqlite3.36版本 btree实现

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

概述

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

  • 读页面：如果页面已经在内存，就不需要到文件中读出页面内容。
  • 写页面：如果页面已经在内存，那么对页面的修改就只需要修改页面在内存中的数据即可，被修改了但是还没有落盘的页面，被称为“脏页面（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操作

pin和unpin操作，在默认的缓存算法中，是针对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;

总结

sqlite里的页面缓存，分为两个大的模块：

  • 页面缓存管理器：主要任务是管理脏页面，以及对外提供根据页面编号查询页面的接口，当某个页面不在内存时，自动将其加载到内存中。
  • 页面缓存算法：负责实现页面的缓存、淘汰、查询。这是可以由用户自己实现的模块，需要实现对应的sqlite3_pcache_methods2结构体即可，也提供了默认的实现。

在内存中的页面，在以下几个数据结构中：

  • 脏页面链表，由页面缓存管理器维护。
  • Hash数组：根据页面编号查询到页面数据的指针，由默认的页面缓存算法维护。
  • LRU链表：负责淘汰页面，由默认的页面缓存算法维护。
#存储 #存储引擎 #sqlite #btree
下一页 sqlite3.36版本 btree实现（零）- 起步及概述

相关

sqlite3.36版本 btree实现（零）- 起步及概述
boltdb 1.3.0实现分析（四）
boltdb 1.3.0实现分析（三）
boltdb 1.3.0实现分析（二）
boltdb 1.3.0实现分析（一）
B树、B+树索引算法原理（下）