关系模型与关系代数 Relation Model & Relation Algebra

**数据库管理系统 Database Management System（DBMS）**允许应用程序存储和分析数据库中的信息的软件，通常支持根据某种数据模型定义、创建、查询、更新、管理数据库

数据模型 data model 是描述数据库中的数据的概念的集合

模式 schema 是使用给定数据模型，对特定数据集合的描述

关系型数据库的发明者——Codd

关系 relation 是包括了表示实体的属性关系的无序集合

元组 tuple 是关系中属性值的集合，类似于行

主键 primary key 唯一地指定了一个 tuple

外键 foreign key

数据操作语言 Data Manipulation Languages（DML）：从数据库中存取信息的方法，有程序性的（关系代数）和非程序性的

关系代数 relational algebra：

  • σpredicate(R)\sigma_{predicate}(R)：类似于过滤器
  • πA1,…,An(R)\pi_{A1,\dots, An}(R)：投影，可以改变属性的顺序和操作值
  • (R⋂S)(R \bigcap S)：交
  • (R⋃S)(R \bigcup S)：并
  • (R−S)(R-S)：差
  • (R×S)(R \times S)：笛卡尔积
  • (RS)(R S)：两张表中有一个或多个共同的属性值的元组

这种代数定义了顺序，我们需要从更高维度使用声明式语句，例如 SQL

现代 SQL Modern SQL

IBM 发明了 SQL(Structured Query Language)，因为其巨大的影响力，最终成为了标准

SQL 经常在更新

聚合 aggregate：只能在 SELECT 输出列表中使用，如

SELECT COUNT(*) FROM student;

GROUP BY：将 tuple 分组，对每个子集计算聚合：

SELECT AVG(s.gpa), e.cid FROM enrolled AS e JOIN student AS s ON e.sid = s.sid GROUP BY e.cid;

HAVING：类似于对 GROUP BY 的 WHERE：

SELECT AVG(s.gpa), e.cid FROM enrolled AS e JOIN student AS s ON e.sid = s.sid
GROUP BY e.cid HAVING AVG(s.gpa) > 3.9;

SQL 标准并不是强制的，不同数据库实现的不同，例如对于字符串，有的只支持 '，有的则都支持；还有大小写敏感等

窗口函数：对每个 tuple 的某个属性施加一个函数，类似于 map，有一些特殊的，如

  • ROW_NUMBER() 当前行
  • RANK() 当前行顺序
  • OVER() 指示如何将 tuple 组合到一个

嵌套查询：

SELECT name FROM student WHERE sid IN (SELECT sid FROM enrolled);

有一些关键词：ALL、ANY、IN、EXISTS

LATERAL 操作符可以让嵌套查询引用在它之前的其他嵌套查询的参数，相当于 for 循环

WITH ... AS 类似于创建了一张临时的表，是嵌套查询的替代：

WITH cteName AS (SELECT 1)
SELECT * FROM cteName;

数据库存储 Database Storage

DBMS 的主要存储位置在非易失性硬盘上，其组件管理在非易失性和易失性存储的数据移动

磁盘的随机访问速度比顺序访问速度慢，所以一般想要最大化顺序访问

如果直接使用 mmap，则有以下的问题：

  • 转移安全
  • I/O 停滞
  • 错误处理
  • 效率低

故通常自己管理，而不是交给 OS

存储管理器用于管理数据库的文件，通常将文件组织为页 page

页是固定大小的数据块，每个页都有一个唯一的 id，DBMS 需要把 page id 映射到物理位置

数据库中页的大小通常为 4KB，8KB，16KB 等

管理磁盘上的页文件的方法：

堆文件：以随机顺序存储的页的无序集合，需要维护特殊的也来追踪数据库文件中的数据页（同步），同样记录的每个页的空余槽和空页等元数据

页目录

每个页都有一个 header，包括了页大小、校验和、压缩元数据、Schema 信息等，有的系统的页是自我包含的

页的布局方式：

面向元组存储 tuple-oriented storage：

面向元组存储

插槽页 slotted page：把槽映射到 tuple 的起点偏移

插槽页

DBMS 为每个 tuple 分配了一个记录 id 表示其物理位置，注意物理位置可能会改变，所以应用程序不应该依赖于这种 id

使用 header 中的 bitmap 来标记页中的 tuple 的某些属性为 NULL

日记结构存储 log-structured storage：维护改变 tuple 的记录日志（每条日志代表一个 tuple PUT/DELETE 操作）

写非常容易，但是为了读给定 id 的 tuple，DBMS 需要维护把 tuple id 映射到日志记录的索引

日志结构存储

需要周期性地将页压实来减少空间浪费，因为很多旧的数据没有用了

压实后，记录的时间顺序已经不重要了，所以可以基于 id 给页排序来提高未来的查找效率，叫做 Sorted String Tables（SSTables）

合并较大的 log 文件来生成较小的文件：

除此之外，这种方法的缺点还有写入放大

索引组织存储 index-organize storage：tuple 基于 key 在页中排好序

因为 tuple 就是字节序列，所以 DBMS 需要将这些字节解释为属性类型和值，其目录中包括了用于找到 tuple 布局的 schema 信息

tuple 需要字长对齐，方法有

  • 填充：添加 0
  • 重新排序：调整顺序（通常仍然需要填充）

数据的表示通常有：

  • INTEGER、BIGINT、SMALLINT
  • FLOAT/REAL、NUMERIC/DECIMAL
  • VALCHAR/VARBINARY、TEXT/BLOB
  • TIME/DATE/TIMESTAMP、INTERVAL

对于 NULL 数据类型，最常见的方法是在 header 里面存储一个 bitmap 来指明哪些属性是 null

对于存储一个大于一页的值，使用分离的 overflow 存储页

溢出页

有的系统可以在另一个外部文件中存储一个大的值，但是 DBMS 不能操作外部文件的内容

存储模型和数据库压缩 Storage Models & Database Compression

数据库的工作负载：

  • 联机事务处理 On-Line Transaction Processing（OLTP）：每次只读/更新一小部分数据的快速操作
  • 联机分析处理 On-Line Analytical Processing（OLAP）：每次读许多文件以计算聚合的复杂查询
  • 杂交事务 + 分析处理：以上两者的结合

数据库工作负载

注意到关系模型并没有指明必须把一个 tuple 的所有属性存到一个页中，所以对不同的工作负载可以有不同的布局

N 元存储模型 N-ary Storage Model(NSM)：一个 tuple 的所有属性连续地储存在一个页中，即“行存储”，利于 OLTP

解耦存储模型 Decomposition Storage Model(DSM)：所有 tuple 的一个属性连续地存储在一个属性中，即“列储存”，利于 OLAP

DSM 的 tuple 识别：

  • 固定长度的偏移量
  • 潜入 tuple id

变长数据：字段压缩 dictionary compression，将变成数据转换为固定长度的值

但是，OLAP 基本上不会只访问一张表的一列，所以仍然需要以列布局存储数据以获得存储 + 执行的收益

分割属性 Partition Attributes Across(PAX)：在一个数据库页中垂直分割属性，是一种杂交存储模型

将行水平分割为组，然后竖直将其属性分割为列

PAX

注意到 I/O 通常是 DBMS 的瓶颈，可以压缩数据以提高数据 I/O 的利用率，当然，代价就是提高了 CPU 的花费，但对于硬盘上的文件来说，通常是值得的

压缩的目标：

  • 固定长度的值
  • 尽可能在执行时延迟解压
  • 必须是无损的

压缩的粒度：块、tuple、属性、列级别

运行长度编码 run-length encoding：把一列的相同数值压缩到三元组（值，起始位置，数量）中，需要智能排序以获得更好地的压缩率

运行长度编码

运行长度编码

位打包 bit packing：如果一个 integer 属性的大小小于更定的数据类型的范围，可以减少需要表示每个值的位

位打包

大部分编码 mostly encoding：bit packing 中，有时会出现较大数的情况，需要以原始形式存储

大部分编码

位映射编码 bitmap encoding：bitmap 中的第 i 位关联 tuple 中的第 i 条，只有在基数很低的情况下使用

位映射编码

delta 编码 delta encoding：记录相同列中的值的差，可以同 RLE 结合获得更好的压缩率

delta 编码

字典压缩 dictionary compression：将值转化为固定长度的编码并维护一个从编码到原始数据的映射（字典），也是最常用的方法

字典压缩

字典结构

  • 数组
  • Hash 表
  • B+ 树

数据库内存 & 磁盘 I/O 管理 Database Memory & Disk I/O Management

  • 空间控制：在磁盘的哪里写页，目标是使在磁盘上的页物理上尽可能近
  • 时间控制：何时将页读入内存，何时写进磁盘，目标是最小化从磁盘上读数据的停滞

面向磁盘的数据库系统

缓冲区组织 buffer pool organization

内存区域组织为固定大小的页数组，每个数组项叫帧 frame。当 DBMS 请求页时，一个复制被放到帧中，dirty pages 被缓存，不会立刻写回磁盘（写回缓存）

buffer pool 的元数据：

  • 页表跟踪当前内存中的页（通常是固定大小的被 latch 保护的 hash 表）
  • dirty flag
  • pin 计数器：跟踪有多少 works 需要该页保留在内存中，防止被逐出
  • 访问跟踪信息

缓冲池的元数据

lock

  • 从其他事务中保护数据库的逻辑内容
  • 在事务期间维持
  • 需要能够回滚改变

latch 类似于 mutex，是一个较低级的概念

  • 从其他线程中保护 DBMS 内部数据结构的关键部分
  • 在操作期间维持
  • 不需要能够回滚改变

分配策略

  • 全局策略
  • 局部策略

多重缓冲池 multiple buffer pool，选择 buffer pool 的方法：

  • 在 record id 中嵌入对象识别符
  • 对页 id 使用 Hash

预获取 pre-fetching：对于顺序或索引扫描，可以预先获取页

扫描共享 scan sharing：允许多重询问附着到一个扫描表的游标上

扫描共享

缓冲区旁路 buffer pool bypass：顺序扫描操作不会在缓冲池中存储获取的页

缓冲区替换策略 buffer replacement policies：决定要驱逐哪个页

最近最少使用 least-recently used：维护每页最后访问的时间戳，选择最旧的时间戳对应的页逐出

最近最少使用

钟 clock：不需要额外的时间戳的近似 LRU，每页都有一个引用位，当被访问时，设为 1。把页组织为一个环，有一个指针，当指到 0，则逐出

注意到以上两种方法都易受顺序洪水影响，即在 OLAP 中，通常最近最多使用页是最佳的逐出的页

LRU-K：通常是 LRU-2

近似方案：把 LRU 链表分为两——新的和旧的

  • 新页总是插入旧列表的头部
  • 当旧列表中的页被访问时，插入到新列表头部

本地化 localization：DBMS 基于 query 选择逐出的页

优先提示 priority hints：DBMS 提示缓冲池某页是否重要

脏页 dirty page：

  • 快速路径：如果某页不 dirty，则可以直接丢弃它
  • 慢速路径：如果某页 dirty，则必须写回磁盘

后台写 background writing：周期性地遍历页表写回 dirty 页到磁盘

注意到 OS 会重排合并 I/O 请求以最大化磁盘带宽，但不知道哪个 I/O 请求更重要

大部分 DBMS 会还用直接 I/O 来旁路 OS 缓存以防止多余的页复制等

fsync 错误

哈希表 Hash Tables

常用的 Hash 函数：Facebook XXHash

静态哈希策略：

  • 线性探针哈希
    • 对于删除操作，在被删除的地方放置一个特殊的“墓碑”
    • 非唯一的键，一般将重复的键存在哈希表中
  • 布谷鸟哈希
    • 多个哈希函数

需要预先了解要储存的元素数量，否则需要重建哈希表

链式哈希

布隆过滤器 Bloom filter：回答所有权的概率数据结构（位图）

  • false negative 不会出现
  • false positive 可能出现

可扩展哈希 extendible hashing：维护跟踪下一个分裂的 bucket 的指针，任何 bucket 溢出时，分裂指针位置的 bucket。使用多重哈希找到所给 key 的哈希位置

如果最高的 bucket 空了，可以移除

线性哈希 linear hashing：相当于分裂 bucket 而不是无限增加 list 长度的链式哈希

B+ 树索引 B+ Tree Indexes

泛化的二叉搜索树

性质：

  • 完美平衡
  • 除了根以外的所有结点至少半满
  • 每个 k 个键的内部结点有 k+1 个非空子结点

在实现中，兄弟结点间有指针

叶结点的值：

  • 记录 id
  • tuple 数据

B+ 树相比 B- 树，区别在与只在叶结点存值，内部结点只用于导航搜索过程

插入时可能会分裂，删除时可能会合并

重复键：

  • 添加记录 id
  • 溢出叶结点

聚类索引 clustered index：表以主键顺序存储

可变长度键：

  • 指针
  • 可变长度结点
  • 填充
  • 键映射

内部键搜索：

  • 线性
  • 二分
  • 插值

优化：

  • 前缀压缩 prefix compression：相同叶结点中的排好序的键通常有相同的前缀
  • 重复删除 deduplication：非唯一的索引可能在相同的叶结点中存多份，故只需一个键 + 值列表
  • 后缀截断 suffix truncation：内部结点的键只用于导航，故不需要整个键，只需要前缀
  • 指针交换 pointer swizzling：如果一个页被 pin 在缓冲池了，则可以直接储存原始指针而不是页 id，省去了查询页表
  • 大块插入 bulk insert：建立新 B+ 树时先给键排好序
  • 写优化 B+ 树 write-optimized B+ tree：不是立即应用更新，而是在内部结点中存储修改日志，即 Bε- 树，当日志存不下时，级联向下更新

并发索引 Concurrent Indexes

Lock：

  • 保护数据库的逻辑内容
  • 在事务期间维持
  • 需要回滚改变

latch

  • 保护内部数据结构的关键部分不被其他线程破坏
  • 在操作期间保持
  • 不需要回滚改变

latch 模式

  • 读模式
  • 写模式

哈希表 latch 非常容易，因为所有的线程都向同样方向移动，一次只访问一个 page，故不存在死锁

方法：page latch 或 slot latch

B+ 树较麻烦，需要

  • 获取父结点 latch
  • 获取子结点 latch
  • 如果父结点安全，则释放
  • 其中“安全”指不会分裂或合并
    • 未满
    • 超过半满

注意到如果是写，则会锁上根结点，但绝大部分情况都不会导致分裂，故积极地假设使用读 latch，若猜测错误，重复遍历

因为所有获取 latch 的顺序都是从上到下的，故很好

排序 & 聚合算法 Sorting & Aggregation Algorithms

无法假设查询的结果能够存入内存，因此算法应该最大化顺序 I/O

Top-N 堆排序：ORDER BY + LIMIT 的查询，只需要找到 top-N 个元素

外部归并排序：将数据分成 run，单独排序，并组合成更长的排序好的 run

使用 BB 个缓冲页，生成大小为 BB 的 run ⌈N/B⌉\lceil N / B \rceil 个，然后合并 B−1B-1 个 run

pass 的次数 = 1+⌈log⁡B−1⌈N/B⌉⌉1 + \lceil \log_{B-1}\lceil N / B \rceil \rceil

总 I/O 花费 = 2N⋅pass 数2N \cdot \text{pass 数}

比较优化：

  • 代码特殊化
  • 后缀截断

如果恰好有一个 B+ 树索引，则可以用于加速

  • 对于团簇的 B+ 树，全都是顺序访问，无计算花费
  • 非团簇，很差

外部哈希聚合

  • 划分：用 hash 键将元组划分到 bucket 中，慢的时候写回磁盘
  • 重哈希：对每个划分建立内存中的哈希表并计算聚合

Join 算法 Join Algorithms

假设较小的表是左边的表（外部的表）

数据：

  • 早期实例化：将外部和内部的 tuple 的值复制到新的输出 tuple 中
  • 晚期实例化：只复制记录 ID

花费分析的关键是 IO 数

分块嵌套循环 join：

for block B_r in R:
	for block B_s in S:
		for r in B_r:
			for s in B_S
				if r and s match, emit

如果有索引，则可以优化：

for r in R:
	for s in Index(r_i = s_j)
		if r and s match, emit

排序-归并 join

哈希 join：可以使用 Bloom filter 优化

其中 Hash join 通常是最优的

查询执行 Query Execution

处理模型 Processing model 定义了执行查询的计划

  • 迭代模型 iterator model：每个程序计划操作符实现了 Next() 函数，也叫做火山或流水线模型，一次发射一个元组，最常用
  • 物化模型 materialization model：每个操作一次处理所有输入，一次输出，即将输出物化为一个结果，通常用于 OLTP
  • 向量化模型 vectorization model：类似于迭代模型，但是每个操作符都发射一捆元组而不是一个元组，可以与 SIMD 等使用

计划处理方向

  • 从顶向下
  • 自底向上

访问方法：

  • 顺序扫描
    • 数据跳过：近似查询（有损），区域地图（无损）（预先计算 MAX 等该区域的数据特征）
  • 索引扫描
  • 多索引扫描：取多个索引扫描结果的交集

修改查询

万圣节问题：由于更新操作改变了某元组的物理位置，导致一次扫描操作符多次访问了该元组，因此需要在每次查询时跟踪修改的记录 id

表达式求值：把 WHERE 语句表达为一个表达式树

这种做法比较慢，故更好的方法是直接对表达式求值，即 JIT 编译

并行查询执行 Parallel Query Execution

并行 vs 分布式

worker 代表客户端执行任务

处理模型

  • 每个 worker 一个进程，老的 DBMS 都使用这种方案，因为那时还没有 POSIX 标准，线程非常混乱
  • 每个 worker 一个线程，几乎所有较新的都使用这种方案

调度：

SQL Server 中有 SQLOS，用于取代系统调用

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

inter-query 并行：允许多个查询同时执行，但对于更新操作不便使用，故不常用

intra-query 并行：并行执行一个查询的操作符，通常是生产者/消费者范式

改变操作符：

  • gather：从多个 worker 中将结果组合成一个输出流
  • distribute：将一个输入流分裂为多个输出流
  • repartition：重分配

Bushy 并行：相当于前两种方法的混合版本

通常 I/O 是瓶颈，故可以考虑 I/O 并行，通过 RAID 配置

查询计划 & 优化 Query Planning & Optimization

由于找到“最优”的方法是 NP-Complete，故没有优化器真的生成了“最优”计划

优化器生成了将逻辑算术表达式映射为最优等价的物理算术表达式

物理操作定义了一个特定的执行策略

总体结构

逻辑计划优化

分裂连结谓词

谓词下推

替代笛卡尔积

投影下推

对于嵌套的子查询，可以重写或解耦合查询

表达式也可以重写

花费估计

谓词 P 的 selectivity 是满足的 tuple 的比例

这种方法有几个假设：

  • 均匀数据
  • 独立的谓词
  • 互斥的原则

统计用普通的直方图太浪费了，可以使用等宽的直方图或等深的直方图

同样分为自顶向下和自底向上优化

并发控制理论 Concurrency Control Theory

基于 ACID 性质的事务

事务 transaction 是对一个数据库的一个或多个操作序列来执行某种高层次的函数

是 DBMS 中的基本改变单元，部分事务不允许

DBMS 只会关心数据是怎么读/写到数据库中的，因此从数据库的角度看，事务由一系列的 R/W 组成

SQL 中的事务以 BEGIN 开头，以 COMMIT 或 ABORT 停止

  • 如果 commit，则保存所有更改或 abort
  • 如果 abort，则撤销所有更改，使得事务未执行过

正确性的准则：ACID

  • Atomicity：要么全部发生，要么全都不发生
    • log
    • shadow pagin
  • Consistency：如果每个事务一致，DB 开始也是一致，则结束一致
  • Isolation：每个事务的执行和其他事务孤立
    • 消极：一开始就不让问题发生
    • 积极：假设冲突很少见，在发生后处理
  • Durability：如果一个事务提交，则效果会保持

调度的性质：

  • 串行调度：不会交替不同事务的操作
  • 等价调度：对于数据库的状态来说，和前者等价

只有 R-R 是不冲突的，其余情况都会冲突

两种不同等级的串行：

  • 冲突串行
  • 视图串行——无法做到

当且仅当依赖图是无环的时，该调度是可冲突串行的

调度

数据库中的二阶段锁 Two-Phase Locking in Databases

使用锁 lock 来保护数据库对象

最常见的两种锁类型：（不同的数据库有不同的更多种类的锁）

  • S-Lock：共享锁
  • X-Lock：互斥锁

由 lock manager 来管理授予和更新锁

2 PL 的两个阶段：

  • 增长 grow：授予/拒绝 lock 请求
  • 收缩 shrink：释放/降级之前获取的 lock，不能获取新的 lock

2PL

严格限制的 2PL：只有在事务结束后才允许释放 lock

严格限制的2PL

新的调度

两种处理死锁的方法：

检测

  • 创建等待图，周期性地检测该图中的环
  • 当检测到死锁时，会选择一个受害者事务回滚以打破环
  • 权衡：检测死锁的频率和等待死锁破坏的事务长度

预防

  • 当事务尝试获取另一个事务的 lock 时，杀死其中一个
  • 基于时间戳分配优先级
    • old wait for young：高优先级的等待获取 lock，反之中断
    • young wait for old：高优先级的中断低优先级的以释放 lock，反之等待

lock 的粒度：并行性和开销的权衡

数据库lock层次结构

意图锁 intention lock：允许在不需要检查所有后代结点的情况下给高级别结点上锁

  • Intention-Shared(IS)：显式指明较低层次有共享 lock
  • Intention-Exclusive(IX)：显示指明较低层次有互斥 lock
  • Shared+Intention-Exclusive(SIX)：子树是共享模式，但是较低层次有互斥 lock

意图lock

时间戳排序并发控制 Timestamp-Ordering Concurrency Control

2 PL 是消极的处理方式，而时间戳排序 Timestamp Ordering(T/O) 是积极的

如果 TS(Ti)<TS(Tj)TS(T_i) < TS(T_j)，则必须保证等价于 TiT_i 在 TjT_j 之前调度

基本 T/O

  • 读
    • 如果 TS(Ti)<W−TS(X)TS(T_i) < W-TS(X)，则违反了时间顺序，TiT_i 必须重启
    • 否则更新 R−TS(X)R-TS(X) 为最大值
    • 对 TiT_i 建立本地的 XX 复制以确保可重复读
  • 写
    • 如果 TS(Ti)<W−TS(X)TS(T_i) < W-TS(X) 或 TS(Ti)<R−TS(X)TS(T_i) < R-TS(X)，则违反了时间顺序，TiT_i​ 必须重启
    • 否则更新 W−TS(X)W-TS(X)
    • 对 TiT_i 建立本地的 XX 复制以确保可重复读

Thomas 写法则 Thomas Write Rule：对于写，如果 TS(Ti)<W−TS(X)TS(T_i) < W-TS(X)，则忽略该 write，继续执行，尽管违反了时间戳顺序

显然，由于复制数据的较高开销和长时间运行的事务可能饿死，没有数据库会使用这种方法

积极并发控制 Optimistic Concurrency Control(OCC)：对每个事务创建一个私有工作区，所有读的对象复制到该工作区，修改也应用于工作区

当事务提交时，比较工作区来了解是否和其他事务冲突，如果没冲突，则写集合被安装到全局数据库中

OCC 阶段：

  • 读阶段：跟踪事务的读/写集合并将写存储到私有的工作区中
  • 验证阶段：当事务提交时，检查是否和其他事务冲突
  • 写阶段：如果验证成功，则将私有改变应用于数据库中

对于验证阶段，有两种验证方法：

后向验证

前向验证

写阶段：

  • 串行提交：全局 latch 来限制一个事务
  • 并行提交：以主键顺序获取 latch 以避免死锁

到此为止，都是在解决静态数据库，即只支持读/写，但事实上还有插入、删除等问题，会引起幻象 phantom 问题

多版本并发控制 MVCC Multi-Version Concurrency Control

解决幻象问题的方法：

重新执行扫描：跟踪事务执行的所有查询的 WHERE 语句，在提交后，重新执行每个查询的扫描部分，检查是否生成了相同的结果

预期上锁：对 WHERE 语句中的 predicate 上锁

索引上锁：

  • 键-值上锁：对索引中的一个键值对上锁，对于不存在的值需要虚拟键
  • 间隙上锁
  • 键范围上锁
  • 层次结构上锁

隔离级别（从高到低）：

  • serializable：无幻象、所有读都可重复、无 dirty read
  • repeatable reads：幻象可能发生
  • read committed：幻象和不可重复的读可能发生
  • read uncommitted：都可能发生

从数据库的角度来看，是

  • serializable：一开始获取所有的 lock，加上索引 lock 和严格 2PL
  • repeatable reads：无索引 lock
  • read committed：S lock 立即释放
  • read uncommitted：允许 dirty read（无 S lock）

绝大部分数据库默认隔离级别是 READ COMMITTED，如 Postgres，但最高通常都支持 SERIALIZABLE

DBMS 维护一个数据库中的逻辑对象的多重物理版本

  • 当事务写一个对象时，创建新的版本
  • 当事务读某个对象时，读事务启动时的最新版本

MVCC 的好处在于 write 不会阻止 read，read 不会阻止 write，也很容易支持时间旅行查询

MVCC

快照隔离 SI：当一个事务开启时，其看到了数据库的一致的快照，但会出现写偏斜异常 write skew anomaly

写偏斜

写偏斜正确情况

版本存储：使用 tuple 的指针域来对每个逻辑 tuple 创建一个版本链，索引通常指向链的 head

只追加存储

版本链的排序：

  • 旧到新：查找时需要遍历链
  • 新到旧：必须对每个新版本更新索引指针

时间旅行存储

delta存储

垃圾收集：

tuple 级

后台吸尘器

协助清理

事务级：

索引管理

二级索引：

  • 逻辑指针
  • 物理指针

数据库日志 & 影子分页 Database Logging & Shadow Paging

事务失败有多种原因，如逻辑错误、内部状态错误

undo：移除未完成或中断的事务的效果

redo：重新应用已提交的事务的效果以求持久化

steal 政策：是否允许一个未提交的事务覆盖最近已经提交的对象的值

  • steal：允许
  • no-steal：不允许

force 政策：是否要求所有事务的更新在事务提交之前反映到非易失性存储上

  • force：要求
  • no-force：不需要

no-steal + force 是最容易实现的，因为既不需要 undo，也不需要 redo

影子分页 shadow paging：写时复制创建两个版本：

  • master：已提交事务的改变
  • shadow：未提交事务的临时改变

事务提交时只需要交换 master 和 shadow 指针，缓冲池使用的政策是 no-steal + force

预写日志 Write-Ahead Log 是现在最常用的方法，DBMS 在刷新对象到磁盘之前将改变写到日志文件中，缓冲池使用的是 steal + no-force

对每个事务写一个 <BEGIN> 记录在开始时，完成时写一个 <COMMIT> 记录，并确保在向应用返回确认时所有的日志记录都被 flush

每条日志项包含了对一个对象的更改：

  • 事务 id
  • 对象 id
  • 之前的值（undo）
  • 之后的值（redo）

缓冲池政策对比

日志方案

为了防止 WAL 无限增长，DBMS 周期性地使用检查点来讲所有缓冲刷新到磁盘上

阻塞检查点协议：

  • 停止所有查询
  • flush 所有内存中的 WAL 记录
  • flush 所有 dirty page
  • 写一个 <CHECKPOINT> 项并 flush 到磁盘
  • 恢复查询

ARIES 数据库恢复 Database Recovery with ARIES

每条日志记录都有一个全局唯一的日志序列号 log sequence number(LSN)

名字 位置 定义
flushedLSN 内存 磁盘上记录中最后的 LSN
pageLSN 页 该页最新的更新
recLSN 页 从该页上一次被 flush 以来最后一次更新
lastLSN 事务 该事务的最后一条记录
MasterRecord 磁盘 最近的检查点的 LSN

事务提交：

  • 一个事务 commit 时，在日志中写一条 COMMIT 记录，确保所有直到该记录的日志都 flush
  • 该 commit 成功时，写一条特别的 TXN-END 记录到日志中（不需要立即 flush）

还需要一个域该事务之前的 LSN prevLSN，相当于维护了一个链表，能够更容易遍历记录

补偿日志 compensation log record(CLR) 描述了 undo 一个之前更新的记录的动作

除了所有更新日志记录的域以外，还有 undoNext 指针（下一个 undo LSN）

因为 DBMS 不会等待日志记录被 flush 就通知应用事务中断了，所以才会有 CLR

综上，中止算法：

  • 写一个 ABORT 记录
  • 反向分析更新，对每条更新记录
    • 写 CLR（CLR 不需要 undo）
    • 恢复原有的值
  • 写 TXN-END 并释放 lock

活跃事务表 active transaction table(ATT)：

  • txndId：唯一的事务标识
  • status：当前事务的模式
    • R->运行中，C->提交中，U->候选 undo
  • lastLSN：事务创建的最近的 LSN

在 TXN-END 记录后移除

dirty page table(DPT)：缓冲池中改变了还没有 flush 到磁盘中的页

fuzzy checkpoint：当系统为检查点写日志记录时，活跃的事务仍可以运行

  • CHECKPOINT-BEGIN：指示检查点开始
  • CHECKPOINT-END：包括 ATT 和 DPT

在检查点开始之后的事务不会出现在 CHECKPOINT-END 记录的 ATT 中

CHECKPOINT-BEGIN 的 LSN 在完成时被写到 MasterRecord 中

ARIES 恢复阶段

  • 分析：从 MasterRecord 开始识别 dirty page 和活跃的事务
  • redo
  • undo

ARIES

分析阶段：

  • 从最后成功的检查点开始扫描，如果发现 TXN-END 记录，从 ATT 中移除
  • 其余记录：
    • 如果不在 ATT 中，添加状态 UNDO
    • 在提交中，改变状态为 COMMIT
  • 对于更新日志记录：如果页不在 DPT 中，则添加到 DPT 中，设置 recLSN

redu 阶段：

  • 从 DPT 中包括最小 recLSN 的记录开始，对每条更新记录日志或 CLR，redo 动作，除非
    • 不在 DPT 中
    • 在 DPT 中，但记录的 LSN 小于页的 recLSN

redo 一个动作：

  • 重新应用日志中的更新
  • 设置 pageLSN 为该日志记录的 LSN
  • 无额外记录，也没有 force flush

在 redo 阶段的结尾，给所有状态 C 的事务写 TXN-END 日志记录并从 ATT 中移除

undo 阶段：

  • ATT 中 U 状态的事务
  • 反向顺序，使用 lastLSN 加速
  • 为每次修改写 CLR

介绍分布式数据库 Introduction to Distributed Databases

相比并行 DBMS ，分布式 DBMS 通信的开销和问题不可忽略

系统架构

其中共享磁盘是最常见的

同构 vs 异构结点

数据对应用透明

数据库划分：逻辑 vs 物理

  • 原始表划分
  • 竖直表划分
  • 水平表划分（最常见）

一般的哈希在添加了新的结点后需要全部重新哈希，一致哈希可以极大地减少变化：

一致哈希

事务协调：中心化 vs 去中心化

分布式事务数据库系统 Distributed Transactional Database Systems

原子提交协议：

二阶段提交

优化：在准备好后早期确认

Paxos 则只需要大部分结点都完成即可

Paxos

spanner 类似，但是在不同的组之间使用 2PC

spanner

K-safety：至少有 K 个结点可用，否则停止执行

多Paxos

复制品配置：

  • 主要复制品
  • 多重复制品

传播方案：

  • 同步
  • 异步

传播时间：

  • 连续
  • commit 时

CAP 定理：Consistency，Availability（有的坏了，仍能使用）和 Partition tolerant（通信出问题）无法兼顾

CAP定理

分布式分析数据库系统 Distributed Analytical Database Systems

star schema

snowflake schema

即 snowflake 反范式化 denormalize 更彻底，需要的空间更少，查询的复杂度更高

push（将查询发送给数据）vs pull（将数据拉取到查询）：一般都使用 push

查询计划分段：通常生成一个查询计划，然后分成特定划分的片段

查询计划分段

分布式 join

供应商可以提供 Database-as-a-Service(DBaaS)

无服务器 serverless 数据库

嵌入式数据库逻辑 Embedded Database Logic

听起来很不错，但没什么人用

优点：

  • 更少的网络延迟
  • 不需要重新实现功能

用户定义函数 user-defined function(UDF) 是由应用程序开发者定义的扩展系统功能的函数（只读）

缺点：一般会被视为黑盒子，很难优化

存储过程 stored procedure 是自我包含的执行更多复杂逻辑的函数（可以修改表结构）