幻灯片和笔记，其他同学整理的笔记，Discord 讨论，dbdb.io。

本来想做个课程总结和项目总结的，但是有点没心情做，排行榜优化也暂时搁置吧。:(

更新：还是做一下总结，课程的内容不只下面这些，有很多内容对我来说可能用不到，所以没有记录。

Advanced SQL

查询满足某个条件的记录数量：

1
2

SELECT COUNT(*) FROM t WHERE xx;
SELECT SUM(IF(xx, 1, 0)) FROM t;

查询满足某个条件的记录百分率：

1

SELECT ROUND(AVG(IFNULL(xx, 0)), 2) FROM t;

窗口函数（文档：12.20 Window Functions）：

1
2

SELECT ROW_NUMBER() OVER(PARTITION BY xx ORDER BY xx) FROM t;
SELECT AVG(xx) OVER (PARTITION BY xx ORDER BY xx ROWS BETWEEN 1 PRECEDING AND 1 FOLLOWING)

日期和时间函数（文档：12.7 Date and Time Functions）：

1
2

SELECT DATE_FORMAT(xx, xx);
SELECT DATEDIFF(xx, xx);

Database Storage

课程主要介绍面向磁盘的 DBMS，数据库以文件的形式存储在磁盘上，文件以特定于 DBMS 的方式编码，它被表示为页面的集合，每个页面都会有一个唯一标识符（页面 ID），大多数 DBMS 使用哈希表将页面 ID 映射为文件路径和文件内的偏移量。注意区分硬件页面（通常为 4 KB）、操作系统页面（4 KB）和数据库页面（1-16 KB）。存储设备可以保证硬件页面的原子写入，如果数据库页面大于硬件页面，则 DBMS 需要采取额外的措施来保证原子性。

每个页面被分为两部分：页面头部和页面内容。页面头部用于记录有关页面内容的元数据，包括页面大小、校验和、DBMS 版本、事务可见性和自包含（Self-containment）等。页面内容有两种主要的数据布局方式：slotted-pages 和 log-structured。

Storage Models & Compression

三种工作负载：OLTP（在线事务处理），OLAP（在线分析处理），HTAP（混合事务和分析处理）。

两种存储模型：行式存储和列式存储。

Memory Management

缓冲池实际上是一个页面数组，用于缓存磁盘中的页面，为了区分缓冲池页面和磁盘页面，我们将缓冲池页面称为帧（frame）。当 DBMS 请求一个页面时，存储管理器会首先搜索缓冲池，如果页面不在缓冲池中，就将该页面从磁盘复制到空闲的帧中。（有关缓冲池的详细信息可以参考 Project #1）

缓冲池优化方式：

• 多缓冲池：可以为不同数据库或不同页面类型提供不同的缓冲池，这样可以根据其中的数据定制优化策略。
• 预取：可以根据查询计划预取页面，通常在顺序访问页面时进行该优化。
• 扫描共享（同步扫描）：当多个查询扫描的数据存储重叠时，重叠部分可以只进行一次扫描。
• 缓冲池绕过：顺序扫描或临时数据处理不会将页面存储在缓冲池中，而是为其单独开一块内存，以避免缓冲池污染，因为这些页面通常不会再被访问。

大部分数据库使用直接 I/O 绕过操作系统缓存，以避免多余的页面缓存（Postgres 除外）。

Hash Tables

哈希表的实现由两部分组成：

• 哈希函数：需要在计算速度和冲突率之间进行权衡。
• 哈希模式：发生冲突时如何处理。（静态哈希和动态哈希）

Trees Indexes

索引的数量越多，查询的速度就越快，但是索引占用的存储空间以及维护成本也会随之提高。

B+ 树是一种平衡查找树，它保持数据有序，并且支持 \(O(\log{n})\) 的查询、插入和删除操作。B+ 树平衡的关键在于，它要求所有节点都至少是半满的。B 树在所有节点中存储值，而 B+ 树只在叶子节点中存储值。B+ 树相比哈希表的优势在于可以进行范围查询以及模糊查询。（有关 B+ 树的详细信息可以参考 Project #2）

Index Concurrency Control

区分 Lock 和 Latch：

• Lock：高级原语，作用是保护数据库的内容（元组、表和数据库），在事务中使用。
• Latch：低级原语，作用是保护数据库的内部数据结构，在临界区中使用。

实现 Latch 的底层原语是比较并交换（CAS）原子指令。有多种不同类型的 Latch 可供 DBMS 使用：

• Blocking OS Mutex：使用操作系统内置的互斥锁基础设施，Linux 提供 futex（fast user-space mutex），它由用户空间的自旋锁和操作系统级别的互斥锁组成。示例 std::mutex，优点是使用简单，缺点是加锁/解锁的时间成本较高并且不可扩展（如果发生竞争，则当前线程会被操作系统阻塞）。
• Test-and-Set Spin Latch（TAS）：自旋锁具有更高的灵活性，DBMS 可以控制当存在竞争时应该执行什么操作。示例 std::atomic<T>，优点是加锁/解锁更快，缺点是在竞争比较激烈时，会浪费很多 CPU 资源。
• Reader-Writer Latches：示例 std::shared_mutex，优点是可以并发读取，缺点是需要额外的空间存储读/写队列。

B+ 树使用蟹行协议（Latch Crabbing Protocol）来保证自上而下的加锁顺序，当线程的访问模式不包含叶节点扫描时，该实现方式可以避免死锁。因为索引锁不支持死锁检测或避免（疑问：这里的描述和幻灯片第 23 页的内容不太一样），所以叶节点扫描在获取同级锁时遵循无等待模式，即如果获取同级锁失败就立即重启操作。

Sorting & Aggregations Algorithms

排序可能被用在 ORDER BY、GROUP BY、JOIN 和 DISTINCT 操作中。如果数据能够放入内存，则可以使用快速排序（当查询包含 LIMIT 和 ORDER BY 时，可以使用堆排序），否则使用外部归并排序。

外部归并排序由两部分组成：

• 排序：将数据分为多个可以放入内存的数据块，分别进行排序，然后将排序后的数据写回磁盘。
• 合并：将排序后的数据块合并。

外部归并排序的 I/O 成本分析：

• 假设 \(N\) 为数据页面的个数，\(B\) 为可以使用的缓冲区页面的个数。
• 在排序阶段，每次可以读取 \(B\) 个数据页面到缓冲区，进行排序之后写回磁盘，总共执行 \(\lceil \frac{N}{B}\rceil\) 次排序，I/O 成本为 \(2N\)（读入缓冲区和写回磁盘各一次）。
• 在合并阶段，可以使用 \(B-1\) 个缓冲区页面存储 \(B-1\) 个数据块的第一个页面，剩下一个缓冲区页面存储合并的结果并根据需要写回磁盘，如果将合并的过程看作多叉树，则树的高度为 \(\lceil\log_{B-1}{\lceil \frac{N}{B}\rceil}\rceil\)，每层合并都会将所有数据读写一次，I/O 成本为 \(2N\times\lceil\log_{B-1}{\lceil \frac{N}{B}\rceil}\rceil\)。
• 最后，总 I/O 成本为 \(2N\times(1+\lceil\log_{B-1}{\lceil \frac{N}{B}\rceil}\rceil)\)。

外部归并排序可以使用双缓冲区优化，前台缓冲区进行计算的同时，后台缓冲区预取数据。如果数据在排序键上存在 B+ 树聚集索引，那么可以直接遍历索引得到有序数据。因为，如果是聚集索引，数据访问将是顺序 I/O，成本为 \(N\)；如果是非聚集索引，数据访问将是随机 I/O，成本为 \(N\times M\)，其中 \(M\) 为每页中的记录个数（缓冲区大小有限，随机 I/O 会导致页面抖动）。

聚合操作有两种实现方式：

• 排序：首先将数据按照聚合键进行排序，然后对有序数据执行顺序扫描来计算聚合值。
• 哈希：除非数据已经有序，否则哈希总是比排序更高效。由于内存可能容纳不下整个哈希表，为了避免随机 I/O，肯定不能将哈希表直接溢出到磁盘。我们可以首先进行一次哈希，将数据分区，然后对每个分区单独进行聚合操作，这样每个分区的哈希表大小应该会足够小，最好情况是能放入内存中。

Joins Algorithms

连接操作有两种输出模式：

• 提前物化（early materialization）：将外表和内表的所有属性都放入临时表。
• 延迟物化（late materialization）：只将连接键以及外表和内表的记录 ID 放入临时表。

连接算法的 I/O 成本分析（假设连接是等值连接）：

• 假设外表 \(R\) 有 \(M\) 页，总共包含 \(m\) 个元组；内表 \(S\) 有 \(N\) 页，总共包含 \(n\) 个元组。
• Nested Loop Join：
  • 该算法由两个嵌套的 for 循环组成，外层循环遍历外表，内层循环遍历内表，如果两个元组满足连接谓词，则将它们连接并输出。注意，我们总是应该使用较小的表作为外表，因为。
  • Naive Nested Loop Join：对于外表的每个元组，将其和内表中的每个元组进行比较，I/O 成本为 \(M+(m\times N)\)。
  • Block Nested Loop Join：对于外表的每个块，将其和内表中的每个元组进行比较。假设有 \(B\) 个可用的缓冲区，该算法可以使用 \(B-2\) 个缓冲区扫描外表，\(1\) 个缓冲区扫描内表，\(1\) 个缓冲区存储连接结果，I/O 成本为 \(M+(\lceil \frac{M}{B-2}\rceil\times N)\)。
  • Index Nested Loop Join：如果内表在连接键上建有索引（或者临时建立索引），那么可以直接使用索引搜索到满足条件的元组，I/O 成本为 \(M+(m\times C)\)，其中 \(C\) 为单次索引搜索的成本。
• Sort-Merge Join：
  • 首先对外表和内表进行排序，然后使用双指针分别遍历外表和内表，来进行连接谓词判断。如果内表的连接键有重复值，那么内表指针在匹配时可能需要回退。当外表或内表已经有序，或者输出结果要求按照连接键排序时，可以选择使用该算法。
  • 排序成本：外表为 \(2M\times(1+\lceil\log_{B-1}{\lceil \frac{M}{B}\rceil}\rceil)\)，内表为 \(2N\times(1+\lceil\log_{B-1}{\lceil \frac{N}{B}\rceil}\rceil)\)。
  • 合并成本：最坏情况下，两个表中的所有元组的连接键都相等，合并的成本为 \(MN\)。一般情况下，连接键大多是唯一的，合并成本为 \(M+N\)。
• Hash Join：
  • Basic Hash Join：首先将外表的连接键作为 key 构建哈希表，将外表的元组或者元组 ID 作为 value。然后对于内表中的每个元组，可以直接通过哈希表获取匹配的元组。由于可能存在哈希冲突，即使元组被哈希到某个桶，在桶内肯定还需要进行比较来判断元组是否真的匹配，这里我们可以额外使用布隆过滤器来过滤元组，以减少磁盘 I/O。
  • Grace Hash Join / Partitioned Hash Join：当哈希表无法放入内存时，Basic Hash Join 存在页面抖动问题，解决该问题的方法是进行分区。首先分别对外表和内表构建哈希表，并根据需要写入磁盘，如果单个桶都无法放入内存，则递归的进行分区（前提是桶内的键存在不同，否则会导致无限递归），I/O 成本为 \(2\times(M+N)\)。然后将外表和内表对应的桶进行嵌套循环连接，此时页面都可以放入内存，I/O 成本为 \(M+N\)。

假设 \(M=10^{3}\)，\(m=10^{5}\)，\(N=5\times 10^{2}\)，\(n=4\times 10^{4}\)，\(B=100\)，每页的 I/O 花费 \(0.1\) 毫秒，各个算法花费的时间如下：

该表是课程笔记上的，但是有点疑问，Block Nested Loop Join 的 I/O 成本计算公式有问题吧，如果按照之前说的公式计算，I/O 花费的时间是 \(0.65\) 秒。

Query Execution

DBMS 将 SQL 语句转化为查询计划，查询计划由操作符构成的树表示，数据从叶子节点流向根节点，根节点的输出就是查询的结果。处理模型（processing model）定义系统如何执行查询计划，下面介绍三种处理模型：

• 迭代器模型/火山模型（Iterator Model）：每个操作符都会实现 Next 函数，该函数由其父节点调用，以获取子节点的输出元组。因为每次调用只会返回单个元组，所以 Next 函数的调用一般放在循环中。调用从根节点传递到叶子节点，数据从叶子节点通过层层处理返回至根节点（实际上就是一个递归的过程，有点像树的后序遍历）。该模型允许以流水线的方式处理元组，有些操作符需要其子节点传递所有元组才能进行计算，包括哈希连接、子查询和排序等，这些操作符被称为流水线破坏者（pipeline breakers）。
• 物化模型（Materialization Model）：每个操作符都会实现 Output 函数，该函数会返回所有元组。该模型相比迭代器模型可以减少函数的调用次数，适合 OLTP 工作负载，因为其单词查询访问的数据量不大，而 OLAP 工作负载会查询大量数据，操作符的返回结果将会溢出到磁盘，从而增加 I/O 成本。
• 向量模型（Vectorization Model）：类似迭代器模型，区别在于每次调用 Next 会返回一批元组（即向量）。该模型适合访问大量数据的 OLAP 工作负载，相比迭代器模型，它可以减少函数调用的次数，还可以允许使用 SIMD 指令成批的处理元组。

PS：这些模型实际上是很简单的东西，无非就是返回的数据量不同，写这么多是不是有点浪费笔墨，额。这让我想起之前的一个感想，有些术语看上去很难懂，但是它们的本质其实非常简单，所以有些东西真的是增加学习难度。如无必要，勿增实体，不知道放在这合不合适。

Query Planning & Optimization

应用程序连接到数据库并发送 SQL 查询，该查询可以被重写为不同的形式，然后查询被解析为抽象语法树，绑定器通过查看系统目录，将语法树中的命名对象替换为内部标识，并生成逻辑计划，该逻辑计划同样可以被重写，之后优化器使用成本模型进行估计，将逻辑计划转化为物理计划。

逻辑计划和物理计划的区别：逻辑计划只描述了抽象的关系代数表达式，物理计划将抽象的表达式对应到某个具体实现，例如连接运算符有多种不同实现。逻辑计划和物理计划并不总是一一对应的。

查询优化有启发式优化（heuristics）和基于成本的搜索（cost-based search）两种策略：

• 启发式方法将查询的各个部分与已知的模式进行匹配，以将其转换为更有效的模式。
• 基于成本的搜索枚举等价的查询计划，然后选择成本最低的那个。

基于成本的搜索，如何估计谓词的选择性（就是谓词选择的数据占总数据的比率）：

• 关系 \(R\) 中的元组数量 \(N_{R}\)，属性 \(A\) 的不同值的数量 \(V(A,R)\)。使用这两个信息就可以计算出每个属性值的平均记录数 \(\frac{N_{R}}{V(A,R)}\)，称作选择基数（selection cardinality）。DBMS 可以根据选择基数估计谓词的选择性。
• 由于数据并不是均匀分布的，各个谓词之间也不是相互独立的，所以通过选择基数估计谓词的选择性偏差较大。DBMS 还可以维护等宽/等深直方图，或者对原表进行抽样得到类似原表分布的副本表，然后通过遍历副本表来计算选择性。

Concurrency Control Theory

关键问题：如何避免竞态条件（race condition），以及实现崩溃恢复。

事务的 ACID 原则：

• 原子性：事务中的操作要么全部执行，要么都不执行。有两种实现方式：日志（主流实现），写时复制。
• 一致性：数据在逻辑上是正确的，遵循完整性约束。
• 隔离性：并发执行的事务相互隔离，就像在串行执行一样，通过使用并发控制协议（concurrency control protocol）实现。并发事务之间存在三种冲突：读写冲突（不可重复读），写读冲突（脏读），写写冲突（丢失修改）。
• 持久性：已提交的事务所做的修改将会持久化到磁盘上。

Two-Phase Locking Concurrency Control

两阶段锁（2PL）是一种悲观的并发控制协议，将事务执行过程分为两个阶段：加锁阶段（Growing）和解锁阶段（Shrinking）。两阶段锁存在脏读和死锁等问题，它有多个变体：

• Conservative Two-Phase Locking（C2PL）：在事务开始时获取需要的所有锁，此协议可以避免死锁。
• Strict Two-Phase Locking（S2PL）：事务结束时释放写锁，读锁可以在解锁阶段逐步释放，此协议可以避免脏读。
• Strong Strict Two-Phase Locking（SS2PL）：事务结束时释放读/写锁，此协议在 S2PL 的基础上保证了事务的提交顺序（Commitment Ordering，CO）。

死锁是事务之间发生循环等待的现象，2PL 中有两种处理死锁的方法：

• 死锁检测：DBMS 定期构建等待图，如果图中存在环，则通过中止环中的某个事务，来打破循环。
• 死锁预防：当一个事务试图获取另一个事务持有的锁时，DBMS 会中止两个事务中的某个事务，从而避免死锁。

锁兼容矩阵图：

锁升级矩阵图：

存在的异常：脏读、不可重复读和幻读。隔离级别：读未提交、读已提交、可重复读和可串行化。（基于 2PL 实现的隔离级别、死锁检测可以参考 Project #4）

Timestamp Ordering Concurrency Control

Timestamp Ordering（T/O）和 Optimistic Concurrency Control（OCC） 都是乐观的并发控制协议，这些协议假设事务之间很少发生冲突，并且使用时间戳而不是锁来控制事务的执行顺序。

Basic Timestamp Ordering（BASIC T/O）：每个事务都会被分配唯一的时间戳，每个数据库对象都会记录最后一次被读/写的时间戳。每当事务读/写数据库对象时，都会将事务时间戳和对象时间戳做比较，以此确定操作是否能够执行。事务还需要保留对象的本地副本，以确保可重复读。

Optimistic Concurrency Control（OCC）：该协议将数据库对象复制到本地进行更改（写时复制），当事务想要提交时，进行冲突检测（比较事务的时间戳），如果通过则将事务的本地更改应用到数据库。

PS：这节课有点没太明白，特别是 OCC 的验证阶段看不懂。

Multi-Version Concurrency Control

多版本并发控制（MVCC）：DBMS 维护数据库中单个逻辑对象的多个物理版本，当事务开始时，DBMS 会创建数据库快照（通过复制事务状态表），然后根据快照来确定事务可见的对象版本。

MCC 有四个重要的设计决策：使用什么并发控制协议（2PL、T/O、OCC），多版本的存储方式，垃圾收集（回收对所有事务都不可见的版本），索引管理（辅助索引存储对象的逻辑指针还是物理指针，主键索引总是存储对象的物理指针）。

Database Logging

崩溃恢复算法的两个关键原语：

• UNDO：回滚不完整的更改。
• REDO：如果已提交事务的更改没有写入磁盘，则重做这些更改。

两个崩溃恢复算法：

• 写时复制：字面意思。该算法的 UNDO 操作就是删除所有页面副本，没有 REDO 操作，因为事务提交的同时会原子的修改数据库根节点的指针，即已提交的事务必定会将更改落实到数据库中。
• 预写日志（Write-Ahead Logging，WAL）：日志首先存放在日志缓冲区中，DBMS 必须先将日志写入磁盘（顺序 I/O），然后才能将脏页写入磁盘（不需要立即执行，可以使用后台线程进行写入操作）。只有当日志写入磁盘，事务才能被视为已提交。DBMS 可以通过批量提交事务，来避免频繁的日志 I/O 操作。每个日志记录都包含：事务 ID，对象 ID，之前的值（用于 UNDO），之后的值（用于 REDO）。（这里应该是指物理日志）

日志的模式（Logging Schemes）：

• 物理日志（Physical Logging）：记录数据的字节级更改。
• 逻辑日志（Logical Logging）：记录 INSERT、DELETE 和 UPDATE 语句。
• 混合日志（Physiological Logging）：混合方法，以逻辑地址（页面中的槽号）的方式记录物理日志。

Database Recovery

Algorithms for Recovery and Isolation Exploiting Semantics（ARIES） 是由 IBM 在 1990 年代开发出的恢复算法，该算法包含三个关键概念：

• Write Ahead Logging：先将日志写入磁盘，才能将脏页写入磁盘。
• Repeating History During Redo：数据库重启时，重做日志将数据库恢复到崩溃之前的状态。
• Logging Changes During Undo：将回滚操作记录到日志中，以确保再次崩溃时不会重复回滚。

该算法为每个日志记录分配全局唯一的日志序列号（log sequence number，LSN），系统中的各个组件会跟踪与其相关的 LSN。每个数据页面会包含最近一次更新对应的 LSN（\(pageLSN\)），缓冲池会包含已经刷到磁盘的最大 LSN（\(flushedLSN\)），DBMS 在将第 \(i\) 页刷新到磁盘之前，必须保证 \(pageLSN_{i}\leq flushedLSN\)，即预写日志。

• 事务提交：DBMS 首先将 COMMIT 日志记录写入日志缓冲区，然后将日志刷新到磁盘（顺序 I/O）。当日志已经成功刷新到磁盘之后，DBMS 就会向应用程序返回事务提交成功的信息。在之后的某个时刻，DBMS 将 TXN-END 日志记录写入日志缓冲区，表明该事务已经完成。（额，课程中没有说明在这段时间内，事务会执行什么操作）
• 事务中止：每个日志记录会包含 \(prevLSN\) 字段，表示该 LSN 在事务中对应的上一个 LSN 是多少。DBMS 使用 \(prevLSN\) 维护事务的日志链表，以方便进行 UNDO 操作。这里引入一个新类型的日志 compensation log record（CLR），表示所执行的 UNDO 操作，该类型的日志不会被 UNDO。事务中止时，DBMS 首先将 ABORT 日志记录写入日志缓冲区，然后根据 ABORT 日志的 \(prevLSN\) 回滚事务的更新，当回滚完成时 DBMS 将 TXN-END 日志记录写入日志缓冲区。

为了避免数据库崩溃之后重做整个日志，DBMS 会定期设置检查点（Checkpoint，其实就是存档），在设置检查点时会将缓冲池中的所有脏页都刷新到磁盘中，Checkpoint 有下面几种实现方式：

• Blocking Checkpoints：首先停止开始新事物，等待活动事务完成，然后将日志和脏页刷新到磁盘，最后将 CHECKPOINT 日志记录写入缓冲区并刷新到磁盘。之所以要停止并等待事务，是为了避免丢失更新。
• Slightly Better Blocking Checkpoints：在开始设置检查点时，会记录内部系统的状态，从而不必等待活动事务完成，取而代之的是暂停活动事务。内部系统状态包括：Active Transaction Table（ATT）和 Dirty Page Table（DPT）。
• Fuzzy Checkpoints：通过使用额外的日志记录（CHECKPOINT-BEGIN 和 CHECKPOINT-END）跟踪检查点的边界，从而不需要暂停活动事务。

ARIES 算法在 DBMS 崩溃重启之后执行，分为三个阶段：

• 分析（Analysis）：从 \(MasterRecord\) 对应检查点开始扫描日志，以构建 ATT 和 DPT，它们包含崩溃时缓冲池中存在的脏页以及活动的事务信息。
• 重做（Redo）：从 DPT 的所有脏页中最小的 \(recLSN\) 开始重做，即所有脏页中最旧的修改日志记录。
• 回滚（Undo）：从崩溃时所有活动事务中最旧的日志记录开始，撤销崩溃时活动事务所做的修改。

Introduction to Distributed Databases

并行数据库和分布式数据库的区别：

DBMS 的系统架构指定 CPU 可以访问哪些共享资源，有如下四种架构方式：

一致性哈希：

• 优势：假设有 \(n\) 个键，\(m\) 个节点，则一致性哈希平均只需要对 \(\frac{n}{m}\) 个键进行再散列。
• 原理：使用哈希函数将键和节点映射到圆上，每个键都会被分配给在顺时针方向上的下一个节点。每当添加一个节点时，只需要对其顺时针方向的下一个节点上的键进行再散列；每当删除一个节点时，只需要将当前节点的键移动到顺时针方向的下一个节点。（相当于多个节点将圆划分为多个圆弧，每个节点只包含映射到对应圆弧上的键）

Distributed OLTP Database Systems

如果某个事务需要访问多个节点上的数据（由于数据分区），则其是分布式事务。提交分布式事务时，根据协议的不同，可能需要得到所有或大多数节点的同意。原子提交协议（Atomic Commit Protocols）有：Two-Phase Commit，Three-Phase Commit，Paxos，Raft，ZAB，Viewstamped Replication。如果节点不可信，则需要使用拜占庭容错（byzantine fault tolerant）协议。

PS：虽然该课程将以上算法统称为原子提交协议，但是 2PC/3PC 和其他共识算法有一个显著的区别，就是 2PC/3PC 通常用于分布式事务，而其他共识算法通常用于数据复制。前者涉及多个节点上的不同数据，且协调器存在单点故障。后者涉及多个节点上的相同数据，且基于多数原则，不存在单点故障。可以将 2PC/3PC 和其他共识算法结合使用，从而消除单点故障（例如 Spanner 分布式数据库所做的）。

CAP 定理（Consistency，Availability，Partition tolerance）：指在发生网络分区故障时，要么选择一致性（指的是可线性化），要么选择可用性（允许读写网络分区节点）。

项目准备

项目地址：Project #4 - Concurrency Control。

准备工作：阅读 Chapter 18 19，学习 Lecture #15 #16 #17 #18 #19 #20，以及阅读课堂笔记。

项目结构

项目的注释中有锁升级的矩阵图，但是没有兼容性的矩阵图，这里贴一下。

Task #1 - Lock Manager

实现

① 比较关键的一个问题是，LockRequestQueue 里面存什么。我之前漏掉 granted_ 成员，导致整个项目理解都有问题。一个请求会经历未获取锁、已获取锁，已释放锁三个过程，LockRequestQueue 存储所有没有被释放的锁请求，即前两个过程。因为之后能否获取锁，需要和之前已经获取的锁做兼容性判断。

② 加锁阶段：

• 代码组织：我们可以根据请求的锁模式来分类讨论，也可以根据事务的锁模式来分类讨论，也可以根据事务是否有锁进行分类讨论。我最后是选择最后一种方式，这样写起来真的简洁。如果当前事务没有该资源的锁，则将请求入队，并且根据该资源是否被其他事务上锁，从而直接拿锁或者进行等待；否则，判断能否进行锁升级。
• 锁升级：
  • 根据提示，首先判断请求的锁模式是否和事务的锁模式是否相同，如果相同则直接返回 true。我在这里有个比较疑惑的点，如果请求锁模式的级别低于当前持有的锁模式，应该也可以直接返回 true，但是注释中并没有提及，并且线上测试结果告诉我不行，必须抛出异常。似乎是设计的问题，讨论在此，而且这个讨论似乎说的也不完整。
  • 然后判断是否可以锁升级，如果可以，我们需要释放之前的锁，并等待获取升级的锁。这两个步骤可以通过修改队列中的 LockRequest 实现，将锁模式修改为新的锁模式，将 granted_ 修改为 false，然后 cv_.wait() 即可。关键是条件变量的获取锁的条件如何编写。注意，一定要在等待之前从当前事务的锁集中移除原来的锁，因为线上测试会在等待时检查锁集。
• 获取锁：如何以 FIFO 的方式获取锁，并且使兼容的锁可以同时获取，以及使锁升级的优先级最高。遍历请求队列，如果当前事务是锁升级请求，则只需判断当前请求是否和已 granted_ 的请求兼容。如果当前事务不是锁升级请求，并且存在其他事务的锁升级请求，则直接返回 false，否则不仅需要判断当前请求是否和已 granted_ 的请求兼容，还需要判断当前请求是否和在该请求之前的未 granted_ 的请求兼容。

③ 解锁阶段：按照注释模拟，需要注意从队列中移除完成的锁请求，并在最后执行 cv_.notify_all()。

④ 事务的 ABORTED 状态：如果事务被中止，那么应该取消该事务所做的操作，事务中止之后会自动调用 TransactionManager::Abort 函数来进行解锁和还原所有写操作。但是如果事务在等待锁的过程中被中止，那么就需要我们手动重置，因为 Abort 函数不会清除未获取锁的请求。步骤如下：在使用条件变量时，额外判断当前事务的状态是否是 ABORTED，如果是则直接退出等待，并从队列中移除该请求，如果是锁升级还要记得重置 upgrading_，最后调用 cv_.notify_all() 并返回 false。

补充

① 一个细节问题，在获取 map 中的 LockRequestQueue 时，我依赖 C++ 在使用 [] 访问会自动创建对象的特性，没有注意到 map 中存的是智能指针，这样默认是创建空指针，结果就会报各种奇怪的错误。

② 表解锁同样需要改变事务的状态，一开始我天真的以为只需要在行解锁的时候改变就行，因为我以为加表锁必定会加行锁，但是不是这样的，可以只加表锁（或许全表扫描就是只加表锁而不加行锁）。

③ 线上测试遇到神奇的错误，pthread_mutex_lock.c:94: _pthread_mutex_lock: Assertion ‘mutex->data.__owner == 0’ failed，而且不是每次测试都会发生。经过排查，发现又是自动补全的锅，导致重复执行 unlock() 操作，有关该错误的讨论在此。

④ 目前似乎不需要使用事务锁，单个事务加锁/解锁是单线程的。

Task #2 - Deadlock Detection

① 构建等待图，使用二重循环遍历 table_lock_map_ 和 row_lock_map_ 来向 waits_for_ 添加从 granted_ == false 请求到 granted_ == true 请求的边。其实这样单纯的加边是比较简单的，但是可能存在锁兼容的情况，这样构成的环是不会造成死锁的，导致误杀事务，不过测试能过就不改代码了。记得加锁。

② 因为可以存在很多环，如果检测顺序不一样，中止的事务可能完全不同，所以 NOTES 中要求我们从最小的事务开始做 DFS，按照从小到大的顺序遍历相邻节点，如果找到环，则中止环中最大的事务。如果事务被中止，则应该从图中删掉连接该事务的边，或者也可以打标记。有坑！！！HasCycle 应该包含什么代码，之前我是把最小事务编号作为参数传递，然后从该事务开始做 DFS 来检测环。但是线上 GraphTest 测试会调用 HasCycle，按照线上测试代码的逻辑，HashCycle 应该包含整个环检测代码，包括排序 waits_for_，排序 GetEdgeList 得到的边集，以及 DFS。特别注意，不要在 HashCycle 中调用 txn_manager_ 的任何方法，因为 GraphTest 测试根本就没创建事务！！！我是调试半天找不到错，才反应过来，非常无语。

③ 最后，从 HasCycle 返回时，删除中止事务的边，然后调用 TransactionManager::Abort 函数中止事务。在消除所有环之后清空 waits_for_。

Task #3 - Concurrent Query Execution

① 非常非常无语！！！就是我在 Task#1 中提到的，高级锁可以包含低级锁的需求，不应该抛出异常，结果测试不给过，Task#3 又需要我兼容这种情况，那么只能在 Executor 代码中特判了。

② 根据提示，should not acquire S/X table lock, grab IS/IX instead，只为表加 IS/IX 锁。

③ 细节问题：行加锁之后再判断行是否删除，这个错误找很长时间才发现；死锁检测在调用 Abort 函数之前，先将事务状态设置为 ABORTED，否则当前事务可能会在之后的解锁过程中被唤醒，触发 LOCK_ON_SHRINKING 异常；实现 Abort 函数时，将恢复阶段放在解锁阶段之前，不然可能会有并发问题。

Leaderboard Task (Optional)

① 初次提交。

测试结果

1
2
3
4
5
6
7
8
9
10
11
12
13

#!/bin/bash
make lock_manager_test -j$(nproc)
make deadlock_detection_test -j`nproc`
make txn_integration_test -j`nproc`
make -j`nproc` terrier-bench 
./test/lock_manager_test
./test/deadlock_detection_test
./test/txn_integration_test
./bin/bustub-terrier-bench --duration 30000
make format
make check-lint
make check-clang-tidy-p4
make submit-p4

项目小结

难点就在项目理解以及代码细节上，Task#1 和 Task#2 被队列和 HashCycle 的理解整晕了，然后要使代码能够在多线程情况下正常运行，一定要注意代码中逻辑的先后顺序！！！实现过程部分参考做个数据库：2022 CMU15-445 Project4 Concurrency Control，Task#1 的解释帮助很大。

项目准备

项目地址：Project #3 - Query Execution。

准备工作：阅读 Chapter 15 16 22，学习 Lecture #10 #11 #12 #13 #14，以及阅读课堂笔记。

项目结构

通过查看 sqllogictest.cpp，可以知道 SQL 语句的整个执行流程。首先调用 SQLLogicTestParser::Parse 将测试文件解析为多个测试记录，然后根据记录的类型分别处理。目前我们主要关注查询语句，只需查看 BustubInstance::ExecuteSqlTxn 函数的代码。如项目介绍描述的那样，代码分别执行 Binder,Planner,Optimize,ExecutionEngine。然后，本来想详细分析一下整个流程，但是由于时间原因，以及项目确实比较复杂，所以暂时搁置。

Task #1 - Access Method Executors

实现

① 遇到第一个问题，如何在 SeqScanExecutor 中遍历表，可以发现 exec_ctx 成员所属的类 ExecutorContext 中有一个 GetCatalog 方法，只要拿到 Catalog 就可以根据 plan_ 中的信息拿到 TableHeap 的迭代器 TableIterator。然后第二个问题就是如何存储迭代器，TableIterator 是不可复制的，我们可以使用 unique_ptr 来存储迭代器，并使用 make_unique 初始化。（注意，不能在构造函数初始化，一定要在 Init 函数中初始化，不然多次全表扫描会出问题！）

② 实现 Insert 时报错 “The executor will produce a single tuple of integer type as the output, indicating how many rows have been inserted into the table”，并且可以看到 Next 函数的注释中表示 “tuple The integer tuple indicating the number of rows inserted into the table”。说实话有点难以理解，我一开始以为每次调用 Next 会像迭代器模式一样，只执行一次插入，但是这样实现就会报上面的错误。然后通过查看 Discord 的讨论，发现是一次性插入所有记录，因为只要返回 true 就会打印插入的行数，返回 false 就不会打印。当插入零行时，还必须打印一个零，这说明，Next 必定要先返回 true，再返回 false。并且在构造 tuple 时需要使用 BIGINT 类型，不然会报其他错误（明明注释说的是 INTEGER 额）。

③ 在 Insert 的同时需要更新索引，一开始我是直接用普通的 tuple 作为 InsertEntry 的参数，结果在测试 p3.05-index-scan.slt 时报 stack buffer overflow 错误。通过 Debug 发现，在 InsertEntry 时会调用 GenericKey 类的 SetFromKey 函数，该函数会将 tuple 的数据拷贝到该类的 data_ 成员中，作为索引的 key 使用。所以传入的 tuple 必须只包含 key，那么如何确定 tuple 中的哪个数据是 key 呢。可以发现 Tuple 类中有 KeyFromTuple 函数，它的会生成只包含 key 的 tuple，因为需要的索引的 key，那么该函数必定需要传入和索引相关的模式，以及 key 所在列的下标，这些信息可以在 IndexInfo 中找到。（之前我有点迷糊，当成 MySQL 默认使用主键索引了，BusTub 使用的是 TableHeap，也就是说表默认是没有索引的）

④ 实现时不要使用 GetTableOid 函数，因为线上测试的函数名是 TableOid，可能是因为我 fork 的版本太新了，仓库的代码和测试代码不一样，所以只能直接使用 table_oid_ 成员。

⑤ 实现 update 时要注意，在创建新 tuple 时，使用的是 child_executor_->GetOutputSchema()，而不是 GetOutputSchema()。

⑥ 实现 index_scan 时，会使用到 b_plus_tree_index.h 中定义的别名，如 BPlusTreeIndexIteratorForTwoIntegerColumn。

⑧ 在 IndexScan 的提示中有这么一句话，“do not emit tuples that are deleted”，但是当从表中删除 tuple 时，也会从索引中删除对应的 key，所以应该不会遍历到已经删除的 key 才对，也就是说此时应该不用特判 TupleMeta 中的 is_deleted_ 成员。

⑨ 测试 p3.06-empty-table.slt 时，遇到 B+Tree 迭代器实现问题。当 B+Tree 的为 empty 时，获取迭代器我原来是抛出异常，现在改为返回一个默认构造的迭代器。

补充

① 当没有显示声明复制/移动构造函数或复制/移动运算符，以及析构函数时，编译器才会隐式生成这些函数（其他更复杂的情况可以查看 cppreference.com）。

② 创建 TupleMeta 时，会将 insertion_txn 和 deletion_txn_ 都初始化为 INVALID_TXN_ID，提示表示这些成员会在以后切换到 MVCC 存储时使用，有点遗憾没能体验一下。

③ vector 的 reserve 只会影响 capacity 的大小，而不会影响 size，讨论在此。

④ 重载前置和后置 ++ 的区别，前置 ++ 的重载声明为 operator++()，后置 ++ 的重载声明为 operator++(int)。

⑤ 为什么应该将移动构造声明为 noexcept，可以阅读 Friendly reminder to mark your move constructors noexcept。

Task #2 - Aggregation & Join Executors

实现

① 一开始实现真摸不着头脑，AggregationPlanNode 里面怎么这么多东西。group_bys 是指 GROUP BY 时对列的求值表达式，aggregates 是指使用聚合函数时对列的求值表达式，agg_types 是指聚合函数的类型。例如：GROUP BY DAY(col)、MIN(col1 + col2)。我们使用 InsertCombine 函数向哈希表插入值，参数可以使用 MakeAggregateKey 和 MakeAggregateValue 函数获得。

② 根据项目介绍，AggregationExecutor::Next 返回的 tuple 应该包含 key 和 value（我没看到，找错好难）。特别需要注意，当哈希表为空时，应该返回什么：如果是对某列进行 GROUP BY 操作，那么就返回 false，因为有个测试用例有注释 no groups, no output；否则，返回 true，并且 tuple 存储聚合函数的默认值。（可以通过判断 key 模式的列数是否为零，或者 value 模式的列数是否等于 plan_ 输出模式的列数，来判断当前是否对某列进行 GROUP BY 操作）

③ 实现 NestedLoopJoinExecutor：外层循环遍历左表，内层循环遍历右表，只有当右表遍历完，才会获取下一个左表中的元组。但是，因为每找到一个匹配就会返回，所以我们应该将左表的元组作为数据成员，并且添加一个标志表示右表是否遍历完。每当右表遍历完成，都需要重置标志，获取左表中的下一个元组，并且重新 Init 右表。我们调用 EvaluateJoin 判断元组是否匹配，如果匹配，就将两个元组合并为一个元组。特别注意，如果当前是左连接，并且左元组没有匹配任何右元组，仍然需要返回一个为右元组填充 null 值的合并元组。比较迷惑的是怎么表示 null，我的想法是根据列类型获取对应的 null 值，但是找不到这样的函数，所以我就直接返回 BUSTUB_INT32_NULL 了。突然看到聚合执行器里用到 ValueFactory::GetNullValueByType 函数，太久没写项目给忘了。我还遇到一个 BUG，调试半天，发现我没有在 Init 函数中初始化 SeqScanExecutor 的迭代器，导致重复调用 Init 时不会重置迭代器。

④ 实现 HashJoin：根据提示我们可以参考 SimpleAggregationHashTable 的实现建立一个哈希表，我们创建一个 JoinKey 类作为键，然后创建一个 hash<bustub::JoinKey> 类，直接复制 aggregation_plan.h 中的代码改个名字就行（不然 C++ 真不熟，又要搞半天）。在哈希表中，将 vector<Tuple> 作为值以处理哈希冲突。搞定哈希的方式之后，我们可以像 aggregation_executor.h 一样添加两个辅助函数 MakeLeftJoinKey 和 MakeRightJoinKey。然后直接在 Init 中对左表建立哈希表，在 Next 中遍历右表，类似 NestedLoopJoinExecutor 的实现，只不过此时需要维护更多的数据成员。特别需要注意如何处理左连接，因为我们是将左表建为哈希表，那么在遍历完右表后，还需要处理没有任何匹配的左表中的元组。这可以在匹配时将元组的地址存储在 unordered_set 中，然后在遍历完右表后再遍历一次左表，并检查 unordered_set 来判断是否输出。（之前我是将元组的 RID 存储到集合中作为标识，但是这是错误的，因为左表可能是临时表，其中元组的 RID 是无效的内容；我们也可以为右表建立哈希表而不是左表，这样对于左连接来说，更好处理）

⑤ 实现 Optimizing NestedLoopJoin to HashJoin：非常的神奇，参考 nlj_as_index_join.cpp 瞎改，感觉代码是一坨，但是竟然没有任何错误，直接通过测试（激动半天）。具体实现的话，一开始我以为传入的参数就是 NestedLoopJoin 计划节点，但是似乎不是，所以我们需要遍历当前计划的子节点，递归的进行优化。之前比较令我迷惑的一点，怎么判断表达式是否是某个类型，我查找很久 API 都没有找到类似的函数，然后想到 Project #0 中好像是直接做 dynamic_cast 转换，如果返回值为 nullptr 就表示类型不匹配，查看 nlj_as_index_join.cpp 发现果然是这样。搞定表达式类型判断之后，就可以根据 ColumnValueExpression::GetTupleIdx 值来交换左右表达式，并返回转换后的节点。

Task #3 - Sort + Limit Executors and Top-N Optimization

Easy！只有两点需要注意：一个是每次调用 Init 时都要初始化所有数据成员，不然下次调用会包含上次调用的数据；第二个是 C++ 的 priority_queue 默认是大顶堆，并且比较器和 Java 中的用法完全相反。

Optional Leaderboard Tasks

① 初次提交。

② 之后优化。

测试结果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

#!/bin/bash
make sqllogictest -j$(nproc)

./bin/bustub-sqllogictest ../test/sql/p3.00-primer.slt --verbose
./bin/bustub-sqllogictest ../test/sql/p3.01-seqscan.slt --verbose
./bin/bustub-sqllogictest ../test/sql/p3.02-insert.slt --verbose
./bin/bustub-sqllogictest ../test/sql/p3.04-delete.slt --verbose
./bin/bustub-sqllogictest ../test/sql/p3.03-update.slt --verbose
./bin/bustub-sqllogictest ../test/sql/p3.05-index-scan.slt --verbose
./bin/bustub-sqllogictest ../test/sql/p3.06-empty-table.slt --verbose

./bin/bustub-sqllogictest ../test/sql/p3.07-simple-agg.slt --verbose
./bin/bustub-sqllogictest ../test/sql/p3.08-group-agg-1.slt --verbose
./bin/bustub-sqllogictest ../test/sql/p3.09-group-agg-2.slt --verbose
./bin/bustub-sqllogictest ../test/sql/p3.10-simple-join.slt --verbose
./bin/bustub-sqllogictest ../test/sql/p3.11-multi-way-join.slt --verbose
./bin/bustub-sqllogictest ../test/sql/p3.12-repeat-execute.slt --verbose
./bin/bustub-sqllogictest ../test/sql/p3.14-hash-join.slt --verbose
./bin/bustub-sqllogictest ../test/sql/p3.15-multi-way-hash-join.slt --verbose

./bin/bustub-sqllogictest ../test/sql/p3.16-sort-limit.slt --verbose
./bin/bustub-sqllogictest ../test/sql/p3.17-topn.slt --verbose

./bin/bustub-sqllogictest ../test/sql/p3.18-integration-1.slt --verbose
./bin/bustub-sqllogictest ../test/sql/p3.19-integration-2.slt --verbose

make format
make check-lint
make check-clang-tidy-p3
make submit-p3

项目小结

项目难度主要在项目理解上，常常是不理解某些变量的实际含义，或者知道该怎么做，却找不到对应的 API，或者对返回值理解有错误，而函数文档也不清晰。最后，看到实现的代码能够执行各种 SQL 语句，感觉还是很不错的。