关于mysql:实现一个简单的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…）。

sqlite architecture

(https://www.sqlite.org/zipvfs…)

一个查问通过组件链来获取数据或者批改数据。前端如下组件：

• 分词器(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 社区助手 微信好友，发送验证信息 加群。