“What I cannot create, I do not understand.” – Richard Feynman

創(chuàng)新互聯(lián)建站主要從事網(wǎng)站建設、網(wǎng)站設計、網(wǎng)頁設計、企業(yè)做網(wǎng)站、公司建網(wǎng)站等業(yè)務。立足成都服務柞水,10多年網(wǎng)站建設經(jīng)驗,價格優(yōu)惠、服務專業(yè),歡迎來電咨詢建站服務:18982081108

I’m building a clone of sqlite from scratch in C in order to understand, and I’m going to document my process as I go.

譯注：cstsck在github維護了一個簡單的、類似SQLite的數(shù)據(jù)庫實現(xiàn)，通過這個簡單的項目，可以很好的理解數(shù)據(jù)庫是如何運行的，原文標題：Let's Build a Simple Database，本文是第一篇。

Part 1 介紹&設置REPL

作為一名開發(fā)人員，在工作中我每天都使用關系型數(shù)據(jù)庫。但是對我來說，它們是一個黑盒。我有一些問題：

• 數(shù)據(jù)存儲使用什么格式？（在內(nèi)存與磁盤中）
• 數(shù)據(jù)什么時候從內(nèi)存轉(zhuǎn)移到磁盤？
• 為什么每張表只能有一個主鍵？
• 事務回滾是怎么工作的？
• 索引是什么格式的？
• 全表掃描時什么時候發(fā)生，如何發(fā)生的？

預處理語句（prepared statement）是使用什么格式存儲的？

換句話說，數(shù)據(jù)庫是怎么工作的？

為了弄清楚這些，我從頭寫了一個數(shù)據(jù)庫。它是模仿SQLite實現(xiàn)的，因為SQLite設計小巧，并且相比于MySQL和PostgreSQL，它的功能相對要少很多，所以我希望能更容易的理解它。在實現(xiàn)上，整個數(shù)據(jù)庫都存儲在一個數(shù)據(jù)文件中。

SQLite

在SQLite的網(wǎng)站上，有很多SQLite的內(nèi)部文檔（https://www.sqlite.org/arch.html）。另外我還拷貝了文檔（SQLite Database System: Design and Implementation.）的一個副本（https://play.google.com/store/books/details?id=9Z6IQQnX1JEC）

SQLite architecture

(https://www.sqlite.org/zipvfs/doc/trunk/www/howitworks.wiki)

一個查詢通過組件鏈來獲取數(shù)據(jù)或者修改數(shù)據(jù)。前端如下組件：

• 分詞器(tokenizer)
• 解析器（parser）
• 代碼生成器（code generator）

前端的輸入是SQL語句。輸出則是SQLite的虛擬機字節(jié)碼（virtual machine bytecode），本質(zhì)上是一個可以在數(shù)據(jù)庫運行的編譯程序。

譯注：數(shù)據(jù)庫實現(xiàn)查詢優(yōu)化模型分為傳統(tǒng)的火山模型（Volcano model）與Code gen模型，本文作者實現(xiàn)的是code gen模型。

后端包括如下組件：

• 虛擬機（virtual machine）
• B-tree
• 頁管理（pager）
• 系統(tǒng)接口（os interface）

virtual machine

虛擬機將前端生成的字節(jié)碼作為指令。它接下來可以在一個或更多的表、索引上執(zhí)行操作，表以及索引都是存儲在叫B-tree的數(shù)據(jù)結(jié)構(gòu)中。VM 本質(zhì)上是字節(jié)碼指令類型的一個大開關語句（a big switch statement on the type of bytecode instruction）

B-tree

每個B-tree有許多節(jié)點。每個節(jié)點是一個page的長度。B-tree可以通過執(zhí)行命令到pager，從磁盤獲取一個page或者保存回page到磁盤。

pager

pager接收命令來讀取或者寫入數(shù)據(jù)的pages。它是負責來讀、寫數(shù)據(jù)庫文件的適當偏移位置。也負責保持當前訪問的pages在內(nèi)存中，并且決定何時這些pages需要寫回磁盤。

os interface

系統(tǒng)接口與SQLite根據(jù)不同操作系統(tǒng)平臺來編譯不同，在這個系列教程中，我不準備去支持多平臺適配。

千里之行始于足下，所以我們從一些簡單的事開始：REPL

實現(xiàn)簡單的REPL

譯注：REPL，Read - Execute - Print - Loop，即讀取 - 執(zhí)行 - 打印輸出 - 循環(huán)，這個過程。有時候翻譯成交互式解釋器

當你執(zhí)行命令行命令時，SQLite開始讀取-執(zhí)行-打印循環(huán)：

sqlite3
    SQLite version 3.16.0 2016-11-04 19:09:39
    Enter ".help" for usage hints.
    Connected to a transient in-memory database.
    Use ".open FILENAME" to reopen on a persistent database.
    sqlite> create table users (id int, username varchar(255), email varchar(255));
    sqlite> .tables
    users
    sqlite> .exit

為了實現(xiàn)這樣的效果，我們的主程序需要有一個無限循環(huán)來打印這個提示，獲取一行輸入，然后處理這行輸入：

int main(int argc, char* argv[]) {
      InputBuffer* input_buffer = new_input_buffer();
      while (true) {
        print_prompt();
        read_input(input_buffer);
    
        if (strcmp(input_buffer->buffer, ".exit") == 0) {
          close_input_buffer(input_buffer);
          exit(EXIT_SUCCESS);
        } else {
          printf("Unrecognized command '%s'.\n", input_buffer->buffer);
        }
      }
    }

我們定義一個InputBuffer來作為一個封裝，封裝圍繞在我們需要存儲的、與getline()函數(shù)交互的狀態(tài)（稍后將對此進行詳細介紹）

typedef struct {
      char* buffer;
      size_t buffer_length;
      ssize_t input_length;
    } InputBuffer;
    
    InputBuffer* new_input_buffer() {
      InputBuffer* input_buffer = (InputBuffer*)malloc(sizeof(InputBuffer));
      input_buffer->buffer = NULL;
      input_buffer->buffer_length = 0;
      input_buffer->input_length = 0;
    
      return input_buffer;
    }

接下來，print_prompt()函數(shù)為用戶打印出提示。在做這個之前需要讀取每一行輸入。

void print_prompt() { printf("db > "); }

讀取命令行輸入，需要使用getline()函數(shù):

ssize_t getline(char **lineptr, size_t *n, FILE *stream);

（以下為getline的函數(shù)釋義）

lineptr：

一個指針指向我們在buffer中包含的，從命令行讀取的命令的變量。如果設置為NULL，它由getline()函數(shù)分配內(nèi)存。并且后續(xù)由用戶來釋放，即使命令行的命令執(zhí)行失敗也能保證會被釋放已分配的內(nèi)存。

n：

一個指針變量，指向已經(jīng)分配內(nèi)存的buffer的大小（size）。

stream：

讀取的輸入流，這里是從標準輸入讀取的。

return value（返回值，ssize_t類型）: 

讀取的字節(jié)數(shù)量，可能會比buffer的size小。

我們告訴getline()函數(shù)保存讀取的命令行到input_buffer->buffer，存儲buffer的size到input_buffer->buffer_length，保存返回值到input_buffer->input_length

buffer在初始時是NULL，所以getline()函數(shù)分配足夠的內(nèi)存來存輸入的命令行數(shù)據(jù)然后讓buffer來指向這些數(shù)據(jù)。

void read_input(InputBuffer* input_buffer) {
      ssize_t bytes_read =
          getline(&(input_buffer->buffer), &(input_buffer->buffer_length), stdin);
    
      if (bytes_read <= 0) {
        printf("Error reading input\n");
        exit(EXIT_FAILURE);
      }
    
      // Ignore trailing newline
      input_buffer->input_length = bytes_read - 1;
      input_buffer->buffer[bytes_read - 1] = 0;
    }

現(xiàn)在就可以定義一個函數(shù)來釋放已分配給InputBuffer實例和buffer中元素各自的數(shù)據(jù)結(jié)構(gòu)的內(nèi)存了（在read_input()函數(shù)中，調(diào)用getline()函數(shù)為input_buffer->buffer分配內(nèi)存）。

void close_input_buffer(InputBuffer* input_buffer) {
        free(input_buffer->buffer);
        free(input_buffer);
    }

在最后，我們解析并執(zhí)行命令?，F(xiàn)在這只是僅有的一個認可的命令：.exit，一個終止程序的命令。除此之外的命令，我們打印一個報錯信息然后繼續(xù)程序的循環(huán)。

if (strcmp(input_buffer->buffer, ".exit") == 0) {
      close_input_buffer(input_buffer);
      exit(EXIT_SUCCESS);
    } else {
      printf("Unrecognized command '%s'.\n", input_buffer->buffer);
    }

讓我們來試試吧！

~ ./db
    db > .tables
    Unrecognized command '.tables'.
    db > .exit
    ~

好了，我們得到了一個可以工作的REPL。在下一部分，我們將開始開發(fā)我們的命令語言。同時，下面是是這部分的全部程序代碼：

1 #include 
2 #include 
3 #include 
4 #include 
5    
6    typedef struct {
7      char* buffer;
8      size_t buffer_length;
9      ssize_t input_length;
10    } InputBuffer;
11    
12    InputBuffer* new_input_buffer() {
13      InputBuffer* input_buffer = malloc(sizeof(InputBuffer));
14      input_buffer->buffer = NULL;
15      input_buffer->buffer_length = 0;
16      input_buffer->input_length = 0;
17    
18      return input_buffer;
19    }
20    
21    void print_prompt() { printf("db > "); }
22    
23    void read_input(InputBuffer* input_buffer) {
24      ssize_t bytes_read =
25               
26      getline(&(input_buffer->buffer), &(input_buffer->buffer_length), stdi n);
27    
28      if (bytes_read <= 0) {
29        printf("Error reading input\n");
30        exit(EXIT_FAILURE);
31      }
32    
33      // Ignore trailing newline
34      input_buffer->input_length = bytes_read - 1;
35      input_buffer->buffer[bytes_read - 1] = 0;
36    }
37    
38    void close_input_buffer(InputBuffer* input_buffer) {
39        free(input_buffer->buffer);
40        free(input_buffer);
41    }
42    
43    int main(int argc, char* argv[]) {
44      InputBuffer* input_buffer = new_input_buffer();
45      while (true) {
46        print_prompt();
47        read_input(input_buffer);
48    
49        if (strcmp(input_buffer->buffer, ".exit") == 0) {
50          close_input_buffer(input_buffer);
51          exit(EXIT_SUCCESS);
52        } else {
53          printf("Unrecognized command '%s'.\n", input_buffer->buffer);
54        }
55      }
56    }

分享文章：實現(xiàn)一個簡單的Database1，你會了嗎？
本文URL：http://uogjgqi.cn/article/djjgsgs.html