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

来源:https://www.cnblogs.com/greatsql/archive/2022/09/19/16706642.html
-Advertisement-
Play Games

“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)。

image-20220919090434505

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

您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • 源碼安裝apache腳本部署 [root@localhost ~]# ls anaconda-ks.cfg httpd.tar.xz [root@localhost ~]# tar xf httpd.tar.xz 解壓存放腳本的壓縮包 [root@localhost ~]# ls anaconda- ...
  • lrTimelapse for Mac是MAC OS上的一款視頻編輯軟體,lrTimelapse mac是一款配合 Adobe Lightroom、Adobe Camera RAW 和 Adobe After Effects 等程式製作延時攝影的軟體。lrtimelapse mac將帶你到下一個水平 ...
  • sed高階用法 sed編輯器 sed是一種流編輯器,流編輯器會在編輯器處理數據之前基於預先提供的一組規則來編輯數據流。 1.sed編輯器工作流程 sed編輯器可以根據命令來處理數據流中的數據,這些命令要麼從命令行中輸入,要麼存儲在一個命令文本文件中。 sed的工作流程主要包括讀取、執行和顯示三個過程 ...
  • 零基礎學MySQL 筆記目錄:(https://www.cnblogs.com/wenjie2000/p/16378441.html) 一個問題 淘寶網,京東、微信,抖音都有各自的功能,那麼當我們退出系統的時候,下次再訪問時,為什麼信息還存在? =》資料庫 解決之道-文件、資料庫 為瞭解決上述問題, ...
  • 案例1:MySQL8.0實現資料庫冷備份和還原 10.0.0.10 -- MySQL8.0 #停止資料庫 [root@CentOS8 my.cnf.d]# systemctl stop mysqld.service #備份數據 [root@CentOS8 ~]# scp -pr /var/lib/m ...
  • 在日常開發工作中,我經常會遇到需要統計總數的場景,比如:統計訂單總數、統計用戶總數等。一般我們會使用MySQL 的count函數進行統計,但是隨著數據量逐漸增大,統計耗時也越來越長,最後竟然出現慢查詢的情況,這究竟是什麼原因呢?本篇文章帶你一下學習一下。 ...
  • 當前伺服器上創建表(單節點) 創建新表具有幾種種語法形式,具體取決於用例。預設情況下,僅在當前伺服器上創建表。分散式DDL查詢作為子句實現,該子句另外描述。 語法形式 使用顯式架構 CREATE TABLE [IF NOT EXISTS] [db.]table_name [ON CLUSTER cl ...
  • 摘要:華為雲資料庫助力德邦快遞打造的“基於數智融合的一站式物流供應鏈平臺”項目從500多個項目中脫穎而出,榮獲2022 IDC中國未來企業大獎優秀獎“未來智能領軍者”。 本文分享自華為雲社區《華為雲資料庫助力德邦快遞斬獲IDC中國未來企業大獎“未來智能領軍者”優秀獎》,作者: GaussDB 資料庫 ...
一周排行
    -Advertisement-
    Play Games
  • Timer是什麼 Timer 是一種用於創建定期粒度行為的機制。 與標準的 .NET System.Threading.Timer 類相似,Orleans 的 Timer 允許在一段時間後執行特定的操作,或者在特定的時間間隔內重覆執行操作。 它在分散式系統中具有重要作用,特別是在處理需要周期性執行的 ...
  • 前言 相信很多做WPF開發的小伙伴都遇到過表格類的需求,雖然現有的Grid控制項也能實現,但是使用起來的體驗感並不好,比如要實現一個Excel中的表格效果,估計你能想到的第一個方法就是套Border控制項,用這種方法你需要控制每個Border的邊框,並且在一堆Bordr中找到Grid.Row,Grid. ...
  • .NET C#程式啟動閃退,目錄導致的問題 這是第2次踩這個坑了,很小的編程細節,容易忽略,所以寫個博客,分享給大家。 1.第一次坑:是windows 系統把程式運行成服務,找不到配置文件,原因是以服務運行它的工作目錄是在C:\Windows\System32 2.本次坑:WPF桌面程式通過註冊表設 ...
  • 在分散式系統中,數據的持久化是至關重要的一環。 Orleans 7 引入了強大的持久化功能,使得在分散式環境下管理數據變得更加輕鬆和可靠。 本文將介紹什麼是 Orleans 7 的持久化,如何設置它以及相應的代碼示例。 什麼是 Orleans 7 的持久化? Orleans 7 的持久化是指將 Or ...
  • 前言 .NET Feature Management 是一個用於管理應用程式功能的庫,它可以幫助開發人員在應用程式中輕鬆地添加、移除和管理功能。使用 Feature Management,開發人員可以根據不同用戶、環境或其他條件來動態地控制應用程式中的功能。這使得開發人員可以更靈活地管理應用程式的功 ...
  • 在 WPF 應用程式中,拖放操作是實現用戶交互的重要組成部分。通過拖放操作,用戶可以輕鬆地將數據從一個位置移動到另一個位置,或者將控制項從一個容器移動到另一個容器。然而,WPF 中預設的拖放操作可能並不是那麼好用。為瞭解決這個問題,我們可以自定義一個 Panel 來實現更簡單的拖拽操作。 自定義 Pa ...
  • 在實際使用中,由於涉及到不同編程語言之間互相調用,導致C++ 中的OpenCV與C#中的OpenCvSharp 圖像數據在不同編程語言之間難以有效傳遞。在本文中我們將結合OpenCvSharp源碼實現原理,探究兩種數據之間的通信方式。 ...
  • 一、前言 這是一篇搭建許可權管理系統的系列文章。 隨著網路的發展,信息安全對應任何企業來說都越發的重要,而本系列文章將和大家一起一步一步搭建一個全新的許可權管理系統。 說明:由於搭建一個全新的項目過於繁瑣,所有作者將挑選核心代碼和核心思路進行分享。 二、技術選擇 三、開始設計 1、自主搭建vue前端和. ...
  • Csharper中的表達式樹 這節課來瞭解一下表示式樹是什麼? 在C#中,表達式樹是一種數據結構,它可以表示一些代碼塊,如Lambda表達式或查詢表達式。表達式樹使你能夠查看和操作數據,就像你可以查看和操作代碼一樣。它們通常用於創建動態查詢和解析表達式。 一、認識表達式樹 為什麼要這樣說?它和委托有 ...
  • 在使用Django等框架來操作MySQL時,實際上底層還是通過Python來操作的,首先需要安裝一個驅動程式,在Python3中,驅動程式有多種選擇,比如有pymysql以及mysqlclient等。使用pip命令安裝mysqlclient失敗應如何解決? 安裝的python版本說明 機器同時安裝了 ...