實現一個簡單的Database1(譯文）

“What I cannot create, I do not understand.” – Richard Feynman I’m building a clone of sqlite from scratch in C in order to understand, and I’m going ...

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

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的資料庫實現，通過這個簡單的項目，可以很好的理解資料庫是如何運行的，實現教程原文是英文，共有13篇，這裡翻譯過來以饗讀者。原文標題：Let's Build a Simple Database，本文是第一篇

Part 1 介紹&設置REPL

作為一名開發人員，在工作中我每天都使用關係型資料庫。但是對我來說，它們是一個黑盒。我有一些問題：

數據存儲使用什麼格式？（在記憶體與磁碟中）
數據什麼時候從記憶體轉移到磁碟？
為什麼每張表只能有一個主鍵？
事務回滾是怎麼工作的？
索引是什麼格式的？
全表掃描時什麼時候發生，如何發生的？
預處理語句（prepared statement）是使用什麼格式存儲的？

換句話說，資料庫是怎麼工作的？

為了弄清楚這些，我從頭寫了一個資料庫。它是模仿sqlite實現的，因為sqlite設計小巧，並且相比於MySQL和PostgreSQL，它的功能相對要少很多，所以我希望能更容易的理解它。在實現上，整個資料庫都存儲在一個數據文件中。

Sqlite

在sqlite的網站上，有很多sqlite的內部文檔（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)

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

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

前端的輸入是SQL語句。輸出則是sqlite的虛擬機位元組碼（sqlite virtual machine bytecode），本質上是一個可以在資料庫運行的編譯程式。

譯註：資料庫實現查詢優化模型分為傳統的火山模型（Volcano model）與Code gen模型，本文作者實現的是code gen模型。

後端包括如下組件：

虛擬機（virtual machine）
B-tree
頁管理（pager）
系統介面（os interface）

virtual machine

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

B-tree

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

pager

pager接收命令來讀取或者寫入數據的pages。它是負責來讀、寫資料庫文件的適當偏移位置。也負責保持當前訪問的pages在記憶體中，並且決定何時這些pages需要寫回磁碟。

os interface

系統介面與sqlite根據不同操作系統平臺來編譯不同，在這個系列教程中，我不准備去支持多平臺適配。

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

實現簡單的REPL

譯註：REPL，Read - Execute - Print - Loop，即讀取 - 執行 - 列印輸出 - 迴圈，這個過程。有時候翻譯成互動式解釋器
當你執行命令行命令時，sqlite開始讀取-執行-列印迴圈：

~ 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
~

為了實現這樣的效果，我們的主程式需要有一個無限迴圈來列印這個提示，獲取一行輸入，然後處理這行輸入：

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()函數交互的狀態（稍後將對此進行詳細介紹）

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()函數為用戶列印出提示。在做這個之前需要讀取每一行輸入。

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

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

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

（以下為getline的函數釋義）

lineptr：

一個指針指向我們在buffer中包含的，從命令行讀取的命令的變數。如果設置為NULL，它由getline()函數分配記憶體。並且後續由用戶來釋放，即使命令行的命令執行失敗也能保證會被釋放已分配的記憶體。

n：

一個指針變數，指向已經分配記憶體的buffer的大小（size）。

stream：

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

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

讀取的位元組數量，可能會比buffer的size小。

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

buffer 在初始時是null，所以getline()函數分配足夠的記憶體來存輸入的命令行數據然後讓buffer來指向這些數據。

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;
}

現在就可以定義一個函數來釋放已分配給InputBuffer*實例和buffer中元素各自的數據結構的記憶體了（在read_input()函數中，調用getline()函數為 input_buffer->buffer 分配記憶體）。

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

在最後，我們解析並執行命令。現在這隻是一個認可的命令：.exit，一個終止程式的命令。除此之外的命令，我們列印一個報錯信息然後繼續程式的迴圈。

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。在下一部分，我們將開始開發我們的命令語言。同時，下麵是是這部分的全部程式代碼：

#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
  char* buffer;
  size_t buffer_length;
  ssize_t input_length;
} InputBuffer;

InputBuffer* new_input_buffer() {
  InputBuffer* input_buffer = malloc(sizeof(InputBuffer));
  input_buffer->buffer = NULL;
  input_buffer->buffer_length = 0;
  input_buffer->input_length = 0;

  return input_buffer;
}

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

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;
}

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

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);
    }
  }
}

Enjoy GreatSQL