實作一個簡單的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 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 ??

關于 GreatSQL

GreatSQL是由萬里資料庫維護的MySQL分支，專注于提升MGR可靠性及性能，支持InnoDB并行查詢特性，是適用于金融級應用的MySQL分支版本，

相關鏈接： GreatSQL社區 Gitee GitHub Bilibili

GreatSQL社區：

歡迎來GreatSQL社區發帖提問
https://greatsql.cn/

GreatSQL社區

技術交流群：

微信：掃碼添加GreatSQL社區助手微信好友，發送驗證資訊加群，

轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/509069.html

標籤：其他

上一篇：Oracle 洗掉大量表記錄操作總結

下一篇：2022 IDC中國未來企業大獎優秀獎頒布，華為云資料庫助力德邦快遞獲獎