<未完成>数据库系统的基本概念和底层存储方式

发表于 更新于 分类于 阅读次数：

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

为什么需要数据库?

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

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

当然, 这些看似朴素的做法也并不是错误的, 事实上早期的数据库就是这种数据的结构和存储方式耦合度较高的做法(直到关系型数据库的提出), 而直到现在许多数据库(某些 NoSQL)也使用 JSON 等文件格式来表达一个对象的方式来存储数据. 然而, 这样的方式存在许多问题. 其中的主要矛盾是, 现实工程中的数据和数据间关系是复杂的, 而计算机科学中处理复杂问题的最主要手段(可能是唯一的手段)就是抽象. 序列化与反序列化一个对象的方式尚且较为灵活, 此处以纯文件输入输出举例: 我们可以明显看出从”纯粹文本文件”到”有语义的数据”之间有一个较大的跨度, 如果用户数据新增了某个属性(酒店管理系统新增了检验年龄的功能), 则需要重新构建整个数据文件; 除此之外, CRUD 等基本操作也过于朴素不利于优化. 这种抽象层次的缺失造成了一种耦合: 如果数据间的关系发生变化, 就会对较底层的文本文件有较大的影响, 引入无关复杂性而不利于维护(白话说就是麻烦).

因此, 我们需要将”纯粹的文本”和”有意义的数据”区分开来, 就需要新增一层抽象, 我们称之为数据库的 Schema. Schema 是数据库的蓝图和框架, 定义了数据的结构, 关系和约束等规则. 在逻辑层面上, Schema 包含表/列/主键/外键等\(^{[1]}\). 为了实现这一层抽象, 我们需要维护操作数据的一套行为, 包括 DDL(数据定义语言, 用于表示一个 Schema), DML(数据操作语言, 用于在数据上进行操作). 有了这一层抽象, 我们在刚才的例子中就可以简单地使用 DDL 为 Schema 新增一个”年龄”列(Schema 是可变的!), 我们只需要使用 DDL 就可以了, 真正要考虑多的是这一套行为的具体实现——我们称之为 DBMS(数据库管理系统).

$[1]: $ 在实现上, 不同数据的差异可能较大, 例如 MySQL 中 SCHEMA 和 DATABASE 是同义词, 而 PostgreSQL 的一个 DATABASE 可能包含多个 SCHEMA.

基本概念

我们已经介绍了 Schema 的基本概念, 这里不再赘述.

关系型数据库

对于关系型数据库, 我们把表中的某一列属性(比如用户的年龄)建模为一个年龄的集合, 而整个关系型数据库实际上就是不同集合(年龄集合, 名字集合, 电话号码集合)之间的关系运算: 整个数据表也就是这些集合的笛卡尔积的子集(笛卡尔积的概念参考 Wikipedia, 没学过离散数学也可以轻易理解概念). 同样地, 其他操作也可以看作集合间的关系运算, 我们会在后面详细介绍其中的主要运算.

从而, 数据表就是一个”关系”. 还记得离散数学中”n 元关系”的定义吗? 我忘了 反正就是笛卡尔积的子集

一些术语:

列/属性/集合/字段

列, 也称为一个属性或一个集合(在关系代数的语境下), 上文已介绍.

需要注意的是, 在具体的 SQL 语言语境下, 通常会将属性的名字称为字段.

行/记录/元组

行, 也称为一个元组. 在关系代数的语境下, 集合之间的笛卡尔积运算可以得到一个元组.

例如, 一个名字集合 \(N = \{\text{Adam},\text{Eve}\}\) 年龄集合 \(A = \{930, \text{929}\}\) 作笛卡尔积得到 \(N \times A = \{ (n, a) \mid n \in N, a \in A \} = \{ (\text{Adam}, 930), (\text{Adam}, 929), (\text{Eve}, 930), (\text{Eve}, 929) \}\).

一张数据表往往是笛卡尔积结果的子集, 即从所有可能的组合中选取那些符合业务逻辑和现实约束的有意义组合: \(\{ (\text{Adam}, 930), (\text{Eve}, 929) \}\). 即:

Name Age
Adam 930
Eve 929

所以数据库中的一行也称为一个元组, 一列也称为一个集合. 这是在关系代数中对现实数据的建模.

笑点解析: 我本来想随便编个 A/B 开头的人名, 突然蹦出了个写亚当夏娃的念头, 然后现查的活了多少岁

笑点解析2: 实际上夏娃的年龄没有准确的定论. 为了处理这种情况, 现实中的数据库往往不会严格按照关系代数实现, 现实数据库往往是基于 bags (背包, 允许重复元素) 而不是 sets (集合, 不允许重复元组)的, 同时允许 NULL 值 (如果 Schema 没有明确 NOT NULL).

另外, 一行/一元组有时也称”一条记录”. 这是为了区分在不同语境下同一样事物的特点.

主键(Primary Key)

拒绝主码翻译谢谢喵。用来唯一确认一条记录\(^{[2]}\), 例如学生 id. 主键这一集合必然是纯粹的集合, 不允许重复的主键存在, 毕竟 Primary Key 也叫 Unique Key.

$[2]: $ 大部分数据库管理系统中, 不定义主键会导致数据变成一坨东西(具体来说, 没有行标识符, 没有聚簇索引… 后面再说). 而 SQLite 中, 即使你不在 Schema 中手动写 id INTEGER PRIMARY KEY, 也会自动分配一个 rowid, 承担类似主键的职责. (如果手动定义了主键也会有 rowid, 但此时主键是用户定义的主键)

外键(Alien Foreign Key)

用于在当前表中引用其他表的主键, 强制两个表之间的数据同步和数据完整性. 例如, 不应当在订单列表插入一个根本不存在的客户 ID. 棍母下的订单说是

SQL 基础

这里只介绍简单的 SQL 语法及语义. SQL 的语法并不难, 应当把重点放在”如何写出好的查询”这一类问题上, 故对语法不作过多赘述.

子句的逻辑执行顺序(FROM, JOIN, WHERE, GROUP BY, HAVING, SELECT, ORDER BY)

SQL 的子句书写顺序贴近英语语法, 但是实际执行并非按照书写顺序执行. 简单来说分为以下步骤:

  1. FROM 和 JOIN 子句: 数据库确认数据来源, 找到需要操作的表: 可以是已经存在的表, 也可以是两个表的连接
  2. WHERE 子句: 过滤行, 挑选出符合要求的行, 如 WHERE s.age >= 18
  3. GROUP BY 子句: 按照要求将符合要求的行聚合为一个逻辑组(这也是一张表, 但是每一行包含了多个”同类”的行). 例如 GROUP BY dept, 会把 dept 列相同的所有行聚集为一行, 所有部门每个不同的 dept 一行形成一个逻辑组.
  4. HAVING 子句: 对于 GROUP BY 结果的过滤
  5. SELECT 子句: 对上一步结果表的每一行, 独立计算 SELECT 子句中的表达式, 形成最终输出表的一行中的一个单元格.
    • 最常见的用法, SELECT t.salary * 1.1, 对于输出的每一行, 直接获取 salary 列的值增加 \(10\%\) 的结果;
    • 聚合函数, SELECT AVG(t.salary) ... GROUP BY t.dept, 输入是 GROUP BY 产生的结果表中的一行(也就是一个逻辑组, 对于本例一个逻辑组是同一部门的所有行); 如果没有 GROUP BY, 则将整个表视为一个逻辑组. 总结来说, 聚合函数的作用对象是行的集合, 逻辑组或将子查询整个表的所有行视为一整个的逻辑组
    • 一个标量子查询(只有一行一列即一个单元格的值): 对于每一行都执行一次这个子查询, 把返回的单一值作为这一行的结果
  6. ORDER BY: 字面意思. ORDER BY name ASC, salary DESC, 对行进行排序

这里的描述(尤其是 SELECT 的实际语义)写得较为繁琐(相比其他教程), 但正因为如此才能避免一些编写 SQL 语句时可能遇到的陷阱致使初学者困惑. (困惑是必然的, 区别只是学 SELECT 时就开始困惑还是 SELECT 的语义没掌握好导致到写出陷阱时才开始困惑)

我们来看一个简单的聚合例子:

1
2
3
SELECT AVG(score), major
FROM students AS s
GROUP BY major

计算学生表中每个专业学生的平均分数. 考虑 SELECT 子句:

  • AVG(score): 聚合函数, 对 GROUP BY 产生的逻辑组 (例如 major 为 CS 的所有同学) 的 score 列计算均值, 没有问题
  • major: 每一行(由于存在 GROUP BY, 这里一行是一个逻辑组)中的 major 是相同的, 都是同一专业的学生, 也没有问题.

如果我此时我们想顺便也查看每个学生的名字, 缺乏经验的人可能会这样写

1
2
3
SELECT name, AVG(score), major
FROM students AS s
GROUP BY major

此时便出现错误, 此时的”一行”实际上是一个”逻辑组”, 包含了许多同专业的学生, 显然不会全部是一个名字\(^{[3]}\). 聚合函数会把单独的学生行聚集成逻辑组, 导致 SELECT 无法 SELECT 单个行的属性!

由此可以得出使用 GROUP BY 子句时 SELECT 子句的相应规则: 要么是一个聚合函数, 要么是一个 GROUP BY 的列本身. 当然死记硬背也可以写对, 但是就缺乏了”为什么会有这样规则”的理解.

$[3]: $ 遇到这种情况就需要使用窗口函数, 请自行查阅.

关系代数模型及其闭包性质

SQL 是一门编程语言. 这看上去比较反直觉, 因为 SQL 实际上是一种领域特定语言 (DSL). 有关 DSL 其实有很多好玩的东西, 但是这里尽可能不偏离主题. 正因如此, 许多熟悉了常见高级语言的人学习 SQL 时往往会感到疑惑, 最具代表性的是有关类型的疑问: “这个子句执行后得到的结果是什么类型?”

产生此疑惑的原因之一是 许多高校并没有专门的编程语言理论课 SQL 的类型系统高度基于关系模型(这里只讨论表等关系类型, 除此之外如 INTEGER 等标量类型不做讨论). 你可能已经注意到了, 所有关系运算符 (SELECT, JOIN, GROUP BY 等) 的输入都是一个或多个关系, 输出是一个新的关系 (或者说表也可以), 这是关系代数的封闭性(也叫闭包性质, 指对一个集合进行运算后的结果仍然属于该集合), 使得代数大大简化(子句操作的都是关系, 整个语言中只分为关系类型和标量类型), 毕竟数据表的规模和大小可能有非常多的形式.

<TODO 此处补充: 关系代数与关系演算; 关系代数的常见运算…>

语义和实现的抽象屏障

在命令式语言的教学中通常缺乏对”语义”和”实现”这两种抽象层次的分离, 例如: “引用占不占内存空间?\(^{[4]}\)” 这类问题就是在模糊语义和实现的边界. 而在声明式语言中, 语义和实现往往有了不言自明的区分: 声明式语言只需要描写出”我想要什么”, 实际实现并不是我详细描述出来的步骤. (具体来说, 就是查询优化器等存在)

<TODO 在此处补充: 不同的 JOIN; JOIN 和 嵌套查询的性能差异…>

$[4]: $ “References are not objects; they do not necessarily occupy storage, although the compiler may allocate storage if it is necessary to implement the desired semantics (e.g. a non-static data member of reference type usually increases the size of the class by the amount necessary to store a memory address).”

Reference declaration - cppreference.com

进一步有用的 SQL

<TODO 在此处补充: 嵌套子查询; 窗口函数; 横向连接>

存储模型

<这部分应该拆出来另一篇文章, 但是前面还没写好感觉太特么单薄了, 我没写过这么短的文章, 等前面补一补再往后开>

文件存储: Heap File

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

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

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

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

为什么重造轮子?

以上这些东西听起来像是操作系统虚拟内存的功能, 甚至也有对应功能的实现: sys_mmap 系统调用, 映射磁盘页到内存, 标记脏页, 写回磁盘, 甚至还有 COW, 看上去非常”最佳实践”. 事实上也的确有很多数据库完全采用 mmap 系统调用来实现数据的, 但实际上 mmap 会导致许多问题: * 首先, 数据库的事务必须是原子性的(设想一个修改余额的操作进行了一半会怎么样?), 而操作系统诞生之初就是对一些功能的封装和抽象, 这意味着其资源管理是完全透明的(这意味着我们对其细节不可知), 具体来说, 它可能在任何时候 flush dirty page, 我们没法控制何时把脏页写回磁盘

  • 其次, 由于操作系统对页面资源的管理完全透明, 我们对页面是否在内存中并不了解, 每一次对页面的访问都可能导致一个 PAGE FAULT. 这往往是很耗时的, 操作系统会阻塞当前线程并从磁盘加载页面到主存

  • 由于 BPM 中可能存在驱逐等操作, 会改变磁盘页到内存帧上的映射, 在使用 mmap 时, 这些 page id to frame id 的映射是在页表中的(事实上, 有经验的开发者应该提到页表就开始敏感性能问题), 修改页表需要粒度较大的锁, 而且为了维护多核 CPU 的缓存一致性, 修改页表的 CPU 核心必须通过处理期间中断通知其他核心也及时更新 TLB, 造成 TLB Shootdown; 那么使用自己的 BPM 会怎么样呢? 所有的锁都是用户态的锁(POSIX 互斥锁的实现通常是 futex, 而实际上 futex 的特点就是在用户态执行大部分锁操作), 不涉及任何 TLB Shootdown, 性能很高

    所以手动实现一个 Buffer Pool Manager 是有意义的.

我们称这样的文件存储方式叫 “Heap File”, 因为其中的页只是无序地存在, 通过 Page Directory 查询页的位置, 没有树形组织或者哈希等应用.

页面布局:

把数据库中的行和列存到页面中有几种方式, 可以选择以行为单位存 \(r\) 个行, 也可以选择以列为单位存 \(c\) 个列

  1. NSM, 面向行进行存储: 适用于多次写(而每次写入少量)少读的 OLTP (事务型数据库)

    一般是 tuple-orientation storage, 例如 PostgreSQL 就是行存储

  2. DSM, 面向列进行存储: 适用于复杂 SQL 查询而写入操作较少的 OLAP (分析型数据库)

    先将若干行为一组形成行组(row group), 然后将每个行组按列分为列块, 以列块为单位进行存储

    可使用日志结构存储或索引组织存储. 但注意列块到页是另一层抽象.

  3. PAX, 混合型: 若干个完整的行存入同一页面中, 但页内的存储是按照列存

而具体的实现目前主要有以下几种:

(这部分建议参考 cmu15-445 24Fall 的 Slides 图示)

  1. Tuple-Orientation Storage: NSM 的实现, 与 NSM 强相关. 一页中存储 header 和 slot 数组, 而元组本身从后往前存 <缺点>
  2. Log Structure Storage: 一种高效的 DSM 实现. Log Structure Merge Tree, MemTable 和多级压缩的 SSTable, 以及摘要表
  3. Index-Organization Storage: 使用平衡树(考虑到并发和缓存性能, 通常是 B+)存储行节点, 按照主键索引排序.

元组布局:

压缩: