折鸦夜明け前

上一篇博客: 数据库系统的数据存储方式 | Amiriox’s Storage

上次写博客是在一个多月前了, 最近比较忙, 博客只能抽空写. 精神状态也不是很好, 得想想办法 ()

数据库系统的访问方法

我们在这个系列的第一篇文章(数据库系统的基本概念 | Amiriox’s Storage)中就介绍了数据库的架构分层, 但没能真正展开.

具体来说:

• 磁盘管理器单纯用来和磁盘进行交互, 不过通常实现一些异步方案进行优化(Bustub 就利用了 std::promise)
• 缓冲池在上一篇文章(数据库系统的数据存储方式 | Amiriox’s Storage)中介绍了, 为防止磁盘 I/O 成为性能瓶颈, 有计划地(一些页驱逐策略)将磁盘中的页加载到内存中作为内存中的一个页帧\(^{[*]}\)
• 访问方法通过特定的数据结构从页中找到上层算子执行所需要的信息, 本文将详细解释这些数据结构
• 算子是关系代数中的具体操作实现(当然, 事实上是基于可重集合, 甚至有序可重集合的特殊关系代数), 这在后面的文章中会详细介绍, 例如数据和逻辑是如何在这些算子间流动最终得出查询结果的, 算子的执行体现了程序究竟在做什么: “用逻辑塑造一个管道让数据在其中塑形”。
• 查询优化, 面对一个已知的 SQL 语句, 预估大概的执行成本, 选择采用什么索引, 某些算子的执行顺序交换, 以形成相对更优的执行计划

上一篇博客: 数据库系统的基本概念 | Amiriox’s Storage

存储管理: 数据存储模型

上一篇博客提到了数据库管理系统本身的抽象层次, 其中就有 Disk Manager 和 Buffer Pool Manager 作为数据库的存储管理器。

提到”数据库的数据存储方式”时, (尽管有些早)一半涉及到三个层次的存储方式: 文件的存储方式、页面内部的布局、元组的内部布局. 其中为什么需要文件的存储方式与元组的内部布局较好理解, 而数据库中页面的概念将会在下面说明, 为什么数据库需要实现自己的页面.

文件存储方式: Heap File

您可能需要阅读 CSAPP3e第六章(存储器层次结构) | Amiriox’s Storage 来对计算机存储器的层次结构的意义有一定的认识.

简单来说, 由于不同存储设备的访问速度不同, 在冯诺依曼体系的计算机不可避免地数据传输中会拖慢更快速的存储设备的效率, 所以按照存取效率进行排序, 利用时间/空间局部性, 将更快的存储器作为次快的存储器的缓存, 最大化利用存储器的存取效率.

很显然, 数据库的数据必须是可持久化的, 也就是最终要存在文件系统上, 而 CPU 对磁盘的访问通常较慢(尽管有 DMA), 最主要的原因是某个公司曾推出的可持久化的快速主存没能发展起来(大雾) 所以我们需要将主存作为磁盘的缓存, 利用磁盘加载到内存中的页面, 主要的数据操作在主存中进行, 最后将修改后的(脏页)写回磁盘. 这些页面交由执行引擎使用, 而与 Disk Manager 交互, 提供这个页面交换功能本身的组件叫 Buffer Pool Manager (BPM)

具体来说, 数据库的一个文件分为若干个固定大小的连续空间, 称为页, 这个文件称之为 Heap File, 也就是一堆无序的页面的集合; 同时还会有一页称为页目录 (Page Directory), 记录某个页在哪个 Heap File 上的哪个偏移量(位置).

当执行引擎指明我需要页号为 \(\text{page_id}\) 的页时, BPM 负责从磁盘中先提取 Page Directory 所在页, 解析其中的布局, 获取到一些元信息: \(\text{page_id}\) 这一页存在哪个文件里, 偏移量是多少; 然后通过文件和便宜量找到对应页, 加载到内存(单纯的复制). 当然, BPM 还要负责标记脏页/驱逐页面/写回等任务. (当然, 实现上肯定会分为不同组件, 单一职责)

数据的可持久化需求的抽象层次矛盾

为什么需要数据库?

绝大多数学校的程序设计课节课时或开课期间的实验课都会有一个工程实践, 一般是 XX 管理系统, 向刚刚学习程序设计的学生浅显地介绍实际工程中的一些应用(输入输出交互/控制流/数据处理/可持久化), b 格高一点的如 gitlet 针对可持久化还会有对象的序列化/反序列化等介绍, 建立起对于可持久化数据的基本认知.

一个运行中的程序的实例(进程以及其中可能存在的多个线程) 实质上是一段内存中的数据(代码区/数据区, 堆/栈, 环境和参数), 例如局部变量或者动态分配的内存, 而这些都是不可持久化的数据, 在程序关闭后大部分数据会被操作系统清理. 此时如果想可持久化某些数据使得下次程序启动仍然可以打开, 就需要将数据可持久化到磁盘上(更现代来说是闪存). 例如, 在 XX 管理系统中会通过语言标准库提供的文件输出接口把用户数据或日志逐行存在文件中, 在 gitlet 项目中会把 Commit 的对象等序列化后写入文件.

当然, 这些看似朴素的做法也并不是错误的, 事实上早期的数据库就是这种数据的结构和存储方式耦合度较高的做法(直到关系型数据库的提出), 而直到现在许多数据库(某些 NoSQL)也使用 JSON 等文件格式来表达一个对象的方式来存储数据. 然而, 这样的方式存在许多问题. 其中的主要矛盾是, 现实工程中的数据和数据间关系是复杂的, 而计算机科学中处理复杂问题的最主要手段(可能是唯一的手段)就是抽象.

“对复杂性管理的关键是抽象这个概念.”