谈谈关系数据库的设计与实现(1)——总览

pedrogao大约 10 分钟

前言

数据库是一个老生常谈的话题，类别众多，如内存数据库(Redis)，文档数据库(MongoDB)，时序数据库(InfluxDB)，图数据库(Neo4j)等，还有目前使用最广泛、最重要的关系数据库(MySQL、PostgreSQL 等)，这也有今天的主角——关系数据库。

对于关系数据库，与它有关的论文、书籍、博文都数不胜数，但是大部分书籍和博文都在教开发者如何去使用一款数据库，鲜有去教开发者如何去弄懂数据库系统架构设计、原理和实现的。

《Database System Concepts》正是这样一本书(中文名：《数据库系统概念》)，而恰好也有这么一门课程 CMU15445，来教我们如何去弄懂数据库原理，掌握数据库系统设计，甚至去实现一个小巧的数据库—— bustubopen in new window 。

而这恰好也是本文主题——关系数据库的设计与实现。本文不会去介绍如何写 SQL，如何用索引，如何数据备份，而是希望通过剖许 bustub 这个精巧的关系数据库来告诉你：数据库系统架构是什么样的？为什么要这么设计？它又是如何实现的？

在正式介绍数据库设计和实现之前，请你先尝试回答如下几个问题：

数据库会预读数据到缓冲池中，缓冲池是如何实现的，它有何作用？
B+树似乎是数据库组织数据的最常用数据结构，它又是如何实现的？B+树一个节点究竟能存储多少项？B+树又是如何支持并发访问的？
数据库是如何执行 SQL 的，执行器究竟是如何实现的？
数据库事务隔离级别有哪几个？不同级别又是如何实现？数据库是如何处理并发访问控制的？如果你能迅速回答出这几个问题，那么本文可能不适合你，可是如果你还有疑惑，想要尝试从源码级别上来搞懂这几个问题，那么希望你能耐心阅读完本文，相信你能从中自己发掘出答案。

注意：bustub 是 CMU 数据库组开源的一款关系数据库，用于 CMU15445 课程实验。目前 bustub 开源于 Github，代码虽然开源，但是由于涉及到课程实验作业，因此开源的只有一部分，为了保护课程，避免抄袭，本文只会贴出部分实现代码进行剖析，其它部分只会用画图的方式来说明。

总览

整体架构

bustub 究竟有哪些模块，这些模块负责哪些功能，模块之间如何协调？下面，我们一起来看看。

bustub 整体架构图如下：

图 1 bustub 架构图

bustub 暂时没有 SQL 解析器、优化器等，其着重点在于数据库后端部分，即上图 1 中的查询处理、存储管理和磁盘存储三大部分，这三部分又包含了数据库很多模块：

执行器(executor)：负责执行查询、插入等计划(plan)，bustub 暂时并未实现 SQL 解析器，无法将 SQL 语句转化为执行计划，因此需直接写代码构建执行计划来执行；
缓存管理器(buffer_pool_manager)：从磁盘中读取页数据并缓存在内存中，避免每次查询、更改都读写磁盘，是数据库性能提升的核心组件；
磁盘管理器(disk_manager)：负责向磁盘写数据页、日志，或者从磁盘读数据页、日志；
事务管理器(transaction_manager)：bustub 支持数据库事务，保证数据操作的原子性、一致性等；
日志管理器(log_manager)：为避免物理机突然崩溃，bustub 实现了日志记录功能，用于故障后数据恢复；
快照管理器(checkpoint_manager)：实现数据库数据快照功能；
磁盘存储：由磁盘管理器和宿主机操作系统共同完成。在这个架构下，bustub 每执行一次查询(或更新、插入)的流程就如图 1 中的箭头所示：

应用程序构建执行计划，并将执行计划交给执行器；
执行器根据执行计划，请求事务管理器获取事务，然后以事务的方式请求缓存管理器获取数据页；
缓存管理器判断数据页是否已在缓存中，如已在，则直接返回页数据，不存在则调用文件管理器读取对应页然后再返回；
执行器根据执行计划中过滤条件筛选数据返回给应用程序。当然这个过程中还伴随着索引、锁、日志、缓存淘汰等操作，这些将在后面详细介绍。

代码结构

了解了 bustub 整体架构后，我们一起来看一下其代码结构，对项目整体有一个基本认识。如下：

./src
├── buffer // 缓存模块，如缓存管理器，淘汰算法LRU
├── catalog // 数据库目录，如数据列、数据表定义
├── common  // 公共模块
├── concurrency // 并发控制，如事务管理器、锁管理器
├── execution // 执行模块，如查询执行器、插入执行器等
├── include   // 头文件
├── recovery  // 故障恢复模块，如快照管理器，日志管理器
├── storage   // 存储模块
│   ├── disk  // 磁盘存储，磁盘管理器
│   ├── index // 索引，B+树
│   ├── page  // 数据页，如B+树索引页，数据表页，元数据页
│   └── table // 数据表，数据记录，数据表迭代器
└── type // 字段类型，如整型、bool类型等

每个目录后面用注释说明了当前模块的作用和功能，这些模块将按照如下顺序依次介绍：

缓存池：buffer 目录，缓存池、LRU 算法实现；
并发 B+树：storage 目录，B+树实现及并发；
执行器：execution 目录，执行期实现；
并发控制：concurrency 目录，事务管理器、锁管理器实现；
故障恢复：recovery 目录，日志记录、快照实现。下面，我们来依次详细介绍这些模块的作用和实现。

参考资料

CMU15445-fall2020open in new window
Database System Concepts, 6th Edition

谈谈关系数据库的设计与实现(1)——总览

# 前言

# 总览

# 整体架构

# 代码结构

# 参考资料

前言

总览

整体架构

代码结构

参考资料