任务  lab6 的任务是实现基于日志的回滚和恢复。任务要求如下： 对整个 page 做物理日志，读入时记录原始内容，用于回滚 基于 STEAL/NO-FORCE 将 page 写回磁盘前，先写日志 STEAL/NO-FORCE 指的是： 允许将未提交事务所作的修改落盘 事务提交时不强制马上落盘 允许 STEAL/NO-FORCE 如何实现事务的一致性呢？那就是使用预写日志，在将数据写入磁盘前，先写日志，只要日志落盘了，即使数据没有落盘，也可以通过日志恢复。 通过文档、注释和代码，我们可以知道我们要实现的日志格式大致如下图所示： 日志的开头是一个 int 类型的整数，标识 log 的类型，比如 begin、update、commit、abort等 BEGIN 后面是事务 ID，表示该事务开启了事务 COMMIT 后面也是事务 ID，表示事务提交了 ABORT 后面除了事务 ID 还有一个 BEGIN 的偏移量，方便快速找到该事务开始的地方 UPDATE 后面除了事务 ID，还记录了修改前和修改后的值，可以用于 redo 或者 undo CHECKPOINT 会记录 ...

任务  lab4 的任务时实现基于锁的事务。任务要求如下： 实现 page 粒度的锁，实现对锁的管理 使用 Strict two-phase locking 保证事务的 A 与 I； 使用 NO-STEAL/FORCE 策略管理 buffer pool，保证持久性。也就是说不能将未提交事务的修改刷回磁盘，同时提交事务提交时，其做出的修改必须强制刷盘。因此你需要实现 undo，因为事务提交时必须刷盘（lab6 会实现基于 log 的恢复策略） 首先我们要思考，如何使用 S2PL 实现事务的原子性与隔离性。 S2PL 要求事务在需要时获取锁，直到事务在提交时才全部释放。通过加锁，我们自然而然地可以实现一定的隔离性。那么能够实现那种级别的隔离呢？ 读未提交？我们能否读取到未提交事务做出的修改呢？答案是不能，因为数据加着锁呢 读已提交？事务提交后会释放所有的锁，所以我们只能读到事务提交后做出修改。 可重复读？那能不能做到可重复读呢？可以。因为我们使用的是 Strict 2PL，事务持有自己需要的锁，其他事务不能获取锁，所以数据根本不会被修改，所以可以实现可重复读 可串行化？可 ...

概述  随着多核 CPU 的发展，每个 CPU 中都有自己专用的缓存（比如 L1，L2）。当 CPU 处理数据时，会从共享缓存（比如 L3 缓存）中读取数据，然后在本地缓存中进行操作。如果 CPU 每次修改本地缓存的数据都将其写回下层缓存，并且在此期间，其他处理器并不会对该数据进行修改，那么这似乎并不会发生什么问题。但是，这样串行化执行必然会对性能造成影响。但是如果不串行化执行，一个处理器对一个过期的数据进行了操作，那就会造成数据不一致的问题，这就是著名的缓存一致性问题。 为了解决缓存一致性问题，人们提出了缓存一致性协议。实现缓存一致性协议的关键在于跟踪数据块的共享状态。目前的协议有两类： 目录式：存储器的共享状态保存在一个目录中，通过查看目录来跟踪数据块的状态 监听式：缓存拥存储器块中的数据副本，所有缓存通常都可以通过某种介质访问，所有缓存监视器都监听这个介质，以跟踪数据块的状态 本文介绍的式 MESI 协议，它属于监听式协议。监听式协议有两种实现方法： 写入失效：确保处理器在写入某一数据项之前，获取对该数据项的独占访问。因此进行读操作的处理器所保留的副本必须都失效，强制读取新 ...

在之前的文章中介绍到了 x86-64 下 C 语言函数的调用过程，最近又看到了一篇文章介绍 Go 语言的函数调用，于是便想了解下在不同语言中函数调用中参数传递的方式有什么不同。 C 通过之前的文章，我们知道在 x86-64 下，少于 6 个的参数是通过寄存器来传递的。一旦需要传递的参数大于 6 个，大于 6 个的部分会存储到栈中。下面看一下 csapp 中的一个例子 123456789void proc(long a1, long *a1p, int a2, int *a2p, short a3, short *a3p, char a4, char *a4p) { *a1p += a1; *a2p += a2; *a3p += a3; *a4p += a4;} 查看程序的汇编代码如下 123456789proc:.LFB0: movq 16(%rsp), %rax ; 将 a4 放入 %rax 中 addq %rdi, (%rsi) ; *a1p + ...

15-445 地址 https://15445.courses.cs.cmu.edu/fall2021/schedule.html  MVCC 的基本思想就是写操作不阻塞读操作，读操作也不阻塞写操作。要做到这一点，我们基本上就不能加锁了。在 MVCC 中会为每个事务创建一个一致性快照，事务都是在这个快照上进行操作的。 实现原理  MVCC 为每个事务分配了一个时间戳，并根据时间戳来决定是否能够访问某个数据的历史版本。以下图的例子，我们来分析一下 MVCC 的执行流程。  T1T_{1}T1​ 的时间戳为 1，T2T_{2}T2​ 的时间戳为 2。T1T_{1}T1​ 先开始事务，并读取 A，这时它读取的版本是 A0A_{0}A0​。然后 T1T_{1}T1​ 对 A 进行写操作，会创建一个新版本的数据 A1A_{1}A1​。并将老版本 A0A_{0}A0​ 的结束时间戳设置为 1，表明在时间戳 0~1 内，该版本数据有效。  接着 T2T_{2}T2​ 开启了事务，并读取 A，那么这是它应该读取哪个版本的数据呢？在这里，它应该读取 A0A_{0}A0​ 版本的数据，因为 T1T_ ...

15-445 地址 https://15445.courses.cs.cmu.edu/fall2021/schedule.html Query Plan  SQL 是一种声明式语言，它只是告诉 DBMS 它想要哪些数据，但是并不会告诉 DBMS 如何获取他们。当 DBMS 接收到一个 SQL 语句，它会经历若干阶段，形成逻辑计划，然后根据逻辑计划来执行得到用户想要的数据。一般一个 SQL 语句会经过的阶段如下图所示 SQL Rewriter：在该阶段，DBMS 会通过某些规则，对 SQL 进行重写，比如通过 SQL 中指定的表名，到 catalog 中查找到表，然后替换为该标识，如果没有找到就会报错。这个阶段是可选的。 Parser：该阶段会进行词法分析、语法分析，将 SQL 语句转换为抽象语法树，然后传递给下一阶段 Binder：该阶段会到 System Catalog 中查找相关信息，并将 SQL 查询中所引用的命名对象转换为内部的某种标识，输出逻辑计划。 Tree Rewriter：该阶段会重写抽象语法树，通过静态规则对每个查询都进行改写，这个过程需要查询 System ...

概览 这一部分主要是实现 DB 的一些运算操作 根据已经提供的 Project 和 OrderBy，实现运算符 Filter 和 Join 实现 IntegerAggregator 和 StringAggregator。 实现聚合运算。聚合运算符的输出是每次调用 next() 时整个组的聚合值 在 BufferPool 中实现 tuple 的插入、删除、页牺牲等相关方法 实现插入和删除运算符 请注意，SimpleDB 不实现任何类型的一致性或完整性检查，因此可以将重复记录插入文件中，并且无法强制执行主键或外键约束。 DB 使用迭代模型，以数据流的模型不断调用next方法获取数据流。 Predicate Predicate 谓词，可以用来过滤。支持 =、>=、>、<=、<、<>、like 条件。 12345678910private Op op; // 操作private Field operand; // 要比较的属性private int field; // tuple 中的第几个属性publi ...

15-445 地址 https://15445.courses.cs.cmu.edu/fall2021/schedule.html  DBMS 将 SQL 转化为查询计划，而查询计划会将 operators 组织成一颗树，数据可以从根流向叶子节点，称为 Top-To-Bottom，也可以从叶子节点向上传递到根节点，称为 Top-To-Bottom。本文的重点是 Top-To-Bottom 处理模型  DBMS 的处理模型定义了 DBMS 应该如何执行一个查询计划，下面会介绍三种可用的模型 Iterator Model Materialization Model Vectorization Model  在处理模型中，每个 operator 都会定义一个 next 函数供父节点调用，这个函数会返回父节点需要处理的 tuples，而我们要介绍的三种模型都是只是对 next 函数进行了改造 Iterator Model  迭代(Iterator)模型要求一次返回一个完整的 tuple，即父节点调用 next 从子节点处获取 tuple，子节点将一个完整的 tuple 返回给父节点 ...

6.830 Lab1  6.830 的 lab 的目标是实现一个简单的数据库管理系统，只提供了 DMBS 的基础功能，包括对数据的存储进行描述和解释，应用查询条件来找到匹配的 tuples，提供查询 tuples 的访问方法等。 Tuple Layout  Exercise 1：完成 Tuple 和 TupleDesc 的相关信息。  SimpleDB 采用的是行存储的形式，即所有属性都通过数组组织到一起。 TupleDesc 这个类用于描述 tuple 的 schema，里面包含了一个 tuple 应该拥有哪些属性，以及属性的类型信息。而 Tuple 存储着记录的实际内容，即 tuple 中的属性值。由此我们可以写出 TupleDesc 和 Tuple 应有的属性 1234567public class TupleDesc implements Serializable { private TDItem []fields; public static class TDItem implements Serializable { ...

15-445 地址 https://15445.courses.cs.cmu.edu/fall2021/schedule.html Aggregations Aggregations 的工作就是将多个属性的值根据某种策略聚合为一个值，比如 COUNT, SUM, AVG 等操作。 Aggregations 有两种实现方法，一种是 Sorting，一种是 Hashing Sorting 这里介绍的是基于磁盘的数据库，所以我们无法假设需要排序的数据都可以放入内存。因此我们需要对数据进行外部排序，在课程中介绍了 External Merge Sort。 假设我们有 N 个待排序的 pages，Buffer Pool 可以容纳 B 个 pages。外部归并排序首先会将待排序的数据集划分为 ⌈N/B⌉\lceil N/B \rceil⌈N/B⌉ 个部分，每一部分称为一个 run。在第一阶段，将 B 个 pages 放入 Buffer Pool，进行内部排序，然后写回磁盘。第一阶段完成后，每个 page 中的数据都是有序的，接下来进行第二阶段。第二阶段会将有序的 B - 1 个 page ...