Skip to main content

差点忘了 CMU 15445

· 26 min read
therainisme

我不是没有学过，是真的快忘完了……

目前来说，这篇文章可能只会关注数据库的存储，执行，并发、恢复机制，对于 SQL 的执行优化部分比较少，这与我的研究方向有一定的关系。

数据库为何而来​

数据库至始至终只为解决两个问题：（1）如何快速地存放数据？（2）如何快速地查询数据？

最简单的数据库即为 CSV 文件：（1）在写入时，直接将数据写入文件末尾。（2）查询时，直接从文件末尾向前查询。非常 Easy 对吧！下面是两个 Table，一个是 Artist 表，一个是 Album 表。在数据量非常小的时候，这么存完全没有问题。但在数据量大，或者用户量大的时候，就不行了。

// Artist
"Wu-Tang Clan", 1992, "USA"
"Notorious BIG", 1992, "USA"
"Ice Cube", 1989, "USA"
// Album
"Enter the Wu-Tang", "Wu-Tang Clan", 1993
"St.Ides Mix Tape", "Wu-Tang Clan", 1994
"AmeriKKKA's Most Whated", "Ice Cube", 1990

完整性约束带来的问题​

  1. 如何保证 Album 表中的艺术家，一定存在 Artist 表中？
  2. 年份如何保证的是数字，而不是字符串？
  3. 当一个专辑，属于多个艺术家时，还能用 CSV 这么存吗？
  4. 如果从 Artist 表中删除了某个艺术家，它在 Album 表中的专辑也要删去吗？

并发带来的问题​

  1. 如何快速定位 CSV 数据行？
  2. 如果两个线程同时读写 CSV，如何保证并发安全？

持久化带来的问题​

  1. 如果在更新一条记录时，程序崩溃，怎么办？数据是完整的还是缺失的？
  2. 如果想复制数据库到多台机器上，达到高可用性，怎么做？

数据库的未来​

总之，上面这些问题是数据库一定会有的。当解决一个问题时，又会有新的问题诞生，这样大家又可以继续水论文了。

现在数据库管理程序只能通过编写 SQL 数据将期望的数据查询出来，理想中的数据库管理程序，用自然语言就能查询期望的数据。（应该在不就之后吧）

反正就只需要记住数据库至始至终只为解决两个问题：（1）如何快速地存放数据？（2）如何快速地查询数据？

存储形式​

数据库存储背景​

下图中是计算机存储层次架构图，越往上的存储介质，速度越快，空间更少。反之，越往下的越慢，但有更廉价的存储。不过还是主要分为两类：易失（Volatile）和非易失（Non-Volatile）

  • 易失（Volatile）：访问速度非常快，但是非常昂贵。通常指断电易失的介质，例如 CPU 寄存器、CPU 缓存、内存。
  • 非易失（Non-Volatile）：访问速度较慢，但是非常廉价。通常指固态硬盘、机械硬盘、网络硬盘。

在不同访问方式的速度上，也有不同：

  • 顺序访问（Sequential Access）：快
  • 随机访问（Random Access）：慢

那么此时，在这种存储介质限制的背景下，数据库的设计目标就转变成了：

  1. 需要管理一个占用空间大小超过内存的数据库，会涉及 IO 读写
  2. 读/写磁盘的 IO 代价非常昂贵，应该避免出现大量 IO 读写，导致性能下降
  3. 读写 IO 时尽可能进行顺序访问，减少 IO 读写的性能损失

问题1：如何在磁盘上表示数据库中的数据​

一般来说，DBMS 会组织一堆文件在磁盘上，但操作系统不知道这些文件内容是什么，仅能由 DBMS 的 Storage Manager 进行正确地读取和写入。Storage Manager 的职责有：

  1. 将一个文件看成是一组 Page 的集合
  2. 自行调度 Page 的读取和写入，以最大化时间利用率和空间利用率

Page 是 Storage Manager 的操作的最小单位：

  • Page 是一个固定长度的数据段，不同 DBMS 的 Page 大小也不同，有 4KB、8KB 甚至 16KB 的
  • Page 可以存 DBMS 想要存储的任意形式：Tuple、Metadata、Index、Log 等等
  • Page 是 Self-contained 的，意思是该 Page 中有 Page Header 的信息，读取 Page 时先读 Header，识别出何种 Page 后才能读数据
  • Page Header 部分信息包括：Page Size、Checksum、DBMS Version、Transaction Visibility、Compression Information

问题2：File 内部如何管理 Page​

不过在此阶段，不需要知道 Page 内部是什么。

File 内部的 Page，就是 Page Heap，就像把一堆 Page 堆放在 File 里。如果存放 Page 的文件只有一个，又因为 Page 大小固定，通过计算偏移量，就能很快地将对应 Page 的下标 Offset 找到，从而加快 Page 读取速度。

如果一个文件太大，就需要多个文件来存放 Page。哪个文件剩余空间多少，存放什么 Page，这就需要额外的 metadata 来维护这些信息。

这样一来，为了索引 Page，DBMS 就需要维护一些特殊的 Page，这些 Page 会记录 Data Page 在数据库文件中的位置，这有点像操作系统的 Page 目录。

  • 确保目录 Page 中的信息和 Data Page 中的信息一致
  • 记录每个 Page 有多少个空闲的 Slot
  • 维护空闲 Page 的列表
  • 等等等职责……

当然可以不以 Page 目录的形式，也可以以 Page 空闲链表的形式：DBMS 在文件开头维护一个 header 页，储存两个指针：指向第一个空闲页、指向第一个数据页。

问题3：Page 内部如何管理 Tuple？​

这里只介绍两种：（1）Tuple-oriented 是传统的 MySQL 为首的关系型数据库采用的方式，（2）Log-structed 是以 LevelDB 为首的日志型数据库采用的方式。

Tuple-oriented​

最简单的方式！在 Page 头部记录有多少个 Tuple，有新 Tuple 时直接插入到 Page 末尾即可。但这会出现其他问题：

  • 如果删除了一个 Tuple，例如删除了 Tuple #2，会发生什么？
  • 如果在删除之后插入了 Tuple #4，插入到了原先删除的位置，会发生什么？
  • 如果 Tuple 长度可变？哪怎么维护？

很显然啦，这种方法缺陷太多。一个改进的方法是 Slotted Pages，如图。

  • Header 就是前文说的 Page Header，存储一些 metadata。
  • Slot Array 储存每一个 Tuple 的起始 offset。Header 还会记录已经使用的 Slot 和最后一个使用的 Slot，便于查询和写入
  • 写入时 Slot Array 向后写入、Tuple 数据从后往前写入，当两个即将相邻时意味着该 Page 将要写满
  • 删除时例如删除了 Tuple #3，那么 Tuple #4 将会移动至 Tuple #3 先前的位置

Tuple 肯定需要唯一的标识 ID。大多数情况，每一个 Tuple ID（Record ID）都会以 page_id + offset/slot 形式，当然也可以附带文件的信息，变成 filename + page_id + offset/slot。不过这个 ID 对于上层应用来说毫无语义，需要注意这一点。

Log-structed​

可参考资料

后面再写了……

问题4：Tuple 内部如何组织 RAW 数据？​

Tuple 本质上是一个字节数组，DBMS 的工作是将这些字节译为属性类型和值。对于关系数据库，属性通常按照创建表时指定的顺序存储。然而，以不同的方式排列它们可能更有效。

如果两个表之间有外键的关系，可用将两个表的 Tuple 储存在一起。这样可用潜在地减少 IO，但也会增大了更新 Tuple 的开销。

问题5：磁盘中 RAW 数据的表示形式​

Variable Precision Number（可变精度数字）​

和 C/C++ 类型一致，按 IEEE-754 规定直接存储。这样通常比 Arbitrary Precision Number 更快，但可能有舍入误差。

Fixed Precision Number（定长精度数字）​

例如：Postgres 中的 DECIMAL、MYSQL 中的 NUMBERIC。

它们是具有任意精度的数字类型，有不同的实现方式，一半会额外存储一些元数据（例如红色剪头指向的数据，即为额外存储的元数据）。如果放弃任意精度，那么开销会更低。

Large Values（数据大小超过 page 大小）​

大多数 DBMS 不允许 Tuple 超过单个 Page 的大小。如果 DBMS 储存的值超过了 Page 大小，DBMS 会使用额外的页（Overflow Page）。不同数据库对溢出的定义也不同：

  • Postgres: TOAST (>2KB)
  • MySQL: Overflow (>½ size of page)
  • SQL Server: Overflow (>size of page)

External Value Storage（再大就只能存外部文件）​

一些 DBMS 还允许用户储存非常大的值，储存在外部文件（External File）里，作为 BLOB 类型。但是它没有持久性保证，也没有事务进行保护。

主要工作负载​

On-Line Transaction Precssing（OLTP）​

读取或更新一小部分数据的快速操作。比较常用，开发小型应用都是它。

On-Line Analytical Processing（OLAP）​

复杂的查询，读取大量数据进行计算分析。当数据量非常大的时候，可以从 OLTP 数据库提取数据到 OLAP 数据库中，再进行数据分析。

Hybrid Transaction + Analytical Processing​

前两者的混合

存储模型​

N-Ary Storage Model（NSM）​

NSM 又称为行存储。DBMS 将单个 Tuple 的所有属性连续地存储在一个 Page 中，这是 OLTP 理想的存储模型。

  • 优点：插入、更新、删除操作非常快速。非常适合需要读取整个 Tuple 数据的查询。
  • 缺点：不适合大部分扫描全表，不适合查询 Tuple 子集数据的查询。如右图中，只想查询 LastLogin，但是也会将 Tuple 中的 UserID、userName 和 userPass 给扫描到。

Decomposition Storage Model（DSM）​

DBMS 将所有 tuple 的单个属性的值储存在了一个 page 里，一般用于 OLAP，也称为列存储。

  • 优点：减少了不必要属性的读取，也就减少了磁盘 IO，更适合 OLAP 的查询过程。
  • 缺点：不利于单点的查询、插入、更新和删除，因为改动一个 Tuple 会对多个 Page 进行操作。

Choice #1: Fixed-length Offsets（Tuple 定长）

在这种方法中，无论其实际内容如何，每个属性值都占用相同的存储空间。

  • 优点：（1）访问速度快，因为每个属性值的位置是固定的，可以通过简单的算术运算快速定位值的位置。（2）如果属性值长度固定，存储空间会更紧凑，不需要额外存储标识符 ID。
  • 缺点：（1）如果属性值长度不一，可能会导致存储空间的浪费，因为所有值都必须填充到相同的长度。 对于长度变化较大的属性，这种方法可能不太适用。

Choice #2: Embedded Tuple Ids（Tuple 变长）

在这种方法中，每个属性值都与其对应的 Tuple ID 一起存储，这样可以明确知道每个属性值属于哪个 Tuple。

  • 优点：更灵活，可以处理长度不一的属性值。
  • 缺点：可能会占用更多的存储空间，因为需要额外存储元组 ID。访问速度可能稍慢，因为需要根据 Tuple ID 来确定属性值的归属。

磁盘 Page 在内存中的缓存池​

数据库受限于空间和时间。

  • 空间：内存无法容纳数据库全部的数据，当 CPU 在内存中写一个 Page 时，需要及时的将其写入磁盘，以免断电丢失数据。当 CPU 尝试读取一个 Page，但如果它不在内存，需要进行昂贵的磁盘 IO 将其读入到内存。所以理想中的数据库，希望操作一个 Page 时一定在内存中，不需要磁盘 IO。
  • 时间：什么时候将 Page 写入磁盘，什么时候将 Page 读入内存，这些高昂的磁盘 IO 会导致程序中断，影响性能。一个好的数据库应该想尽办法隐藏磁盘 IO，就像 Page 永远在内存中一样。

Buffer Pool Manager​

Buffer Pool Manager 会在内存中维护一组定长的 Page，在内存中叫做 Frame（帧）。当 DBMS 请求一个 Page 时，Buffer Pool Manager 会从磁盘中读取该 Page 的副本，存放在一个 Frame 中。

Buffer Pool Manager 会为所有 Page 的元数据维护一个 Page Table。主要是记录：

  • Dirty Flag：内存中的 Page 是否被写了。如果没有被写，则可以直接在内存删除该 Page 数据，不需要写回磁盘。
  • Pin/Reference Count：目前有多少个线程在使用该 Page。如果没有了，说明它可以在空闲时被安全地写入磁盘。

Page Directory 和 Page Table 的区别
  • Page Directory 是 Page ID 到数据库文件中 Page 位置的映射。它必须记录在磁盘上，以便 DBMS 重启时能直接读取它。
  • Page Table 是 Page ID 到 Buffer Pool Manager 中 Frame 的映射。它只需要在内存中，不需要存储在磁盘上。
区分 Lock 和 Latch
  • Lock：数据库的逻辑锁，用于保护一个交易执行时，免受被另一个交易影响。
  • Latch：在程序实现时使用的锁，例如 Mutex。用于保护程序执行时关键数据段的并发安全。

Buffer Pool Manager 优化技术​

  • Multiple Buffer Pools

DBMS 可以采用多个 Buffer Pool，这样可以减少 Latch 的争用，甚至可以通过局部性提高性能。下面两种方法本质上都是通过标识 Record 的局部信息，由 DBMS 自行选择使用哪个 Buffer Pool。

  • Pre-Fetching

在某些时刻，SQL 执行的是迭代操作，就可以在迭代操作的后几个 Page 提前读取到 Buffer Pool 中，借此来掩盖磁盘 IO 的延时，就像 Page 一直存放在内存中。

  • Scan Cursor Sharing

在某些扫描操作中，如果存在两个相同的扫描操作，可以将其二者的 Cursor 合并。例如下图中，Q1 先扫描了 Page 0、Page 1 和 Page 2。此时 Q2 才到来，它不需要从头 Page 0 继续扫描，而是和 Q1 共享 Cursor。当 Q1 继续扫完 Page 3、Page 4 和 Page 5，Q2 能继续利用 Cursor 从 Page 0 继续扫描。

  • Buffer Pool Bypass

当遇到大数据量的 Sequential Scan 时，如果将所需的所有 Pages 顺序存入 Buffer Pool，将会污染 Buffer Pool。因为这些 Pages 通常只使用一次，而它们的进入将导致一些可能在未来更需要的 Pages 被移除。所以一些 DBMS 做了相应的优化，在这种查询出现时，为它单独分配一块局部内存，将其对 Buffer Pool 的影响隔离。

  • Direct Disk IO

大部分磁盘操作都是通过系统调用完成，通常操作系统会维护自身的数据缓存，这就导致一份数据分别在操作系统和 DMBS 中被缓存两次。所以大多数 DBMS（除了 Postgres）都会使用直接 IO (O_DIRECT) 来告诉操作系统不要缓存这些数据。

Frame 替换策略​

当 Buffer Pool 空间不足时，读入新的 Pages 必然需要 DBMS 从已经在 Buffer Pool 中的 Pages 选择一些移除，这个选择就由 Buffer Replacement Policies 负责完成。它的主要目标是：

  • Correctness：操作过程中要保证脏数据同步到 Disk
  • Accuracy：尽量选择不常用的 Pages 移除
  • Speed：决策要迅速，每次移除 Pages 都需要申请 Latch，使用太久将使得并发度下降
  • Meta-data overhead：决策所使用的元信息占用的量不能太大

缓冲池的分配策略决定了如何将缓冲池中的 Frame 分配给事务：

  • Global Policies（全局策略）：全局策略是指那些为所有活跃事务做出决策的策略。这种策略会考虑系统中所有事务的需求和行为，以实现资源的最优分配。实现起来可能更复杂，需要更多的计算和协调。
  • Local Policies（局部策略）：局部策略是指那些只为特定事务分配 Frame，而不考虑并发事务行为的策略。这种策略专注于单个事务的需求，可能会忽略其他事务的状态和需求。因为不需要考虑并发事务的影响，实现起来相对简单。

LRU​

对每个 Page 维护一个最新访问时间戳，当 DBMS 需要淘汰一个 Page 时，选择访问时间距离现在最远的那个 Page。

Clock​

Clock 算法是 LRU 的近似算法，它不需要每个 Page 维护一个时间戳，只需要为每个 Page 维护一个 bit。

Clock 算法会像时钟一样循环访问每个 Page。每个 Page 进入时，置为 1。在需要淘汰一个 Page 时，如果 1 被扫描到，置 0；如果再被扫描到，就被淘汰。

Sequential Flooding

指在数据库的缓冲池中，由于顺序扫描操作，一次性加载了大量可能只会被访问一次的 Page，这导致缓冲池被这些 Page “污染”。LRU 和 Clock 算法都会出现这样的问题。

（导致最近被访问的 Page 实际上却是最不可能需要的 Page）

LRU-K​

LRU-K 是一种改进的页面置换策略，它旨在解决传统 LRU 策略面对 Sequential Flooding 问题时的不足。LRU-K 跟踪 Page 过去 K 次访问的时间戳，意味着记录了 Page 访问历史的一个窗口。当 DBMS 尝试淘汰 Page 时，不仅要考虑时间戳的远近，还要考虑 Page 历史窗口的大小。

Localization​

  • 跟踪查询访问的页面：为了实现本地化策略，DBMS 需要跟踪每个查询访问了哪些 Page。
  • 按事务/查询选择淘汰的 Page：本地化策略允许 DBMS 在每个事务或查询的基础上决定哪些 Page 应该被置换出缓冲池。这样可以针对每个查询的具体需求来优化淘汰策略。
  • 最小化缓冲池污染：通过为每个查询定制 Page 置换策略，本地化策略有助于减少查询之间对缓冲池的相互影响，从而降低一个查询对缓冲池的“污染”。

Priority Hints​

在查询执行期间，DBMS 能够了解每个 Page 的上下文信息。基于对页面上下文的了解，可以帮助缓冲池更智能地决定哪些 Page 应该保留在内存中，哪些可以被置换出去。

如下图中，Q1 和 Q2 都会访问 Page 0，DBMS 可以识别将其标识为重要的页面，使其那么不易淘汰出去。

关于 Dirty Pages​

  • FAST 操作：如果 Page 不是脏的（即没有修改），数据库可以直接丢弃这个 Page，磁盘上的数据仍然是最新的
  • SLOW 操作：如果 Page 是脏的（即被修改过），在释放 Page 之前必须将其写回磁盘，以确保数据持久化。

现在大多数 DBMS 都会在空闲时后台扫描 Page Table，将 Dirty Page 定时写入磁盘，这样有助于 Page 被淘汰时减少磁盘写入延迟。Dirty Page 写入磁盘后，DBMS 可以直接选择淘汰该页面，也可选择保留不动，清除其 Dirty 标记。

其他的 Buffer Pool​

DBMS 不仅要维护磁盘的 Page 缓存，还需要维护其他的缓存，总之缓存在数据库中非常常见，需要根据具体的场景选择不同的淘汰策略和优化方法：

  • 排序和连接缓冲区（Sorting + Join Buffers）：用于支持排序和连接操作的临时内存。
  • 查询缓存（Query Caches）：用于存储查询结果或中间结果，加速后续相同查询的执行。
  • 维护缓冲区（Maintenance Buffers）：支持系统内部维护任务，例如统计信息的更新。
  • 日志缓冲区（Log Buffers）：暂存事务日志数据，确保写磁盘的性能和数据一致性。
  • 字典缓存（Dictionary Caches）：缓存元数据字典（如表定义或列属性）以减少重复读取的开销。