NOW的侧写

我已经学了（至少看完了）CMU15445的#01#02，了解了数据库所基于的关系模型和一些关于SQL的语法。然而#03这节课真正具体介绍了整门课程的框架。相当于给了我一个地图，我可以看到自己在其中的位置。然后我感觉本堂课介绍了数据在磁盘（disk）的存储逻辑和布局状况，包括FILE,PAGE,TUPLE三个层次。并且提出了一个重要的结论：应用于数据的算法和数据结构应当取决于数据存储的层次。当然对于这些层次，我的了解并不深入，事实上，我听说过他们，比如CPU register,CPU caches,内存，SSD之类的，但仅限名字和它们之间的整体关系。然而正如一句话所写的：真理隐藏在细节中。怀着这样对细节的留意，我开始写这篇文章。

COURSE OUTLINE

Relational Database：定义了数据是如何被逻辑地组织和看待的。核心思想是用二维表（称为“关系”）来组织数据，表中的行是记录（元组），列是属性。

• 相关知识点：
  • 关系模型 (Relational Model): 由 E.F. Codd 提出。包括关系、属性、元组、域、键（主键、外键、超键）等基本概念。
  • 关系代数 (Relational Algebra): 操作关系（表）的一套形式化查询语言，是 SQL 的理论基础。包括选择（Select, σ）、投影（Project, π）、并（Union, ∪）、差（Set Difference, -）、笛卡尔积（Cartesian Product, ×）、连接（Join, ⋈）等操作。理解关系代数有助于你理解查询优化器是如何工作的。
  • SQL (Structured Query Language): 声明式的、用户友好的关系数据库查询语言。你需要知道 DDL (Data Definition Language, e.g., CREATE TABLE), DML (Data Manipulation Language, e.g., INSERT, UPDATE, DELETE), DQL (Data Query Language, e.g., SELECT).
  • 数据库范式 (Normalization): 设计良好关系模式的理论指导，旨在减少数据冗余和避免更新异常。包括第一范式 (1NF)、第二范式 (2NF)、第三范式 (3NF)、BCNF 等。

Storage：它研究数据如何被物理地存放在硬件上（磁盘、内存），以及如何在这些硬件层次之间高效地移动数据。这是从“构建者视角”看数据库的起点。

• 相关知识点：
  • 存储层次结构 (Storage Hierarchy): CPU寄存器 -> L1/L2/L3 Cache -> 内存(DRAM) -> SSD/HDD -> 网络存储。理解不同层次的速度、容量、易失性差异是所有优化的前提。
  • 磁盘/文件管理 (Disk/File Manager): 负责管理磁盘上的文件和空间。
  • 缓冲池管理 (Buffer Pool Manager): 核心组件！在内存中开辟一块区域（Buffer Pool）来缓存从磁盘读上来的数据页（Page）。它负责处理读请求（如果在内存就直接返回，否则去磁盘读）、页面替换策略（LRU, Clock 等）、将“脏页”（被修改过的页）写回磁盘。
  • 页面布局 (Page Layout): Page 内部的组织结构，如页头、槽数组（Slot Array）、数据区等，用于高效地管理 Tuple。
  • 元组布局 (Tuple Layout): 单个 Tuple 如何序列化成字节，包括元数据（如 NULL 位图）、定长/变长字段的表示。

Query Execution：这个模块负责解析、优化并执行查询计划。

• 相关知识点：
  • 查询解析与优化 (Query Parsing & Optimization): 将 SQL 文本解析成语法树，然后查询优化器会生成多个等价的物理执行计划，并根据成本模型（Cost Model）选择一个最优的。例如，对于 Join 操作，是使用嵌套循环连接（Nested Loop Join）、哈希连接（Hash Join）还是排序归并连接（Sort-Merge Join）？
  • 执行模型 (Execution Models): 数据库如何执行这个计划？是火山模型/迭代器模型（Iterator Model，一次拉取一个元组），还是物化模型（Materialization Model，一次处理完一个操作符的所有输入），或者是向量化/批处理模型（Vectorized/Batch Model，一次处理一批元组）？
  • 访问方法 (Access Methods): 如何从表中获取数据？是全表扫描（Sequential Scan），还是通过索引扫描（Index Scan）？
  • 索引 (Indexing): 这是查询执行的加速器。核心数据结构是 B+树，它非常适合磁盘存储。还有哈希索引（Hash Index）、R树（用于地理空间数据）等。你需要理解它们的结构、操作（查找、插入、删除）以及适用场景。

Concurrency control：数据库通常被多个用户/应用同时访问。并发控制要解决的问题是：如何让多个事务（Transaction）同时运行，既能最大化系统吞吐量，又能保证数据的正确性，避免出现脏读、不可重复读、幻读等问题。

• 相关知识点：
  • 事务 (Transactions) 与 ACID 属性: 事务是逻辑上的一组操作，要么全做，要么全不做。ACID 是其四大特性：原子性 (Atomicity)、一致性 (Consistency)、隔离性 (Isolation)、持久性 (Durability)。
  • 隔离级别 (Isolation Levels): 定义了不同事务之间“看见”彼此修改的程度。从低到高包括读未提交、读已提交、可重复读、可串行化。
  • 并发控制协议 (Concurrency Control Protocols):
    • 基于锁 (Locking): 悲观并发控制。通过锁（共享锁 S、排他锁 X）来防止冲突。关键技术是 两阶段锁协议 (2PL)。还需要处理死锁 (Deadlock) 的检测与解除。
    • 基于时间戳/多版本 (Timestamp Ordering / MVCC): 乐观并发控制。系统为每个事务分配时间戳，或者为每个数据项维护多个版本。读操作读取合适的旧版本，写操作创建新版本。这是 PostgreSQL、Oracle 等现代数据库广泛采用的技术。

Database Recovery：如果系统突然崩溃（断电、软件Bug），如何保证已经提交的事务的修改不会丢失（Durability），同时保证未完成的事务的修改被撤销（Atomicity）？这就是恢复系统要解决的问题。

• 相关知识点：
  • 预写日志 (Write-Ahead Logging, WAL): 核心原则！在将数据修改写入数据页（Data Page）之前，必须先将描述该修改的日志记录（Log Record）写入到磁盘上的日志文件（Log File）中。这样即使崩溃，也可以通过重放日志来恢复。
  • 日志记录 (Log Records): 记录了对数据的修改，如 (事务ID, PageID, offset, old_value, new_value)。
  • ARIES 恢复算法: 一种工业界广泛使用的、非常经典的恢复算法。它包含三个阶段：分析（Analysis）、重做（Redo）、撤销（Undo）。
  • 检查点 (Checkpoints): 定期执行的操作，用于将内存中的脏页刷到磁盘，并减少恢复时需要扫描的日志量。

Distributed Database：当数据量或并发请求量超过单台机器的处理能力时，就需要将数据库扩展到多台机器上，构成一个集群。

• 相关知识点：
  • 数据分区/分片 (Partitioning/Sharding): 如何将数据拆分到不同的节点上？可以按范围（Range）分，也可以按哈希（Hash）分。
  • 分布式查询处理 (Distributed Query Processing): 一个查询可能需要访问多个节点上的数据，如何协调执行并合并结果？
  • 分布式事务 (Distributed Transactions): 跨多个节点的事务如何保证其原子性？经典的算法是两阶段提交 (Two-Phase Commit, 2PC)。
  • 复制与一致性 (Replication & Consistency): 为了高可用性，数据通常会有多个副本。如何保证副本之间数据的一致性？这里会涉及到 Paxos、Raft 等共识算法。

Potpourri：大杂烩，数据库安全 (Security)、流处理数据库 (Streaming Databases)、列式存储 (Columnar Storage)、内存数据库 (In-memory Databases)等等，用于开阔视野。

所有这些内容完全基于数据库的查询逻辑：

Application -> SQL -> [Query Parser -> Query Optimizer (生成 Query Plan)] -> [Query Executor (使用 Operator Execution 和 Access Methods)] -> Buffer Pool Manager -> Disk Manager

Disk-Based Architecture

The DBMS assues that the primary storage location of the database is on non-volatile disk.

The DBMS’s components manage the movement of data between non-volatible and volatible storage.

1. Disk-Based Architecture (基于磁盘的架构):
   • 含义: 这首先是一个定性。它告诉我们，这个数据库系统（DBMS）从设计之初，就不是为纯内存操作设计的。它的核心假设是，数据的主体、完整副本存放在磁盘上。
   • 为什么? 因为数据量通常远大于内存（RAM）的容量。内存是昂贵的、易失的（断电数据就丢失），而磁盘是廉价的、非易失的（持久化的）。为了能存储海量的、需要永久保存的数据，”基于磁盘”是唯一的选择。
2. “The DBMS assumes that the primary storage location of the database is on non-volatile disk.” (DBMS 假设数据库的主要存储位置是在非易失性磁盘上。)
   • 含义: 这句话是对第一点的具体化。它强调了数据库的“家”在哪里。无论内存里缓存了多少数据，无论计算多快，数据的“真相” (Ground Truth) 和“最终归宿” (Primary Storage) 都在磁盘上。
   • 引申出的设计约束:
     • 持久性 (Durability): 所有对数据的永久性修改，最终必须反映到磁盘上。
     • I/O 是性能瓶颈: 磁盘的读写速度比内存慢几个数量级（毫秒 vs 纳秒）。因此，最小化磁盘 I/O 次数 成为数据库系统设计的首要优化目标。整个系统里的大量复杂设计，如缓冲池、B+树索引、查询优化等，都是为了这个目标。
3. “The DBMS’s components manage the movement of data between non-volatile and volatile storage.” (DBMS 的组件负责管理数据在非易失性存储和易失性存储之间的移动。)
   • 含义: 这句话揭示了该架构下的核心工作内容。既然数据在磁盘上，而计算（处理数据）必须在内存中由 CPU 完成，那么必然存在一个持续的“数据搬运”过程。数据库系统的核心任务之一，就是做一个高效的“搬运工头”。
   • 非易失性存储 (Non-volatile): 主要指磁盘 (HDD, SSD)。
   • 易失性存储 (Volatile): 主要指内存 (DRAM)。

首先，数据库的储存建构是这样的：

• CPU 寄存器 (Registers) / 缓存 (Caches): 最快，最小，最贵。
• 主存 (Main Memory / DRAM): 很快，中等大小，较贵，易失。
• 固态硬盘 (SSD): 较快，较大，价格适中，非易失。
• 机械硬盘 (HDD): 慢，巨大，便宜，非易失。
• 网络/磁带存储 (Network/Tape): 最慢，用于备份和归档。

计算发生在顶端（内存），而存储发生在底端（磁盘）

SEQUENTIAL VS. RAMDOM ACCESS

Random access on non-volatible storage is almost always much slower than sequential access.

DBMS will want to maximize sequential access

->Algorithms try to reduce number of writes to random pages so that data is stored in contiguous blocks

->Allocating multiple pages at the same time is called an extent

“Random access on non-volatile storage is almost always much slower than sequential access.” (在非易失性存储上，随机访问几乎总是比顺序访问慢得多。)

对于机械硬盘 (HDD): 这个差异是巨大的。

• 随机访问 (Random Access): 比如要读取文件 A 的第 1 块，然后读取文件 B 的第 100 块。硬盘的磁头需要进行两次“移动(seek) + 旋转(rotate)”来定位到这两个物理位置。这个机械动作是主要的耗时部分，通常在毫秒（ms）级别。
• 顺序访问 (Sequential Access): 比如要连续读取文件 A 的第 1、2、3…100 块。磁头只需要进行一次定位，然后就可以在盘片旋转时连续不断地读取数据。一旦定位完成，数据传输率（throughput）是非常高的。

对于固态硬盘 (SSD): 虽然 SSD 没有机械部件，随机访问比 HDD 快得多，但这个法则依然成立。

• 原因: SSD 内部的闪存芯片被组织成 Page（不同于数据库的Page，这里指物理单位，如16KB）和 Block（由多个Page组成）。虽然它可以“随机”读取任何 Page，但读取连续的、位于同一个物理区域的 Page 依然比读取分散在不同芯片、不同 Block 的 Page 要高效。这涉及到更少的内部寻址开销和更优化的并行读取。

“DBMS will want to maximize sequential access.” (DBMS 会希望最大化顺序访问。)

• 这是什么？ 这是从上述物理事实中得出的首要设计原则。既然随机访问是性能杀手，那么数据库系统的所有设计都应该朝着一个共同的目标努力：将随机 I/O 转化为顺序 I/O。
• 如何实现？ 这句话引出了接下来的一系列设计决策和算法。数据库系统会在多个层面应用这个原则：
  • 数据写入时: 尽量将相关的数据写在一起。
  • 数据读取时: 设计出能够进行顺序扫描的算法和数据结构。
  • 数据修改时: 尽量避免产生大量“碎片化”的随机写入。

“Algorithms try to reduce number of writes to random pages so that data is stored in contiguous blocks.” (算法会尝试减少对随机页面的写入次数，以便数据能存储在连续的块中。)

• 全表扫描 (Sequential Scan): 这是最直接利用顺序访问的例子。当需要读取整张表时，数据库会从文件的第一个 Page 开始，一个接一个地顺序读取，直到文件末尾。这是最高效的 I/O 模式。
• 日志系统 (Write-Ahead Logging, WAL): 当多个事务并发执行时，它们可能会修改磁盘上不同位置的多个数据页（Page），这会导致大量的随机写。WAL 聪明地将这些修改操作首先顺序地追加 (append) 到一个单独的日志文件中。这个“追加”动作是纯粹的顺序写，非常快。然后，数据库可以在后台空闲时，再慢慢地将这些修改应用回磁盘上各自的数据页（这个过程称为 Checkpoint 或脏页刷盘）。WAL 用一次廉价的顺序写，换取了系统能够快速响应事务提交，并推迟了昂贵的随机写。
• B+ 树的叶子节点: B+ 树的叶子节点之间通过双向链表连接。这使得进行范围查询（例如 WHERE age BETWEEN 20 AND 30）变得极其高效。一旦通过索引定位到 age=20 的第一条记录，数据库就可以沿着叶子节点的链表顺序地向后扫描，直到 age > 30 为止。这个过程访问的 Page 在物理上可能是连续的，从而实现了高效的顺序读。

 “Allocating multiple pages at the same time is called an extent.” (一次性分配多个连续的页被称为一个“区”。)

一张表不断增长，每次需要新空间时，文件系统就在磁盘的某个“角落”找一个空闲的 Page 分配给你。久而久之，这张表的 Page 就会像“散落的拼图”一样，遍布在磁盘的各个角落。当咱对这张表进行全表扫描时，磁头就需要不停地在这些分散的 Page 之间来回跳跃，这实际上是大量的随机 I/O，性能会非常差。

为了避免这种情况，数据库在向操作系统申请空间时，不会说“请给我一个 Page”，而是会说“请给我 8 个连续的 Page”（或者 64 个，这个数量是可配置的）。这 8 个连续的 Page 组成一个 Extent (区)。当表需要增长时，数据库会优先在当前已分配的 Extent 的空闲 Page 中写入数据。当一个 Extent 用完后，它会再去申请下一个全新的、内部连续的 Extent。

总结一下：

1. 物理现实: 随机 I/O 很慢，顺序 I/O 很快。
2. 设计目标: 将随机 I/O 尽可能转化为顺序 I/O。
3. 实现策略:
   • 在算法层面: 设计偏好顺序读写的算法（如 WAL、B+树的范围扫描）。
   • 在空间管理层面: 使用 Extent (区) 来预分配连续的物理空间，保证数据存储的连续性，从而在读取时能够受益于顺序访问。

System Design Goals

Allow the DBMS to manage database that exceed the amout of memory available.

Reading /Writing to disk is expensive,so it must be managed carefully to avoid large stalls and performance degradation.

Random access on disk is usually much slower than sequential access,so the DBMS will want to maximize sequential access.

Allow the DBMS to manage databases that exceed the amount of memory available.” (允许 DBMS 管理超过可用内存大小的数据库。)

此部分的挑战在于规模。

这是设计基于磁盘的数据库的根本原因 。如果所有数据都能轻松放入内存，我们就可以使用更简单的内存数据库（In-Memory Database）架构。但现实世界的数据集（TB 甚至 PB 级别）远远超出了单机内存的容量。这就要求 DBMS 必须有一个机制，能够按需、智能地将数据从磁盘加载到内存进行处理，并在内存不足时，将一些数据“请”出内存，为新数据腾出空间。

为此，我们引入Buffer Pool Manager的概念。它在有限的内存中开辟一块缓存区（Buffer Pool），并负责整个数据在内存和磁盘之间的换入换出（swapping）逻辑。它的存在，使得上层的查询执行引擎可以“假装”所有数据都在内存中（通过请求 Buffer Pool Manager），而无需关心数据到底在磁盘的哪个位置。

“Reading/Writing to disk is expensive, so it must be managed carefully to avoid large stalls and performance degradation.” (读/写磁盘是昂贵的，因此必须小心地管理，以避免大的停顿和性能下降。)

强调了磁盘的性能瓶颈。这个目标要求 DBMS 必须尽可能地隐藏 I/O 延迟，让系统看起来运转流畅。

通过将频繁访问的数据页保留在内存中，可以极大地减少实际发生的 I/O 次数。Buffer Pool 的命中率 (Hit Rate) 是衡量其“管理”得有多“小心”的关键指标。如果 DBMS 预测到接下来可能会需要某些数据页（例如，在进行全表扫描时），它可以异步地、提前地将这些页从磁盘加载到内存。这样，当查询真正需要它们时，它们已经在内存中等待了，从而避免了同步等待的“停顿”。

对于写操作，DBMS 不会立即将修改后的“脏页”同步写回磁盘。而是将它们标记为“脏”，然后由一个或多个后台线程在系统不那么繁忙的时候，或者在内存紧张需要腾出空间时，再将它们批量刷回磁盘。这就是 Buffer Pool Manager 中“脏页刷盘”的逻辑。

很明确，我们的任务就是：在数据库容量大于内存的时候设计两者之间的关系，减少磁盘的读取数量，增加顺序读取的比例。在中间我们使用了buffer pool作为工具。

后面的话

本次文章的书写体验比较糟糕，我准备写一篇两周总结来谈谈这一阶段的学习。不管怎样，学习还要继续。