关于mysql:实现一个简单的Database5译文

• GreatSQL 社区原创内容未经受权不得随便应用，转载请分割小编并注明起源。
• GreatSQL 是 MySQL 的国产分支版本，应用上与 MySQL 统一。

前文回顾

实现一个简略的 Database1(译文）

实现一个简略的 Database2(译文）

实现一个简略的 Database3(译文）

实现一个简略的 Database4(译文）

译注：cstsck 在 github 保护了一个简略的、相似 SQLite 的数据库实现，通过这个简略的我的项目，能够很好的了解数据库是如何运行的。本文是第五篇，次要是实现数据长久化

Part 5 长久化到磁盘

“Nothing in the world can take the place of persistence.”– Calvin Coolidge(美国第 30 任总统)

咱们数据库能让你插入数据并读取进去，然而只能在程序始终运行的时候才能够。如果你 kill 掉程序后再次重启当前，你所有的数据就失落了。

咱们冀望的行为是这样的，上面是一个 spec 测试：

it 'keeps data after closing connection' do
  result1 = run_script(["insert 1 user1 [email protected]",
    ".exit",
  ])
  expect(result1).to match_array([
    "db > Executed.",
    "db >",
  ])
  result2 = run_script([
    "select",
    ".exit",
  ])
  expect(result2).to match_array(["db > (1, user1, [email protected])",
    "Executed.",
    "db >",
  ])
end

像 SQLite 一样，咱们会把数据长久化，保留整个数据库到一个繁多的文件中。

咱们曾经实现了将行序列化为页面大小的内存块。为数据库减少长久化的性能，咱们能够简略的把这些内存中的块（blocks）写入到文件，在下次程序启动时，再把这些数据块读取到内存。

为了让实现更简略点，咱们创立了一个叫做 pager 的形象。咱们向 pager 申请的数据页 page 号为 x（page number x），而后 pager 会返给咱们一个内存块。申请会首先查看内存中的数据，如果内存中没有（缓存未命中，cache miss），pager 就会从磁盘上拷贝数据到内存中（通过读取数据库文件）。

咱们的程序是如何与 SQLite 架构匹配的

Pager 拜访页缓存（page cache）和文件。表对象（Table object）通过 Pager 申请数据页（pages）：

+typedef struct {
+  int file_descriptor;
+  uint32_t file_length;
+  void* pages[TABLE_MAX_PAGES];
+} Pager;
+
 typedef struct {-  void* pages[TABLE_MAX_PAGES];
+  Pager* pager;
   uint32_t num_rows;
 } Table;

因为 new_table() 有了关上一个数据库连贯的成果，所以我把 new_table() 重命名为db_open()。

关上一个连贯的含意是：

• 关上数据库文件
• 初始化一个 Pager 数据结构
• 初始化一个 table 数据结构

-Table* new_table() {+Table* db_open(const char* filename) {+  Pager* pager = pager_open(filename);
+  uint32_t num_rows = pager->file_length / ROW_SIZE;
+
   Table* table = malloc(sizeof(Table));
-  table->num_rows = 0;
+  table->pager = pager;
+  table->num_rows = num_rows;

   return table;
 }

db_open() 接下来调用 pager_open()，pager_open() 会关上数据库文件并跟踪文件的大小。它也会初始化页缓存（page cache）为 NULL（NULL 在 C 语言中为一个宏，定义为: #define NULL 0，也就是 0）。

+Pager* pager_open(const char* filename) {
+  int fd = open(filename,
+                O_RDWR |      // Read/Write mode
+                    O_CREAT,  // Create file if it does not exist
+                S_IWUSR |     // User write permission
+                    S_IRUSR   // User read permission
+                );
+
+  if (fd == -1) {+    printf("Unable to open file\n");
+    exit(EXIT_FAILURE);
+  }
+
+  off_t file_length = lseek(fd, 0, SEEK_END);
+
+  Pager* pager = malloc(sizeof(Pager));
+  pager->file_descriptor = fd;
+  pager->file_length = file_length;
+
+  for (uint32_t i = 0; i < TABLE_MAX_PAGES; i++) {+    pager->pages[i] = NULL;
+  }
+
+  return pager;
+}

有了下面的 Pager 的形象，咱们把获取一个页面（fetch a page）的逻辑挪动到它本人的办法里：

void* row_slot(Table* table, uint32_t row_num) {
  uint32_t page_num = row_num / ROWS_PER_PAGE;
-  void* page = table->pages[page_num];
-  if (page == NULL) {
-    // Allocate memory only when we try to access page
-    page = table->pages[page_num] = malloc(PAGE_SIZE);
-  }
+  void* page = get_page(table->pager, page_num);
  uint32_t row_offset = row_num % ROWS_PER_PAGE;
  uint32_t byte_offset = row_offset * ROW_SIZE;
  return page + byte_offset;
}

get_page() 办法有解决缓存未命中（cache miss）的逻辑。咱们假如数据页一个接一个地保留在数据库文件中：

Page 0 在 offset 0
page 1 在 offset 4096
page 2 在 offset 8192
等等。

如果申请的 page 在文件的边界之外，那咱们就晓得它应该是空白，所以咱们只须要调配一些内存并返回它就能够了。当咱们 flush 这些缓存到磁盘时，这些 page 就会增加到文件中。

+void* get_page(Pager* pager, uint32_t page_num) {+  if (page_num > TABLE_MAX_PAGES) {
+    printf("Tried to fetch page number out of bounds. %d > %d\n", page_num,
+           TABLE_MAX_PAGES);
+    exit(EXIT_FAILURE);
+  }
+
+  if (pager->pages[page_num] == NULL) {
+    // Cache miss. Allocate memory and load from file.
+    void* page = malloc(PAGE_SIZE);
+    uint32_t num_pages = pager->file_length / PAGE_SIZE;
+
+    // We might save a partial page at the end of the file
+    if (pager->file_length % PAGE_SIZE) {
+      num_pages += 1;
+    }
+
+    if (page_num <= num_pages) {+      lseek(pager->file_descriptor, page_num * PAGE_SIZE, SEEK_SET);
+      ssize_t bytes_read = read(pager->file_descriptor, page, PAGE_SIZE);
+      if (bytes_read == -1) {+        printf("Error reading file: %d\n", errno);
+        exit(EXIT_FAILURE);
+      }
+    }
+
+    pager->pages[page_num] = page;
+  }
+
+  return pager->pages[page_num];
+}

当初，咱们想始终到用户敞开数据库的连贯时候再 flush 这些缓存到磁盘。当用户退出时，咱们就调用新的办法：db_close()，办法执行上面几个操作：

• flush 页缓存到磁盘
• 敞开数据文件
• 开释 Pager、table 数据结构的内存

+void db_close(Table* table) {
+  Pager* pager = table->pager;
+  uint32_t num_full_pages = table->num_rows // ROWS_PER_PAGE;
+
+  for (uint32_t i = 0; i < num_full_pages; i++) {+    if (pager->pages[i] == NULL) {
+      continue;
+    }
+    pager_flush(pager, i, PAGE_SIZE);
+    free(pager->pages[i]);
+    pager->pages[i] = NULL;
+  }
+
+  // There may be a partial page to write to the end of the file
+  // This should not be needed after we switch to a B-tree
+  uint32_t num_additional_rows = table->num_rows % ROWS_PER_PAGE;
+  if (num_additional_rows > 0) {
+    uint32_t page_num = num_full_pages;
+    if (pager->pages[page_num] != NULL) {+      pager_flush(pager, page_num, num_additional_rows * ROW_SIZE);
+      free(pager->pages[page_num]);
+      pager->pages[page_num] = NULL;
+    }
+  }
+
+  int result = close(pager->file_descriptor);
+  if (result == -1) {+    printf("Error closing db file.\n");
+    exit(EXIT_FAILURE);
+  }
+  for (uint32_t i = 0; i < TABLE_MAX_PAGES; i++) {+    void* page = pager->pages[i];
+    if (page) {+      free(page);
+      pager->pages[i] = NULL;
+    }
+  }
+  free(pager);
+  free(table);
+}
+
-MetaCommandResult do_meta_command(InputBuffer* input_buffer) {+MetaCommandResult do_meta_command(InputBuffer* input_buffer, Table* table) {if (strcmp(input_buffer->buffer, ".exit") == 0) {+    db_close(table);
     exit(EXIT_SUCCESS);
   } else {return META_COMMAND_UNRECOGNIZED_COMMAND;

_译注：前面作者会把应用 array 组织 page 的形式改为 B -tree，有些代码只是临时这样实现，前面还会批改。

在以后的设计中，文件长度是编码存储多少行来决定，所以咱们可能会须要在文件的结尾写入局部页面（partial page，页的一部分，并非全页）。这也是为什么 pager_flush() 同时应用页码（page number）和数据页大小（size）两个参数的起因。这不是最好的设计，然而在咱们开始实现 B -tree 之后，他们就会很快的隐没了。

+void pager_flush(Pager* pager, uint32_t page_num, uint32_t size) {+  if (pager->pages[page_num] == NULL) {+    printf("Tried to flush null page\n");
+    exit(EXIT_FAILURE);
+  }
+
+  off_t offset = lseek(pager->file_descriptor, page_num * PAGE_SIZE, SEEK_SET);
+
+  if (offset == -1) {+    printf("Error seeking: %d\n", errno);
+    exit(EXIT_FAILURE);
+  }
+
+  ssize_t bytes_written =
+      write(pager->file_descriptor, pager->pages[page_num], size);
+
+  if (bytes_written == -1) {+    printf("Error writing: %d\n", errno);
+    exit(EXIT_FAILURE);
+  }
+}

最初，咱们须要承受一个命令行参数：filname。也不要忘了在 do_meta_command() 增加额定参数：
译注：db_open(filename)返回一个 table 构造的指针，将这个指针作为参数传给 do_meta_command()。

int main(int argc, char* argv[]) {-  Table* table = new_table();
+  if (argc < 2) {+    printf("Must supply a database filename.\n");
+    exit(EXIT_FAILURE);
+  }
+
+  char* filename = argv[1];
+  Table* table = db_open(filename);
+
  InputBuffer* input_buffer = new_input_buffer();
  while (true) {print_prompt();
    read_input(input_buffer);

    if (input_buffer->buffer[0] == '.') {-      switch (do_meta_command(input_buffer)) {+      switch (do_meta_command(input_buffer, table)) {

有了这些批改，咱们能在敞开而后从新关上数据库时，咱们记录依然还在数据库中。

~ ./db mydb.db
db > insert 1 cstack [email protected]
Executed.
db > insert 2 voltorb [email protected]
Executed.
db > .exit
~
~ ./db mydb.db
db > select
(1, cstack, [email protected])
(2, voltorb, [email protected])
Executed.
db > .exit
~

为了多找点乐子，让咱们看看 mydb.db 文件中数据库是如何存储的。我应用的是 vim 来作为 hex 编辑器来查看文件在内存中是如何布局的：

vim mydb.db
:%!xxd

以后的文件布局

前四个字节是第一行数据的 id（四个字节是因为咱们存储应用的 uint32_t 类型）。它以小端字节序存储，因而低位字节首先呈现（01），紧跟的是高位字节（(00 00 00)）。咱们用 memcpy() 从 Row 数据结构拷贝字节到页缓存（page cache）中，这也就意味着这些构造在内存中的布局是小端字节序。这是我编译程序的机器的属性。如果想在咱们的机器上写数据文件，而后把它读取到一个大端字节序的机器上，就不得不批改 serialize_row() 和 deserialize_row() 办法（序列化和反序列化）始终应用雷同的顺序存储和读取字节。

译注：将多个字节的数据存储在一片间断的地址上，而将数据的各个字节从这片空间的高地址位开始存储还是从低地址位开始存储就决定了零碎的存储字节序。大端字节序：高位字节数据寄存在低地址处，低位数据寄存在高地址处；小端字节序：高位字节数据寄存在高地址处，低位数据寄存在低地址处。这个别是服务器个性决定的，并不需要特地关注。作者在此浓墨重彩的介绍了一下。

接下来的 33 字节是存储以 null 为结尾的 username（占 32 个字节，未应用地位填充 0，结尾以一个字节的 null 完结）。显然“cstack”在 ASCII 十六进制中是 63 73 74 61 63 6b（占用了 6 个字节，其余应用 0 填充），接下来是一个 null 字符(00)。其余 33 字节未应用。

接下来的 256 字节是应用雷同形式存储的 email（占 255 个字节，未应用地位填充 0，结尾以一个字节的 null 完结）。在这里能看到在 null 结束符之后有一些随机的垃圾字符。这很可能是因为在咱们的 Row 构造没有初始化内存导致的。咱们拷贝整个 256 个字节长度 email 缓存写入到文件中，蕴含了任何在结束符之后的字节。当咱们调配该构造内存时，内存中的任何原来的内容还在那里。然而因为咱们应用了 null 结束符，所以它对数据库行为没有影响。

留神：如果咱们须要确认所有的字节都被初始化，在 serialize_row() 中拷贝 username 和 email 字段时用 strncpy() 替换 memcpy() 就足够了，像上面这样：

void serialize_row(Row* source, void* destination) {memcpy(destination + ID_OFFSET, &(source->id), ID_SIZE);
-    memcpy(destination + USERNAME_OFFSET, &(source->username), USERNAME_SIZE);
-    memcpy(destination + EMAIL_OFFSET, &(source->email), EMAIL_SIZE);
+    strncpy(destination + USERNAME_OFFSET, source->username, USERNAME_SIZE);
+    strncpy(destination + EMAIL_OFFSET, source->email, EMAIL_SIZE);
}

论断

好了！咱们实现了长久化。这样实现不是最好的。例如，如果你 kill 程序而不是执行“.exit”退出，你就会失落你的更新。此外，咱们写回所有数据页到磁盘，只管数据页自从咱们从磁盘读取进去就没有被更新。这些都是咱们前面能够解决的问题。

下次咱们将要介绍游标（cursors）。这会让咱们实现 B -tree 变得更容易。

在此之前，看一下残缺代码比照（与上一部分比照）：

+#include <errno.h>
+#include <fcntl.h>
 #include <stdbool.h>
 #include <stdio.h>
 #include <stdlib.h>
 #include <string.h>
 #include <stdint.h>
+#include <unistd.h>

 struct InputBuffer_t {
   char* buffer;
@@ -62,9 +65,16 @@ const uint32_t PAGE_SIZE = 4096;
 const uint32_t ROWS_PER_PAGE = PAGE_SIZE / ROW_SIZE;
 const uint32_t TABLE_MAX_ROWS = ROWS_PER_PAGE * TABLE_MAX_PAGES;

+typedef struct {
+  int file_descriptor;
+  uint32_t file_length;
+  void* pages[TABLE_MAX_PAGES];
+} Pager;
+
 typedef struct {
   uint32_t num_rows;
-  void* pages[TABLE_MAX_PAGES];
+  Pager* pager;
 } Table;

@@ -84,32 +94,81 @@ void deserialize_row(void *source, Row* destination) {memcpy(&(destination->email), source + EMAIL_OFFSET, EMAIL_SIZE);
 }

+void* get_page(Pager* pager, uint32_t page_num) {+  if (page_num > TABLE_MAX_PAGES) {
+     printf("Tried to fetch page number out of bounds. %d > %d\n", page_num,
+         TABLE_MAX_PAGES);
+     exit(EXIT_FAILURE);
+  }
+
+  if (pager->pages[page_num] == NULL) {
+     // Cache miss. Allocate memory and load from file.
+     void* page = malloc(PAGE_SIZE);
+     uint32_t num_pages = pager->file_length / PAGE_SIZE;
+
+     // We might save a partial page at the end of the file
+     if (pager->file_length % PAGE_SIZE) {
+         num_pages += 1;
+     }
+
+     if (page_num <= num_pages) {+         lseek(pager->file_descriptor, page_num * PAGE_SIZE, SEEK_SET);
+         ssize_t bytes_read = read(pager->file_descriptor, page, PAGE_SIZE);
+         if (bytes_read == -1) {+         printf("Error reading file: %d\n", errno);
+         exit(EXIT_FAILURE);
+         }
+     }
+
+     pager->pages[page_num] = page;
+  }
+
+  return pager->pages[page_num];
+}
+
 void* row_slot(Table* table, uint32_t row_num) {
   uint32_t page_num = row_num / ROWS_PER_PAGE;
-  void *page = table->pages[page_num];
-  if (page == NULL) {
-     // Allocate memory only when we try to access page
-     page = table->pages[page_num] = malloc(PAGE_SIZE);
-  }
+  void *page = get_page(table->pager, page_num);
   uint32_t row_offset = row_num % ROWS_PER_PAGE;
   uint32_t byte_offset = row_offset * ROW_SIZE;
   return page + byte_offset;
 }

-Table* new_table() {-  Table* table = malloc(sizeof(Table));
-  table->num_rows = 0;
+Pager* pager_open(const char* filename) {
+  int fd = open(filename,
+           O_RDWR |     // Read/Write mode
+               O_CREAT,    // Create file if it does not exist
+           S_IWUSR |    // User write permission
+               S_IRUSR    // User read permission
+           );
+
+  if (fd == -1) {+     printf("Unable to open file\n");
+     exit(EXIT_FAILURE);
+  }
+
+  off_t file_length = lseek(fd, 0, SEEK_END);
+
+  Pager* pager = malloc(sizeof(Pager));
+  pager->file_descriptor = fd;
+  pager->file_length = file_length;
+
   for (uint32_t i = 0; i < TABLE_MAX_PAGES; i++) {-     table->pages[i] = NULL;
+     pager->pages[i] = NULL;
   }
-  return table;
+
+  return pager;
 }

-void free_table(Table* table) {-  for (int i = 0; table->pages[i]; i++) {-     free(table->pages[i]);
-  }
-  free(table);
+Table* db_open(const char* filename) {+  Pager* pager = pager_open(filename);
+  uint32_t num_rows = pager->file_length / ROW_SIZE;
+
+  Table* table = malloc(sizeof(Table));
+  table->pager = pager;
+  table->num_rows = num_rows;
+
+  return table;
 }

 InputBuffer* new_input_buffer() {@@ -142,10 +201,76 @@ void close_input_buffer(InputBuffer* input_buffer) {free(input_buffer);
 }

+void pager_flush(Pager* pager, uint32_t page_num, uint32_t size) {+  if (pager->pages[page_num] == NULL) {+     printf("Tried to flush null page\n");
+     exit(EXIT_FAILURE);
+  }
+
+  off_t offset = lseek(pager->file_descriptor, page_num * PAGE_SIZE,
+              SEEK_SET);
+
+  if (offset == -1) {+     printf("Error seeking: %d\n", errno);
+     exit(EXIT_FAILURE);
+  }
+
+  ssize_t bytes_written = write(+     pager->file_descriptor, pager->pages[page_num], size
+     );
+
+  if (bytes_written == -1) {+     printf("Error writing: %d\n", errno);
+     exit(EXIT_FAILURE);
+  }
+}
+
+void db_close(Table* table) {
+  Pager* pager = table->pager;
+  uint32_t num_full_pages = table->num_rows / ROWS_PER_PAGE;
+
+  for (uint32_t i = 0; i < num_full_pages; i++) {+     if (pager->pages[i] == NULL) {
+         continue;
+     }
+     pager_flush(pager, i, PAGE_SIZE);
+     free(pager->pages[i]);
+     pager->pages[i] = NULL;
+  }
+
+  // There may be a partial page to write to the end of the file
+  // This should not be needed after we switch to a B-tree
+  uint32_t num_additional_rows = table->num_rows % ROWS_PER_PAGE;
+  if (num_additional_rows > 0) {
+     uint32_t page_num = num_full_pages;
+     if (pager->pages[page_num] != NULL) {+         pager_flush(pager, page_num, num_additional_rows * ROW_SIZE);
+         free(pager->pages[page_num]);
+         pager->pages[page_num] = NULL;
+     }
+  }
+
+  int result = close(pager->file_descriptor);
+  if (result == -1) {+     printf("Error closing db file.\n");
+     exit(EXIT_FAILURE);
+  }
+  for (uint32_t i = 0; i < TABLE_MAX_PAGES; i++) {+     void* page = pager->pages[i];
+     if (page) {+         free(page);
+         pager->pages[i] = NULL;
+     }
+  }
+
+  free(pager);
+  free(table);
+}
+
 MetaCommandResult do_meta_command(InputBuffer* input_buffer, Table *table) {if (strcmp(input_buffer->buffer, ".exit") == 0) {close_input_buffer(input_buffer);
-    free_table(table);
+    db_close(table);
     exit(EXIT_SUCCESS);
   } else {
     return META_COMMAND_UNRECOGNIZED_COMMAND;
@@ -182,6 +308,7 @@ PrepareResult prepare_insert(InputBuffer* input_buffer, Statement* statement) {return PREPARE_SUCCESS;}
+
 PrepareResult prepare_statement(InputBuffer* input_buffer,
                                 Statement* statement) {if (strncmp(input_buffer->buffer, "insert", 6) == 0) {@@ -227,7 +354,14 @@ ExecuteResult execute_statement(Statement* statement, Table *table) { }

 int main(int argc, char* argv[]) {-  Table* table = new_table();
+  if (argc < 2) {+      printf("Must supply a database filename.\n");
+      exit(EXIT_FAILURE);
+  }
+
+  char* filename = argv[1];
+  Table* table = db_open(filename);
+
   InputBuffer* input_buffer = new_input_buffer();
   while (true) {print_prompt();

上面是与上一部分的测试不同的中央：

describe 'database' do
+  before do
+    `rm -rf test.db`
+  end
+
  def run_script(commands)
    raw_output = nil
-    IO.popen("./db", "r+") do |pipe|
+    IO.popen("./db test.db", "r+") do |pipe|
      commands.each do |command|
        pipe.puts command
      end
@@ -28,6 +32,27 @@ describe 'database' do
    ])
  end

+  it 'keeps data after closing connection' do
+    result1 = run_script([+      "insert 1 user1 [email protected]",
+      ".exit",
+    ])
+    expect(result1).to match_array([
+      "db > Executed.",
+      "db >",
+    ])
+
+    result2 = run_script([
+      "select",
+      ".exit",
+    ])
+    expect(result2).to match_array([+      "db > (1, user1, [email protected])",
+      "Executed.",
+      "db >",
+    ])
+  end
+
  it 'prints error message when table is full' do
    script = (1..1401).map do |i|
      "insert #{i} user#{i} person#{i}@example.com"

Enjoy GreatSQL :)

## 对于 GreatSQL

GreatSQL 是由万里数据库保护的 MySQL 分支，专一于晋升 MGR 可靠性及性能，反对 InnoDB 并行查问个性，是实用于金融级利用的 MySQL 分支版本。

相干链接：GreatSQL 社区 Gitee GitHub Bilibili

GreatSQL 社区：

欢送来 GreatSQL 社区发帖发问
https://greatsql.cn/

技术交换群：

微信：扫码增加 GreatSQL 社区助手 微信好友，发送验证信息 加群。