Lecture 15: Concurrency Control Theory

主要介绍了并发控制的原理

Transaction Managment

首先是一些常见的数据库事务上会出现的并发问题：

比如对于以下一系列操作：

1
2
3
4
5

Read(A)
Check(A > 25)
Pay(25)
A = A - 25
Write(A)

• 如果执行到A = A - 25的时候，突然发生了断电，那么很有可能银行就收不到钱（这个其实和恢复系统有关系）
• 如果某个人同时执行了两个相同的该操作，则如果他们同时从数据库中读取了A=100，最终A会变成75（即少扣了25）

最基础最笨拙的解决这些问题的方式就是让数据库将所有的事务排成一个队列依次执行，只有当前一个事务执行完毕、数据写会，再执行下一个事务，但是这样就会丧失数据库的并发性，还会占用大量的存储（因为我们需要把整个数据库文件进行复制）

因此我们需要数据库支持并发控制，并且在此基础上要保证数据的正确性和公平性

Transaction

在正式开始之前，需要明确一下事务的定义。从正式一点的定义上来说，数据库是由一组组固定的命名对象A、B、C组成的，而事务就是对这些对象的一系列处理（比如说读写、插入、删除）

以Sql语言为例，事务的起点会显式地用BEGIN来表示，而结束一般由成功的提交（COMMIT）或者报错（ABORT），如果事务提交，数据库会保存事务所做的所有修改（或者引发报错）；而如果事务报错，那么所有修改都将不复存在，数据库会进行回滚操作

Correctness Criteria：ACID

事务的正确性标准被称为ACID

• 原子性（Atomicity）：事务是一个不可分割的工作单位，事务中的操作要么全部成功，要么全部失败
• 一致性（Consistency）：事务必须使数据库从一个一致性状态变换到另外一个一致性状态
• 隔离性（Isolation）：多个事务并发执行就像事务单独执行一样并不会相互影响
• 持久性（Durability）：持久性是指一个事务一旦被提交，它对数据库中数据的改变就是永久性的，接下来即使数据库发生故障也不应该对其有任何影响

Atomicity

事务只有两种可能的输出：提交和报错，要么完成所有的修改，要么所有的修改都不执行

那么该如何保证原子性：

Logging

日志技术几乎在所有的DBMS中都会被使用到，其中有UndoLog（回滚未提交的操作）和RedoLog（执行已经提交的操作）

DBMS在日志中按照顺序记录了事务所作出的所有修改，然后Undo所有报错事务已经执行了的操作

Shadow Paging

在事务执行之前，DBMS首先复制相关的page，让事务修改其中的数据，当且仅当事务正确提交之后，这些page才会对外可见

Consistency

如果 DBMS 在事务开始之前是 consistent，那么在事务执行完毕后也应当是 consistent

比如对于一个银行所使用的数据库，至少钱的数值不能小于100，如果a有90块钱，他想转100给b，此时，事务提交之前符合数据库的规则，但是在提交之后就不符合了，那么此时事务就不能够提交，这就是所谓的一致性

• 数据库一致性：数据库中的数据是对现实世界中的模拟，并且满足约束的规则

• 事务一致性：事务执行前后数据库均满足一致性

Isolation

用户提交事务，不同事务执行过程应当互相隔离，互不影响，每个事务都认为只有自己在执行

并发控制协议

为了达到并发执行事务的目的，我们需要并发控制协议，包含两种锁

• 乐观锁：假设事物之间的冲突是罕见的，当冲突发生之后再进行处理
• 悲观锁：事务执行时获取需要的锁，这样不会导致冲突的发生

事务并发顺序的正确性

为了保证结果的正确性，并发执行的顺序必须等同于某种串行的顺序

• Serial Schedule：不同事务之间没有重叠，串行执行
• Equivalent Schedules：对于任意数据库起始状态，若两个调度分别执行所到达的数据库最终状态相同，则称这两个调度等价
• Serializable Schedule：如果一个 schedule 与事务之间的某种 serial execution 的效果一致，则称该 schedule 为 serializable schedule

事务冲突

两个不同的事务指向了同一个对象，如果其中一个对对象有写操作，则会产生冲突

• 读写冲突：事务先A读取某行数据、事务B后修改该行数据，和事务B先修改某行事务、事务A后读该行记录两种schedule。事务A读到的结果不同。这种冲突可能会导致Unrepeatable Read（不可重复读，两次读取的数据可能不一样）和Dirty Read（脏读，一个事务读取了另一个事务还没有提交的数据）
• 写读冲突：读未提交（脏读）
• 写写冲突：Lost Update（更新丢失，一个事务将另一个事务的未提交的数据覆盖）

冲突串行化

冲突的串行化执行可以通过一定的转换为某种串行化的结果

• 两个 schedules 在 transactions 中有相同的 actions，且每组 conflicting actions 按照相同顺序排列，则称它们为 conflict equivalent
• 一个 schedule S 如果与某个 serial schedule 是 conflict equivalent，则称 S 是 conflict serializable
• 如果通过交换不同 transactions 中连续的 non-conflicting operations 可以将 S 转化成 serial schedule，则称 S 是 conflict serializable

什么是消息队列（MQ）

顾名思义，将消息以队列的形式缓存，生产者（producer）和消费者（consumer）分别使用队列的两个端口进行消息的收发

核心能力

消息队列有两个核心能力：解耦和削峰

• 解耦：

  如果没有消息队列，那么在一次业务流程中，上游的http或者rpc发出请求之后，下游的消费者需要马上进行反馈，否则整个流程就会一直阻塞，这即浪费时间，又浪费CPU性能

  因此我们需要一个能够持久化存放请求的容器，这就是消息队列的解耦——将生产者和消费者的应用进行解耦

• 削峰

  如果在某一时刻，生产者给消费者生成了大量的请求，而消费者无法一次性全部消费，那么会产生消息的丢失

  而有了消息队列，就可以分批次处理数量过多的请求

基础要求

作为消息队列组件，需要满足一些要求：

• 消息不丢失

  很好理解，毕竟如果消息易失，那么有没有消息队列就都没太大区别了，这一方面可以分为三个部分来看待：

  • 生产者将消息投递到MQ的时候不出现丢失
  • 消息存放在MQ时不丢失
  • 消费者从MQ消费消息时不出现丢失

  针对第二点，各个MQ组件基本都是基于数据落盘+数据备份的方式来完成的

  而对于第一第三点，则是通过两个交互环节中的ack机制保证的，譬如生产者向MQ中投递消息，如果没有收到MQ的ack返回确认，那么生产者就应当一直投递这个消息给MQ；另一方面，消费者也需要避免接收重复的消息，所以对于下游的消费者，同样需要具备消息幂等去重的能力

• 支持消息存储

  就像前面提到的，MQ至少需要支持一定规模的数据的存放，而且这种存放需要持久性，能够让消费者自由选择时间进行消费操作

流程类型

根据消费者的消费流程，MQ可以被分为两种类型：

• Push型：

  指当生产者将消息投递到MQ时，由MQ主动将消息以推送的方式发送给各个订阅了的消费者

• Pull型：

  当MQ中存在消息时，由消费者主动执行拉取消息的操作来获取消息

两种类型各有优劣，实际操作中需要按需取舍

如何用Redis实现消息队列

Redis虽然是一种非关系型数据库，但是其部分数据结构是能够支持实现消息队列组件的

可能存在的问题

首先需要指出可能存在的一些问题

• 存储昂贵

  由于Redis是基于内存实现的缓存中间件，所以存储消息容量的限制比较大

• 数据丢失

  • 由于Redis是基于内存实现的缓存中间件，所以不可避免地会产生丢失数据的风险（比如断电和宕机），虽然有rdb/aof这种持久化机制，但是无法做到百分百安全

  • 此外，Redis走的是ap高可用流派，数据的主从复制流程是异步的，主从切换时数据存在弱一致的问题

Redis List

具体方法

一种比较容易想到的思路就是使用Redis的List结构，这是一个双向链表，天然契合MQ的队列模型，只需要使用LPUSH和RPOP进行消息的投递和读取即可

这种方法的缺点也是显而易见的：如果生产者生产消息的速度赶不上消费者的消费速度，那么消费者使用RPOP拉取消息的时候就会立刻返回空值nil，也就是说，需要消费者不断轮询地访问，这种高频的自旋对于CPU是一种无用的损耗；另一方面，如果让消费者每次轮询之后休眠一段时间，那么可能会导致消息处理不及时，也是我们不希望看到的情况

最理想的方案是：在List中有数据到达时，消费者马上能够意识到，并且处理数据，此外始终保持睡眠状态，也就是阻塞态

因此，我们可以使用Redis中的BRPOP指令来代替RPOP，即可弥补上述的缺点

1

BRPOP my_topic 0

其中topic后面的数字代表阻塞等待时长，达到此阈值仍未获取数据时会返回nil；如果设置为 0 ，则代表没有这个超时限制

局限性分析

尽管解决了阻塞问题，List仍然不能算是一个合格的消息队列组件，原因如下：

• 无法支持发布/订阅模式

  显然List的消费者和生产者是一对一的，因为数据在POP出去之后就不复存在，只此一份，如果我们有多个消费者，每个都需要消费者所生产的数据，那么List就束手无策了

• 无法支持消费端ack机制

  当消费者出现了宕机等意外，没有一种有效的手段告诉MQ消息处理失败的反馈，在这种情况下，一旦数据POP，就真的完全丢失了

Redis pub/sub

为了解决无法支持发布/订阅模式的问题，Redis提供了pub/sub机制，全称为publisher/subscriber

具体方法

pub/sub模式会在两者之间建立一个用于实时通信的信道channel，在传递消息时，会根据channel查找到所有建立订阅关系的subscriber，一一传送消息

操作指令为：

发布者：publish topic_name message

比如：publish my_new_message 今天天气怎么样

订阅者：subscribe topic_name

订阅者会使用阻塞模式进行监听，解决了List方法中的CPU浪费问题

这里解释一下背后的原理：

• 首先，消费方 subscriber 通过 subscribe 指令建立和指定 channel 之间的订阅关系. 这时在 redis 中会维护好 channel 和对应 subscriber 列表的映射关系，并在内存中为每个在线活跃的 subscriber 分配好一个缓冲区 buffer，用以承载后续到来的消息数据
• 接下来随着 publisher 执行 publish 指令，往对应 channel 中投递消息后，此时 redis 会实时查看 channel 对应 subscriber 名单，往每个 subscriber 的缓冲区 buffer 中推送这条数据
• 各执行了 subscribe 指令的 subscriber 会处于阻塞监听缓冲区 buffer 的状态，随着新数据到达，subscriber 会获取到这笔数据

基于这个流程，我们能看出来，pub/sub 对于 channel 以及 subscribers 之间的实时映射关系存在强依赖. 因此在操作的执行顺序上，我们需要保证先执行 subscribe 指令，再执行 publish 执行，否则前几笔 publish 投递的数据就会因为不存在 subscriber 而被直接丢弃

优缺点分析

pub/sub模式最大的优点就是实现了发布/订阅能力，然而其缺点也很明显：关于消息丢失的处理

• 缺乏ack机制：

  与List相同，没有ack意味着pub/sub模式依然没有办法提醒发布者消息处理的成功与否，无法执行消息的重放

• 缺乏消息储存能力

  Redis的pub/sub模式相当于golang中的无缓冲型channel，仅仅是维护了channel和subscribers之间的映射关系，每当消息来临，不会停留在channel中，而是直接送往映射的buffer中，所以会出现以下问题：

  • subscriber 宕机：倘若某个 subscriber 中途宕机，则会被踢出名单，在恢复前的这段时间内，到达的消息都会彻底与这个 subscriber 无缘
  • Redis 宕机：每条 publish 的消息都会第一时间分发到 subscriber 对应的内存缓冲区中，而这个缓冲区是完全基于内存实现的易失性存储，一旦 Redis 服务端宕机，缓冲区中的数据就完全丢失且不可恢复了；此外，pub/sub 模式下的消息数据不属于 Redis 中的基本数据类型，因此 redis 中的持久化机制 rdb 和 aof 对于 pub/sub 中的数据是完全不生效的，数据丢失的可能性大幅度提高
  • subscriber消息积压：由于消息数据会被放在 Redis 侧各 subscriber 的缓冲区 buffer 中，这部分空间是相对有限的，一旦某个 subscriber 因为消费能力弱，导致 buffer 中的的数据发生积压，此时 Redis 很可能会自动把 subscriber 踢除下线，于是这部分数据也丢失了

  对于最后这一点，可以在redis.conf文件中配置：

  1	client-output-buffer-limit pubsub 32mb 8mb 60s

  对应的含义是，倘若某个 subscriber 的缓冲区 buffer 大小达到 32MB，则 subscriber 会被踢下线；倘若缓冲区内数据量在连续 60s 内达到 8MB 大小，subscriber 也会踢下线

Redis Streams

操作指令

首先需要介绍一下几个核心的操作指令，所有指令都可以在官方文档中找到：

• 生产消息：

  使用该指令可以向topic中投放一组键值对消息

  1 2	127.0.0.1:6379> XADD my_streams_topic * key1 value1 "1710412272535-0"

  • My_streams_topic：topic名称
  • *：表示该消息自动生成唯一标识id，基于时间戳+自增序列号生成
  • Key1、value1:输入的键值对

• 消费消息：

  使用该指令可以从对应的topic中获取消息

  1 2 3 4 5

  127.0.0.1:6379> xread [BLOCK] [Time] streams my_streams_topic 0-0 1) 1) "my_streams_topic" 2) 1) 1) "1710412272535-0" 2) 1) "key1" 2) "value1"

  • BLOCK：表示是否使用阻塞消费模式
  • Time：如果加入BLOCK参数，那么此处需要填写time表示阻塞等待时间，超过这个时间就会返回nil；设置为0表示不设置超时阈值
  • streams：表示从一个streams对象读取消息
  • my_streams_topic：topic名称
  • 0-0：表示从头开始消费；这里如果填写的是某条消息的id的话，就会从这条消息之后开始消费

此外streams支持发布/订阅模式，可以保证消息被多个消费者组访问

• 创建消费者组：

  1 2	127.0.0.1:6379> XGROUP CREATE my_streams_topic my_group 0-0 OK

  • my_streams_topic：topic 名称
  • my_group：消费者组名称
  • 0-0：从头开始消费

• 基于消费者组消费信息：

  同一份数据在同一个消费者组下只会被消费到一次. 不同消费者组各自能获取到独立完整的消息数据

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

  127.0.0.1:6379> XREADGROUP GROUP my_group consumer1 BLOCK 0 STREAMS my_streams_topic > 1) 1) "my_streams_topic" 2) 1) 1) "1710412272535-0" 2) 1) "key1" 2) "value1" 2) 1) "1710413025712-0" 2) 1) "key2" 2) "value2" 3) 1) "1710413031719-0" 2) 1) "key3" 2) "value3" 4) 1) "1710413036009-0" 2) 1) "key4" 2) "value4"

  • my_group: 消费者组名称
  • Consumer1：消费者名称
  • my_streams_topic：topic 名称
  • BLOCK 0: 采用阻塞等待的模式，0 代表没有超时上限
  • >：读最新的消息 (尚未分配给某个 consumer 的消息)

  此外还有一种消费模式，读取的是已经分配给当前消费者，但是还未经确认的旧消息：

  1 2 3 4 5

  127.0.0.1:6379> XREADGROUP GROUP my_group consumer1 BLOCK 0 STREAMS my_streams_topic 0-0 1) 1) "my_streams_topic" 2) 1) 1) "1710413250364-0" 2) 1) "key5" 2) "value5"

  • 0-0：标识读取已分配给当前 consumer ，但是还没经过 xack 指令确认的消息

  > 与 0-0，两者之间的区别在于，“>”读取新消息，“0-0”读取旧消息

• 确认消息：

  通过 xack 指令，携带上消费者组、topic 名称以及消息 id，能够完成对某条消息的确认操作

  1 2	127.0.0.1:6379> XACK my_streams_topic my_group 1710413250364-0 (integer) 1

  • my_streams_topic：topic 名称
  • my_group：消费者组名称
  • 1710413250364-0：消息 id

优缺点分析

首先是最明显的优点：

• 支持发布/订阅模式

  Redis Streams 引入了消费者组 group 的概念，因此是能够保证各个消费者组 consumer group 均能够获取到一份独立而完整的消息数据

• 数据可持久化

  Redis 中的 streams 和 string、list 等数据类型一样，都能够通过 rdb( redis database)、aof( append only file) 的持久化机制进行落盘存储，能够在很大程度上降低数据丢失的概率

• 支持消费端 ack 机制

  Redis Streams 中另一项非常重要的改进，是支持 consumer 的 ack 能力，consumer 在处理好某条消息后，能通过 xack 指令对该消息进行确认。这样对于没经过 ack 确认的消息，Redis Streams 还是为 consumer 保留了重新消费的能力

• 支持消息缓存

  和 pub/sub 模式不同的是，Redis Streams 中会实际开辟内存空间用于存储 Streams 中的数据，因此哪怕某个 consumer group 是在消息生产之后才完成注册操作，也能够进行消息溯源，从 topic 起点开始执行消息的消费操作

  然而由于Redis是基于内存实现的存储，因此如果消息量过于庞大，可能会造成很大的资源压力甚至out of memory。因此，可以在XADD指令中加上maxlen，显式地设定topic中能缓存的数据长度

  1	XADD my_topic MAXLEN 10000 * key1 value1

  • 最多缓存10000条数据

整体对比

现在对Redis实现MQ的各个方法做个比较：

可以看到，在各项能力上 List 和 pub/sub 互有千秋，而 Streams 可以说是兼具了各方面的优势，称得上是已经趋近于成熟的MQ实现方案

下面我们再进一步拿 Redis Streams 和业界专业的 MQ 组件进行对比

由于Redis Streams在存储上需要使用内存，因此消息存储容量相对有限；且同一个 topic 的数据由于对应为同一个 key，因此会被分发到相同节点，无法实现数据的纵向分治，因此不具备类似于 kafka 纵向分区以提高并发度的能力

因此使用Redis作为MQ的主要优势就在于运维成本低，如果在实际的业务流程中，对于数据的精度没有特别高的要求，那么使用Redis Streams这种轻量化的MQ方案不失为一种好的选择

Lecture 14: Query Planning & Optimization

主要讲了查询的规划以及优化

SQL查询在不同的规划下会有显著的性能上的差异，在先前介绍Join的那一章课已经提到过了

Query Optimization Techniques

需要注意的是，决定优化的方式、规模与执行查询一样是需要占用时间的，所以查询的优化不在于要做到极致（Query Optimization是一个NP-Hard问题），而是在可能的几个计划之中选取折中的一个

• Heuristics/Rules：

  • Rewrite the query to remove stupid/inefficient things

  • Does not require a cost model

• Cost-based Search

  • Use a cost model to evaluate multiple equivalent plans and pick the one with the lowest cost

Logical VS. Physical Plans

其实优化查询无非两个步骤：在逻辑上对操作对象进行编排（比如是Join(A,B)还是Join(B,A)，是否要下移谓词等等）、要选择用哪种方式来优化（比如对于nested loop join，是否要更换为nested index join，sort+limit是否要更换为topn算法等等），这就是所谓的逻辑计划与物理计划

Heuristics/Rules

如果两个关系代数表达式 (Relational Algebra Expressions) 如果能产生相同的 tuple 集合，我们就称二者等价。DBMS 可以通过一些 Heuristics/Rules 来将关系几何表达式转化成成本更低的等价表达式，从而达到查询优化的目的。这些规则通常试用于所有查询，如：

• Predicate Pushdown
• Projections Pushdown

Predicate Pushdown

Predicate 通常有很高的选择性，可以过滤掉许多无用的数据。将 Predicate 推到查询计划的底部，可以在查询开始时就更多地过滤数据

核心思想如下：

• 越早过滤越多数据越好
• 重排 predicates，使得选择性大的排前面
• 将复杂的 predicate 拆分，然后往下压，如 X=Y AND Y=3 可以修改成 X=3 AND Y=3

Replace Cartesian Product

将笛卡尔积替换成Join，不多赘述

Projections Pushdown

在行存储数据库中，越早过滤掉不用的字段越好，因此将 Projections 操作往查询计划底部推也能够缩小中间结果占用的空间大小

需要注意的是这种方法对于列存储数据库是不管用的

Cost-based Search

除了 Predicates 和 Projections 以外，许多操作没有通用的规则，如 Join：Join 操作既符合交换律又符合结合律，等价关系代数表达式数量庞大，这时候就需要一些成本估算技术，将过滤性大的表作为 Outer Table，小的作为 Inner Table，从而达到查询优化的目的

由于需要遍历各种类型的plan来决定最终的选择，所以这里可以简单划分成三种类型的plan：

• Single relation
• Multiple relations
• Nested sub-queries

Single relation Query Planning

对于这类查找，只需要用简单的启发式方法譬如顺序扫描、二分搜索、索引扫描等就够用了

具体来说就是将查询拆分成若干个小块，为每一块都生成一个逻辑运算符，为每一个逻辑运算符都生成一组物理运算符，然后依次迭代构建一棵left-deep join tree（就是类似于哈夫曼树一样的结构，两个节点由join作为父节点），这样可以最小化工作量

这里直接去看课上那个Artist、Album、Appears的例子更加直观，整个搜索的过程就是在不断地[枚举、计算代价]

Multi-relation Query Planning

又分为自顶向下与自底向上两种优化方式，这里重点讲了自顶向下的思路

比如一个操作的目标是A join B join C，这是我们的目标，也是优化的根节点。接下来需要考虑有哪些方法可以得到这个根节点，比如可以选择Hash_Join(A join B, C)或者SM_Join(A join B, C)两者之间选择一个代价更小的（这里假设hash join代价更小），然后继续决策有哪些方法可以得到hash join这个节点

Nested Sub-Queries

有的时候一个查询的嵌套太深，如果对于每一个嵌套都分别优化，而没有一个整体的优化方向的话，最终会导致计划十分低效。因此可以考虑将一个嵌套查询扁平化，或者至少减少其嵌套层数，尽可能水平展开

这就延伸出了两种方法：

• 重写查询，降低语句之间的关联性或者将其扁平化
• 分解嵌套查询，将其结果保存在临时的表中

Rewrite

直接举个例子

1
2
3
4
5
6

select name from sailors as s
	where exists(
		select * from reservers as r
  		where s.sid = r.sid
  		and r.day = '2022.1.1'
)

可以被改写成

1
2
3

select name from sailors as s, reservers as r
	where s.sid = r.sid 
		and r.day = '2022.1.1'

Decomposing Queries

同样举个例子

1
2
3
4
5
6
7
8
9

SELECT S.sid, MIN(R.day)
 	FROM sailors S, reserves R, boats B
		WHERE S.sid = R.sid
 			AND R.bid = B.bid
 			AND B.color = 'red'
 			AND S.rating = (SELECT MAX(S2.rating)
 		FROM sailors S2)
	GROUP BY S.sid
		HAVING COUNT(*) > 1

可以改写成

1
2
3
4
5
6
7
8
9
10
11

SELECT MAX(rating) FROM sailors

SELECT S.sid, MIN(R.day)
 	FROM sailors S, reserves R, boats B
		WHERE S.sid = R.sid
 			AND R.bid = B.bid
 			AND B.color = 'red'
 			AND S.rating = (SELECT MAX(S2.rating)
 		FROM sailors S2)
	GROUP BY S.sid
		HAVING COUNT(*) > 1

毕竟(SELECT MAX(S2.rating)对于整个查询来说只是一个常量

Cost Estimation

一个查询需要花费多长时间，取决于许多因素

• CPU: Small cost; tough to estimate
• Disk: #block transfers
• Memory: Amount of DRAM used
• Network: #messages

但本质上取决于：整个查询过程需要读入和写出多少 tuples

因此 DBMS 需要保存每个 table 的一些统计信息，如 attributes、indexes 等信息，有助于估计查询成本。值得一提的是，不同的 DBMS 的搜集、更新统计信息的策略不同

Statistics

对于任意table R，DBMS都保存了关于R的一些相关信息比如：

• $$N_{R}$$：R中tuple的数量
• $$V(A, R)$$：R中A属性的不同取值的个数
• $$A_{max}, A_{min}$$：A属性的最大值和最小值

利用上面这些数据可以得到R中A属性的每一个值所对应的平均记录个数
$$
SC(A, R) =N_R / V(A, R)
$$
利用以上信息，就可以针对不同的predicate，预估不同的selectivity：

• Equality
• Range
• Negation
• Conjunction
• Disjunction

Equality Predicate

1

select * from people where age = 2

假设people中有5个人，所有的age一共有5个取值，则$$N_R$$=5，$$V(age, people)$$=5：
$$
sel(A = constant) = SC(P) / V(A, R) = \frac{1}{5}
$$

Range Predicate

1

select * from people where age >= 2

则可以利用最大值最小值来估计：
$$
sel(A >= a) = (A_{max} - a) / (A_{max} - A_{min})
$$

Negation Predicate

1

select * from people where age != 2

其实就是Equality Predicate取个补集
$$
sel(not P) = 1 - sel(P) = 1 - SC(age = 2) = \frac{4}{5}
$$

Conjunc Predicate

1
2
3

select * from people 
	where age = 2
		and name like 'A%'

如果两个predicate是相互独立的话
$$
sel(P1 \bigwedge P2) = sel(P1) \times sel(P2)
$$

Disjunction Predicate

1
2
3

select * from people 
	where age = 2
		or name like 'A%'

如果两个predicate相互独立，则有：
$$
sel(P1 \bigvee P2) = sel(P1) + sel(P2) - sel(P1 \bigwedge P2) = sel(P1) + sel(P2) - sel(P1) \times sel(P2)
$$

Lecture 12,13: Query Execution

主要讲了SQL语句查询执行的相关问题

Processing Model

首先是处理模型，定义了数据库中执行查询计划的三种模式，分别是：

• Iterator Model
• Materialization Model
• vectorization Model

Iterator Model

又被称为Volcano Model或者Pipeline Model

• Iterator Model一共有三种基本的接口：Next()、Open()、Close()

• 该计算将关系代数中的每一种操作都抽象为一个operator，将整个SQL语句构造成一个operator树，这样一来，在进行查询的时候会从树顶向下不断调用next函数，而数据则会被自底向上拉取

• 迭代模型的优点：

  • 简单，每个operator可以单独实现逻辑，达到模块化处理，因此市面上有很多数据库都使用了迭代模型比如：SQLite、MongoDB、Impala、DB2、SQLServer、Greenplum、PostgreSQL、Oracle、MySQL

• 迭代模型的缺点：

  • 查询树调用的Next接口次数太多，而且每次调用都指返回一条数据，使得CPU执行效率很低
  • Join、Subqueries、Order by等操作经常会阻塞

Materialization Model

物化模型优化了迭代模型的缺点：对于每一个operator，一次性处理所有的输入，处理完之后将所有结果一次性输出

伪代码看上去和火山模型大差不差，区别只在于每一个operator都会将结果放到一个out列表中，最后进行输出

• 物化模型对于OLTP负载更加友好，因为每一个查询所涉及到的数据范围都是较小的，并且调用的函数更少
• 因此从另一方面来说，物化模型不适用于OLAP负载（因为OLAP涉及到的中间数据太多）

Vectorization Model

向量化模型与火山模型类似，对于每一种operator都要实现一种Next()函数，区别在于，向量化模型返回的是一批tuple，而不是火山模型中的一个tuple，可以简单理解成火山模型与物化模型两者的结合

该模型适用于OLAP数据库，使得中间的结果不需要溢出到磁盘，同时也能够减少Next函数的调用次数

Access Methods

在执行查找的时候，DBMS需要一定的手段去访问叶子结点处的数据

一共可以分为三种方法

Sequential Scan

最容易想到的就是顺序扫描：对于表中的每一个page，DBMS都从缓冲池中对其进行检索，并在此基础上遍历每一个tuple来决定是否要将其作为数据进行返回

• DBMS会保存一个游标（cursor），用来标记其上次访问的page/slot

Sequential Scan : Optimization

尽管顺序扫描是一种比较笨拙的方法，但可能也是我们唯一的选择

然而顺序扫描是可以进行优化的，我们在之前的课中已经接触过一些了，比如：

• Pre-Fetching（Lecture 6）
• Buffer Pool Bypass（Lecture 6）
• Parallelization（Lecture 13）
• Heap Clustering（Lecture 8）
• Late Materialization（Lecture 11）

这节课讲了一个新的方法，Data Skipping

Data Skipping

有两种方法可以实现数据跳过组件：

1. Approximate Queries（Lossy）

   近似查询会首先对整张表做一个抽样，形成一个表的子集，对这个子集执行查询，这样能够得到一个近似的结果

   近似查询是易失性的，这里的易失性应该是指会丢失一些本来应到能够找到的数据

2. Zone Map（Lossless）

   这里重点介绍的方法就是Zone Map法，简单来说就是对于查询涉及到的每一个page，都实现处理出一些聚合属性，比如这个page上的MAX、MIN、AVG、SUM、COUNT，这样在查询到来的时候就能够直接进行比较，判断是否值得花时间遍历这个page，达到加速的效果

   比如现在我们有如下数据，我们要执行select * from table where val > 600，DBMS拿到了查询指令和Zone Map进行比较，发现这个page的MAX值为400，显然整个page的数据都是我们不需要的，那么直接跳过这个page即可

Index Scan

由DBMS来选择一个index来查找tuple（13章会详细解释DBMS根据哪几个方面的来选择index）

• 索引扫描又分为单索引扫描和多索引扫描（Multi-Index Scan），两者的区别和特点从名字就可以看出来，需要知道的是，多索引扫描会根据查询条件，在多个索引上查询结果并且将结果集合做一个并集或者交集

Modification Queries

负责修改数据库中的表以及相关索引的操作称为修改查询，这些查询的输出可以是数据记录的id，也可以是tuple（比如returning）

这里首先介绍了Halloween Problem（万圣节难题）：

譬如在火山模型的数据库中执行更新操作update people set salary = salary + 100 where salary < 1100的时候，会首先根据index，调用Next（）查找出来目标tuple，删除、重新赋值、插入，由此完成更新

然而如果有一个tuple为：（Andy，999），在被更新之后会变成（andy，1099），此时这个tuple的物理位置已经改变，很有可能会被插入到原本位置之后，并且依然满足salary < 1100的条件，所以会被第二次进行更新，变为（Andy，1199），这并不符合我们更新操作的目的

解决办法就是：跟踪所有修改过的记录id

Expression Evaluation

对于Where子句，DBMS会将其表示为一棵表达式树（expression tree），树中的不同结点代表不同的表达式类型例如：比较、析取、连接、算术运算符、常值、元祖属性引用等

还介绍了Prepare子句，类似于函数的功能

这一部分感觉就是普通的介绍，没有做很深入的讲解，看看就行

Scheduler

迄今为止我们所讨论的内容几乎都是基于数据流的角度来看待查询处理模型的，控制流以隐式的形式藏在一系列的查询操作中

而有了scheduler（调度器），我们就可以显式地明确控制流了

以下是个人理解：

面向数据流是一件很复杂的事情，因为你没有办法非常细致地划分数据。比如人脑是没有办法清晰地认知：这一团数据是从哪里来的、要对它做什么、要把它发到哪里去之类的问题

但是面向控制流就会让上述的事情变得很简单明了，是一种抽象程度更高的方法，此外可能对于分布式存储的系统更加友好？因为可以将每一个控制任务push或者pull到远程主机做处理然后再传输回来，比单纯发送数据的方式封装程度更高？

Parallel / Distributed

首先需要区分并行数据库和分布式数据库：

• 首先需要明确的是，对于用户而言，两者是一样的，即对于某个查询返回某种结果，区别在于其内部设计

• Parallel DBMSs：

  • 结点资源在物理上离得很近
  • 结点资源通过高速互联进行通信
  • 通信开销小并且是可靠的

• Distributed DBMSs：

  • 结点资源之间的物理位置相距远
  • 结点资源通过低速互联进行通信
  • 无法忽视结点之间的通信开销

Process Model

过程模型定义了系统将为何种架构以处理并发的请求/查询，其中，Worker负责执行一个单独的任务并且返回结果，是DBMS中的一个组件

而模型的不同点就在于Worker的形式

Process per Worker

第一种形式是进程模型：给每一个Worker都分配一个进程，由OS负责调度，对于一个查询中的每一个operator，都交给一个Worker来负责执行

在线程的思想流行之前诞生的很多数据库都是用了这种模型

优点是：其中一个进程的崩溃并不会影响整个系统的崩溃

缺点是：极度依赖OS的调度，DBMS没有办法做到自行调度工作

Thread per Worker

第二种是线程模型：以线程的形式管理每一个Worker，是如今常用的数据库并行处理模型，DBMS能够主动控制线程的调度，调度算法能够更加灵活

线程相对于进程的区别，即为线程模型相对于进程模型的优点和缺点——减少了进程带来的上下文切换、相比创建/销毁一个进程，创建/销毁一个线程的开销更小、不用管理公共内存；与此同时，一个线程的崩溃也会导致整个系统的崩溃

关于Scheduling

对于每一个查询计划，DBMS都要决定执行的时间、地点和方式

需要考虑这个查询需要用到多少个Worker？需要用多少个CPU？这个查询需要在哪个CPU上处理？输出要保存在哪里？等等问题

因此DBMS知道的内容（比如上下文相关的信息）总是要比OS多一些

Embedded DBMS

最后一种方式是嵌入式，DBMS与应用程序运行在同一地址空间，由应用程序来负责线程和调度（这一部分没怎么看懂）

Inter- VS. Intra-Query Parallelism

这里提出了两种并行化的思想的大概内容，姑且将其翻译为查询内并行性和查询间并行性

Inter-Query

查询内并行性通过允许多个查询同时进行从而提高整体性能

如果查询都是只读的，那么没有必要显式地协调查询与查询之间的先后，必要时，buffer pool可以处理大部分共享

然而如果有多个查询在同时更新数据库，那么将会很难保持正确性，这个问题会在Lecture 15讨论事务相关内容的时候提及

Intra-Query

通过并行执行运算符来提高单个查询的性能，在组织操作符的时候可以参考生产者/消费者模型

每一个operator都有一个并行化的版本

这样可以让多个线程访问集中式的数据结构，也或者使用分区来分工合作

其中操作又可以被划分为横向并行和纵向并行

Horizontal

横向并行，也可以称为操作内并行，将运算符分解为独立的片段，这些片段在不同的数据子集中执行相同的功能

DBMS在查询计划中插入一个exchange操作符，用来合并/拆分多个子操作符/父操作符的结果

即把一个操作分配给多个Worker，每个Worker都执行一部分，最终用exchange算子对结果进行合并

Exchange Operator

exchange算子有三种类型：

• Gather：

  从多个Worker处得到结果，进行合并之后作为一个单独的输出传递给上游

• Distribute：

  将一个单独的输入分裂成多个输出传递给上游

• Repartition：

  将多个输入重新分组成多个输出传递给上游

Vertical

纵向并行，思想类似于CPU的流水线，在运行一个操作的同时，另一个操作也在准备运行，一旦操作1处理完了一道数据就马上发给下一个操作2，因此不会出现类似于物化模型那样一次性传递一个数组的数据的情况

Bushy Parallelism

Inter和Intra-Parallelism的结合，上下游之间的不同部分都可以被划分成一个个独立的部分交给一个或几个Worker来处理

I/O Parallelism

前面从过程模型的角度，介绍了基于并行查询的操作并行性。这里介绍了I/O并行，是一种更加底层的并行方式

对于单设备来说，I/O始终是DBMS的瓶颈，如果能够把I/O任务分配到多个设备中并行处理，那么就能够一定程度上突破这个瓶颈

相关的方法有很多，这里主要介绍了两种：Multi-Disk Parallelism和Database Partitioning

Multi-Disk Parallelism

即数据库文件分布在多个磁盘进行存储

多磁盘并行主要考虑三方面因素：Performance、Durability、Capacity

• 如果是基于硬件实现的多磁盘并行化：

  硬件控制器需要能够支持管理多个设备：例如现在有1～6号page，3个磁盘，那么控制器需要将page按照顺序分配给每个磁盘；或者将每一个page都复制3份到不同的磁盘上

• 如果是基于软件实现的多磁盘并行化：

  需要在文件/对象的级别上使用擦除码，相较于传统的基于硬件实现，更加高效灵活（这一部分没怎么听懂）

无论基于哪种方法实现，数据交换的过程对于DBMS都是透明的

Database Partitioning

将数据库本身拆分成多个不相交的子集，进行分布式存储，这对于应用层而言是透明的

Lecture 11: Join Algorithms

本章介绍了join算法的思想和实现

Join Operator

• 首先是join在底层是如何实现的：这里有两种方式

  例如对于MySql语句：select R.id, S.date from R join S on R.id = S.id where S.value > 100

  • Early Materialization：

    这种方法一开始就将所有我们需要用到的具体数据都读取好放入内存，详细一点来讲就是把R.id和S.data直接作为新的tuple插入表中，这样一来，该查询的所有后续操作都不用再回到磁盘中读取数据

  • Late Materialization：

    与前者相对的，滞后具象方法在一开始只会将匹配到的tuple的Record IDS放入表中，等到上层的操作需要获取数据的时候再去磁盘中拿。这种方法对于列存储的DBMS比较友好，因为最终除了我们需要的数据以外，我们不会读取到任何无关的数据

Join vs. Cross-Product

这里需要进行一下连接操作与笛卡尔积之间的比较：

相对而言笛卡尔积是一种更加低效的方法，因为对于两张大小分别为m和n的表，一次笛卡尔积操作需要用两个for循环来遍历两张表，最终获得一张m*n大小的输出表

例如select * from s cross join e就是一个笛卡尔积操作，最终输出的结果一来没有规律可言，而来耗费时间更长

而select * from s join e on s.id = e.id是一个join操作，输出结果明显会更小更快

Join Algorithms

Nested Loop Join

Naive Nested Loop Join

• 这是最简单的join算法，遍历两个表中的所有tuple，如果两两匹配，则输出

• 显然这是一个糟糕的算法，如果R表有M个page、m个tuple，S表有N个page、n个tuple，则对于一次join，开销将会是$$M + (m \times N)$$

  例如R有1000页，100000个tuple；S有500页，40000个tuple

  那么做一次join的IO次数为：$$1000 + (100000 \times 500) = 50001000$$次

  如果一次IO要0.1ms，那么join一次就要将近1.3小时

  即使使用大小比较小的S表作为outer loop的主体，最终也要近乎1.1小时

Block Nested Loop Join

朴素的循环算法没有充分利用缓冲池，由此引出了块嵌套循环

• 假设我们缓冲区大小为B，则我们使用B-2个缓冲区用来装载外表（即外侧遍历的表），用一个缓冲区装载内表，最后一个缓冲区用来输出，写成伪代码如下：

  1 2 3 4 5

  for each page pR(Belong to R) in range(B-2): for each page pS(Belong to S) in range(1): for each tuple r in pR: for each tuple s in pS: if r matches s then emit

• 这个算法的IO复杂度为$$M + \lceil M / (B-2) \rceil \times N$$

  如果外循环可以完全装入内存：

  加入一次IO要0.1ms，那么总时长只要0.15秒

Index Nested Join Loop

上述两种算法，性能瓶颈在于：对于外循环中的每一个tuple，都需要遍历一次内循环中的tuple来进行判断，因此我们可以使用索引进行优化

• 具体做法为：在关系S的连接属性上建立索引，对于R中的每一个元组，根据索引找到对应的S中元组进行连接
• 假设在索引上查找的代价为C，则IO复杂度为：$$M + m \times C$$

Sort-Merge Join

如果我们手上的两张表都是有序的，那么join工作就会简单很多；如果他们不是有序的，那就可以考虑使用上节课讲到的排序算法让他们变得有序

• 具体流程如下：

  • Phase #1: Sort

    • 对两张表以join所使用到的key作为关键字进行排序

    • 如果内存放不下这么多page，则需要使用外部排序

  • Phase #2: Merge

    • 对两张排好序的表进行配对，这样外循环的元素就不用每次都遍历一遍内循环的元素了
    • 可能会需要根据join的类型进行回溯，这里具体

    比如表R：

    id	name
    100	Andy
    200	GZA
    200	GZA

    表S：

    id	value	cdate
    100	2222	10/4/2023
    100	9999	10/4/2023
    200	8888	10/4/2023
    400	7777	10/4/2023

    当R表遍历到第二行，而S表遍历到第三行时，会输出这组tuple，S表的指针会向下移动到第四行，此时发现R表中仍然有id=200的tuple存在，则需要进行回溯，将指针退回第三行

• IO开销如下：

  Sort Cost(R) : $$2M \times (1 + \lceil log_{B-1}{\lceil M / B \rceil} \rceil)$$

  Sort Cost(S) : $$2N \times (1 + \lceil log_{B-1}{\lceil N / B \rceil} \rceil)$$

  Merge Cost : $$M + N$$

  ->Total Cost : Sort + Merge

  例如R有1000页，100000个tuple；S有500页，40000个tuple

  则一共需要IO次数7500次，如果每次IO需要0.1ms，则一共需要0.75s

• 排序join算法的最坏情况为：如果两张表的所有tuple都一模一样，那么回溯的次数将会大大增加，开销会来到$$(M \times N) + (sort cost)$$

Hash Join

• 哈希join算法也有两个阶段：

  • Phase #1: Build

    首先使用哈希函数h1扫描外层表来获取一张哈希表，其中哈希方式可以任选，只不过在实际应用中，线性探查法是效果最好的

  • Phase #2: Probe

    扫描内层表并且使用哈希函数h1来跳转并且寻找匹配的tuple

Hash Table Contents

对于一张哈希表，我们不仅仅要记录哈希值，还要记录对应的key，以防发生冲突时形成错误的match

此外，有些DBMS还会记录下来tuple的value，这取决于其使用的策略是一开始所提到的Early Materialization 还是Later Materialization

Optimization : Probe Filter

对于Hash Join的一种常见的优化方式是使用Bloom Filter。这是一种概率性的数据结构，存放在CPU的cache中，Bloom Filter会在创建哈希表的时候判断：这个key是否存在于内层表中，他可能会将不存在误判为存在，但不会将存在的key误判为不存在

这样一来，当我们想要进入哈希表进行查找的时候，我们可以首先访问一下Bloom Filter，可以加快join的速度

Partition Hash Join

• 有的时候哈希表没有办法装进内存，这个时候我们可以使用聚类哈希join，大概意思就是在build之前就先对输入的relation进行分类，然后针对每一个partition进行前面提到的hash join算法

• Recursive Partition: 关于这一部分其实有点没太看懂，好像是说要用两个哈希函数来对两个表分别进行递归聚类，然后看tuple是否匹配（？）

• IO开销如下：

  如果我们不使用递归聚类，那么

  Partition Phase: $$2(M+N)$$次IO

  Probe Phase: $$M+N$$次IO

Optimization : Hybrid Hash Join

如果一个表中的key是skewed的（大概意思就是这个key在这个表中非常多），那么DBMS会将这个partition视作热点分区，将其保存在内存而非写回磁盘

Lecture 10: Sorting & Aggregation Algorithms

本章主要介绍了几种排序与聚合算法的思想

Sorting

在关系型数据库中，tuple之间并没有特定的顺序关系，因此在进行诸如group by, distinct, partition by, order by, join之类的操作时，需要对tuple进行排序
如果内存足够放下这些数据，那么使用qsort进行排序即可；然而内存未必能够放下这么多的tuple，因此在这种情况下需要使用external sorting，能够根据需要将排序溢出到磁盘，并且倾向于顺序I/O

Top-N Heap Sorting

• 如果一个查询包含一个带有limit的order by，则DBMS只需要查找到前N个元素即可，也就是使用Top-N Heap Sort。理想情况是将前N个元素放入内存，这样DBMS只需要维护一个优先队列即可

例如我们有以下查询：select * from enrolled order by sid fetch first 4 rows with ties，我们需要输出学号前四小的学生信息，如果学号相同，则并列输出。排序方法如下：

• 首先创建大小为4的堆
• 遍历数据，如果堆未满，则直接放入堆；否则，如果fetch指向的数据已经在堆中，则将堆的大小扩大到两倍（因为要求with ties）并且放入堆；如果该数据不在堆中，则判断是否是我们需要的数据：如果是，则将堆首的相同元素全部pop，放入堆；如果不是，则跳过该fetch

External Merge Sort

Two-way Merge Sort

• 最基本的两路归并排序：在排序阶段从磁盘中读取page到内存，排序结束后写回磁盘；在合并阶段，他使用三个缓冲页——从磁盘中读取两个page到其中两个frame，并且将其合并到第三个frame，每当第三个frame被填满，就会将其写回磁盘，并且替换成一个空的page。其中每一组排好序的page被称为一个run，每一次遍历称为一个pass
• 如果参与排序的page数量为N，则该算法一共进行了$$1+\lceil\log_2N\rceil$$次遍历，总IO成本为$$2N\times (pass nums)$$

General（K-way） Merge Sort

• 该算法的一般版本允许DBMS使用三个以上的缓冲页

  B表示缓冲页总数，在排序阶段，一次可以读取B个page，并且将$$\lceil \frac{N}{B} \rceil$$个排好序的run写回磁盘；在合并阶段，可以在每个通道中合并最多B-1个runs，将结果放入最后一个缓冲页并且写回磁盘

• 在一般的版本中，一共需要遍历$$1 + \lceil log_{B-1} \lceil \frac{N}{B} \rceil \rceil$$次排序，总IO开销依然是$$2N\times (pass nums)$$

Double Buffering Optimization

• 优化思想是：假设我们从原本有的4个缓冲页扩大到了8个，那么如果还是按照原本3+1的思路进行串行的归并排序和写回，就会浪费一部分的IO请求等待时间。双缓冲优化使用多线程，组成两个3+1：当第一组缓冲区正在进行归并排序的时候，第二组缓冲区已经开始从磁盘中预读取page到frame中，这样一旦第一组IO结束，即可马上开始下一组IO的运算

Using B+ Tree

• 对于DBMS，可以使用聚类B+索引来帮助排序，因为在B+树的叶子结点中，所有数据的存储都是有序的，IO的访问也都是顺序的，可以有效减小计算开销，这比外部归并排序要来的高效
• 反之，如果是非聚类的B+索引，那么使用它就不是一个很好的选择（因为数据不连续），几乎所有访问都要从磁盘中读取而非buffer pool

Aggregation

在执行聚合运算的时候，往往是将一个或者多个tuple的值折叠成一个标量值，例如select distinct cid from enrolled where grade in ('B','C) order by cid

总体来说有两种实现聚合的方法：(1)排序，(2)散列

Sorting

• DBMS首先根据group by语句对tuple进行排序，如果buffer pool够用，则直接使用qsort，否则使用外部归并算法。然后DBMS会对排好序的数据进行顺序扫描来计算聚合
• 在执行排序聚合，重要是要对查询操作进行排序，以效率最大化。例如：如果查询需要一个过滤器，最好先执行过滤器，然后对过滤后的数据进行排序，以减少数据量

Hashing

• 由于在计算聚合的时候，散列的计算成本总是要比排序低得多，所以DBMS在扫描表的时候会填充一个临时的哈希表（ephemeral hash table），对于每一条记录，都会检查哈希表中是否已经有该条目，并且进行适当的修改。如果哈希表太大，DBMS就会将其溢出到磁盘上（？）。完成这个任务有两个阶段：

  • Phase #1 - Partition：

    使用哈希函数h1，根据目标的hash key将tuple分割到不同的磁盘分区，这样所有匹配的tuple都会被分配到同一片区域，然后DBMS会通过输出缓冲区将分区溢出到磁盘上

  • Phase #2 - ReHash：

    对于磁盘上的每一个分区，将其page读入内存，并且根据第二个哈希函数h2，建立一个哈希表，由此把所有匹配的tuple都聚集到一起。如果hash表太小了以至于无法容纳所有数据，那么可以考虑将当前分区重新进行分割，或者混杂其他基于排序或者基于散列的算法

• 在ReHash阶段，DBMS可以将需要输出的聚合存储为（GroupByKey -> RunningValue）的配对，RunningValue的内容取决于聚合函数

  例如如果我们想要输出select cid, AVG(gpa) from enrolled，可以将AVG存储为(COUNT,SUM)的形式

• 而对于一个新插入的tuple

  • 如果它能够找到一个匹配的GroupByKey，则适当更新RunningValue
  • 否则插入一个新的(GroupByKey -> RunningValue)

Lecture 9: Index Concurrency Control

本章主要介绍了数据库中几种闩锁的概念和简单的实现（非代码）

Locks vs. Latches

• lock
  1. 保护当前事务的索引内容不会受到其他事务的影响
  2. lock在整个事务的执行期间都会被持有
  3. DBMS需要在发生冲突的时候回滚变更
• latch
  1. 保护索引内部数据不会被其他线程影响
  2. 仅在线程对索引进行某个操作的时刻被持有（一般持有时间很短）
  3. DBMS不需要对数据的更新进行回滚
  4. latch有两种mode，分别为Read Mode和Write Mode，其中Read Mode可以同时被多个线程持有，但Write Mode不行

Latch Implementation

Blocking OS Mutex

• 依赖OS内置的互斥机制，由用户空间的自旋latch以及OS的互斥锁组成。当DBMS无法获得用户空间的latch时，会试图进入内核态并获取更加昂贵的mutex，如果还是无法获取，则会被阻塞
• OS mutex在DBMS中不是一个好的选择，因为会被OS介入，而且开销比较大
  • 例子：std::mutex
  • 优点：使用简单
  • 缺点：消耗大，不可扩展

Test-and-Set Spin Latch(TAS)

• 自旋锁比mutex更有效，因为DBMS可以控制自旋锁在无法获取latch的情况下的下一步动作：比如可以继续尝试获取或者允许OS取消调度
  • 例子：std::atomic<T>
  • 优点：上锁更高效，一个std::atomic_flag latch指令即可上锁
  • 缺点：没有扩展性，对于cache和OS并不友好

Reader-Writer Latches

• mutex和自旋锁并不区分读写（对于数据库而言是不好的），DBMS需要一种可以支持并发读取的方法，这样如果程序有大量读取的需求就可以获得更好的效果
• 读写锁允许latch以read或者write的mode进行等待，可以跟踪有多少线程持有该latch，以及有多少线程在等待获取latch。对于read锁，我们可以定义其在任何情况下都可以获得这把latch，也可以指定其只有在等待write的线程为空的时候才能获取；对于write锁，则需要等待read锁被全部释放
  • 例子：std::shared_mutex
  • 优点：能够并发读取
  • 缺点：必须要额外维护两个队列：read线程和write线程以防止饥饿现象，内存开销会更大

Hash Table Latching

• 由于Hash数据结构本身的特性，所有线程在访问的时候都是按照顺序自上而下的，每次也都只会访问一个slot，因此不会出现死锁现象
• 按照粒度的大小，Hash Table Latching可以被分成两种：
  • Page Latches：每个Page都用一把大锁锁住，每个线程在访问Page之前获取一个Read或者Write锁，这样的做法会降低程序的并发性，但是由于线程访问每个slot的速度很快，因为只需要一把锁即可实现
  • Slot Latches：Page中的每个slot都有自己的锁，所以读写线程可以同时访问一个Page的不同slot，提高了并发度，但同时也增加了存储和计算开销

B+ Tree Latching

• B+树的锁主要为了防止以下问题：
  • 不同线程同时修改同一个结点
  • 当一个线程对结点进行插入/删除，导致结点出现了split/merge现象时，另一个线程正在遍历树
• Latch Crabbing/Couping Protocol（锁存耦合协议）允许多个线程并发访问B+树，具体规则如下：
  • 获取父节点锁
  • 获取子结点锁
  • 如果子结点被认为是安全的（不会发生split、merge、再分配），则释放父节点的锁
• Basic Latch Crabbing Protocol
  • Search：从根结点开始向下，获取子结点锁->释放父节点锁，重复此步骤
  • Insert/Delete：从根结点向下按需获取x个结点的latch，一旦孩子结点被锁住了，检查是否安全，如果安全，则释放所有祖先的锁
  • 释放锁的顺序在逻辑上不重要，然而在现实中越靠近根结点的锁需要更先释放，否则会造成性能的下降
• Better Latch Crabbing Protocol：
  • 在改进的算法中，每一个线程都会默认到达目标结点的路径是安全的，并且以不断抓去Read锁的形式来到达，最终检验是否安全。如果不安全，则停止操作，重新开始，只不过重新遍历会抓去Write锁
  • Search：与朴素的算法一致
  • Insert/Delete：跟Search一样，不断获取和释放READ latch。最后在叶子结点上设置WRITE latch。如果叶子不安全，则重来，这次用基本算法的思路
• Leaf Node Scan
  • 前两种算法都是自上而下的，线程无法获取更上一层的锁存器，因此不会出现死锁现象
  • 然而扫描叶子结点的时候很容易出现死锁，当两个线程以相反的方向遍历到了相邻的叶子结点，就会出现死锁，而Index Latch本身并不支持死锁的检测和预防
  • 因为，唯一能够解决这个问题的方式就是通过code discipline，叶子结点的兄弟结点的锁存器必须遵循“no wait”原则。B+树必须面对锁存器获取失败的情况，一般会选择终止操作，重新启动

Letcure 6: Memory Management

本章主要介绍了数据库中内存管理的相关内容，主要引入了缓冲池的概念

Introduction

DBMS的任务就是管理内存以及从磁盘写入写出数据。数据库如果希望对磁盘上的数据进行处理，则必须首先将数据移动到内存中

因此我们需要设计一个DBMS，满足以下几个要求：

• 其能够处理的数据量超出内存的大小
• 最小化磁盘上执行查询所带来的低效率问题
• 使得所有的操作看起来都像是在磁盘上进行的一样

这个问题可以从时间上和空间上两个方面来考虑：

• 空间上：我们需要将Page写在磁盘的哪一个部分？这是为了保证数据的空间局部性
• 时间上：我们应该何时进行Page的写入写出？这是为了尽可能减少从磁盘上读取数据的停顿次数

Buffer Pool

• 执行引擎在请求Page的时候会先去buffer pool查询，如果没有，则buffer pool会执行替换算法将目标Page换入其中。此时脏页会被写会磁盘，而非脏页会被直接舍弃。可以参考cache在计算机硬件中的作用
• 缓冲池是一个从磁盘上读取数据的内存区域，该内存区域被组织称一个个固定大小的页面阵列，被称为frame。每个frame保存的都是磁盘中的一个Page，因此为了方便调度，我们需要Page Table（页表）。
• 页表是一个Hash表，用来跟踪处于buffer pool中的Page，我们可以通过页表以及上面的page_id来确认此Page是否还在buffer pool中。当然页表还会记录一些元数据
  • Dirty Flag：标志位，表示这个Page是否被改写过，这是为了保证数据持久化
  • Pin Count：正在引用或者正在访问该Page的线程的数量，如果这个meta data非零，那么我们当下就不应该将这个Page驱逐出buffer pool

Lock vs. Latch

由于我们并不希望我们在移动Page的时候被其他线程干扰（比如修改这个Page上的数据），所以我们需要对Page进行上锁操作

这涉及到了数据库中Lock和Latch的一些区别：

• lock
  1. 保护当前事务的索引内容不会受到其他事务的影响
  2. lock在整个事务的执行期间都会被持有
  3. DBMS需要在发生冲突的时候回滚变更
• latch
  1. 保护索引内部数据不会被其他线程影响
  2. 仅在线程对索引进行某个操作的时刻被持有（一般持有时间很短）
  3. DBMS不需要对数据的更新进行回滚
  4. latch有两种mode，分别为Read Mode和Write Mode，其中Read Mode可以同时被多个线程持有，但Write Mode不行

Page Table vs. Page Directory

这里需要辨析两个概念，页表和页目录虽然看上去很像，但本质上有很大区别：

• Page Table：内存中的一个哈希表，并不需要持久化，即哪怕丢弃了，只需要重新建立一个就行
• Page Directory：从page_id到数据库文件中页面位置的映射，对于页目录的所有改变都必须要记录到磁盘上，以允许DBMS在重启之后能够发现，否则会破坏数据的一致性

Allocation Policies

数据库中的内存是根据两个策略来分配给buffer pool的

• Global Policies：
  全局策略处理DBMS应该作出的决定，以有利于正在执行的整个工作负载
  他考虑到所有活动的事务，以找到分配内存的最佳策略
• Local Policies：
  本地策略作出的决定会使得单个查询或事务的执行更快
  本地策略将框架分配给特定的事务而不考虑事务的并发行为

Buffer Pool Optimization

有许多方法可以来优化buffer pool

Multiple Buffer Pool

我们可以分配多块内存区域以支持多个Buffer Pool，每个区域可以有自己的页表，并且自己一套page id和frame的映射关系，这样可以更好地运用局部策略，并且根据不同的类型来分配page的置换策略（例如index或者table data），这样也能减少访问缓存池的不同线程之间对于页表锁的争夺

有两种办法来将Page映射到不同的buffer pool中：

• Objects IDs：
  对象ID涉及扩展记录标识(extending the record IDs)，使其具有一个对象标识符(object identifier)。然后，通过对象标识符，可以维持一个从对象到特定缓冲池的映射关系。
• Hashing：
  哈希也是老生常谈的方法了，不展开

Pre-Fetching

DBMS也可以通过基于查询计划的预取页面来进行优化。然后，当第一组页面被处理时，第二组页面可以被预取到缓冲池中。这种方法是DBMS在连续访问许多页面时常用的

Scan Sharing

查询游标可以有效减少对于数据的访问

Q1:select sum(val) from A
Q2:select avg(val) from A limit 100
对于以上两个查询，如果Q1在执行到一半的时候，Q2加入了进来，那么就可以将Q2定位到Q1此时的游标位置，当游标遍历结束之后，Q2再针对前面没有被查询到的数据进行访问

Buffer Pool Bypass

对于需要线性读取大量数据的查询操作，可以选择不将获取的页面存储在buffer pool中，可以随意丢弃

此外，对于中间数据（类似于join和sorting），也可以这么做

Buffer Replacement Policies

buffer pool在写入新页而没有空间时，需要执行evict操作给新页腾位子
替换策略的目标是准确性、正确性、并发性、和元数据的开销

Least Recently Used（LRU）

对于缓存池中每个page维护一个时间戳，时间戳记录着每个page最后被访问的时刻。当DBMS需要驱逐（evict）一个page时，选择时间戳最早的page执行驱逐。一般来说我们可以让page按照时间戳排序（优先级队列）以减少搜索的时间。

Clock

CLOCK策略是LRU的一个近似值，不需要每页有单独的时间戳。在CLOCK策略中，每个页面被赋予一个参考位。当一个页面被访问时，设置为1
为了形象地说明这一点，可以用 “时钟指针 (clock hand)”将页面组织在一个圆形的缓冲区中。在清扫时检查一个页面的位是否被设置为1，如果是，则设置为0，如果不是，则驱逐它。通过这种方式，时钟指针在驱逐之间记住了位置

Alternative

无论是LRU还是Clock，都会受到sequential flooding的影响：在进行顺序访问的时候，DBMS会不断把连续的page读入内存，但这些正在使用的page是我们最不想要的（因为我们不过是为了查找到自己想要的page，迫不得已才把之前的page读入buffer pool）
有三种方法可以解决LRU和Clock的缺点：

• LRU-K：
  frame组成的链表被分为两个区域：young list和old list，当old list中的page被再一次访问到，则将其放入young list的头部；而新加入buffer pool的页面会被放入old list的头部
  它跟踪最后K个引用的历史作为时间戳，并计算出后续访问的间隔。这个历史记录被用来预测一个页面下次被访问的时间
• Localization per Query
  DBMS跟踪每一个查询的访问情况，在每个查询的基础上选择哪些页面要被驱逐。这使得每次查询对缓冲池的污染最小化
• Priority Hints
  优先级提示允许事务根据查询执行过程中每个页面的上下文，告诉缓冲池页面是否重要

Dirty Page

DBMS有两种办法来处理有脏位的页面：

• Fast Path：直接丢弃掉buffer pool中任何非脏页
• Slow Path：将脏页写回磁盘

避免不必要的页面写回的方法是后台写入
通过后台写入，DBMS可以周期性地通过页表来写回脏页到磁盘上
当一个脏页被后台写入，DBMS可以要么将这个page驱逐出去，或者保持其在buffer pool中的位置但是重置其dirty flag

Lecture 3,4,5: Database Storage & Storage Model

本章主要介绍了数据库的存储方式以及几种常见的存储模型

Disk_Oriented DBMS

• 数据库保存在磁盘上，按照页（page）作为单元进行划分，第一页为目录页，如果想要对数据库进行操作，则首先需要将数据库中的page调度到内存中
  • 通过一个保存在内存中的缓冲池（buffer pool）来管理数据在磁盘和内存之间的移动
  • DBMS有一个负责查询的执行引擎，缓冲池将page带入内存，并且给执行引擎返回一个指向该page的指针，以确保在执行引擎在对该page进行操作的时候，此page的确存在于该位置

DBMS vs OS

DBMS的一个高级设计目标就是：创造一个容量远大于内存的数据库，与此同时并不希望过于频繁地访问数据库，因为访问磁盘的代价很大
这就类似于操作系统中的虚拟内存，保证磁盘中的地址空间能够映射到内存中
提起磁盘和内存之间数据的迁移，很容易想起mmap，的确曾经有很多DBMS选择使用mmap来执行，然而实际上是会造成一些问题的

1. DBMS并不知道哪些page在内存中，而mmap在遇到page fault时会阻塞进程
2. OS可以在任何时刻写回脏页，然而OS并不知道哪些page需要在其他page之前写回磁盘，这会造成并发控制方面出现问题
   尽管有办法解决这方面的问题，但是从性能和安全性两方面考虑，并不建议由操作系统来完成这一任务
   因此根据Andy所言，由DBMS自己来实现数据的控制是一个更好的选择

DataBase Storage

File Storage

DBMS使用自己独有的编码形式将数据库作为单个文件或者多层次文件保存在磁盘中，OS对此一无所知
DBMS的存储管理器负责管理数据库的文件，它会将这些文件作为一个page的集合，并且追踪哪些数据被读写、这些page有多少可用空间

DataBase Page

DBMS将数据库文件中固定大小的数据块称为页（page），可以参考OS中的虚拟内存，页面可以包含不同的数据结构（tuple、indexes、log等）
在大多数DBMS中，一个page会被要求只能存储一种类型的数据

例如page1只能存储tuple，page2只能存储日志
所以，每个page都会被赋予⼀个唯⼀的内部标识符，系统会生成属于page的ID。之后，就会有一个indirection层。indirection层允许将⼀个page ID映射到某个物理位置，即某个文件中的某个位置（类似于一个字典映射，其实就是记录⼀个相对位置，方便文件整体移动后，只要知道整体文件的初始位置，我依然可以通过该相对位置（即page ID）找到某个文件某个位置的数据所对应的page）。这样的话，就可以支持磁盘的压缩或者使用另一块磁盘而不改变page ID。

DataBase Heap

关于page之间是如何进行存储的——
堆文件组织是是一个无序的页面集合，是从磁盘上查找我们想要的page地址的一种方法
DBMS可以通过使用页面的链接列表或页面目录在磁盘上找到一个给定的页面ID：

1. Linked List：
   是一种顺序存储（顺序存储并不意味着有序），这是一种很容易想到的存储方式，然而弊端也是显然的：链表的查询时间复杂度为O（n），效率远不及hash
2. Page Directory：
   可以类比书的目录，每次查询只需要从page directory中获取目标page的偏移量即可，然而弊端在于：必须时刻保证目录与实际page信息的同步。如果往某个page中写入数据，此时page满了，但系统也崩溃了，那么目录中的信息是相对滞后的，在重启系统之后需要有对应策略来重新扫描以维护信息的一致性；如果数据量很大，在极端条件下可能始终无法统一

Page Layout

关于page中的信息是如何存放的——
每一个page都有一个页头（header）来存放该page的，譬如页面大小、DBMS版本号之类的相关信息，这些信息被称为元数据（meta data）
一般来说数据在page中有2种常见的存储方式：tuple-oriented和log-structured

1. tuple storage
   一种朴素的思想就是将tuple以数组的方式存放，同时header记录page的信息，但这是一个strawman idea：因为当我们删除其中的一个tuple时，会产生内部碎片，导致文件的不连续；如果tuple的长度是不定长的话，这个问题会更加显著。同时tuple的查找也只能够顺序遍历，所以并不推荐
2. slotted storage
   page中除了header以外还有两种数据结构，一种是slot，一种是tuple
   其中slot从header之后顺序存储，每个slot都保存了对应的tuple在该page中的偏移量；而tuple本身是从page的末尾开始从后往前循序存储。虽然必然会出现一定的内部碎片，然而这是为了处理变长tuple不得不做出的牺牲，当然有些数据库支持对于内部碎片的再整理
   对于slotted storage，一个tuple的查询需要其所在的page_id和slot_id
3. log-structured storage
   slotted storage依然有很多问题没有能够解决：例如删除tuple的时候会留下空隙、必须从磁盘中读取整个page来获取其中的一个tuple、随机读取的效率很低
   由此诞生了log-structured storage，这是一种只允许创建新数据而不允许覆盖已有数据的存储方式，DBMS中只会存放日志记录
   • 将数据库如何被修改的记录存储到文件中（放入和删除）。每条日志包含tuples的唯一标识符
   • 要读取一条记录，DBMS会从最新的到最旧的逆向扫描日志文件，并 “重新创建 “这个 tuple。
   • 写的快，读的可能慢。磁盘写入是连续的，现有的页面是不可改变的，这导致了随机磁盘I/O的减少。
   • 在append-only的存储上工作得很好，因为DBMS不能回溯并更新数据。
   • 为了避免长时间的读取，DBMS可以有索引来允许它跳到日志中的特定位置。它还可以定期地压缩日志。（如果它有一个tuple，然后对其进行了更新，它可以将其压缩到只插入更新的tuple）
   • 由于不再需要时间信息，数据库可以将日志压缩到一个按id排序的表中。这些被称为分类字符串表（SSTables），它们可以使tuple搜索非常快。
   • 紧凑化的问题是，DBMS最终会出现写入放大的情况。（它一次又一次地重写相同的数据）

Tuple Layout

关于tuple的具体结构——
其实通过sql的创建table的句式就可以观察出来，tuple本质上是一个字节的序列，DBMS的工作就是将字节的序列翻译成不同的属性和值

• Tuple Header：包含了tuple的元数据
  • DBMS的并发控制协议的可见性信息。关于哪个事务创建/修改了该元组
  • NULL值的位图
• Tuple Data：数据的实际属性
  • 属性通常按照你创建表时指定的顺序存储
  • 大多数DBMS不允许一个tuple超过一个页面的大小
• Unique Identifier
  • 数据库中的每个tuple都被分配一个唯一的标识符
  • 一般是：page_id + （offset or slow）

Storage Model

数据库并没有规定应该按照哪一种模型来保存数据，然而在实际操作中，storage model的影响是很大的

OLTP（On-line Transaction Processing）

意思是从外界拿到数据后，只会将其放入数据库中进行简单的查询或者更新，一个具体的例子就是网购的购物车，将购物车中的东西删除、或者新增东西到购物车里，tuple的改变是很小的

OLAP（On-line Analytical Processing）

从数据库中的到数据后不会修改原有的数据，而是希望能够从数据中挖掘出更加深入的信息，例如数据挖掘、数据分析之类的工作，某种意义上OLAP是只读的，并且join的操作很多

以上两种不同的数据库使用方式就导致诞生了各种数据的存储模型：

1. N-ary Storage Model（NSM）
   简单来说就是一个tuple会保存表中的所有属性，例如（姓名，性别，生日，年龄）作为一个tuple
   这是一种典型的row storage，并且利好OLTP：因为内容都是顺序排列的，存储粒度足够小，我们可以只关心自己想要的数据
   但是对于OLAP而言，NSM是灾难性的，显然我们的查询会涉及到很多我们并不想要的数据
2. Decomposition Storage Model（DSM）
   这是一种典型的列存储模型，他将每一个tuple按照属性进行拆分存储，例如姓名作为一个tuple，性别作为第二个tuple……
   对于列存储而言，每次查询可以只读取某几个属性的值，这对于OLAP是有利的

“你的叛逆期似乎比其他的小孩来得更晚一些，我不知道这是好是坏”

在某一次与父亲的饭间闲聊产生了激烈的观念冲突后，他对我如是说道。

我知道他口中的“叛逆期”并不针对他们，应该说，即使真的针对他们，他们也只认为是我成长途中自我意识的觉醒，不以为然，更不至于为我感到担忧——我听得出来，我也心知肚明，我所叛逆的对象要比“父母”庞大的多，也难相处的多

自从升入大三，我便开始经常翘课，并不是因为我贪图玩乐，而是因为我认为“没必要”：既然这个老师上课不讲课，那我不如找资料自学，既然我要自学，那我也没必要去他的课堂。同样的，既然我不想卷绩点，那么平时的实验也就没必要做到完美，差不多糊弄糊弄拿个平时分就足够。每当母亲唠叨期末考试的结果，我都嗤之以鼻——因为对我来说，这东西无论是高是低，最终脑回路导向的结果都是“没必要”的

上述所说的讲课跑火车的老师也好，比夏天吸血的雌蚊子的存在更不合理的教学大纲也好，都是客观上存在的事实，直到现在我依然觉得自己的做法是有理可据的，是在特定环境下作出的自救行为。事实上翘课的那段时间我也的确没有荒废，拿来学自己想学的东西，相信着自己能够全凭自己一步步向自己所期望的目标挪动，却又始终放不下我所认为的“没必要”的学校的教学课程

我为自己想要实践却饱受阻挠的生活而痛苦，为身不由己无法从已经被预先定死的框架中彻底脱身而烦恼

所以我选择了最辛苦的方式：鱼和熊掌我全都要，毕竟再怎么说，至少我不想挂科

这就是我的叛逆，认为被形式束缚住的生活是错误的，认为向不合理的事情妥协应当是被禁止的，激进到想要对所有对我指手画脚的人漏出獠牙，推翻循规蹈矩愚昧至极的一切

即使无法甩开像臭虫一般令人讨厌的条条框框也无所谓，幻想着只要我足够强大，就能建立属于自己的秩序，做自己的独裁者

超级幼稚超级天真超级不切实际

人在年轻的时候总是一股冲劲蛮不讲理，从脚心诞生的一瞬间就开始野蛮生长，来不及等待中枢神经的控制就能直上脑门，用殉道者的姿态看待自己，用自毁心态丈量世界，觉得自己总是对的，藏在丹田里的小宇宙总有一天能改变这个垃圾一样的世界

用自己为是的眼光看待周遭而不听劝阻，就叫叛逆

当然叛逆期总会结束的

当我真的用了两个学期的时间去尝试兼顾自己想要的生活和当下的规矩，终于发现，似乎处理得没有想象中那么得心应手，我依然在煎熬，只不过原因从平时作业的拖累这一条，又加上了自己缓慢的学习进度以及对未来愈发强烈的迷茫

我从来不怀疑自己的努力，我只是终于开始怀疑自己的叛逆——赌气一般的行为，是否真的给自己带来了什么东西？取舍之间，结果的确匹配得了长久以来的预期吗？

叛逆期在人生的这个阶段到来，究竟是好是坏，我不知道，父亲不知道，谁都不知道