YY哥的技術(shù)隨筆

——關(guān)注Linux、數(shù)據(jù)庫(kù)和云計(jì)算

SQLite入門與分析(七)---淺談SQLite的虛擬機(jī)

寫在前面：虛擬機(jī)技術(shù)在現(xiàn)在是一個(gè)非常熱的技術(shù)，它的歷史也很悠久。最早的虛擬機(jī)可追溯到IBM的VM/370，到上個(gè)世紀(jì)90年代，在計(jì)算機(jī)程序設(shè)計(jì)語(yǔ)言領(lǐng)域又出現(xiàn)一件革命性的事情——Java語(yǔ)言的出現(xiàn)，它與c++最大的不同在于它必須在Java虛擬機(jī)上運(yùn)行。Java虛擬機(jī)掀起了虛擬機(jī)技術(shù)的熱潮，隨后，Microsoft也不甘落后，雄心勃勃的推出了.Net平臺(tái)。由于在這里主要討論SQLite的虛擬機(jī)，不打算對(duì)這些做過(guò)多評(píng)論，但是作為對(duì)比，我會(huì)先對(duì)Java虛擬機(jī)作一個(gè)概述。好了，下面進(jìn)入正題。

1、概述
所謂虛擬機(jī)是指對(duì)真實(shí)計(jì)算機(jī)資源環(huán)境的一個(gè)抽象，它為解釋性語(yǔ)言程序提供了一套完整的計(jì)算機(jī)接口。虛擬機(jī)的思想對(duì)現(xiàn)在的編譯有很大影響，其思路是先編譯成虛擬機(jī)指令，然后針對(duì)不同計(jì)算機(jī)實(shí)現(xiàn)該虛擬機(jī)。
虛擬機(jī)定義了一組抽象的邏輯組件，這些組件包括寄存器組、數(shù)據(jù)棧和指令集等等。虛擬機(jī)指令的解釋執(zhí)行包括3步：
1．獲取指令參數(shù)；
2. 執(zhí)行該指令對(duì)應(yīng)的功能；
3. 分派下一條指令。
其中第一步和第三步構(gòu)成了虛擬機(jī)的執(zhí)行開(kāi)銷。
很多語(yǔ)言都采用了虛擬機(jī)作為運(yùn)行環(huán)境。作為下一代計(jì)算平臺(tái)的競(jìng)爭(zhēng)者，Sun的Java和微軟的.NET平臺(tái)都采用了虛擬機(jī)技術(shù)。Java的支撐環(huán)境是Java虛擬機(jī)（Java Virtual Machine，JVM），.NET的支撐環(huán)境是通用語(yǔ)言運(yùn)行庫(kù)（Common Language Runtime，CLR）。JVM是典型的虛擬機(jī)架構(gòu)。
Java平臺(tái)結(jié)構(gòu)如圖所示。從圖中可以看出，JVM處于核心位置，它的下方是移植接口。移植接口由依賴平臺(tái)的和不依賴平臺(tái)的兩部分組成，其中依賴于平臺(tái)的部分稱為適配器。JVM通過(guò)移植接口在具體的操作系統(tǒng)上實(shí)現(xiàn)。如果在Java操作系統(tǒng)（Java Operation System, JOS）上實(shí)現(xiàn)，則不需要依賴于平臺(tái)的適配器，因?yàn)檫@部分工作已由JOS完成。因此對(duì)于JVM來(lái)說(shuō)，操作系統(tǒng)和更低的硬件層是透明的。在JVM的上方，是Java類和Java應(yīng)用程序接口（Java API）。在Java API上可以編寫Java應(yīng)用程序和Java小程序（applet）。所以對(duì)于Java應(yīng)用程序和applet這一層次來(lái)說(shuō)，操作系統(tǒng)和硬件就更是透明的了。我們編寫的Java程序，可以在任何Java平臺(tái)上運(yùn)行而無(wú)需修改。

JVM定義了獨(dú)立于平臺(tái)的類文件格式和字節(jié)碼形式的指令集。在任何Java程序的字節(jié)碼表示形式中，變量和方法的引用都是使用符號(hào)，而不是使用具體的數(shù)字。由于內(nèi)存的布局要在運(yùn)行時(shí)才確定，所以類的變量和方法的改變不會(huì)影響現(xiàn)存的字節(jié)碼。例如，一個(gè)Java程序引用了其他系統(tǒng)中的某個(gè)類，該系統(tǒng)中那個(gè)類的更新不會(huì)使這個(gè)Java程序崩潰。這也提高了Java的平臺(tái)獨(dú)立性。

虛擬機(jī)一般都采用了基于棧的架構(gòu)，這種架構(gòu)易于實(shí)現(xiàn)。虛擬機(jī)方法顯著提高了程序語(yǔ)言的可移植性和安全性，但同時(shí)也導(dǎo)致了執(zhí)行效率的下降。

2、Java虛擬機(jī)

2.1、概述
Java虛擬機(jī)的主要任務(wù)是裝載Class文件并執(zhí)行其中的字節(jié)碼。Java虛擬機(jī)包含一個(gè)類裝載器(class loader)，它從程序和API中裝載class文件，Java API中只有程序執(zhí)行時(shí)需要的那些類才會(huì)被裝載，字節(jié)碼由執(zhí)行引擎來(lái)執(zhí)行。
不同的Java虛擬機(jī)，執(zhí)行引擎的實(shí)現(xiàn)可能不同。在軟件實(shí)現(xiàn)的虛擬機(jī)中，一般有幾下幾中實(shí)現(xiàn)方式：
（1）   解釋執(zhí)行：實(shí)現(xiàn)簡(jiǎn)單，但速度較慢，這是Java最初階段的實(shí)現(xiàn)方式。
（2）   即時(shí)編譯(just-in-time)：執(zhí)行較快，但消耗內(nèi)存。在這種情況下，第一次執(zhí)行的字節(jié)碼會(huì)編譯成本地機(jī)器代碼，然后被緩存，以后可以重用。
（3）   自適應(yīng)優(yōu)化器：虛擬機(jī)開(kāi)始的時(shí)候解釋字節(jié)碼，但是會(huì)監(jiān)視程序的運(yùn)行，并記錄下使用最頻繁的代碼，然后把這些代碼編譯成本地代碼，而其它的代碼仍保持為字節(jié)碼。該方法既提高的運(yùn)行速度，又減少了內(nèi)存開(kāi)銷。
同樣，虛擬機(jī)也可由硬件來(lái)實(shí)現(xiàn)，它用本地方法執(zhí)行Java字節(jié)碼。

2.2、Java虛擬機(jī)

Java虛擬機(jī)的結(jié)構(gòu)分為：類裝載子系統(tǒng)，運(yùn)行時(shí)數(shù)據(jù)區(qū)，執(zhí)行引擎，本地方法接口。其中運(yùn)行時(shí)數(shù)據(jù)區(qū)又分為：方法區(qū)，堆，Java棧，PC寄存器，本地方法棧。

關(guān)于Java虛擬機(jī)就介紹到此,由于Java虛擬機(jī)內(nèi)容龐大，在這里不可能一一介紹，如果想更多了解Java虛擬機(jī)，參見(jiàn)《深入Java虛擬機(jī)》。

3、SQLite虛擬機(jī)

在SQLite的后端（backend）的上一層，通常叫做虛擬數(shù)據(jù)庫(kù)引擎(virtual database engine)，或者叫做虛擬機(jī)(virtual machine)。從作用上來(lái)說(shuō)，它是SQLite的核心。用戶程序發(fā)出的SQL語(yǔ)句請(qǐng)求，由前端(frontend)編譯器（以后會(huì)繼續(xù)介紹）處理，生成字節(jié)代碼程序（bytecode programs），然后由VM解釋執(zhí)行。VM執(zhí)行時(shí)，又會(huì)調(diào)用B-tree模塊的相關(guān)的接口，并輸出執(zhí)行的結(jié)果（本節(jié)將以一個(gè)具體的查詢過(guò)程來(lái)描述這一過(guò)程）。

3.1、虛擬機(jī)的內(nèi)部結(jié)構(gòu)

先來(lái)看一個(gè)簡(jiǎn)單的例子：

int main(int argc, char **argv)
{
    int rc, i,  id, cid;
    char *name;
    char *sql;
    char *zErr;
    sqlite3 *db; sqlite3_stmt *stmt;
    sql="select id,name,cid from episodes";
    //打開(kāi)數(shù)據(jù)庫(kù)
    sqlite3_open("test.db", &db);
    //編譯sql語(yǔ)句
    sqlite3_prepare(db, sql, strlen(sql), &stmt, NULL);
    //調(diào)用VM，執(zhí)行VDBE程序
    rc = sqlite3_step(stmt);

    while(rc == SQLITE_ROW) {
        id = sqlite3_column_int(stmt, 0);
        name = (char *)sqlite3_column_text(stmt, 1);
        cid = sqlite3_column_int(stmt, 2);
        if(name != NULL){
            fprintf(stderr, "Row:  id=%i, cid=%i, name='%s'\n", id,cid,name);
        } else {
            /* Field is NULL */
            fprintf(stderr, "Row:  id=%i, cid=%i, name=NULL\n", id,cid);
        }
        rc = sqlite3_step(stmt);
    }
    //釋放資源
    sqlite3_finalize(stmt);
    //關(guān)閉數(shù)據(jù)庫(kù)
    sqlite3_close(db);
    return 0;
}

這段程序很簡(jiǎn)單，它的功能就是遍歷整個(gè)表，并把查詢結(jié)果輸出。
在SQLite 中，用戶發(fā)出的SQL語(yǔ)句，都會(huì)由編譯器生成一個(gè)虛擬機(jī)實(shí)例。在上面的例子中，變量sql代表的SQL語(yǔ)句經(jīng)過(guò)sqlite3_prepare()處理后，便生成一個(gè)虛擬機(jī)實(shí)例——stmt。虛擬機(jī)實(shí)例從外部看到的結(jié)構(gòu)是sqlite3_stmt所代表的數(shù)據(jù)結(jié)構(gòu)，而在內(nèi)部，是一個(gè)vdbe數(shù)據(jù)結(jié)構(gòu)代表的實(shí)例。
關(guān)于這點(diǎn)可以看看它們的定義：
//sqlite3.h
typedef struct sqlite3_stmt sqlite3_stmt;

vdbe的定義：

Code

由vdbe的定義，可以總結(jié)出SQLite虛擬機(jī)的內(nèi)部結(jié)構(gòu)：

3.2、指令

int nOp; /* Number of instructions in the program(指令的條數(shù)) */
Op *aOp; /* Space to hold the virtual machine's program(指令)*/

aOp數(shù)組保存有SQL經(jīng)過(guò)編譯后生成的所有指令，對(duì)于上面的例子為：

0、Goto(0x5b-91)    |0|0c
1、Integer(0x2d-45) |0|0
2、OpenRead(0x0c-12)|0|2
3、SetNumColumns(0x64-100)|0|03
4、Rewind(0x77-119) |0|0a
5、Rowid(0x23-35)   |0|0
6、Column(0x02-2)   |0|1
7、Column(0x02-2)   |0|2
8、Callback(0x36-54)|3|0
9、Next(0x68)       |0|5
10、Close
11、Halt
12、Transaction(0x66-102)|0|0
13、VerifyCookie(0x61-97)|0|1
14、Goto(0x5b-91)    |0|1|

sqlite3_step()引起VDBE解釋引擎執(zhí)行這段代碼，下面來(lái)分析該段指令的執(zhí)行過(guò)程：

Goto：這是一條跳轉(zhuǎn)指令，它的作用僅僅是跳到第12條指令；
Transaction：開(kāi)始一個(gè)事務(wù)（讀事務(wù)）；
Goto：跳到第1條指令；
Integer：把操作數(shù)P1入棧，這里的0表示OpenRead指令打開(kāi)的數(shù)據(jù)庫(kù)的編號(hào)；
OpenRead：打開(kāi)表的游標(biāo),數(shù)據(jù)庫(kù)的編號(hào)從棧頂中取得，P1為游標(biāo)的編號(hào)，P2為root page。
如果P2<=0,則從棧中取得root page no；

SetNumColumns：對(duì)P1確定的游標(biāo)的列數(shù)設(shè)置為P2（在這里為3），在OP_Column指令執(zhí)行前,該指令應(yīng)該被調(diào)用來(lái)

設(shè)置表的列數(shù)；

Rewind：移動(dòng)當(dāng)前游標(biāo)（P1）移到表或索引的第一條記錄；
Rowid：把當(dāng)前游標(biāo)（P1）指向的記錄的關(guān)鍵字壓入棧；
Column：解析當(dāng)前游標(biāo)指定的記錄的數(shù)據(jù)，p1為當(dāng)前游標(biāo)索引號(hào)，p2為列號(hào)，并將結(jié)果壓入棧中；

Callback：該指令執(zhí)行后，PC將指向下一條指令。該指令的執(zhí)行會(huì)結(jié)束sqlite3_step()的運(yùn)行，并向其返回

SQLITE_ROW ——如果存在記錄的話；并將VDBE的PC指針指向下一條指令——即Next指令，所以當(dāng)

重新調(diào)用sqlite3_step()執(zhí)行VDBE程序時(shí)，會(huì)執(zhí)行Next指令（具體的分析見(jiàn)后面的指令實(shí)例分析）；

Next：將游標(biāo)移到下一條記錄，并將PC指向第5條指令；
Close：關(guān)閉數(shù)據(jù)庫(kù)。

3.3、棧

Mem *aStack; /* The operand stack, except string values(?？臻g) */
Mem *pTos; /* Top entry in the operand stack(棧頂指針) */

aStack是VDBE執(zhí)行時(shí)使用的棧，它主要用來(lái)保指令執(zhí)行進(jìn)需要的參數(shù)，以及指令執(zhí)行時(shí)產(chǎn)生的中間結(jié)果(參見(jiàn)后面的指令實(shí)例分析)。
在計(jì)算機(jī)硬件領(lǐng)域，基于寄存器的架構(gòu)已經(jīng)壓倒基于棧的架構(gòu)成為當(dāng)今的主流，但是在解釋性的虛擬機(jī)領(lǐng)域，基于棧架構(gòu)的實(shí)現(xiàn)占了上風(fēng)。
1. 從編譯的角度來(lái)看，許多編程語(yǔ)言可以很容易地被編譯成棧架構(gòu)機(jī)器語(yǔ)言。如果采用寄存器架構(gòu)，編譯器為了獲得好的性能必須進(jìn)行優(yōu)化，如全局寄存器分配（這需要對(duì)數(shù)據(jù)流進(jìn)行分析）。這種復(fù)雜的優(yōu)化工作使虛擬機(jī)的便捷性大打折扣。
2. 如果采用寄存器架構(gòu)，虛擬機(jī)必須經(jīng)常保存和恢復(fù)寄存器中的內(nèi)容。與硬件計(jì)算機(jī)相比，這些操作在虛擬機(jī)中的開(kāi)銷要大得多。因?yàn)槊恳粭l虛擬機(jī)指令都需要進(jìn)行很費(fèi)時(shí)的指令分派操作。雖然其它的指令也要分派，但是它們的語(yǔ)義內(nèi)容更豐富。
3. 采用寄存器架構(gòu)時(shí)，指令對(duì)應(yīng)的操作數(shù)位于不同寄存器中，對(duì)操作數(shù)的尋址也是一個(gè)問(wèn)題。而在基于棧的虛擬機(jī)中，操作數(shù)位于棧頂或緊跟在虛擬機(jī)指令之后。由于基于棧的架構(gòu)的簡(jiǎn)便性，一些查詢語(yǔ)言的實(shí)現(xiàn)也采用了此種架構(gòu)。
SQLite的虛擬機(jī)就是基于棧架構(gòu)的實(shí)現(xiàn)。每一個(gè)vdbe都有一個(gè)棧頂指針，它保存著vdbe的初始棧頂值。而在解釋引擎中也有一個(gè)pTos，它們是有區(qū)別的：
（1）vdbe的pTos：在一趟vdbe執(zhí)行的過(guò)程中不會(huì)變化，直到相應(yīng)的指令修改它為止，在上面的例子中，Callback指令會(huì)修改其值（見(jiàn)指令分析）。
（2）而解釋引擎中的pTos是隨著指令的執(zhí)行而動(dòng)態(tài)變化的,在上面的例子中,Integer,Column指令的執(zhí)行都會(huì)引起解釋引擎pTos的改變。

3.4、指令計(jì)數(shù)器(PC)
每一個(gè)vdbe都有一個(gè)程序計(jì)數(shù)器，用來(lái)保存初始的計(jì)數(shù)器值。和pTos一樣，解釋引擎也有一個(gè)pc，它用來(lái)指向VM下一條要執(zhí)行的指令。

3.5、解釋引擎
經(jīng)過(guò)編譯器生成的vdbe最終都是由解釋引擎解釋執(zhí)行的，SQLite的解釋引擎實(shí)現(xiàn)的原理非常簡(jiǎn)單，本質(zhì)上就是一個(gè)包含大量case語(yǔ)句的for循環(huán)，但是由于SQLite的指令較多（在version 3.3.6中是139條），所以代碼比較龐大。
SQLite的解釋引擎是在一個(gè)方法中實(shí)現(xiàn)的：
int sqlite3VdbeExec(
Vdbe *p /* The VDBE */
)
具體代碼如下（為了閱讀，去掉了一些不影響閱讀的代碼，具體見(jiàn)SQLite的源碼）：

/*執(zhí)行VDBE程序.當(dāng)從數(shù)據(jù)庫(kù)中取出一行數(shù)據(jù)時(shí),該函數(shù)會(huì)調(diào)用回調(diào)函數(shù)(如果有的話),
**或者返回SQLITE_ROW.
*/
int sqlite3VdbeExec(
  Vdbe *p                    /* The VDBE */
){

  //指令計(jì)數(shù)器
  int pc;                    /* The program counter */
  //當(dāng)前指令
  Op *pOp;                   /* Current operation */
  int rc = SQLITE_OK;        /* Value to return */
  //數(shù)據(jù)庫(kù)
  sqlite3 *db = p->db;       /* The database */

  u8 encoding = ENC(db);     /* The database encoding */
  //棧頂
  Mem *pTos;                 /* Top entry in the operand stack */

  if( p->magic!=VDBE_MAGIC_RUN ) return SQLITE_MISUSE;

  //當(dāng)前棧頂指針
  pTos = p->pTos;

  if( p->rc==SQLITE_NOMEM ){
    /* This happens if a malloc() inside a call to sqlite3_column_text() or
    ** sqlite3_column_text16() failed.  */
    goto no_mem;
  }
  p->rc = SQLITE_OK;
  //如果需要進(jìn)行出棧操作，則進(jìn)行出棧操作
  if( p->popStack ){
    popStack(&pTos, p->popStack);
    p->popStack = 0;
  }
  //表明棧中沒(méi)有結(jié)果
  p->resOnStack = 0;
  db->busyHandler.nBusy = 0;

  //執(zhí)行指令
  for(pc=p->pc; rc==SQLITE_OK; pc++){
    //取出操作碼
    pOp = &p->aOp[pc];

    switch( pOp->opcode ){
        //跳到操作數(shù)P2指向的指令
        case OP_Goto: {             /* no-push */
          CHECK_FOR_INTERRUPT;
          //設(shè)置pc
          pc = pOp->p2 - 1;
          break;
            }

        //P1入棧
        case OP_Integer: {
          //當(dāng)前棧頂指針上移
          pTos++;
          //設(shè)為整型
          pTos->flags = MEM_Int;
          //取操作數(shù)P1,并賦值
          pTos->i = pOp->p1;
          break;
            }

        //其它指令的實(shí)現(xiàn)

}//end switch
}//end for
}

3.6、指令實(shí)例分析

由于篇幅限制，僅給出幾條的指令的實(shí)現(xiàn)，其它具體實(shí)現(xiàn)見(jiàn)源碼。

1、Callback指令

Code

2、Rewind指令

Code

3、Column指令

Code

4、Next指令

Code

分類: 數(shù)據(jù)庫(kù)技術(shù)