實現一個簡單的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
  • 前言 插件化的需求主要源於對軟體架構靈活性的追求,特別是在開發大型、複雜或需要不斷更新的軟體系統時,插件化可以提高軟體系統的可擴展性、可定製性、隔離性、安全性、可維護性、模塊化、易於升級和更新以及支持第三方開發等方面的能力,從而滿足不斷變化的業務需求和技術挑戰。 一、插件化探索 在WPF中我們想要開 ...
  • 歡迎ReaLTaiizor是一個用戶友好的、以設計為中心的.NET WinForms項目控制項庫,包含廣泛的組件。您可以使用不同的主題選項對項目進行個性化設置,並自定義用戶控制項,以使您的應用程式更加專業。 項目地址:https://github.com/Taiizor/ReaLTaiizor 步驟1: ...
  • EDP是一套集組織架構,許可權框架【功能許可權,操作許可權,數據訪問許可權,WebApi許可權】,自動化日誌,動態Interface,WebApi管理等基礎功能於一體的,基於.net的企業應用開發框架。通過友好的編碼方式實現數據行、列許可權的管控。 ...
  • Channel 是乾什麼的 The System.Threading.Channels namespace provides a set of synchronization data structures for passing data between producers and consume ...
  • efcore如何優雅的實現按年分庫按月分表 介紹 本文ShardinfCore版本 本期主角: ShardingCore 一款ef-core下高性能、輕量級針對分表分庫讀寫分離的解決方案,具有零依賴、零學習成本、零業務代碼入侵適配 距離上次發文.net相關的已經有很久了,期間一直在從事java相關的 ...
  • 前言 Spacesniffer 是一個免費的文件掃描工具,通過使用樹狀圖可視化佈局,可以立即瞭解大文件夾的位置,幫助用戶處理找到這些文件夾 當前系統C盤空間 清理後系統C盤空間 下載 Spacesniffer 下載地址:https://spacesniffer.en.softonic.com/dow ...
  • EDP是一套集組織架構,許可權框架【功能許可權,操作許可權,數據訪問許可權,WebApi許可權】,自動化日誌,動態Interface,WebApi管理等基礎功能於一體的,基於.net的企業應用開發框架。通過友好的編碼方式實現數據行、列許可權的管控。 ...
  • 一、ReZero簡介 ReZero是一款.NET中間件 : 全網唯一開源界面操作就能生成API , 可以集成到任何.NET6+ API項目,無破壞性,也可讓非.NET用戶使用exe文件 免費開源:MIT最寬鬆協議 , 一直從事開源事業十年,一直堅持開源 1.1 純ReZero開發 適合.Net Co ...
  • 一:背景 1. 講故事 停了一個月沒有更新文章了,主要是忙於寫 C#內功修煉系列的PPT,現在基本上接近尾聲,可以回頭繼續更新這段時間分析dump的一些事故報告,有朋友微信上找到我,說他們的系統出現了大量的http超時,程式不響應處理了,讓我幫忙看下怎麼回事,dump也抓到了。 二:WinDbg分析 ...
  • 開始做項目管理了(本人3年java,來到這邊之後真沒想到...),天天開會溝通整理需求,他們講話的時候忙裡偷閑整理一下常用的方法,其實語言還是有共通性的,基本上看到方法名就大概能猜出來用法。出去打水的時候看到外面太陽好好,真想在外面坐著曬太陽,回來的時候好兄弟三年前送給我的鍵盤D鍵不靈了,在打"等待 ...