『 CMU-15445 』课程小结

我的学习顺序,快速过一遍 Notes,了解一下这一节的大纲和重点,之后根据自己的能力选择是看视频还是直接看 slides(并发控制之前的章节难度还 ok ),学习完一章后,尝试用自己的话把一章的重点梳理一遍,最后选择性阅读帆船书。

以下内容为我归纳整理的一些问答式:

1. 和 CSV 文件相比,使用数据库的优势是什么?
2. 为什么不使用 OS 自带的磁盘管理模块 (mmap)?
3. 1
4. 存储模型 N-Ary Storage Model (NSM) 和 Decomposition Storage Model (DSM) 的优缺性?
5. 为什么会有 buffer pool?
6. buffer pool 可以做哪些优化?
7. 为什么数据库BUFFER POOL需要LRU-K的策略?
8. 有哪一些哈希方案?
9. 为什么使用B+ Tree 而不是用 B Tree
10. 是否当有节点不到 half-full,就 MERGE 节点?
  1. 和 CSV 文件相比,使用数据库的优势是什么?

  2. 为什么不使用 OS 自带的磁盘管理模块 (mmap)?

    if i die in this class , you want to have a memorial something just Say Andy hated mmap

    论文

    https://www.codedump.info/post/20220327-weekly-11/

    作为底层的操作系统,他只能看到毫无规律的读取和调用,而 DBMS 希望自己拥有足够的控制权

  3. 页?

  4. 存储模型 N-Ary Storage Model (NSM) 和 Decomposition Storage Model (DSM) 的优缺性?

  5. 为什么会有 buffer pool?

    优点:内存速度大于磁盘

    缺点:命中率很低,刷新很快 -> BUFFER POOL BYPASS

    把一些查询不放入buffer pool中

  6. buffer pool 可以做哪些优化?

    1. MULTIPLE BUFFER POOLS
    2. PRE-FETCHING
    3. SCAN SHARING
    4. BUFFER POOL BYPASS
  7. 为什么数据库BUFFER POOL需要LRU-K的策略?

    LRU ( Least Recently Used ):最近最久未使用,防止了SEQUENTIAL FLOODING,提高了命中率。

  8. 有哪一些哈希方案?

    • 静态哈希方案:

      • Linear Probe Hashing

        线性探测法是开放寻址法(Open Addressing)中的一种,插入元素时,若存在哈希冲突,则往后顺移,直到找到一个空的位置。

        线性探测法会导致同类哈希的聚集 (Primary Clustering)

      • Robin Hood Hashing

        罗宾汉是英国民间传说中的英雄人物,劫富济贫,整治暴戾。罗宾汉哈希是线性探测法的拓展,传统的线性探测只是无条件的顺移,而罗宾汉哈希会记录每个键离本来应该插入的位置的距离,当有新的键冲突,往后顺移的同时会比较冲突位置 key 的距离和自身距离的大小,如果自身的距离已经超过冲突的位置 key 的距离,则选择替换该项,顺移被替换的 key 。

        image-20220726141842367

        罗宾汉哈希可以显著降低探测长度的方差,把 rich key 的位置交给 poor key,从而使大部分元素的探测长度趋于平均值。但是每次 insert 时又增加了新的比对开销,这是不可避免的。

      • Cuckoo Hashing

        Cuckoo Hashing 采用多个 hash table,每个 hash table 都采用不同的 hash function seed 。

        对于任何一个 key ,都可以选择其中一个没有冲突 hash table 插入,若全部 hash table 都没有空的位置,则随机选择一个 hash table 中对应的位置插入,并取出原来这位置上的 key 重新插入。

        在容量不够的情况下,连锁的冲突可能会导致死循环,解决办法只能扩容然后 rehash。

    • 动态哈希方案

      • Chained Hashing

        每个 slot 维护一个 linked list,对于冲突的哈希则直接追加到链表后面。

        如果数据很大链表过长,时间复杂度又退回到 O (n),我们内部会维护一个负载因子(最长链表长度 / slot 个数),当负载因子达到某个阈值便扩容 slot 并 rehash。

      • Extendible Hashing

        简单来说 Extendible Hashing = Hash + Trie( 字典树 )

        image-20220726142640107

        Extendible Hashing 会在 project 2 中实现,详细请见:

      • Linear Hashing

        http://queper.in/drupal/blogs/dbsys/linear_hashing

  9. 为什么使用B+ Tree 而不是用 B Tree

    写了一篇关于树的总结。

  10. 是否当有节点不到 half-full,就 MERGE 节点?

    MERGE 有一定的开销,可以先把该节点保存,然后过一段时间周期性的批量处理这些节点(重新建树)。

  11. B+ 树的优化

    1. Prefix Compression 前缀压缩

      在同一个叶子节点上,如果 key 有共同的前缀,可以提取出来节省空间。

    2. Suffix Truncation 后缀截断

      对于内部节点,如果前面的数据就足够做 ROUTE ,后面的数据没有区分度,那么就可以把没有帮助的部分截断。

    3. Bulk Insert

      在构建一棵 B+ 树时,如果逐个插入节点可能会比较慢,Bulk Insert 就是先对 key 排序,然后自底向上先生成叶子节点,再根据叶子节点形成内部节点。Bulk Insert 让我们能更快去构建一棵 B+ Tree。

    4. Pointer Swizzling

  12. Lock 和 Latch 的区别是什么?

    Lock 是一个高级别,逻辑意义上的锁,一般特指事务锁,用于保护数据库内容免受其他 transactions 的影响 ,而且需要考虑一个事务回滚的问题。

    Latch 是一个低级别的锁,用于维护 DBMS 内部数据结构在多线程情况下安全读写,比如互斥锁 mutex。

  13. B+树的 Latch Crabbing 是什么?

    因为 B+树会经常涉及到分离和归并,所以我们需要严格进行锁处理。

    我们从上到下先拿到父 latch,再拿到孩子的 latch:

    • 针对于 read 的情况,只要拿到孩子的读锁,就可以把祖先们的读锁给解开。
    • 针对 insert 或 delete 的情况,如果孩子是 safe 的(比如 insert 不会导致分离,delete 不会导致归并),则可以把其祖先们的锁全部解开。

    上面这样有一个问题,我们发现根节点始终是一个上锁的状态,这样对效率的影响比较大。我们可以采取一个 『 乐观 』的态度,我们假设叶子节点都是安全的,所以无论是增还是删都先上读锁,等到具体情况如果发现并不安全,则重头再按照写锁的逻辑来一次。

  14. 108个页,内存 buffer pools 中只能容下5个页,怎么利用 General (K-way) Merge Sort 做外部排序?

    • 第一轮:108个页每次放入5个页进行排序,排序后写入磁盘,这样会得到 108 /5 = 22 个排序文件。
    • 第二轮:buffer pools 的5个页4个页用作输入,1个页用作输出,从22个文件中选取4个做归并,最后得到 22 /4 =6个排序文件。
    • 第三轮:同上 buffer pools 的5个页4个页用作输入,1个页用作输出,得到 6/4 = 2个文件。
    • 第四轮:同上 得到一个有序文件。
  15. 有哪一些做 aggregation(聚集)的方案?

    1. 排序聚集

      对于本身需要排序的例子(order by),先排序再去重。

    2. 哈希聚集

      如果不需要排序(group by、distinct),再排序的话开销就会很大,这时候我们可以选择哈希聚集。

      外部哈希聚集(external hash agg)主要分为两部:

      1. Partition:通过 HASH$_1$,我们用1个把数据输出到磁盘
      2. ReHash
  16. join算法有哪些·?以下述例子分析复杂的:

    • M pages in table R (Outer Table), m tuples total

    • N pages in table S (Inner Table), n tuples total

    1. Nested Loop Join

      • Simple Nested Loop Join (stupid)

        把外表的每一个元组和内表的元组进行比对。

        Cost:$M +(m×N)$

      • Block Nested Loop Join

        利用 buffer pools 存储一个一个块扫描,假设buffer pools 容量为B

        Cost:$M+(\lceil \frac{M}{B-2}\rceil×N)$

      • Index Nested Loop Join

        利用B+Tree索引

        Cost:$M +(m×C)$ C是一个常数

    2. Sort-Merge Join

      先排序,再归并

      排序复杂度可见上面的 (K-way) Merge Sort

      • Sort Cost for Table R:$2M×(1+\lceil\log_{B-1}\lceil \frac {M}{B} \rceil\rceil)$
      • Sort Cost for Table S:$2N×(1+\lceil\log_{B-1}\lceil \frac {N}{B} \rceil\rceil)$
      • Merge Cost: $(M+N)$

      Total Cost: Sort + Merge

    3. Hash Join

      把两个表数据做 Hash 然后存储到外部文件,再读取文件进行比对 join 连接。

      • Partitioning Phase Cost: $2 × (M + N )$
      • Probe Phase Cost: $(M + N )$

      Total Cost: $3 × (M + N)$

  17. 有哪一些数据库执行模型?

    1. Iterator Model

      迭代器模型,又称为火山模型,每个关系函数都会调用自己的next方法直到有数据元组返回(整个调用过程有点像栈,先进后出,直到叶子节点返回数据,再一路回到顶,像火山的流动一样)。

      image-20220807235353723

      一些关系函数会堵塞,直到所有数据返回(比如 joins, subqueries, order by),也被称作 pipeline breakers.

    2. Materialization Model

      相比于火山模型流式的一条条返回和读取数据,物化模型会把所有数据全部打包好一次性返回。

      image-20220808101846497

    3. Vectorization Model

      向量化模型是以上两种模型的折中模型,其内部也实现了next方法,但是每个next方法返回的是一批数据而不是单个元组,自定义数据大小也避免了物化模型中数据量返回过大的可能。

      image-20220808102946859

  18. 有哪一些数据读取的方法?

    1. Sequential Scan

      顺序扫描,或者说全表扫描。数据库维护一个扫描当前页的指针,顺序扫描有以下优化方法:

      • Prefetching

      • Buffer Pool Bypass

        上面两种方法都是站在缓存池的角度,具体可以看 6. buffer pool 可以做哪些优化?

      • Parallelization

      • Zone Map

        维护一个额外的分区表去缓存页信息,可以降低扫描时读取页面的总次数。

        image-20220808114454425

      • Late Materialization

        延迟物化,即数据传递中,自底向上只传入一个关键信息(比如关键字段、偏移量等),需要用到具体数据时再获取全部的信息。此方法只在 DSM(列存储)中有效。

    2. Index Scan

      优化器选择最合适的索引去扫描(该索引的选择率最高)。

      还有一种方式是采用 bitmap 多索引扫描,再根据具体语句选择交集或者并集。

  19. 单个 Intra-Query 如何做并行?

    1. Intra-Operator Parallelism (Horizontal)

      算子内并行(水平切分),指把单个数据集拆分为多个单位,然后在数据子集上执行相同的函数,最后再利用Exchange操作进行合并。

    2. Inter-Operator Parallelism (Vertical)

      算子间并行(垂直切分),有一点像火山模型中的流式处理,

      image-20220811114914461

    3. Bushy Parallelism

      相当于水平切分+垂直切分,底层数据读取使用水平切分,数据往上传递使用垂直切分。

  20. 谈一谈数据库执行的逻辑优化和物理优化?

    逻辑优化是站在代数级别的,通常是通过一些静态规则和启发函数(heuristics),在代数等价的前提下对表达式进行优化,比如谓词下放、投影下放等优化。

    物理优化是站在开销的角度,这个开销可以指多方面,比如 CPU、Disk I/O、Memory、Network,然后在执行层进行等价优化,比如单个 join连接 有多种算法,单个数据读取有索引读取和全表读取,优化器就会根据具体的开销决定执行哪一种算法。最后再用动态规划确定整个执行的所有方式,如果需要 join 的表很多,动态规划的开销本身也很大,可以选择遗传算法的思想确定。

  21. 简单介绍一下ACID?

    • Atomicity:原子性,即事务中的所有操作要么全部执行,要不都不执行,原子性通常通过 Logging 的方式保证。
    • Consistency:一致性,站在一个 high - level 的角度,事务执行前后的逻辑都是正确的。
    • Isolation:隔离性,虽然事务是并行运行的,但是对站在单个事务的视角其互不影响,其通过并发控制保证。
    • Durability:持久性,所有事务提交的数据不会丢失。
  22. 如何判断事务的执行顺序(schedule)是否与其串行执行(serial)等价?

    如果 schedule 只有两个事务,可以交换事务间的非冲突操作(冲突指读写冲突、 写写冲突等),如果最终可以转换到 serial schedule(即一个事务的所有操作结束完再执行另外一个,而不是 interleave ),则说明这个 schedule 是可串行的(serializable)。

    如果 schedule 包含多个事务,可以用依赖图判断,如果一个来自事务 A 的操作和来自事务 B 的操作冲突,并且 A 先于 B 执行,则我们加一条从 A -> B 的边,以此遍历,若最后依赖图有环,则说明此 schedule unserializable;若最后依赖图无环,则根据箭头顺序,可构造 serial schedule。

    image-20220828213351195

  23. 什么是 View Serializability?

    上述我们判断是否可串行化,是通过冲突判断的,但是这样有弊端,因为有的事务具体的执行之间即使发生冲突,也不会影响最终结果,我们认为这两者还是可以调度的,这是基于观察的判断,比基于冲突更加缓和一些。这是一种理想化的判断,可以作为是否可串行化的标准,但是很难实现。

  24. 什么是两阶段锁?如何解决集联中止和死锁的问题?

    两段锁协议 2PL(two-Parse-locking)指一个事务分为 GrowingShrinking 两个阶段,第一个阶段事务所有操作申请锁,从一个锁释放开始进入第二个阶段,事务只能释放锁不能再申请。2PL 解决了一致性的问题(某个事物对多个变量操作,不会被其他事务所 interleave):

    image-20220829093451882

    但是 2PL 还是有两个问题需要解决,一个是 cascading aborts ,如果事务 T2 读取了事务 T1 的某个中间状态,但是事务 T1 最后没有 commit 而是 abort,那么事务 T2 也应该回滚。解决的办法是采用 Strong Strict 2PL,即事务只有在最后时刻(commit、abort)才会一同释放锁,这是一种更加悲观的决定,也限制了并发。

    还有一个问题就是死锁,上面这张图中的 T2 事务,如果先申请 B 的锁再申请 A,就会导致 T1 申请 B时被锁住,导致死锁。

    站在死锁检测(Detection)的角度,我们创建一个锁依赖图,如果存在 T1 事务申请锁被 T2 事务堵塞的情况,则绘制一条从 T1 到 T2 的边,如果依赖图成环,则表明存在死锁,我们需要选取一名 victim 事务,对它进行 abort 或者 recommit,以打破死锁。victim 的选择需要考虑多方面,比如已经开始的时间、已经执行的操作、多少事务需要被回滚等等。

    死锁检测是已经发生死锁后再进行处理,死锁预防(Prevention)是在死锁发生前 kill 一个事务,我们给事务定义一个优先级,在这里我们认为决定因素是起始时间,开始早的为 old,晚的为 young

    • Wait-Die (“Old Waits for Young”):如果是新事务占有,老事务申请,则选择等待;反之老事务占有,新事务申请,则新事物直接 abort 。(碰瓷)

    • Wound-Wait (“Young Waits for Old”):如果是新事物占有,老事务申请,则新事物直接 abort,老事务占有锁(抢过来),反之选择等待。

      image-20220829181531617

    还需要注意一点,一个事务如果 abort,begin 时间应该不能改变,不然很有可能导致饥饿。

  25. 什么是 LOCK GRANULARITIES ,为什么要这么设计?

    假设一个表有 100 行数据,我们需要更新里面所有的数据,我们可能需要 100 把锁。所以我们需要引入锁的粒度,也叫 Hierarchical locks(分层锁协议)。 锁可以是面向 Page 的,也可以是面向 Table,再往小还有 Tuple,如果我们往低级别上锁的同时,也给高级别一个标记,可以减少实际的锁用量,这里引入意向锁的概念:

    • Intention-Shared (IS):将给下面低级别上 S 锁。
    • Intention-Exclusive (IX):将给下面低级别上 X 锁。
    • Shared+Intention-Exclusive (SIX):将给下面低级别上 X 锁,并自身上 S 锁。

    我们以下面这个例子为例:

    image-20220829205706562

    T1:扫描 R 并更新几个 Tuple ,我们需要给 Table R 上 SIX 锁,并给更新的Tuple 上 X 锁。

    T2:从 R 中读取一个 Tuple ,给Table R 上 IS 锁,并给读取的 Tuple 上 S 锁。

    T3:扫描 R,需要给 R 上 S 锁,和之前的 SIX 冲突,被堵塞。

    image-20220829211137385

    还有一个问题,我们需要去设计一个这个颗粒度,比如我们读取多个 Tuple,并不是只有读取全部才上 S 锁,从 IS 到 S 有一个自适应的升级过程,需要我们去权衡。

  26. 如何基于时间戳进行并发控制?

    比较基础的方式是 Timestamp Ordering (T/O),每一个事务 $T_i$ 有一个起始时间戳 $TS(T_i)$ ,若 $ TS(T_i)<TS(T_j)$ ,则说明 $T_i$ 的执行顺序应在 $T_j$ 之前。

    对于每一个数据库 item 都全局使用 $R-TS(X)$ 和 $W-TS(X)$ 记录上一次被读、写的时间戳。

    当事务需要读写 item 时,就会去检查上面的这个时间戳,如果发现是将

    • 读取一个未来已写的 item
    • 修改一个未来已读或写的 item

    则选择 abort 该事务,并设置新的 timestamp。

    可以看到 T/O 是一种乐观的事务模型,并没有使用锁机制。但是如果存在某个长事务,会不断被后面的一些短事务中止,有可能出现饥饿的情况。

    如果我确定所有的事务都很短并且冲突较少,Optimistic Concurrency Control(OCC)也是一种很好的乐观处理方式,OCC 中每个事务都有一个私有的属性表,用于暂存读写的内容,并在 Validation Phase 阶段判断是否 abort,通过则把私有表刷新到数据库。( OCC 是最后一起判断是否通过,所以长事务更加容易饥饿)

  27. 并行事务可能出现怎样的问题?事务有哪几种隔离级别,有什么特点及其实现?

    从上往下对一致性的影响依次减轻:

    • Dirty Read(脏读):读取到了其他事务还未提交的数据。
    • Unrepeatable Reads(不可重复读):一个事务前后读取到的数据不一致。
    • Phantom Reads(幻读):一个事务前后读取的记录数量不一致。幻读和不可重复读的区别在于后者通常是 update 导致,前者为在两次顺序遍历时 insert or delete 导致前后不一致。

    四种隔离级别,从上往下隔离级别递增,性能效率递减:

    • READ-UNCOMMITTED(读未提交):一个事务还未提交,它所做的变更就会变其他事物看到。上面三种问题都有可能发生。
    • READ - COMMITTED(读提交):一个事务提交之后,它所做的变更才能被其他事物所看到。解决了脏读的问题。
    • REPEATABLE READS(可重复读):一个事务在启动到结束中看到的数据都是一致的。解决了不可重复读的问题。
    • SERIALIZABLE(可串行化):这个我们已经了解很多了,serializable 通常通过 Strong Strict 2PL 实现。
  28. MVCC 设计需要考虑哪几个方面?

    MVCC (Multi- Version Concurrency Control)的核心思想为读写互不堵塞,一共需要考虑以下四个方面:

  29. Concurrency Control Protocol

    选取一种并发控制协议,也就是我们前面所谈到的 2PL、T/O、OCC 等。

  30. Version Storage

    DBMS 为每个 tuple 维护了一个全局属性表, tuple 不同版本之间通过链表连接起来,根据存储逻辑的不同也分为三种:

    • Append-Only Storage:全部 tuple 存储到一个表空间内。
    • Time - Travel Storage:用一个 单独的 time-travel 表维护老版本的 tuple。
    • Delta Storage:和前者类似,不过表内只维护变化的数据,而不是整个列数据。
  31. Garbage Collection

    那些用不上的旧版本属性,我们需要垃圾回收,GC可以站在 tuple 的角度,一些线程定时扫描整个 table,寻找可回收的旧版本;或者站在事务的角度,事务自身决定哪些 tuple 需要被回收。

  32. Index Management

    我们可以通过索引查询数据,所以索引也是需要链接到多版本的。

  33. 能否不使用 LOG 实现 undo 和 redo?

    • 撤销(Undo):未完成或者由于各种原因发生回滚(rollback)、中断(abort)的事务,其修改需要被撤销,即回滚为事务之前的旧值。
    • 重做(Redo):已经提交的事务,其修改操作的效果需要体现为新值。

SHADOW PAGING 对 database 有 master 和 shadow 两份拷贝,更新只改变 shadow 拷贝的部分,当提交时只需要改变 DB Root 的指向,把 shadow Page 刷盘并 GC 之前的 master。如果 undo 则不需要做任何更改。缺陷是在内存中拷贝一份复制代价太大。

image-20220903112133287

  1. 什么是 WAL?

    WAL 即(Write-Ahead Logging),是现在主流的备份形式。在事务提交前所有操作都会被记录到 WAL,主要包括事务ID、Object ID、Before Value(用来 UNDO)、After Value(用来REDO)。

    WAL的记录格式分为三种:

    1. Physical Logging:记录具体的页偏移位置的变化。
    2. Logical Logging:直接记录事务层的操作语句。
    3. Physiological Logging:混合上面两种,只记录页的某个 slot 的变化。

    image-20220903145626008

    随着 WAL LOG的增大,DBMS 会定时给 WAL 写入 Checkpoints(类似游戏中的存档点),在 checkpoints 之前的日志如果已经 commit,我们可以确保已经写入磁盘,则可以把这部分内容清除。

后续一部分关于分布式数据库的知识,打算有时间结合 6.824 一起学习。