当前位置: 代码迷 >> 综合 >> 简单数据库实现——Part5 - 持久存储到磁盘
  详细解决方案

简单数据库实现——Part5 - 持久存储到磁盘

热度:67   发布时间:2023-12-06 14:07:10.0

简单数据库实现——Part5 - 持久存储到磁盘

目前的数据库在终止程序重新启动后会丢失所有记录,所以我们会通过将整个数据库保存到一个文件来保存记录。

我们已经通过将行序列化到页面大小的内存快中,为了增加持久性,我们可以简单的将内存块写入文件并在下次程序启动时读入内存。

为了简化这一过程,我们将进行一个称为寻呼机(pager)的抽象。我们向寻呼机询问页码x,寻呼机返回给我们一块内存。它会首先查看他的缓存(cache),如果缓存中不存在,那么它会从磁盘(disk)中将数据复制到内存中。
architecture

寻呼机(pager)访问页面缓存和文件,表对象通过寻呼机请求页面:

+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() 重命名为 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() 依次调用 paper_open(),这将打开数据文件并跟踪其大小。它还将页面缓存初始化为 NULL

函数的使用:
open()函数(APUE 3.3和4.5节):

#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
int open(const char *pathname, int oflag,.../*, mode_t mode */);
/* 返回:若成功为文件描述符若出错为-1 */

pathname是要打开或创建的文件的名字。oflag参数可用来说明此函数的多个选择项。

  • O_RDWR 读、写打开
  • O_CREAT 若此文件不存在则创建它。使用此选择项时,需同时说明第三个参数mode,用其说明该新文件的存取许可权位。
  • S_IWUSR 用户-写
  • S_IRUSR 用户-读

lseek()函数(APUE 3.6节):

#include <sys/types.h>
#include <unistd.h>
off_t lseek(int filedes, off_t offset, int whence);
/*返回:若成功为新的文件位移若出错为-1 */

对参数offset的解释与参数whence的值有关。

  • whenceSEEK_END,则将该文件的位移量设置为文件长度加offsetoffset可为正或负。
    lseek成功执行,则返回新的文件位移量。
+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;
+}

我们现在将获取页面移动到它自己的方法 get_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()方法可以处理缓存丢失。我们假设页面一个接一个保存在数据库文件中:第0页位于偏移量0,第1页位于偏移量4096,第2页位于偏移量8192,等等。如果请求的页面位于文件的边界之外,我们知道它应该是空的,所以我们只需分配一些内存并返回它。当我们稍后将缓存更新到磁盘时,该页面将被添加到文件中。

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

现在,我们等待将缓存更新到磁盘,直到用户关闭数据库连接。当用户退出时,我们将调用一个名为db_close()的新方法。这个方法将会:

  • 将缓存更新到磁盘
  • 关闭数据库文件
  • 释放寻呼机和表数据结构的内存
+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;

在我们当前的设计中,文件的长度编码了数据库中的行数,因此我们要在文件的末尾写入部分页面。这就是为什么pager_flush()同时接受页码和大小。它不是最好的设计,它会在我们开始实现B树时去除。

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

最后,我们需要接受文件名作为命令行参数。不要忘记添加额外的参数来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 foo@bar.com
Executed.
db > insert 2 voltorb volty@example.com
Executed.
db > .exit
~
~ ./db mydb.db
db > select
(1, cstack, foo@bar.com)
(2, voltorb, volty@example.com)
Executed.
db > .exit
~

实践结果:
result

原文中还研究了数据库文件中数据的存储方式,可参见原文,这里暂时不翻译了。

结论

现在如果在没有键入.exit的情况下终止了程序,更改将会丢失。另外我们要将所有的页面写回磁盘,其中也包含了读取后没有改变的页面。这是以后要解决的问题。

接下来我们要介绍游标(cursors),它使实现B树更简单。

修改的部分

+#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();