笔记

LEC1&2 关系数据库模型

Pasted image 20220807203949.png

关系数据模型仍然是世界上使用最广泛的模型

nosql不仅仅是一个数据模型，它是涵盖了很多数据模型的一种概念

Pasted image 20220807204250.png

LEC3&4 数据库存储系统

数据库系统是面向磁盘（disk-oriented）考虑的

Pasted image 20220810164843.png

Pasted image 20220810163211.png

易失性存储介质vs.非易失性存储介质

Pasted image 20220810163457.png

易失性介质：

往后通常使用memory来描述这些介质
它们只有在通电状态下可以保存数据
易失性存储通常支持非常快的随机读写以及字节粒度的定位
非易失性介质：
往后通常使用disk来描述
它们在不通电的时候也可以保证数据的持久性
与memory不同的是，它们通常是按照block/page寻址的，这意味着如果需要读一个在特定offset的值，程序需要先将一整页（page）读入内存
通常情况下，disk更善于顺序读（同时读多个连续的数据块）

现如今，新的非易失性存储介质（例如intel的optane）可以做到既有和DRAM一样快的读写性能，还可以保证存储数据的持久性。目前也有相当的研究关注基于非易失性memory 的数据库系统。ps：课程教授说这是未来，但是在形成本文的前不久，intel已经宣布放弃optane业务

DBMS所关注的存储

通常来说，数据库是被存储在disk上的，因此DBMS需要优化disk和memory之间的数据移动，系统无法直接在disk上操作数据

Pasted image 20220810164550.png

disk和memory在对一个64byte的数据进行操作的速度上有非常大的差异（约150倍），通常在disk上进行读写是非常昂贵的操作。因此DBMS关注的是如何优化disk上的延时，而不关注cache和cpu寄存器

DBMS vs. OS(mmap)

DBMS的高层设计是要向虚拟内存一样，提供一个非常大的地址空间让操作系统可以从disk中读取页

一种可行的方法是利用mmap系统调用去将一个文件映射到进程的地址空间中来，这意味着操作系统来负责为disk和memory之间的数据交换，但是这样的话，如果mmap引发了一个缺页异常，则整个程序都会阻塞。

当遇到写操作的时候，特别是多个进程同时写的时候，这是非常危险的
一般来说，DBMS希望自己来控制disk和memory之间的数据交换，因为它对于数据和查询比较熟悉
DBMS也会使用以下的接口来与操作系统交互

Pasted image 20220810170045.png

数据库系统的文件结构

有些数据库系统会用一系列文件来存储数据库，而有些则使用单一的文件（例如SQLite）
操作系统对于数据库文件一无所知，只有DBMS知道如何解读和操作这些文件
DBMS的storage manager负责管理数据库文件，它将文件表示为一系列页，并且管理写入页的数据以及页中的空闲空间

数据库页

DBMS通过**页（page）**来组织数据库，它们是一些固定大小的数据块，页可以包含不同种类的数据（例如tuples，indexes等等），大多数系统不会混用这些类型。

一些DBMS会要求这些页是self-contained的，即这个页本身包含了所有访问该页的所有信息。

每一个页都有一个唯一标识符，如果DBMS讲数据库存储在单一文件上，则可以利用offset为唯一标识符。而有些多文件DBMS则会利用一个中间层映射标识符到文件路径以及偏移。

大多数DBMS将页限定为固定大小，但也有数据库系统支持指定不同大小的页。

Pasted image 20220810171202.png

DBMS中通常在意三种页大小：

硬件页
操作系统页
数据库页

注意存储设备通常只能保证hardware page的读写是原子的，这意味着如果database page比hardware page更大的话，DBMS需要提供额外的机制保证系统崩溃时会产生的读写安全问题

数据库堆

Pasted image 20220810171727.png

不通的DBMS利用不同的方式来在数据库文件中组织页。Heap File是其中一种。堆文件是一个页的无序集合，数据项以随机顺序存储。有两种方式来表示一个堆文件

Linked LIst（对于查找来说非常低效）
Page Directory

Page构成

每一页的页头（Header）包含以下的元数据

页大小
校验和
DBMS版本
事务可见性
压缩信息
...

基于槽存储模式的页（slotted-pages）

在每一页的Header之后维护一个Slot Array做为槽编号到offset的映射

Pasted image 20220810172537.png

Pasted image 20220810172741.png

目前大多数数据库系统采用的方案是槽模式页

Pasted image 20220810172826.png

通过给每一个数据项分配一个标识符，最常见的page_id+offset/slot则数据库系统可以通过这个id来找到数据项

基于日志结构存储的页

日志结构存储仅仅将对数据库的修改写入文件中（例如插入、更新、删除等等）

Pasted image 20220812110720.png

读取一个记录的时候，DBMS通常从后往前扫描日志，“重新构建“一个数据项。因此基于日志结构的存储通常有着非常快的写入速度和比较慢的读取速度。

为了避免读取的速度太慢，DBMS通常会利用索引直接跳转到日志中特定的位置再开始扫描，同时，它也可以通过周期性的压缩日志（例如如果对一个已经存在的数据项进行更新的话，可以压缩成直接插入更新后的数据），频繁压缩同样会造成一个问题写放大

Pasted image 20220812111220.png

数据项构成构成

同样也包含一个Header：

可见性信息（用于并发控制）
Bit Map（用于NULL值）
数据项的列通常是按照定义的顺序存储的
数据项中不包含任何关于表结构（schema）的信息，这些元数据维护在更高层
通常来说，同一个表的数据项都是存储在同一个页上的
也有数据库提供denormalize的特性，讲频繁访问的链接数据库直接存储到一页上以减少I/O

数据库中的数据表示

数据项通常以字节数组的方式存储，DBMS知道要如何翻译这些字节，数据库中通常有四种可以被存储在数据项中的类型：

定点小数是为了避免近似带来的错误而产生的数据类型，但是由于要存储额外的元数据以及特定的数据表示，会产生额外的开销
可变长度的数据通常含有一个Header，记录数据的长度。大多数数据库不允许数据项超过一个页面的大小，所以它们会将一个大数据存储在别的页面中，然后存储一个指向该页面的应用来代表这个大数据，还有一些系统则是直接将数据存在一个外部文件中，然后存储这个文件的指针

负载类别

Pasted image 20220812114329.png

OLTP: On-line Transaction Processing
- 操作通常简单快速
- 一般来说只会在一个实体上操作
- 写操作比读操作多
- 重复操作比较多
- 目前人们开发的应用通常属于这种负载
OLAP: On-line Analyitical Processing
- 运行时间长的，非常复杂的查询
- 大量的从数据库中的读取
- 探索性的查询
- 从OLTP查询中产生新的数据

存储模型

N-ARY存储模型（行存储）

将一个数据项的所有列连续存储，比较适用于OLTP负载，因为这种负载通常是对单个个实体进行操作。
优势：快速的插入、更新以及删除，对于需要整个实体的查询友好
劣势：对于需要大量扫描表的操作不友好，因为它会将很多无用的数据读进buffer pool造成污染

有两种不同的方式组织行存储的数据库：
- Heap-Organized Tables: 数据项无序的存在一个叫做堆的块中
- Index-Organized Tables: 数据项存在一个自索引的主键中，但是和集群索引有区别
分解存储模型（列存储）

利好OLAP负载
为了将列存储的数据项完整的恢复，通常使用以下的方式：
- 采用固定长度的偏移量（大多数数据库采用）
- 对于每一个列中的数据，将数据项id和其一起存储

LEC5 缓冲池（Buffer Pool）

LEC6 哈希表

1. 数据结构

数据库管理系统使用针对系统的不同部分使用各种各样的数据结构。例如说：

内部的元数据：这部分数据维护数据库的信息和系统的状态，例如：页表
核心数据存储：用作数据库中数据项的基础存储的数据结构
缓冲数据结构：数据库管理系统可以构建暂时的数据结构用于加速执行查询（例如join操作的哈希表）
表索引：起到辅助作用的数据结构，可以更加方便的查询特定的数据项

对于数据库管理系统中的数据接哦股通常有两个主要的设计考虑：

数据组织：需要考虑如何分布内存，以及那些信息需要存储在数据结构中以支持高效的访问
并发：同时也需要考虑如何实现多线程安全的访问数据结构

2. 哈希表

哈希表实现了一个联合数组抽象数据类型，将键映射成值。哈希表提供了平均时间复杂度为O(1)的操作（最坏情况下为O(n)）以及O(n)的空间复杂度。**注意尽管是O(1)的平均复杂度，常数在实际系统中仍然影响非常大，需要优化）

哈希表的实现包含两个部分：

哈希函数：哈希函数定义了如何将一个大的键空间映射到一个更小的域中。函数用于计算一个索引对应的slot或者bucket。我们需要考虑计算速度和冲突率之间的平衡。极限情况下，可以考虑一个哈希函数，它永远返回一个常量（非常快，但是每一次计算都会产生冲突）。在另一个极限情况下，我们考虑一个“完美”的哈希函数，它永远也不会发生冲突，但是需要计算非常长的时间。理想的设计就是位于两个极限的中间。
哈希模型：哈希模型定义了如何处理哈希冲突，我们需要考虑申请一个大的哈希表以减少冲突以及当发生哈希冲突的时候执行额外指令这两者之间的开销。

3. 哈希函数

哈希函数接受任何键作为输入，返回一个该键的一个整数表示。函数的输出是确定的，也就是说，相同的key总是会生成同样的哈希输出。

数据库管理系统不需要使用一个有安全保障的哈希函数（例如SHA-256）因为通常不需要担心泄漏key的内容。这些哈希函数主要在在系统的内部使用因此信息通常不会被泄漏到系统之外，只需要关心哈希函数的性能以及冲突表现。

目前主流的哈希函数是Facebook的XXHash3

4. 静态哈希模型

静态哈希模型指的是哈希表的长度是固定的，这意味着如果数据库管理系统用光了了哈希表的存储空间，则它需要从头开始建立一个更大的哈希表，这个操作通常是非常昂贵的。通常将新的哈希表建立为原来的两倍大小。

为了减少无效压缩的次数，避免哈希冲突是非常必要的。通常，我们使用预估元素数量的两倍大小的哈希表。

在真实的情况下，以下的假设通常不能成立：

可能用到的元素的数量提前能够预知
键值是唯一的
存在一个完美的哈希函数

因此，我们需要合适的选择哈希函数和哈希模型

Pasted image 20220901195803.png

4.1 线性概率哈希

这是最基础的哈希模型，同时也是最快的。它使用一个环状的缓冲区来存储slots数组。哈希还书将key映射成slots。当冲突发生时，我们线性搜索相邻的slots直到找到一个空白的slots防止冲突的key。查找时，我们检查key经过hash后的slot，然后依然线性的搜索直到我们找到相应的实体（或者一个空的slot，表明key在哈希表中不存在）。注意我们必须也将key值存储在slots中，一遍我们可以检查这个实体是否是查找的。删除操作则更加需要技巧，对于直接将实体从slot中删除我们要非常小心，因为这样可能会导致未来对于在该实体下面的查找落入一个空的slot中，关于这个问题通常有如下几个解决办法：

最常见的方法是使用“tombstones”，不直接删除实体，作为替代，我们用一个墓碑实体替代它，未来搜索过程中碰到墓碑实体则跳过继续扫描。
另一个操作是将临近的数据整体迁移，以覆盖空的slot。

Pasted image 20220901195852.png

Pasted image 20220901195908.png

非唯一键：这种情况下相同的键可能会和不同的值或数据项联系起来，有两种方法处理：

分体式链表：存储一个指针指向另外的区域，该区域包含该键所有值的链表。而不是将键值存储在一起
冗余的键存储，更加常见的方式是简单的多次存储相同的键在同一个表中，这样的话先行概率哈希的一系列操作仍然可以成立。

Pasted image 20220901195932.png

4.2 Robin Hood哈希

这是一个线性概率哈希的拓展版本，为了减少每一个键距离他们最佳位置（也就是利用哈希函数计算得到的它最开始的位置）的最大值。这个策略是通过定义一个key的”rich“和”poor“然后改表他们的位置来实现的。

在这个变体中，每一个实体也同样记录他们距离原始位置的距离，因此，每一次插入的时候，如果插入的key会距离他们的原始距离相比于当前处于这个slot中的实体更远的话，我们就把要插入的key放在这个slot里，然后尝试将插入旧的key插入到哈希表的后面。

Pasted image 20220901195956.png

4.3 Cuckoo哈希

这个方法包含多个使用不同哈希函数的哈希表，所有的哈希函数使用同样的算法，但是它们通过设定不同的种子来得到不同的哈希值。

当做插入操作时，我们检查每一张表，然后选择一个包含空余slot的（如果有多张表都满足条件，则可以通过比较其他因素来决定，或者更普遍的，直接随机决定）。如果没有可以使用的表了，则（通常随机）选择一个然后剔除旧实体。接着将旧实体重新哈希到另一个表中。罕见的情况是，我们可能会陷入一个死循环，如果这种情况发生了，我们就需要利用新的种子重新构建所有的哈希表（罕见的）或者干脆直接利用更大的表重建（更为常见的）。

Cuckoo哈希保证了O(1)的查询和删除，但是插入变得更加昂贵。

Pasted image 20220901200029.png

5 动态哈希模型

静态哈希模型需要系统提前知道需要存储的元素，否则的话在遇到表满的情况下可能需要重建哈希表。

动态的哈希模型则可以实现在需要的时候扩大或者缩小哈希表的大小，而不用重建整张表。模型根据最大化读或者写操作可以有不同的方式进行实现。

5.1 链状哈希

这是最常见的动态哈希方式，DBMS通过为哈希表中的每个slot以链表形保存buckets，映射成相同slot的key简单的插入该slot的链表中

Pasted image 20220901200049.png

5.2 可拓展哈希

链状哈希的变体，不会让链无限增长，会将buckets进行拆分，这个方法允许同一张哈希表中的不同slot指向同一个bucket链

重新平衡哈希表的核心思想是移动bucket实体然后增加在表中寻找实体的需要检查的位的个数。这意味着数据库管理系统仅仅需要移动要拆分的buckets中的数据，其他的则保持不变。

数据库管理系统维护一个全局的以及局部的位数，表示要在slot数组中寻找buckets需要多少位
当一个bucket满的时候，数据库管理系统拆分bucket然后重新排布所有的元素，如果需要拆分的本地的bit长度小于全局的长度，则新的bucket就添加到现有的slot数组中，否则，数据库管理系统就让slot数组的大小翻倍以装下心的bucket然后增加全局bit count的长度。

Pasted image 20220901200116.png

5.3 线性哈希

作为当一个bucket溢出时马上拆分它的替代，这个模型包含一个拆分指针，拆分指针指向下一个将要被拆分的bucket。无论是哪个bucket发生了溢出，数据库管理系统往往拆分指针指向的那个bucket。而溢出的条件可以单独实现。

当任何的bucket发生溢出的时候，拆分指针指向的那个bucket，方法是增加一个新的slot实体，然后创建一个新的哈希函数。
如果哈希函数映射去了一个指针指向位置之前的slot，那么就使用新的哈希函数
当指针达到的最后一个slot，则删除原油的哈希函数，然后用一个新的哈希函数替换。

LEC7&8 树形索引

索引

表索引是一个表的列的子集，组织成表的形式可以让数据库系统更快的执行序列扫描。数据库系统保证表的内容和索引总是保持一致。

找出最好的索引模式来执行查询是数据库系统的任务，而每一个数据库创建索引的数量又同样需要均衡考虑（因为索引也同样需要存储空间以及维护成本）。

B+树

B+树可视化

B+树是一个自平衡的树形数据结构，它可以保证存储的数据有序并且以O(log(n))的复杂度提供搜索、顺序访问、插入以及删除操作，它是作为面向硬盘的数据库系统来读取和写入大量的数据所做的优化。

几乎所有的现代数据库系统都支持使用B+树来保证顺序。另外值得一提的是另外的B树，但是人们通常用这个名称来指代一系列的数据结构。现代B+树的实现结合了其他B树变体的特点，例如在Blink树中的旁路指针。

Pasted image 20220904204253.png

一般来说，B+树是一个M路搜索树，其具备以下的特性：

它是完全平衡的（也就是说，所有的叶子结点都在同一深度）
除了根结点之外的所有内部节点都至少是半满的（M/2-1 <= num of keys <= M-1）
每一个包含k个键的内部节点都有k+1个非空的孩子

B+树中的每一个节点都包含一个键值对数组：

每一个节点中的数组都（几乎）是根据键值排序的
内部节点中的数组中会包含指向其他节点的指针
有两个方案来作为叶子结点的值
1. 记录ID：指向数据项的指针
2. 数据项：存储在叶子结点中的数据项的实际内容

Pasted image 20220904204311.png

Pasted image 20220904204649.png

Pasted image 20220904204420.png

通常的做法是将键和值分开存储，而不是[K,V]这样紧邻着存储

插入

找到正确的叶子结点L
有序的添加一个新的实体到L中：
- 如果L还存在足够的空间，则直接插入，操作完成
- 否则将L分裂为两个节点L和L2，均匀地重新分配实体，然后记录处于中间的键值，将指向L2的索引插入到L的父节点中
如果分裂了一个内部节点，则均匀的重新分配实体，然后讲中间键向上维护

删除

找到正确的叶子结点L
删除相应的实体：
- 如果L至少是半满的，那么直接删除，操作完成
- 否则，从两边的叶子结点中借实体尝试重建
- 如果重建失败，则需要合并L，并且重新指派旁路指针
如果发生了合并，必须要删除L父亲节点中指向L的实体

B+树的一些设计顾虑

节点的大小

B+树的最佳的节点大小取决于存储介质的速度，核心想法是使得从硬盘读取到内存中的节点中的键值对尽可能的多。
硬盘的速度越慢，理想的节点大小需要越大
一些负载相对于单个的键值查询可能存在更多的需要扫描的任务

合并的阈值

一些数据库系统不是一碰到节点不半满就马上执行合并的
延迟合并操作可能会减少重构的次数
更好的想法是让一些不半满发生，然后周期性的重构整个树以达到平衡

变长的键值

指针：键存储为指向数据项属性的指针（不常用）
变长节点：B+树中的每一个节点的大小是可变的，但是需要细致的内存管理，这个方法通常也很少见
键映射：嵌入一个指针数组，映射到节点中的键值表，这个和之前讨论的基于slotted的页中的做法非常相似，这是最常见的做法。

Pasted image 20220904205152.png

不唯一的索引

可重复的键：使用相同的页节点排布，但是允许多次存储相同的键
值列表：每个键仅仅存储一次但是维护一个不同值的链表

Pasted image 20220904205228.png

Pasted image 20220904205245.png

节点内部的搜索

线性搜索：从头到尾的扫描整个节点中的所有实体，碰到所需要的键就停下来，这个做法不需要节点中的实体是有序的
二分搜索：直接跳到中间的键，然后执行递归的二分搜索，这个需要提前排序节点中的实体
插值法搜索：首先根据节点中已知的低/高键值来估计要开始搜索的位置，跳到这个位置然后开始执行线性搜索

B+树的优化

前缀压缩

存储在同一个叶子结点中的键往往有着相同的前缀
作为存储整个键的替代，找出相同的前缀，然后对于每一个键仅存储不同的后缀

Pasted image 20220904205305.png

前缀切断

内部节点中的键值仅仅是用来“指导方向“，我们不需要整个键全部存储
存储一个能够执行路由的最小前缀就足够了

大量插入

从头开始构建B+树的最快的方法是首先排序键，然后利用这些键从底部到顶部构建整个树
这个会比一个一个的插入更快，因为避免了分裂和合并

其他会用到索引的地方

隐式索引

大多数数据库系统会自动的为完整性限制创建索引（例如：主键、unique限制）

Pasted image 20220913191528.png

部分索引

在整张表的子集上创建索引，这样可以减少索引的大小以及维护索引的成本

Pasted image 20220913193408.png

覆盖索引

所有完成查询所需要的数据都保存在索引中，这样数据库系统就不需要去取数据项，可以基于索引中存储的数据直接完成整个查询

Pasted image 20220913193427.png

包含索引的列

将索引作为列嵌入，以支持仅对序列的查询

Pasted image 20220913193456.png

函数/表达式式索引

将函数或者表达式的输出而不是将原始的值作为键，哪些查询需要用到这种索引是数据库系统的任务

Pasted image 20220913193527.png

Radix树

radix树是前缀树（trie）的一种变体，它使用键的数码表示，并且利用它一个一个的来测试前缀，而不是直接比较整个键。radix和trie不同的是radix中不是对于键中的每一个元素都存

在一个节点，而是会将可以区分出不同键的最大前缀的合并起来表示

树的高度依赖于键的长度，而不是像B+树中依赖键的数量。通往叶子结点的路径作为叶子节点代表的键的表示。并非所有类型的属性值都可以被压缩成可以利用radix表示的数码。

Pasted image 20220913193553.png

倒排索引

倒排索引存储了一个单词到记录的映射表示了包含在这些属性中包含这个单词，这种索引有时候也在数据库系统中被称为全局搜索索引

大多数主要的数据库系统都原生支持了倒排索引。

LEC9 索引并发控制

索引并发控制

并发控制协议是数据库系统保证在对共享对象并发操作时“正确性”的方法

一个协议的正确性可以被分为：

逻辑正确：我能够看到我应该看到的数据吗？这意味着线程应该能够读取它允许读的数据
物理正确：对象的内部表示正确吗？这意味着我们的数据结构中不存在会使得指针读取一个非法的内存地址的指针

索引的逻辑内容是我们在这节课中要考虑的问题，他们和数据库中的其他元素不全一样所以我们要不同的对待他们

Locks和Latches

Locks

从其他的事务中保护索引的逻辑内容
在事务执行的整个过程中都保有
数据库系统需要能够回滚变更

Latches

从其他线程中保护索引内部的数据结构的临界区
在操作的过程中保有
数据库存储系统不需要能够回滚变更
两种模型：
- 读：多个线程可以同时读取同一个对象，一个线程仍然可以获得读锁，尽管有另外的线程已经获得了这个读锁
- 写：只有一个线程可以访问这个对象，一个线程将无法获得写锁，只要有其他的线程以任何模式已经取得了该锁

Latch的实现

CAS（compare-and-swap）

OS阻塞锁

使用操作系统内置的锁结构作为latch，futex(fast user-space mutex)是一个（1）用户态的自旋锁以及（2）一个操作系统级别的锁。如果数据库系统可以获得一个用户态的锁，那么这个锁就被锁定。futex对数据库系统表现为单一锁，虽然在它的内部存在两个锁，如果数据库系统没有能够获得用户态的锁，那么它会陷入内核，然后试着去获取一个更加昂贵的锁。如果数据库系统仍然无法获得第二个锁，那么线程会通知操作系统它被阻塞了，不要执行调度

操作系统锁对于数据库系统总体来说是一个不太好的想法，它受到操作系统的约束，而且有着非常大的负荷

Pasted image 20220913195818.png

Test-and-Set Spin Latch(TAS)

自旋锁往往更加高效，因为它可以被数据库系统控制。一个自旋锁的实现可以是内存中的一个位置，线程们尝试去更新它（例如，将一个boolean值设置为true）。一个线程通过CAS去尝试更新这个内存位置，如果它无法实现更新，那么就通过一个while循环陷入等待，并且不断尝试

Pasted image 20220913200044.png

读写锁

上述的锁对于读写操作都没有做区分（也就是说，它们都不支持不同的模式）。我们需要一个方法允许并行的读操作，所以如果一个应用有着非常多的读请求它就会有更好的表现，因为所有的读者可以共享资源吗，而不是等待

一个读写锁允许锁被以不同的模式获取，例如读模式和写模式。它追踪有多少线程获取了锁以及有多少线程分别以什么模式在排队等待锁的释放。

Pasted image 20220913200654.png

哈希表的锁

在静态哈希表中支持并发访问是比较简单的，因为线程往往只有有限的方式去访问数据结构。例如，所有的线程只能够朝着一个方向移动，从一个slot到下一个slot（例如，从上到下）。线程也只能在同一时间访问一个页或者slot。因此，死锁在这种情况下不会发生，因为不会存在两个线程互相竞争锁的情况。而如果要改变表的大小，则需要对于整张表获取一个全局的锁（也就是说，在头部表中）

在一个动态哈希模型中实现锁（例如，可扩展的哈希）会更加麻烦一些，因为存在更多的共享状态需要更新，但是总体来说方法上没有太大的变化。

总的来说，有两种方法在哈希表中实现锁：

页锁：每一个页含有它自己的读写锁，用来保护整个页的内容，线程在访问页之前需要获得读锁或者写锁。这种方式会减少并行性能因为在同一时间只有一个线程可以访问该页面，但是访问多个在同一页面的slot就会变得更快，因为只需要获取一次锁
slot锁：每一个slot都含有自己的锁，这样会增加并行性，因为多个线程可以访问同一个页面中的不同slot。但同时它也正价了存储和计算的负荷，因为线程在访问每一个slot的时候都必须获取锁。数据库系统可以用单一模式的锁（例如，自旋锁）来减少元数据和计算负荷

Pasted image 20220913205143.png

B+树的锁

锁耦合是允许多个线程在同一时间访问/修改B+树的协议：

获取父亲节点的锁
获取子节点的锁
如果已经被视为安全的，则释放父亲节点的锁。安全被定义为该节点在更新的时候不会分裂或者合并（插入操作的时候没有满，删除操作的时候比半满还要多）

基础的耦合锁协议：

查找：从根节点开始往下，不断的获取子节点的锁，释放父亲节点的锁
插入/删除：从根节点往下，一直获取锁，一旦子节点的锁被获取了，检查它是否安全，如果子节点安全，则释放它所有祖先的锁

Pasted image 20220913205336.png

Pasted image 20220913205408.png

进阶版耦合锁协议：

基础耦合锁算法的问题是事务常常会从获取根节点的锁开始执行插入或者删除操作。这限制了并行性。作为替代，我们可以假设重构操作时非常稀少的（分裂和合并操作），因此事务可以获取叶子节点共享的锁。每一个事务将假设通往目标叶子节点的路径是安全的，然后使用读锁并且耦合的尝试去抵达叶子节点，然后实现更改。如果整条路径的某一个节点是不安全的，则需要从头再来，并且用前面的基础算法实现更改（也就是说获取写锁）

查找：和基础版的同样算法
插入/删除：和搜索一样耦合使用读锁，通往叶子节点，然后在叶子节点上获取写锁。如果叶子节点不安全，则释放所有前面获取的锁，然后利用基础版的算法重新执行事务。

Pasted image 20220913205444.png

叶节点扫描

这些协议中获取锁的线程都遵循“从上到下”的原则，这意味着一个线程只会尝试获取当前节点的下面节点的锁。如果该锁不能够获得，这个线程必须等待直到获取到这个锁。在这种情况下，不会出现死锁的情况。

叶节点扫描比较容易受到死锁的影响因为会存在两个线程同时从不同的方向尝试获取锁（例如，一个从左到右，一个从右到左）。索引锁不支持死锁的检测和避免。

因此，能够解决这个问题的唯一方法是利用代码限制。叶节点扫描的过程中的锁获取过程必须遵循“非等待”的模式。也就是说，B+树的代码必须能够解决锁获取失败的情况，这意味着线程尝试从一个叶子节点上获取锁，但是锁无法得到，接着它会立即放弃它的操作（释放它获取到的所有锁）然后从头开始重新执行一次。

Pasted image 20220913205517.png

LEC 10 排序和聚集

SQL 数据库往往是不排序的，但是某些功能需要排序

ORDER BY
DISTINCT
Index building
GROUP BY

我们需要一种算法，可以在面向硬盘的结构上做排序，因为 DBMS 的数据量一般特别大，内存放不下

TOP-K 推排序

一个带 LIMIT 的 ORDER BY 适合用推排序来找出 top-k 个元素

外部堆排序（external merge sort）包含多次 runs，通常包含两个阶段：

排序：在内存中排序一部分数据然后将排好序的数据写回 disk
归并：把排序 runs 的结果合并

简化的 2-way External Merge Sort

第 0 个 pass：

从表中读一页到内存里
把那一页的数据排序并写回道磁盘中
重复直到整个表的所有页都被排好序
第 1，2，3 ... 个 pass：
递归的将两个 runs 排好序
至少需要能容纳 3 个 buffer pages（2 个输入 1 个输出）
⚠️upload failed, check dev console
如果内存充足，可以使用 K 阶 external merge sort

B+树索引排序

CLUSTERED B+TREE
- 从最左边的叶子结点开始遍历即可获取所有排序好的 tuples
- 这种方法非常高效，因为不用计算，而且所有的 IO 都是顺序的
UNCLUSTERED B+TREE
- value 是一个包含数据的页索引
- 这种做法通常不好，因为每一个 record 都会触发一次 IO（读一个页上来）

AGGREGATIONS

有两种方式实现 aggregation

排序
哈希
有一些不需要有序的操作（例如 DISTINCT GROUP BY）, 使用哈希会更加方便

外部 Hash 聚集

阶段 1：分片
- 将 tuples 根据哈希值分到 buckets 里
- 当 bucket 写满的时候写回到 disk 中（以 bucket 为粒度落盘）
阶段 2：重哈希
- 为每一个分片建立内存哈希表，然后计算聚集
  - 对 disk 上的每一个分片，读进内存然后使用一个不同的哈希函数构建内存哈希表
  - 然后遍历这个哈希表的每个 bucket 把匹配的 tuples 聚集到一起

LEC 11. JOIN

我们需要 JOIN 本质上是因为我们需要将两个具有关系的表联系起来，这与构建关系型数据库是同质的——避免不必要的重复信息，然后使用 JOIN 来避免任何损失地将原始的 tuple 重新构造出来

通常，我们会将更小的表放在 JOIN 的左边（称为驱动表），这样会减少 IO 次数

JOIN 算子的输出内容会由几个因素决定：

processing model
storage model
data requirements in query

JOIN 算子输出的内容有以下几种形式：

Early Materialization：直接将 outer 和 inner tuples 的数据拷贝到新的输出 tuple，好处在于 join 操作输出的结果是完整的，如果 join 的父节点是输出算子，就可以直接将感兴趣的字段输出，不用再回到原始的表中找数据（称为回表）
Late Materialization：输出 record id，这种输出方式符合列存储的思想，DBMS在对join后得到的表执行查询时无需拷贝不需要的数据

JOIN 算法

Nested Loop Join

Naive 方法

这种方法又称为 stupid nested loop join，因为它完全发挥不出来 buffer 的好处，扫描整张 S 表的时候会将缓存灌满，然后对 R 表的下一条记录重新扫的时候又会一页一页剔除，非常低效

这种方法就已经能体现将小表放在 JOIN 操作左边的好处了（对于基于硬盘的DBMS来说，所谓的“小表”一般是指所占的文件页少的，R表虽然行数多，但它比较窄，所占用的页数少，那么遍历R表所需的硬盘IO次数少）

Block Nested Loop Join

这个方法的改进就是相对于 R 表的每条 tuple 进行一次扫描整个 S 表，变成了对于 R 表的每一页，其中的 tuple 共享地遍历一遍 S 表的所有页

再进一步优化，充分利用大 buffer 空间：

拿 B-2 个 buffers 用作存储 outer table 的页

拿 1 个 buffer 用作存储 inner table

拿 1 个 buffer 用作存储输出的页

这种 nested loop join 的优化思想就是拿更多的缓存空间给 outer table 用，从而减少扫描 inner table 的次数，从而减少开销，因为就算给更多的缓存给 inner table ，也无法改变它要被重刷的问题

Index Nested Loop Join

我们可以通过索引来避免整表扫描

Sort Merge Join

阶段 1: 排序
- 对两张表都按照 join 的 key 排序
- 可以使用任意的合适的排序算法
阶段 2: 归并
- 用指针遍历两张表得到匹配的 tuples
- 根据 join 的类型可能需要回溯

这种方式存在退化的问题——如果所有的 tuple 都相等，则退化成 Nested Loop Join

什么时候 Sort Merge Join 有用呢？

其中一个或者两个表都已经按照 join 的 key 排好序了
输出必须要按照 join 的 key 排序

Hash Join

Hash Join的策略是给outer table构建哈希索引，对inner table进行遍历

阶段1 Build，构建哈希表
扫描outer table，使用哈希函数h1构建哈希表，以要join的字段为Key
阶段2 Probe，点查询
去inner table以哈希函数h1进行查询，如下所示，以S表的每一行中要 join的字段为key去阶段1中的哈希表里查询，如果在哈希表里找到了能match的KV，那就可以完成相应的join操作

原始的哈希join中，每次都使用inner table中一行的join key去哈希表里查询，但使用有些join key去查询的时候，根本没有对应的哈希表项，这种无效的查询增大了开销，我们不妨使用布隆过滤器，给outer table构建哈希表的时候顺便构建一个布隆过滤器，inner table在去哈希表中查询前，先去查布隆过滤器，判断本次查询在哈希表中能否找到相应的表项，如果能通过布隆过滤器断定哈希表里没有对应的表项，便可以确定这是一次无效的查询，于是让此次查询提前结束

GRACE Hash Join

如果我们没有足够的内存来存放一整张哈希表怎么办？我们不会想要任由 buffer pool manager 来换入换出 pages

做法：

将 R 哈希到 $k$ 个哈希桶中，将 S 也用相同的 hash 函数哈希到 $k$ 个哈希桶中，并且当桶满的时候将桶写到磁盘中
每次将对应的分片（相同的桶）读入到内存中来，然后比较他们的内容

如果单个的哈希桶太大，也放不进内存，那该怎么办呢？如果使用哈希函数h1构建的哈希表里的哈希桶太大，那我们就把这个大的哈希桶存储硬盘，使用哈希函数h2，对这个哈希表再进行一次哈希操作来进行分区，递归地进行这个过程，直到切成足够小的块

JOIN 算法的性能总结

LEC 12&13 查询执行

执行模型

Iterator Model 迭代器模型/火山模型/流式模型

每一个查询计划操作符实现一个 Next() 方法，每次调用返回一个 tuple 或者当没有更多 tuple 时返回 null
操作符会实现一个循环，循环内部调用其子操作符的 Next() 方法获取数据供自己计算

在这种模型下，一些操作符会阻塞直到他们的孩子节点吐出数据，例如 ORDER BY 需要子操作符将所有 tuples 通过 Next() 返回之后排序再按照顺序吐出

火山模型便于实现对输出的控制，比如说SQL语句中有"limit 100"这样的关键字，限制只输出100条数据，在火山模型下我们只需先流式地输出100条，然后让顶端的算子停止输出。我们不需要额外控制最底层的table reader（也就是读表的算子），只需要在操作符树的顶端控制数据的出口。但火山模型在性能上也有一些问题，每一条数据的传输都依赖函数调用，虽然函数调用的开销远小于硬盘IO，但如果要上千万条这样大量的数据向上流动，函数调用的次数将非常多，这会降低性能

Materialization Model 物化模型

物化模型比较类似于“直觉下的查询语句执行模式”，操作符一次性读入全部要处理的数据，将得到的结果一次性输出

上层的操作符可以将一些限制（LIMIT）传递给子操作符
输出可以时一整个 tuple（NSM）或者某些列（DSM）

交易和事务对应的 OLTP 型数据库会使用这种模型，因为OLTP通常是点查询，只会涉及几条数据，每次子算子吐给父算子的数据不多，DBMS可以接受，如果是 OLAP 的负载，那么每次函数调用会返回过多的数据，DBMS无法承受

Vectorized 向量化模型/分批模型

火山模型每获取一条数据就要经过一系列的函数调用，物化模型每次函数调用可以获取很多数据，它们有各自的优点和缺点，向量化模型是这二者中和的产物，向量化模型中，每个算子也有 Next 函数，但它返回的不是一条数据，而是一批数据（tuple batch），这样可以减少函数调用的次数，从而降低开销

比较适合OLAP型负载，既能做到向上传递的数据量不是太大，又可以控制调用的次数
如果 CPU 支持 SIMD 指令集，可以一次性将一组数据传入 CPU 并一起执行相同的运算，一个SIMD指令就能让负责接收数据的父算子一次性完成对这一批数据的操作，这从硬件层面上大大地加速了DBMS查询语句的执行

访问方法

访问方法指的是 DBMS 访问表中数据的方式

顺序扫描

把 disk 中的每一页读如内存之后就一条一条扫描里面的数据

顺序扫描的优化策略：

预取
Buffer Pool Bypass：是说在顺序扫描的时候不把当前扫描的页送入缓存池，而是在内存中另外使用一块区域，当执行器扫描完这块区域里的数据之后就把这块内存释放，这样做的好处是：顺序扫描时被扫描过的页以后会有很大概率不会再访问，不把它放入缓存池的话可以让其他需要被缓存的页继续呆在缓存池里，而不是过一段时间后因LRU策略被踢出
并行扫描
数据跳过
- 近似查询（有损）：在一个从整个表中采样的子表上执行查询
- Zone Maps（无损）：事先对每个页计算一些统计信息，例如最小值/最大值/平均值/和/数目等，统计信息存放在 disk 的另外的位置，需要读表然后选择符合条件的 tuple 时，可以先看每个页的统计信息，如果通过统计信息能推断出该页里没有我们想要的数据，那我们就不用访问这个表
  - trade off: 额外的存储开销和维护开销（更新表之后统计信息也要更新）
晚物化：列存中算子输出的数据可以不是整条 tuple，而是 tuple 在页里面的 offset，这样就延迟了列存储情况下将不同列的字段拼接成完整的tuple的操作的发生，提升了效率
索引扫描
- 例如我们想筛选出 val>100 的 tuples，显然构建索引而非暴力扫描更有效率
- 如果我们有多个筛选条件，我们选择先使用索引的顺序应该遵循“使用了某个索引之后，经筛选剩下的数据越少，就越先使用这个索引”
多索引扫描：可以先用 age 字段的索引筛选出记录，同时也用 dept 字段的索引筛选，然后把两个结果取交集，取交集的过程可以用 bitmap/bloom filter 实现

更新查询

上述的方法都是 SELECT 的内部实现的方式，而会修改表的查询，例如 INSERT UPDATE DELETE 等，它们的执行逻辑不同，他们往往要检查约束以及维护索引

UPDATE/DELTE 查询语句执行时，子算子会把要处理的tuple的id传递给上层负责完成更新/删除操作的父算子，然后父算子通过id找到相应的tuple，然后执行 a对应的操作。此外，负责更新/删除的算子必须要记住在执行本次的查询语句时操作了哪些数据

执行SQL语句时，上图中上方负责完成更新操作的算子会先把和当前tuple有关的索引删除，然后更新tuple，最后将该tuple重新插回索引。因此，当扫描到salary为999的Andy对应的tuple时，会先从索引里删除该tuple对应的索引项，然后更新tuple，再重新插入对应的索引项，那么问题来了，新的tuple里面salary字段的值是1099，因此会被插到作为索引的B+树的后方的叶子节点里，而当前遍历叶子节点用的“光标”（cursor）还在Andy的tuple原先的位置。也就是说，光标继续往前挪动的时候，会再次碰到这个已经被改过tuple，而且由于它的salary字段是1099，小于1100，因此还会再加100，这就引起了错误。

并行查询

并行 DBMS 和分布式 DBMS

共同点
- 数据库利用多种资源来提高 DBMS 的各项能力
- 对应用表现地像一个逻辑的数据库一样
不同点
- 并行DBMS
  - 资源在物理上离得更近
  - 资源间通过告诉连接进行通信
  - 通信 cheap 而且可靠
- 分布式 DBMS
  - 资源彼此之间相距较远
  - 资源使用更慢的连接通信
  - 通信的开销和问题不能忽视

并行执行模型

执行模型定义了数据库系统是如何构建来支持不通用户应用的并发请求的
一个worker可以理解为数据库的一个组件，用来执行一部分工作，比如说查询语句相应的执行计划可以被分解为多个部分，每个部分给一个worker去执行

Process per DBMS Worker

每个 worker 是一个单独的操作系统进程

依赖操作系统的调度器
通过共享内存的方式进行通信（开销很大），维护全局的数据结构
一个进程崩溃了不会影响整个数据库系统

这种方式的问题是如果进程过多，操作系统因为要调度过多的进程从而降低性能，因此也有用进程池来实现的

Thread Per Worker

单进程拥有多个 worker 线程

DBMS 几乎自己管理调度
线程崩溃了可能会把整个系统宕掉
上下文切换开销更小，天然共享内存（共享页表）

Embedded DBMS

DBMS 在和应用相同的地址空间中运行，应用层负责线程调度

一般来说数据库都会使用操作系统提供的线程模型
线程并发的 DBMS 并不意味着它们可以实现每个 SQL 语句的执行是并发的，而是说明它们会用多个线程并发执行多个 SQL 语句

并发查询

Inter-Query: 同时执行多个不相关的查询，可以提高吞吐量和减少延时
Intra-Query: 并发地执行单个查询中的操作，可以减少长查询的延时

Intra-Operator (Horizontal)

设计思想类似于生产者-消费者模型，成熟的 DBMS 中，每个算子都有并发的版本，有两种实现思路

多个线程去操作集中的全部数据（多个线程同时读一张表）
把集中的数据切开，分发给每个线程处理

例如并发版本的 grace hash join 中，可以让一个 worker 处理一对哈希桶的 join，之后再把多个线程各自的处理结果聚集起来

将数据划分成多个不重叠的段，在数据的不同子集上执行相同算法的 worker，DBMS 还要在执行计划中插入一些 exchange 算子，用于做数据的聚集、拆分和分布

exchange 算子在分布式 DBMS 中也有，包含三大类：

用三个线程并行地构建哈希表，之后用另外的三个线程去并行地进行点查询，并且用exchange算子把并行计算的结果汇聚起来

Inter-Operator (Vertical)

垂直切分是说把执行计划树中的每个算子丢给一个相应的线程/worker去执行，它们之间是并发执行的，同时算子之间也有数据的传递，这和现代处理器中的流水线很像，因此也称作流水线并行

Bushy Parallelism

上述两者的结合，既有水平的也有垂直的

I/O 并行

基于 disk 的 DBMS 大部分情况下硬盘 I/O 是瓶颈，如果不能快速将数据读到内存中来，再多的并行策略也是无效的

I/O 并行指的是将 DBMS 分到多个存储设备中来提高 disk 的带宽和延时，将数据库的数据（例如数据库/表/关系等）切成不同的部分，存到不同的存储设备中，这样在对数据库进行并发存取的时候就会做到在硬件层面的并行

Multi-Disk Parallelism

多磁盘并行对于 DBMS 来说是透明的，它会通过操作系统或者硬件的配置将 DBMS 的数据文件存储到多个设备上（例如使用 RAID 技术）

Database Partitioning

我们可以把数据库实例中的不同Database分配到不同的硬盘当中，还可以在文件系统层面将不同的Database存入不同的文件夹中

Partitioning

垂直分区（如果某个属性特别的时候）
水平分区

LEC 14 查询计划和优化

查询优化是基于给定的查询，找到一个开销最小的正确执行，这是一个 NP-Complete 问题
没有一个优化器能生成最优的计划

使用估计机试去猜真正的开销
使用启发式算法来限制搜索的空间

用户的业务会发出SQL查询语句，少部分DBMS会有SQL Rewriter这个组件，对字符串形式的SQL语句进行文本上的预处理（在字符串层面上做简单的优化），之后SQL查询语句进入Parser，Parser会把SQL语句变成抽象语法树，抽象语法树当中会涉及到库/表/列的名称，这些名称要和数据库系统元数据里面的库/表/列/索引的ID对应上，因此会有Binder（即连接器）把SQL抽象语法树中用户写的表名/列名/索引名转化成数据库内部使用的ID，并且这个步骤中会有检查：如果用户请求了一个不存在的表，那么就会直接报错。经Binder处理过之后的抽象语法树会被送入Tree Rewriter，这个组件大多数DBMS都有，它会输出一个标准的执行计划（比如说SQL语句里有一堆join操作，一开始的抽象语法树中的join的排布可能是乱的，Tree Rewriter会把所有的join排列成左深树，这个步骤也叫正则化），这个过程中也会查一些系统的元数据，Tree Rewriter输出的原始的逻辑计划是优化器进行优化的源头。之后基于规则的优化器（RBO， rule based optimizer）会查询一些系统的元数据来做优化，基于代价的优化器（CBO， cost based optimizer）不仅会查询元数据，还会查询相关的代价模型，根据代价模型去做优化，最后优化器会生成物理计划，被实际使用。

上述的过程有关优化的部分可以分为两种：

启发式/基于规则的：将查询重构，以删除那些低效率的语句
基于 Cost 模型的搜索：使用一个模型来估计执行计划的开销，然后选择开销最小的那个

logical plan是关系代数级别的
physical plan包括了各个算子的具体执行方式，即物理算子（join 到底是 nested-loop join 还是 merge/hash join）

如果两个关系代数表达式所输出的结果集是一样的，那么它们等价

Logical Query Optimization

设置一些优化规则，然后 DBMS 会对原油的逻辑计划进行模式上的匹配，如果原有的逻辑计划能够优化匹配规则，那么就将它变为优化后的等价的逻辑计划

Split Conjunctive Predicates：把连接在一块的谓词分开
Predicate Pushdown：谓词下推，把谓词尽量往下推，推到越接近读表越好，这便可以提前筛掉一部分的数据，减少上层算子的负担
Replace Cartesian Products with Joins：把笛卡尔积换成 join

Nested Query Rewriting

SQL语句中经常会有一些嵌套的子查询，DBMS一般会用如下两大手段去优化它：

对子查询和外层的主查询进行rewrite，将它们写成一个查询，其实就是转换成了 join 操作
进行解耦：在一些复杂的查询当中，可能不太容易将内部的子查询和外部的主查询rewrite成一个查询，那么DBMS可以将子查询分离出来，先把子查询做完，把结果存放在一个临时的表里面，然后把这个临时的表带到主查询中。也就是说，这里的解耦是指：不让子查询嵌套在主查询里面，而是把它拿出来，提前执行它（例如原始的SQL语句的谓词里面带有子查询，但这个子查询返回的值是一个常数，那不妨就进行解耦：先执行这个返回常数的子查询，然后把结果记录下来，否则每次使用谓词筛选时都会把这个子查询执行一遍，效率不高（这就类似于：与其多次进行重复的函数调用，不如把这个函数的返回值保存到某个变量里，然后使用这个变量））

Expression Rewriting

代价估计

具体的物理代价：上图所列举的那些，这和硬件的性能有很大关系（一般数据库一体机的优化器会更多地考虑这类代价，因为数据库一体机的DBMS了解硬件的全部具体信息）
逻辑上的开销：给每个算子大致估算它的开销（比如说hash join算子/table reader每处理100个tuple会有多大开销），而且由于是估算，所以这和算子内部实际采取的算法是无关的。并且优化器还需要估计每个算子所处理的数据的量，这便需要一些数据的统计信息
比较细粒度地估计算子的开销：分析每个算子的内部实现有几步，根据采用的算法的时间复杂度去详细地估计算子的开销

三种统计方法：

hist
sampling
sketch

LEC 15 并发控制

DBMS 有两大组件横跨了多个层级

并发控制：避免数据竞争的发生
数据库恢复：实现持久化的时候一直保持正确的数据库状态

Strawman System: 最简单的想法，我们将所有的事务都串行化，每次执行事务之前把一整个数据库复制一份，如果事务执行失败了，直接把那个脏的数据库删掉就好了

但是我们肯定不想这样做，因为事务之间不引起数据竞争的部分我们是可以并行的，但是我们也不能放任事务并行，我们必须找到一个方法去验证哪些事务交错的方式是有效的：

暂时内部的不一致性是可以的
永久的不一致性是不可行的

问题定义

ACID

实现事务正确性的标准是 ACID

原子性 Atomicity

1. Logging 日志

最常见的做法，也被称为 undo log - 回滚日志
将每一步都 log 下来，同时记在内存中和硬盘中
当用户回滚会这 DBMS 决定开始回滚的时候，就依据 undo log 一步一步将更新撤回
undo log 可以帮助在业务出错的时候拿来复盘，写日志也可以将随机写转换成顺序写，让写更快返回

2. Shadow Paging 只备份被修改了的那些页

隔离性 Isolation

这么做的目的是让可并行的事务好像在串行执行一样，事务并不感知其他事务对数据库状态造成的影响

给了负责写业务的程序一一个很好的抽象和便利，他不用管是否有其他用户也在同时操作数据库，如果因为其他用户的操作导致事务失败，这个事务就没有执行过返回错误

为了实现事务的隔离性，就需要并发控制

并发控制

悲观协议：不要让问题发生，在问题出现之前就让线程挺住
乐观协议：冲突是非常少的，在问题出现之后我们再去回滚就好了

我们为什么需要交错执行事务来最大化并行度？

慢 disk 和网络 IO
多核 CPU

分析一个例子：

T1 和 T2 的事务并行可以出现非常多的结果，但是我们要保证的是他们仍然像串行执行那样结果是一致的

事务的执行可以抽象成一系列的读和写 R 和 W，我们需要一种算法来判断出一系列的读写是否会导致一致性的错误

即我们希望找到一个Equivalent Schedules与Serial Schedule等价，这样的 schedule 称为Serializable Schedule

冲突操作

如果两个操作来自不同的事务，他们都在操作同一个数据并且至少其中一个是写操作，那么这两个操作是冲突的

Read-Write Conflicts
- 会得到一个不可重复的读，读同一个数据对象多次得到的结果不同
Write-Read Conflicts
- 会导致脏读：一个事务读到了被另一个事务写了但还没有提交的数据
Write-Write Conflicts
- 对导致更新丢失：一个事务覆盖写了另一个没有提交的事务的数据

通过上述的冲突，可以证明一个操作的调度是否可串行化

串行的类型也有很多等级：

Conflict Serializability（所有数据库都在努力做到这个）
- 冲突等效（Conflict equivalent）：如果两个执行调度包含了相同事务的相同操作，并且有相同的冲突，那么这两个调度就被称为冲突等效的
- 如果某个执行调度S和某个真正串行的执行调度冲突等效，那么它就是冲突可串行化的（conflict serializable）
- 如果一个调度S经过交换位于不同事务里，时间上连续，并且两者之间不构成前面说的那三种冲突的操作在时间序列上的位置后可以转换为串行的调度，那么它就是冲突可串行化的
- 验证 Conflict Serializability 可以使用
  - 基于交换的方法，不过当系统中事务过多的时候，这种方法复杂度太高
  - 依赖图方法，如果一对冲突操作中 $T_{i}$ 事务里的 $O_{i}$ 操作先于 $T_{j}$ 事务里的 $O_{j}$ 操作执行，那么就在依赖图中画从 $T_{i}$ 指向 $T_{j}$ 的一条有向边，如果最终图是无环的，则验证为 Conflict Serializability
View Serializability：基于观察的可串行性说的就是通过观察来确定某个执行调度是可串行还是不可串行，它与冲突可串行性相比，对执行调度的要求要更加宽松，但目前还没有DBMS能实现它

持久性 Durability

事务的持久性要求事务提交的所有更改必须被写入存储介质持久化，并且不能有更新只进行一半的情况，也不能有事务失败之后更新被残留的情况

一致性 Consistency

数据库中的所反映出的外部世界应该是逻辑上正确的，而且我们对数据库所执行的查询的结果也是逻辑上能讲的通的（A给B转100块钱，A扣100，B加100，A和B的总和不能变）。笔者认为，这也可理解为，事务中的一系列内部操作结束之后invariants不能被破坏

LEC 16 两阶段并发控制

我们需要一种方式来保证在不提前知道整个调度的时候执行调度是正确的（例如：产生序列化的结果）

一种方式是使用锁来保护数据库对象

系统自动的对对象上锁、解锁
保证执行结果与一些顺序执行是等价的

在事务T1访问A之前，先通过DBMS的锁管理器（Lock Manager） 获取A的锁并且注册（记录下来“A的锁当前归T1所有”），之后事务T2想访问A，于是也要获得A的锁，锁管理器便会拒绝它的请求，T2之后便阻塞在这里，直到T1完成了对A的全部操作后通过锁管理器释放A的锁，T2才可以通过锁管理器获取A的锁，并且完成对A的全部操作后释放A的锁

Lock 保护的不是具体的数据结构，而是数据库级别的抽象，例如一个 tuple 及与其有关的索引

Lock 的类别

S-LOCK：读的共享锁
X-LOCK：写的独占锁

带锁的事务执行的过程：

事务获取对应的锁
锁管理器授权或阻塞事务
事务释放锁
锁管理器更新其内部锁表，锁表记录着什么锁被什么事务获取着，以及哪些事务在等待什么锁

两阶段锁（2 PL）

二阶段锁是一个悲观的并发控制协议，它规定了一个事务在运行的过程中如何跟其他事务之间协调锁，从而实现可串行化。使用两阶段锁不需要提前知道完整的执行调度，它会在调度进行的过程中避免不可串行化的情况发生

两阶段锁的两个阶段：

阶段 1: Growing
- 每个事务向 lock manager 请求其所需要的锁
- lock manager 给予/推迟锁请求
- 这个阶段不能释放锁
阶段 2: Shrinking
- 事务在释放它的第一个锁之后马上进入 Shrinking 阶段
- 事务在 growing 阶段完成之后不能够获取/升级锁
- 只允许事务释放/降级它之前获得到的锁，它不能申请新的锁

使用 2 PL 协议后，相应的执行调度对应的依赖图一定是无环的，2 PL 可以严格地保证冲突可串行化

但是二阶段锁也有一个问题——级联回滚（Cascading Aborts）

（SS2PL）严格二阶段锁

如果一个被某个事物写的对象不回被其他事物读到或覆写直到这个事物完成，则说明一个调度是严格的

级联回滚本质上的原因是T2事务在T1事务更新得到的临时版本的数据上进行了操作，那我们可以通过一些手段让T2不在T1修改得到的临时版本上进行操作：比如说，可以让事务先获取各个需要获取的锁，等到它commit时再一次性把这些锁释放掉，这样的话，T2就不可能在临时版本上进行操作，因为当T2能获得锁执行事务时，和它访问共享数据的其他事务已经被提交了。这个方法也被称为严格二阶段锁（Strong Strict 2PL，简称SS2PL）

SS2PL 可以解决脏读的问题

二阶段锁中的死锁问题

有两个方法可以解决死锁

死锁检测

DBMS 内部维护一个 waits-for graph，它记录了当前所有的并发事务里谁在等待谁的锁，DBMS 会周期性地检查这个图，看看图里如果有环的话就想办法把环解开

当 DBMS 检测到了一个死锁，它会选择一个 victim 事务，让它回滚（要么重启要么中止，取决于业务）

死锁检测的频率和事务等待的时间之间要做 trade off选择哪个事务 victim 也有讲究

回滚 victim 有两种方式：

完全回滚：回滚整个事务，然后通知应用它被中止了
部分回滚（savepoints）：DBMS 回滚一个事务的一部分，然后尝试重新执行没有完成的查询

死锁预防

死锁预防是预防死锁的发生，当一个事务试图去获取另一个事务已经持有的锁的时候，DBMS 会中止其中一个来防止死锁

死锁预防算法会给每个事务赋予一个优先级，规定越早开始的事务优先级越高，然后通过以下的两种手段来预防死锁：

Wait-Die:
- 高优先级事务向获取低优先级事务已经获取的锁时，它将等待低优先级的事务去释放锁
- 如果低优先级事务向获取高优先级事务已经持有的锁，那么这个事务将直接被 abort，然后回滚
Wound-Wait:
- 高优先级事务向获取低优先级事务已经持有的锁时，持有锁的低优先级事务会直接 abort 并释放锁，低优先级事务想获取高优先级事务已经持有的锁时，它会等待高优先级事务释放这个锁
因为死锁预防被 abort 重启的事务将保持它原有的优先级，防止这个事务被饿死

Lock Hierarchy

获取 locks 是一个比获取 latchs 昂贵非常多的操作，如果我们只让一个锁对应一个数据对象，那么一个要更新多行的事务，就要尝试去获取非常多的 locks

因此，我们可以让 DBMS 来决定一个事务获取锁的粒度（列？行？页？表？）

理想情况下，DBMS 应该要决定该事务需要的最小数量的锁，但这是一个并发度和开销之间的 trade off

更少的锁，更大的粒度
更多的锁，更小的粒度

Intention Locks

在 Hierarchy 的情况下，如果要获取一个 table 的 lock，就要检查它里面所有 tuple 的锁的情况，如果扫了一遍发现最后一个 tuple 被其他事务锁住，就不能执行，这非常低效。

Intention Locks（意向锁）可以解决这样的问题，对 table 这样更高层级的对象的锁赋予模式（shared，exclusive），如果一个树中的一个节点被上了意向锁，就说明有事务显式地对其子节点上了锁，但是意向锁不是真正的锁住了这个节点，只是一个标记

Intention-Shared(IS)：子节点中有某个节点被其他事务上了共享锁
Intention-Exclusive(IX)：子节点中有某个节点被其他事务上了排他锁
Shared+Intention-Exclusive (SIX)：以该节点为根的树被上了共享锁，并且其子节点被上了排他锁

意向锁协议

要获取S锁或者IS锁，事务必须至少获取了其父节点的IS锁
要获取X，IX或者SIX锁，事务必须至少获取了其父节点的IX锁

T1可能是带着一个谓词去寻找符合的tuple，然后更新

因为要读整个R表，所以需要给它上S锁，又因为需要更新某些tuple，所以要给这些tuple上X锁，进而需要先给R表上IX锁，因此要给R表上SIX锁，并且读表的时候不需要给tuple上S锁，因为已经给整个表上了S锁

T2 点查询需要给某个tuple上S锁，因此需要先给table上IS锁，SIX和IS可兼容

由于遵守了严格二阶段锁协议，在T1事务和T2事务结束之前，图中这些锁都不能释放，T3到达时，由于要全表扫描，因此需要给table上S锁，但由于SIX和S不兼容（本质上是IX和S不兼容，内部有tuple正在更新时不能读表），所以它要阻塞等待，直到T1释放它所持有的所有锁

LEC 17 时间戳顺序并发控制

二阶段锁协议（2PL）有一个不可避免的缺点：锁的存在会导致并行性能下降，因此二阶段锁属于一种悲观的并发控制方法：总是假设可能出现数据竞争，因此总是给共享的对象上锁

而基于时间戳顺序的并发控制（T/O）则是一种乐观的方法：给每个事务一个时间戳，根据事务的时间戳来决定它们的顺序以及出现出现冲突时应该如何处理。

T/O 并发控制

如果 $T S (T_{i}) < T S (T_{j})$ ，那么 DBMS 必须保证执行调度与顺序执行（ $T_{i}$ 先于 $T_{j}$ 执行）等价。

时间戳分配

系统/墙时钟：系统时钟并不准确（每隔一段时间和服务器通信进行同步）
逻辑计数器：本地的逻辑计数器
混合方法：对于分布式系统来说，由于存在网络延时，逻辑计数器变得不可靠，因此存在系统时钟和逻辑计数器混合使用的方法

基础时间戳顺序并发控制

事务读写对象不加锁
数据库中的所有对象（例如 tuple）维护两个时间戳，一个读时间戳 $R - T S (X)$ ，一个写时间戳 $W - T S (X)$ ，分别表示这个对象上次被读/写的时间戳
每次操作之前要检查时间戳，如果事务发现尝试操作一个拥有更高时间戳的对象，事务就 abort 并重启。不能操作未来的数据

读

如果 $T S (T_{i}) < W - T S (X)$ ，abort $T_{i}$ 并且以一个更新的时间戳重启
否则：
- 允许 $T_{i}$ 读 $X$
- 更新 $R - T S (X)$ 为 $M a x (R - T S (X), T S (T_{i})$
- 把对象从数据库拷贝一份到事务本地，保证对 $X$ 的可重现的读

写

如果 $T S (T_{i}) < R - T S (X)$ 或 $T S (T_{i}) < W - T S (X)$ ，abort 并重启
否则：
- 允许 $T_{i}$ 写 $X$ 并且更新 $W - T S (X)$
- 把对象从数据库拷贝一份到事务本地，保证对 $X$ 的可重现的读

在例子 2 中，如果我们不让 $T_{1}$ 的 $W (A)$ 写入数据库，而是缓存在事务本地，随后的 $R (A)$ 也只读本地的值，这个执行调度的结果和串行化一样，并且 $T_{1}$ 不用 abort，这个优化就是托马斯写规则

如果当前事物写共享对象的时候，它的时间戳早于这个对象的读时间戳，那么就表明：未来有事务读取这个对象当前的值，那就不能让当前事物进行对这个共享对象的写操作，因此需要abort当前事务；但是如果仅仅是当前事务的时间戳早于共享对象的写时间戳，这就表明未来有事务会修改这个共享对象的值，那么其实当前事务不对这个对象进行写操作也没事，因为这等效于当前事务完成了写操作但写的结果在未来被覆盖了

如果不考虑托马斯写规则带来的优化，基础T/O协议会生成冲突可串行化的执行调度，

它的优点是没有采用锁，因此不可能构成死锁
但也有一个问题：较长的事务（比如说有几百条SQL语句）有可能会饥饿，因为很有可能它执行了一段时间之后，想要访问的数据都是被比它更“年轻”的事物修改过的，那它只能abort，重启之后又迎来同样的结局...
basic T/O 的执行调度是不可恢复的（如果一个长事务运行了很久之后发生异常要重启，这不可完成，因为在它运行的过程中，可能有很多短事务已经读取了它写入的数据）
basic T/O 在读任何数据的时候都要往本地拷贝一份，这回带来不小的开销
所以通常 basic T/O 协议是作为构建 OCC/MVCC 的 blocks

Optimistic Concurrency Control (OCC)

DBMS 为每个事务创建一个私有的 workspace

任何事务的读会拷贝进 workspace
修改会在 workspace 中执行
当事务提交的时候，DBMS 会比较两个 workspace 的写集合，来判断是否与其他事务存在冲突
如果没有冲突，写集合会被实装到全局的数据库里

OCC 分为三个阶段：

读阶段：跟踪事务的读写集合，并且将它们的写存在本地私有的 workspace 里，这个阶段称为读阶段是因为数据库在这个阶段是只读的
校验阶段：当一个事务准备提交时，将它完成的数据更新与其他事务相比较如果校验通过则进入下一阶段，否则 abort 重启
写阶段：将事务本地记录的更新提交到数据库中。实现OCC的DBMS一般会在写阶段锁全表，除了当前事务以外没有其他线程可以修改数据库，也就不能多个事务并发地写，虽然这牺牲了并发性，但由于前面已经准备好了要写的数据，所以写操作的时间并不长，因此开销可以接受。OCC策略下数据库中的对象只有写时间戳，先进入校验阶段的事务会先拿到较早的时间戳，在进入校验阶段之前事务都没有自己的时间戳

OCC 校验

当事务调用commit的时候就进入了校验阶段，然后会给它分配一个时间戳，校验时DBMS要保证serializable的原则：执行调度的结果等效于时间戳早的事务在时间戳晚的事务之前串行发生，因此它会检查RW冲突与WW冲突，判断相应的Dependency Graph有没有成环

向后校验

即向已经发生过的事务校验，如果依赖图中出现了环，则 abort 当前提交的事务

向前校验

即向未来的事务校验，只会校验与还没有执行完的事务重叠的部分，因为此时两个事务都还没 commit，因此可以选择其中一个 abort

OCC 比较适合冲突很少发生的时候（其实所有的乐观协议设计都是这个假设）：

所有的事务都是只读的（理想情况）
不同事务访问的对象没有交集

如果数据库非常大，而且负载不是倾斜的（没有热点数据），那么冲突就很少发生，这个时候上锁就是浪费性能

OCC 的缺点：

OCC 也要拷贝数据到本地
校验阶段是很复杂的，容易构成性能瓶颈
写阶段通常要给数据库上一把大锁，容易形成瓶颈
Aborts 相对于 2PL 来说更加浪费，因为 abort 只发生在事务执行结束之后，而 2PL 有死锁检测可以在中间就 abort

动态数据库

二阶段锁和基础T/O以及OCC其实都没有处理insert/delete时的并发问题

幻读：第二次读到了第一次读的时候不存在的东西

幻读问题有以下三种解决方案：

Re-Execute Scans: 记录下来事务所有可能出现幻读的地方（像查最大值，平均值，最小值这些涉及到范围扫描的操作），为了防止察觉不到有其他事务在扫描完成后再向表里插入新数据，在事务提交之前会再执行一遍前面所记录的所有扫描
Predicate Locking(谓词锁)：对于含有where clause的SQL语句：给select语句对应的谓词加共享锁，给update/insert/delete语句对应的谓词加独占锁
索引锁：如果谓词已经构建了索引，就可以给索引上锁，如果没有索引，就可以（1）给每个页上锁，防止该谓词状态改变（2）给整张表上锁，防止有该谓词的记录被添加或者删除
1. Key-Value Locks：
2. Gap Locks：间隙锁，锁上那个将要访问的 key 和它的下一个 key
3. Key-Range Locks

LEC 18 多版本并发控制

隔离级别

如果我们顺序执行，那么就不用考虑并发的问题，也没有一致性的问题，但这样也会损失性能。

因此我们可能需要一个更弱的一致性来提高病发，这就是隔离级别——我们通过控制一个事务暴露给其他事务的部分来提高并发。

脏读
不可重复读
幻读

上述现象将隔离级别从弱到强分为：

READ UNCOMMITTED：上述所有都有可能发生，和上面一样，但是允许脏读（完全没有 S 锁）
READ COMMITTED：幻读和不可重复读有可能发生，和上面一样，但是 S 锁会被立即释放
REPEATABLE READS：只有幻读有可能发生，和上面一样，但是不需要索引锁
SERIALIZABLE：执行时需要获取所有的锁，包括索引锁，包括严格的 2 PL

多版本并发控制（MVCC）

DBMS 对于一个逻辑的对象维护多个物理的版本

当一个事务写某个对象时，DBMS 创建一个该对象的新版本
当一个事务读某个对象时，它读这个事务开始时该对象的最新版本
当一个事务开始的时候，DBMS 会对数据库做一个快照（拷贝事务状态表）
DBMS 使用快照来决定哪个版本对该事务可见

MVCC 的优势包括：

只读的事务可以不用获得任意类型的锁就读到一个一致的数据库快照
- 可以看到所有在该事务启动之前提交的数据
- 如果两个事务更新同一个对象，则第一个写会成功，第二笔写需要等到第一笔写提交之后再提交（通过检查 txn status table）
可以很方便地实现 time-travel queies，即针对以前的某个时间点的数据库状态作查询

MVCC 的实现里会维护一个版本的开始和结束时间戳，以及一个全局的事务状态表，便于事务之间互相查询

但是光靠 MVCC 是无法实现串行化的，因为 T2 对数据的更改并不是基于在 T1 更改的基础上的（两个事务分别对同一个旧版本的数据进行了更改）

MVCC 的设计

并发控制协议

单靠 MVCC 无法实现可串行化，因此通常和以下的协议结合在一起：

Timestamp Ordering：给每个事务一个时间戳来决定串行顺序
Optimistic Concurrency Control：
- 三阶段协议
- 私有的新版本更新空间
Two-Phase Locking：事务通过获取物理版本的锁来实现更新他们的逻辑版本

版本存储

DBMS 使用 tuple 的指针来建立一个包含各个版本的链表，索引会指向链表的头节点

方案 1：仅追加写存储：版本之间混合在同一个表里，每次更新的时候，将一个最新版本的数据添加到表的空余空间上
- 把新版本放在表尾，追加新版本的时候开销小，但是想要读取快照的时候开销就大了
- 把新版本放在表头，读取相应版本的时候开销小，但是追加新版本的时候维护链表开销大，还要更新索引
方案 2: Time-Travel Storage：单独建立一个额外的表用于存储历史数据（time-travel table），每次更新的时候，DBMS 将旧版本的数据拷贝到 main table 中然后更新，main table 中的 tuple 的指针指向 time-travel 表中的历史版本
方案 3: Delta Storage：不是拷贝整个数据项而是写一个增量更新的段，但是查找的话就需要对增量段作恢复

垃圾回收

如果任何 active 状态的事务都看不到某个历史版本，就可以把它删除
如果某个事物创建了某个版本，但是这个事务最后回滚了，那么这个历史版本也可以删除

垃圾回收的两种实现：

Tuple 级别
- 一个后台线程周期性地对表做扫描，可以维护一张 dirty map，仅对上次扫描之后被修改过的页做扫描
- worker 线程在遍历历史链的时候识别出来垃圾
事务级别
- DBMS对每个事务会记下来它读/写了哪些东西，除此之外还会记录因为这个事务所进行的更新所导致的历史版本）
- DBMS便可以在一个事务过期了（out of scope）之后把这些东西都删除

索引管理

主健索引：主键索引总是指向版本链的 head，主键索引的更新是更新指向的物理地址，需要完成一次删除和一次插入的操作
二级索引：key 都是那个列的值，value 可以是：
- 逻辑指针：比如主键/行 id 的值，这样查询就需要回表，这样插入新版本后只需要更新于维护主键索引中的指针
- 物理指针：记录的是物理地址，不需要回表，但是在插入新版本之后需要修改/维护二级索引里面的指针
- 或者维护一个 tuple id -> 物理地址的中间表，版本更新的时候更新中间表就可以了

LEC 19日志系统

故障级别

事务级别的故障：数据库不可避免的，由于死锁检测或者可串行化检测或者是用户主动发起而不得不回滚的事务
系统级别的故障：
1. 软件异常：DBMS 或者 OS 的 bug
2. 硬件故障：断电等引起的，非易失性介质不会丢失数据
3. 存储介质故障：无法修复的硬盘故障，数据铁定丢了，DBMS 不用考虑这个级别的故障

Buffer Pool Policies

根据还未提交的事务是否被允许覆盖写非易失性介质中的数据对象分为 STEAL 和 NO-STEAL

根据事务提交之前是否需要把所有的更新持久化道非易失性介质中分为 FORCE 和 NO-FORCE

No-Steal+Force

No-Steal+Force策略下，事务的更新操作会申请一个新的页，这个页只包含自己的更新，然后在提交之前持久化到硬盘上

[p] 这种策略很容易实现，回滚时不需要做 Undo 操作，故障恢复时也不需要做 Redo 操作，因为被确认的更新已经持久化到了硬盘上
[c] 这种策略也有一些问题：
- 刷盘操作过多，每次 commit 的时候都有 IO，用户需要等待
- 事务在提交之前所有读写的页都要 pin 在 buffer pool 里，否则被踢出就破坏了事务的原子性，全表扫描这种操作会受到缓存池大小的限制

Shadow Paging

shadow paging 是 NO-Steal+Force 策略的一个实现，DBMS 写时复制页创建两个版本

Master：包含所有已经提交事务的数据
Shadow：在 Master 之上增加未提交事务的数据变动
正在执行的事务都只将修改的数据写到 shadow copy 中，当事务提交时，再原子地把 shadow copy 修改成新的 master，即将 DB Root 覆盖为为指向新的 shadow page table。为了提高效率，DBMS 不会复制整个数据库，只需要复制有变动的部分即可(COW)。
在 Root 覆盖之前，shadow page 的任何内容都不属于数据库
Root 覆盖之后，shadow page 的任何内容都属于数据库

[p] 实现 Redo 和 Undo 相对容易：
- Undo：直接删除 Shadow pages 就好
- Redo：根本不需要，因为确认更新之前所有的更新都已经进行完成了
[p] 新的 shadow page 在事务执行的过程中可以被刷到磁盘中，其他事物看不到这些页，因此可以支持大于 buffer pool 的更新
[c] 磁盘 I/O 次数也随之增多了，并且 commit 的开销变得更大：
- commit 的时候需要一次性刷很多盘下去
- 小更改也需要拷贝一整个页，不经济
- 需要垃圾回收，因为之前的 master 页就不在有效了，并且垃圾回收会产生碎片/空穴
[c] 只支持一个 writer 或者一个 batch 的事务
[c] shadow paging 会在 DBMS 中引发很多随机写，因此后来有了 WAL

Steal+No-Force

WAL（预写日志）

DBMS在把用户所修改过的缓存池中的页刷入磁盘之前，它需要先把预写日志写入磁盘中的日志文件，也就是说先完成预写日志的持久化，再完成缓存池里 dirty page 的持久化

WAL 的每一条日志内容包含以下的信息：

事务 id
对象 id
旧值（undo log）：如果有 append-only 的 MVCC 则不需要
新值（redo log）

MySQL 会将 undo log 和 redo log 分开存储在不同的文件里，undo log 可以单独用来实现 MVCC

group commit
数据库系统中，磁盘I/O的开销是非常巨大的，如果每提交一个事务就要进行一系列的磁盘I/O，那么性能不是太好。不妨让用户多等待一会儿，把多个事务的日志攒到一起提交（第一个到达的事务执行到commit时先阻塞住，然后多攒几个要commit的事务，之后一次性地把它们的日志全部刷入磁盘，然后同时将“事务成功提交”返回给所有等待着的用户

WAL的格式

物理日志：记录每一个页具体到字节级别的变化（类似 git diff），记录了某个 page 某个偏移量的数据的变化
- 物理日志的缺点是体积非常庞大
- DBMS 整理由于删除产生的碎片的时候会导致偏移量发生变化，进而导致了维护物理日志的开销
逻辑日志：记录事务执行的操作，例如事务的每一条 SQL 语句
- 逻辑日志回放的时候需要重新执行一遍事务，比较耗时
- 有的事务会有一些带状态的操作（例如获取当前的时间），或者在并发执行的时候，调度序列也会对数据库状态产生不一样的影响，换句话说，逻辑日志不具有可复现性
Physiological：大体上和物理日志类似，但是记录的是某个 slot 而不是某个 page 的某个偏移量

Checkpoint

磁盘中的日志如果不清理的话会越来越大，并且恢复的时候需要从头开始一遍，checkpoint 允许把之前的日志都清理掉，并且恢复的时候只用回放 checkpoint 之后的日志即可

暂停所有的查询
将 WAL 中的记录刷盘
将 buffer pool 中所有的脏页刷盘
记录一个 checkpoint 到 WAL 中并刷盘
恢复查询