SQLite—-Page Cache之事务处理(1)

写在前面：从本章开始，将对SQLite的每个模块进行讨论。讨论的顺序按照我阅读SQLite的顺序来进行，由于项目的需要，以及时间关系，不能给出一个完整的计划，但是我会先讨论我认为比较重要的内容。本节讨论SQLite的事务处理技术，事务处理是DBMS中最关键的技术，对SQLite也一样，它涉及到并发控制，以及故障恢复，由于内容较多，分为两节。好了，下面进入正题。

本节通过一个具体的例子来分析SQLite原子提交的实现（基于Version 3.3.6的代码）。 CREATE TABLE episodes( id integer primary key,name text, cid int) ； 插入一条记录：insert into episodes(name,cid) values(“cat”,1) ; 它经过编译器处理后生成的虚拟机代码如下：

  1. sqlite> explain insert into episodes(name,cid) values("cat",1);
  2. 0|Trace|0|0|0|explain insert into episodes(name,cid) values("cat",1);|00|
  3. 1|Goto|0|12|0||00|
  4. 2|SetNumColumns|0|3|0||00|
  5. 3|OpenWrite|0|2|0||00|
  6. 4|NewRowid|0|2|0||00|
  7. 5|Null|0|3|0||00|
  8. 6|String8|0|4|0|cat|00|
  9. 7|Integer|1|5|0||00|
  10. 8|MakeRecord|3|3|6|dad|00|
  11. 9|Insert|0|6|2|episodes|0b|
  12. 10|Close|0|0|0||00|
  13. 11|Halt|0|0|0||00|
  14. 12|Transaction|0|1|0||00|
  15. 13|VerifyCookie|0|1|0||00|
  16. 14|Transaction|1|1|0||00|
  17. 15|VerifyCookie|1|0|0||00|
  18. 16|TableLock|0|2|1|episodes|00|
  19. 17|Goto|0|2|0||00|

1、初始状态（Initial State）

当一个数据库连接第一次打开时，状态如图所示。图中最右边（“Disk”标注）表示保存在存储设备中的内容。每个方框代表一个扇区。蓝色的块表示这个扇区保存了原始数据。图中中间区域是操作系统的磁盘缓冲区。开始的时候，这些缓存是还没有被使用，因此这些方框是空白的。图中左边区域显示SQLite用户进程的内存。因为这个数据库连接刚刚打开，所以还没有任何数据记录被读入，所以这些内存也是空的。 document/2015-09-15/55f7c36622c27

2、获取读锁(Acquiring A Read Lock)

在SQLite写数据库之前，它必须先从数据库中读取相关信息。比如，在插入新的数据时，SQLite会先从sqlite_master表中读取数据库模式(相当于数据字典)，以便编译器对INSERT语句进行分析，确定数据插入的位置。 在进行读操作之前，必须先获取数据库的共享锁(shared lock)，共享锁允许两个或更多的连接在同一时刻读取数据库。但是共享锁不允许其它连接对数据库进行写操作。 shared lock存在于操作系统磁盘缓存，而不是磁盘本身。文件锁的本质只是操作系统的内核数据结构，当操作系统崩溃或掉电时，这些内核数据也会随之消失。 document/2015-09-15/55f7c380a0816

3、读取数据

一旦得到shared lock，就可以进行读操作。如图所示，数据先由OS从磁盘读取到OS缓存，然后再由OS移到用户进程空间。一般来说，数据库文件分为很多页，而一次读操作只读取一小部分页面。如图，从8个页面读取3个页面。 document/2015-09-15/55f7c3a07a20f

4、获取Reserved Lock

在对数据进行修改操作之前，先要获取数据库文件的Reserved Lock，Reserved Lock和shared lock的相似之处在于，它们都允许其它进程对数据库文件进行读操作。Reserved Lock和Shared Lock可以共存，但是只能是一个Reserved Lock和多个Shared Lock——多个Reserved Lock不能共存。所以，在同一时刻，只能进行一个写操作。 Reserved Lock意味着当前进程(连接)想修改数据库文件，但是还没开始修改操作，所以其它的进程可以读数据库，但不能写数据库。 document/2015-09-15/55f7c3b0c9365

5、创建恢复日志(Creating A Rollback Journal File)

在对数据库进行写操作之前，SQLite先要创建一个单独的日志文件，然后把要修改的页面的原始数据写入日志。回滚日志包含一个日志头(图中的绿色)——记录数据库文件的原始大小。所以即使数据库文件大小改变了，我们仍知道数据库的原始大小。 从OS的角度来看，当一个文件创建时，大多数OS(Windows,Linux,Mac OS X)不会向磁盘写入数据，新创建的文件此时位于磁盘缓存中，之后才会真正写入磁盘。如图，日志文件位于OS磁盘缓存中，而不是位于磁盘。 document/2015-09-15/55f7c3c163a3a

  3. //事务指令的实现
  4. //p1为数据库文件的索引号---0为main database;1为temporary tables使用的文件
  5. //p2 不为0，一个写事务开始
  6. case OP_Transaction: {
  7.     //数据库的索引号
  8.     int i = pOp->p1;
  9.     //指向数据库对应的btree
  10.   Btree *pBt;
  12.   assert( i>=0 && i<db->nDb );
  13.   assert( (p->btreeMask & (1<<i))!=0 );
  14.   //设置btree指针
  15.   pBt = db->aDb[i].pBt;
  17.   if( pBt ){
  18.       //从这里btree开始事务,主要给文件加锁,并设置btree事务状态
  19.     rc = sqlite3BtreeBeginTrans(pBt, pOp->p2);
  21.     if( rc==SQLITE_BUSY ){
  22.       p->pc = pc;
  23.       p->rc = rc = SQLITE_BUSY;
  24.       goto vdbe_return;
  25.     }
  26.     if( rc!=SQLITE_OK && rc!=SQLITE_READONLY /* && rc!=SQLITE_BUSY */ ){
  27.       goto abort_due_to_error;
  28.     }
  29.   }
  30.   break;
  31. }
  33. //开始一个事务,如果第二个参数不为0,则一个写事务开始,否则是一个读事务
  34. //如果wrflag>=2,一个exclusive事务开始,此时别的连接不能访问数据库
  35. int sqlite3BtreeBeginTrans(Btree *p, int wrflag){
  36.   BtShared *pBt = p->pBt;
  37.   int rc = SQLITE_OK;
  39.   btreeIntegrity(p);
  41.   /* If the btree is already in a write-transaction, or it
  42.   ** is already in a read-transaction and a read-transaction
  43.   ** is requested, this is a no-op.
  44.   */
  45.   //如果b-tree处于一个写事务;或者处于一个读事务,一个读事务又请求,则返回SQLITE_OK
  46.   if( p->inTrans==TRANS_WRITE || (p->inTrans==TRANS_READ && !wrflag) ){
  47.     return SQLITE_OK;
  48.   }
  50.   /* Write transactions are not possible on a read-only database */
  51.   //写事务不能访问只读数据库
  52.   if( pBt->readOnly && wrflag ){
  53.     return SQLITE_READONLY;
  54.   }
  56.   /* If another database handle has already opened a write transaction 
  57.   ** on this shared-btree structure and a second write transaction is
  58.   ** requested, return SQLITE_BUSY.
  59.   */
  60.   //如果数据库已存在一个写事务,则该写事务请求时返回SQLITE_BUSY
  61.   if( pBt->inTransaction==TRANS_WRITE && wrflag ){
  62.     return SQLITE_BUSY;
  63.   }
  65.   do {
  66.     //如果数据库对应btree的第一个页面还没读进内存
  67.       //则把该页面读进内存，数据库也相应的加read lock
  68.     if( pBt->pPage1==0 ){
  69.       //加read lock，并读页面到内存
  70.       rc = lockBtree(pBt);
  71.     }
  73.     if( rc==SQLITE_OK && wrflag ){
  74.         //对数据库文件加RESERVED_LOCK锁
  75.       rc = sqlite3pager_begin(pBt->pPage1->aData, wrflag>1);
  76.       if( rc==SQLITE_OK ){
  77.         rc = newDatabase(pBt);
  78.       }
  79.     }
  81.     if( rc==SQLITE_OK ){
  82.       if( wrflag ) pBt->inStmt = 0;
  83.     }else{
  84.       unlockBtreeIfUnused(pBt);
  85.     }
  86.   }while( rc==SQLITE_BUSY && pBt->inTransaction==TRANS_NONE &&
  87.           sqlite3InvokeBusyHandler(pBt->pBusyHandler) );
  89.   if( rc==SQLITE_OK ){
  90.     if( p->inTrans==TRANS_NONE ){
  91.         //btree的事务数加1
  92.       pBt->nTransaction++;
  93.     }
  94.     //设置btree事务状态
  95.     p->inTrans = (wrflag?TRANS_WRITE:TRANS_READ);
  96.     if( p->inTrans>pBt->inTransaction ){
  97.       pBt->inTransaction = p->inTrans;
  98.     }
  99.   }
  101.   btreeIntegrity(p);
  102.   return rc;
  103. }
  105. /*
  106. **获取数据库的写锁,发生以下情况时去除写锁:
  107. **   *  sqlite3pager_commit() is called.
  108. **   *  sqlite3pager_rollback() is called.
  109. **   *  sqlite3pager_close() is called.
  110. **   *  sqlite3pager_unref() is called to on every outstanding page.
  111. **   pData指向数据库的打开的页面,此时并不修改,仅仅只是获取
  112. **   相应的pager,检查它是否处于read-lock状态。
  113. **如果打开的不是临时文件,则打开日志文件.
  114. **如果数据库已经处于写状态，则do nothing
  115. */
  116. int sqlite3pager_begin(void *pData, int exFlag){
  117.   PgHdr *pPg = DATA_TO_PGHDR(pData);
  118.   Pager *pPager = pPg->pPager;
  119.   int rc = SQLITE_OK;
  120.   assert( pPg->nRef>0 );
  121.   assert( pPager->state!=PAGER_UNLOCK );
  122.   //pager已经处于share状态
  123.   if( pPager->state==PAGER_SHARED ){
  124.     assert( pPager->aInJournal==0 );
  125.     if( MEMDB ){
  126.       pPager->state = PAGER_EXCLUSIVE;
  127.       pPager->origDbSize = pPager->dbSize;
  128.     }else{
  129.         //对文件加 RESERVED_LOCK
  130.       rc = sqlite3OsLock(pPager->fd, RESERVED_LOCK);
  131.       if( rc==SQLITE_OK ){
  132.           //设置pager的状态
  133.         pPager->state = PAGER_RESERVED;
  134.         if( exFlag ){
  135.           rc = pager_wait_on_lock(pPager, EXCLUSIVE_LOCK);
  136.         }
  137.       }
  138.       if( rc!=SQLITE_OK ){
  139.         return rc;
  140.       }
  141.       pPager->dirtyCache = 0;
  142.       TRACE2("TRANSACTION %d\n", PAGERID(pPager));
  143.       //使用日志,不是临时文件,则打开日志文件
  144.       if( pPager->useJournal && !pPager->tempFile ){
  145.           //为pager打开日志文件,pager应该处于RESERVED或EXCLUSIVE状态
  146.           //会向日志文件写入header
  147.         rc = pager_open_journal(pPager);
  148.       }
  149.     }
  150.   }
  151.   return rc;
  152. }
  155. //创建日志文件,pager应该处于RESERVED或EXCLUSIVE状态
  156. static int pager_open_journal(Pager *pPager){
  157.   int rc;
  158.   assert( !MEMDB );
  159.   assert( pPager->state>=PAGER_RESERVED );
  160.   assert( pPager->journalOpen==0 );
  161.   assert( pPager->useJournal );
  162.   assert( pPager->aInJournal==0 );
  163.   sqlite3pager_pagecount(pPager);
  164.   //日志文件页面位图
  165.   pPager->aInJournal = sqliteMalloc( pPager->dbSize/8 + 1 );
  166.   if( pPager->aInJournal==0 ){
  167.     rc = SQLITE_NOMEM;
  168.     goto failed_to_open_journal;
  169.   }
  170.   //打开日志文件
  171.   rc = sqlite3OsOpenExclusive(pPager->zJournal, &pPager->jfd,
  172.                                  pPager->tempFile);
  173.   //日志文件的位置指针
  174.   pPager->journalOff = 0;
  175.   pPager->setMaster = 0;
  176.   pPager->journalHdr = 0;
  177.   if( rc!=SQLITE_OK ){
  178.     goto failed_to_open_journal;
  179.   }
  180.   /*一般来说，os此时创建的文件位于磁盘缓存，并没有实际
  181.   **存在于磁盘,下面三个操作就是为了把结果写入磁盘,而对于
  182.   **windows系统来说,并没有提供相应API，所以实际上没有意义.
  183.   */
  184.   //fullSync操作对windows没有意义
  185.   sqlite3OsSetFullSync(pPager->jfd, pPager->full_fsync);
  186.   sqlite3OsSetFullSync(pPager->fd, pPager->full_fsync);
  187.   /* Attempt to open a file descriptor for the directory that contains a file. 
  188.   **This file descriptor can be used to fsync() the directory
  189.   **in order to make sure the creation of a new file is actually written  to disk.
  190.   */
  191.   sqlite3OsOpenDirectory(pPager->jfd, pPager->zDirectory);
  192.   pPager->journalOpen = 1;
  193.   pPager->journalStarted = 0;
  194.   pPager->needSync = 0;
  195.   pPager->alwaysRollback = 0;
  196.   pPager->nRec = 0;
  197.   if( pPager->errCode ){
  198.     rc = pPager->errCode;
  199.     goto failed_to_open_journal;
  200.   }
  201.   pPager->origDbSize = pPager->dbSize;
  202.   //写入日志文件的header---24个字节
  203.   rc = writeJournalHdr(pPager);
  205.   if( pPager->stmtAutoopen && rc==SQLITE_OK ){
  206.     rc = sqlite3pager_stmt_begin(pPager);
  207.   }
  208.   if( rc!=SQLITE_OK && rc!=SQLITE_NOMEM ){
  209.     rc = pager_unwritelock(pPager);
  210.     if( rc==SQLITE_OK ){
  211.       rc = SQLITE_FULL;
  212.     }
  213.   }
  214.   return rc;
  216. failed_to_open_journal:
  217.   sqliteFree(pPager->aInJournal);
  218.   pPager->aInJournal = 0;
  219.   if( rc==SQLITE_NOMEM ){
  220.     /* If this was a malloc() failure, then we will not be closing the pager
  221.     ** file. So delete any journal file we may have just created. Otherwise,
  222.     ** the system will get confused, we have a read-lock on the file and a
  223.     ** mysterious journal has appeared in the filesystem.
  224.     */
  225.     sqlite3OsDelete(pPager->zJournal);
  226.   }else{
  227.     sqlite3OsUnlock(pPager->fd, NO_LOCK);
  228.     pPager->state = PAGER_UNLOCK;
  229.   }
  230.   return rc;
  231. }
  233. /*写入日志文件头
  234. **journal header的格式如下:
  235. ** - 8 bytes: 标志日志文件的魔数
  236. ** - 4 bytes: 日志文件中记录数
  237. ** - 4 bytes: Random number used for page hash.
  238. ** - 4 bytes: 原来数据库的大小(kb)
  239. ** - 4 bytes: 扇区大小512byte
  240. */
  241. static int writeJournalHdr(Pager *pPager){
  242.   //日志文件头
  243.   char zHeader[sizeof(aJournalMagic)+16];
  245.   int rc = seekJournalHdr(pPager);
  246.   if( rc ) return rc;
  248.   pPager->journalHdr = pPager->journalOff;
  249.   if( pPager->stmtHdrOff==0 ){
  250.     pPager->stmtHdrOff = pPager->journalHdr;
  251.   }
  252.   //设置文件指针指向header之后
  253.   pPager->journalOff += JOURNAL_HDR_SZ(pPager);
  255.   /* FIX ME: 
  256.   **
  257.   ** Possibly for a pager not in no-sync mode, the journal magic should not
  258.   ** be written until nRec is filled in as part of next syncJournal(). 
  259.   **
  260.   ** Actually maybe the whole journal header should be delayed until that
  261.   ** point. Think about this.
  262.   */
  263.   memcpy(zHeader, aJournalMagic, sizeof(aJournalMagic));
  264.   /* The nRec Field. 0xFFFFFFFF for no-sync journals. */
  265.   put32bits(&zHeader[sizeof(aJournalMagic)], pPager->noSync ? 0xffffffff : 0);
  266.   /* The random check-hash initialiser */ 
  267.   sqlite3Randomness(sizeof(pPager->cksumInit), &pPager->cksumInit);
  268.   put32bits(&zHeader[sizeof(aJournalMagic)+4], pPager->cksumInit);
  269.   /* The initial database size */
  270.   put32bits(&zHeader[sizeof(aJournalMagic)+8], pPager->dbSize);
  271.   /* The assumed sector size for this process */
  272.   put32bits(&zHeader[sizeof(aJournalMagic)+12], pPager->sectorSize);
  273.   //写入文件头
  274.   rc = sqlite3OsWrite(pPager->jfd, zHeader, sizeof(zHeader));
  276.   /* The journal header has been written successfully. Seek the journal
  277.   ** file descriptor to the end of the journal header sector.
  278.   */
  279.   if( rc==SQLITE_OK ){
  280.     rc = sqlite3OsSeek(pPager->jfd, pPager->journalOff-1);
  281.     if( rc==SQLITE_OK ){
  282.       rc = sqlite3OsWrite(pPager->jfd, "\000", 1);
  283.     }
  284.   }
  285.   return rc;
  286. }

其实现过程如下图所示： document/2015-09-15/55f7c3eba1fd4