为什么需要数据库系统？

因为读写磁盘是昂贵的，数据库系统可以管理超过内存大小的数据，并且有效的避免很长的停顿和性能的退化。

数据库底层是如何存储的？

首选数据库会有一个模块叫storage manager他的职责就是负责读写磁盘上对应数据的PAGE，同时保持较好的空间和时间的局部性。数据文件在底层会有不同的组织形式，比较常见的是无序的HEAP FILE， 或者是有序的聚集索引（B树），还有一种是HASH FILE。

HEAP FILE 内部是怎么组织变成一个数据库的？

有2种方式可以组织。 第一种是链表的方式，会有一个PAGE 头，然后会有指针存储指向下一个和上一个PAGE位置的信息。 里面分为2个链表，一个是指向free page list, 另一个是指向data page list. 每一个page 自己会记录自己还有多少free的slot。

image.png

另外一种方式是有一个字典的文件，他会记录全部数据文件的位置，同时也记录了每一个页的FREE SLOT数量。

image.png

每一个数据页的头会存哪些元数据？

页大小，CHECKSUM， 数据库版本，事务可见性。。

页内如何存数据？

首先页头，会说SLOT 数组有多少大，数组里的每个数字表示TUPLE的OFFSET。 数组从前往后增，TUPLE从后往前增。

image.png

另外一种存储形式就是LSM ,文件里存的是操作本身，需要数据的时候，根据LOG 把数据恢复出来。这里为了加速读性能，会对文件建索引，同时可以加入布隆过滤器优化

image.png

TUPLE是怎么在文件里表示的？

首先TUPLE的结构已经有表结构在外部已经定义好了。那么TUPLE只需要存每个COLUMN实际数据以字节形式就可以了。每一个TUPLE 在DBMS里会有以page_id + offset/slot的二元组唯一定位。

image.png

存储模型有哪2种？

一种是行存储，一种是列存储。

行存储更加适合OLTP，他的优点是快速插入，更新和删除。对查询整个TUPLE的语句友好。缺点是对很大量的表扫描只需要一点列的不友好。会因为这一点信息，而使得BUFFER POOL被污染。

列存储正好相反，它能够有效减少IO让费，他只读他需要的列数据。并且因为一列的数据都在一起，可以更好的处理和数据压缩。缺点就是对单点的QUERY和插入，删除，更新不优化。因一个TUPLE是要切割开存进不同的文件的。所以他更适合OLAP。

为什么需要buffer pool manager?

数据库本身比OS更加了解该怎么加载磁盘文件。比如他可以做自己的淘汰策略，可以做预取优化， 把脏页用正确的顺序去刷盘。

BUFFER POOL 内部是如何？

首先会有一个POOL 从DISK把PAGE加载进POOL，同时还有一个PAGE TABLE 去维护当前哪些页再内存里。同时还会维护一些额外的信息，比如这个也是否脏了，已经PIN COUNT。

PAGE DIRECTORY 和 PAGE TABLE的区别？

PAGE DIRECTORY是映射PAGE ID 到PAGE在DB FILES里的位置，这个是存在硬盘上的。PAGE TABLE是维护PAGE ID到 PAGE 在BUFFER POOL的映射，这个是个内存信息。

BUFFER POOL 的优化

1. 预取，就是把之后可能要的页提前存入BUFFER POOL，然后之后就可以读内存拿了。

2. 共享扫描，如果2个QUERY要扫的页是差不多的，可以让第二个QUERY 先和第一个页共享那部分一起扫的页。最后再分别扫不同的页。

3. BYPASS。 如果是顺序全表扫描，可以不存进BUFFER POOL。避免热点数据被刷走

4. 用O_DIRECT 跳过OS自己的CACHE

为什么数据库BUFFER POOL需要LRU-K的策略？

LRU策略会有顺序扫描时的BUFFER POOL 污染问题。

数据库除了TUPLE的BUFFER POOL 还有什么内存POOL？

比如要排序的时候会用到SORT BUFFER，在写LOG的时候会用到LOG BUFFER。

Hash表主要关注什么？

Hash 函数的选择，就是在性能和冲突率之间的TRADE OFF。另外就是冲突之后的策略选择。其实是在开一个更大的表和找到其他地方去插KEY的TRADE OFF。

静态HASH算法有哪些，动态有哪些, 区别是什么？

静态算法有LINEAR PROBE, 链表法，cukoo hash. 动态有extendible hashing, linear hashing

静态算法要求DBMS事先知道要存多少元素，否则就需要在一定时间对整个表做扩容和缩容然后rehash。而动态没这个限制。

B树有哪些性质？

1. 他是完美平衡的，所有叶子节点的深度一致。

2. 每个非根节点至少是半满的。（如果最多有M个孩子，那么至少会有[m/2 -1, m -1]个key ） 3.每个内部节点有K个KEY，就会有K + 1个孩子。

聚集索引和非聚集索引在叶子节点的区别？

聚集索引KEY对应的是TUPLE， 而非聚集索引KEY对应的是RECORD_ID(PRIMARY KEY)

为什么有些DBMS不会MERGE节点当节点不到HALF FULL？

延迟MERGE 可以减少重新组织数据的数量。而更好的策略是，周期性的重建整个树。

节点的SIZE如何选择？

其实就是LEAF SCAN的代价 和 ROOT-TO -LEAF的代价的权衡。一般存储设备越慢，节点就需要越大。

如果KEY的长度是可变的，应该怎么做？

1. 存储指向TUPLE属性的指针。 2. 构建可变长度NODE。 3. Padding 到max length.

2. 构建一个间接的KEY MAP。就存在叶子节点本身。一个类似于上面存TUPLE的方式，同时在这个节点里构建一个SORTED KEY MAP。

   
   

如果有重复的key 怎么存？

可以用2个数组，上面是SORTED KEY，下面对应的是VALUE

或者一个KEY 对应一组VALUE。

B树有哪些常用优化？

1． 前缀压缩，如果这个节点的STRING 都是以ABC，开头，可以把这个ABC提出来，这样之后的信息都会少，就能存更多。

2． 后缀截断。如果后缀的信息没有区分度，则在中间节点的时候可以砍掉。

3． 指针调整，如果一个PAGE已经再BUFFER POOL 里PINNED了，我们可以存直接的指针来代替原来存的PAGE ID。来避免去PAGE TABLE 查ADDRESS。

4． 批量插入。如果一开始你就知道要插的所有KEY，可以对他们先排序，然后对这些KEY去构建INDEX BOTTOM UP。这样性能最好

B+树插入的时候，叶子节点和内部节点分裂有什么不同？

叶子节点是把中间的KEY复制进父节点。而内部节点是把中间的KEY直接推到父节点。

请说说什么是隐式索引，局部索引，覆盖索引，包含索引(index include column)？

隐式索引比如建表的时候 写了unique, 或者primary key 会帮你自动建UNIQUE INDEX

局部索引，就是对表的数据的子集建索引。

覆盖索引，就是建联合索引来保证要QUERY的字段都在索引里有，而不用回表查主键索引

包含索引，就是包含的COLUMN 只在叶子节点有，而不会在搜索时被用到。其他同覆盖索引。

说一下latch crabbing 基本思想？

首先拿父PAGE的LATCH， 然后拿孩子的LATCH。如果父节点是SAFE的则释放父PAGE的LATCH。SAFE的意思是这个节点不会发生SPLIT 或 MERGE

查的时候，拿到孩子的读锁就可以释放父亲的读锁。

删增的时候，拿写锁，如果某一个孩子是SAFE的，可以释放祖先持有的全部锁

还有一个优化是可以先假设叶子节点是安全的，在一开始可以只上读锁。如果发现这个假设是错的，再重头来一遍写锁。

如果要同时支持LEFT->RIGHT， TOP->BOTTM, 当发现锁被占有了，最好的方式是等一小会然后放弃自己，重头开始。

还有一个优化是把PARENT节点的更新延迟到下次获取写锁的时候

描述一下有108个页，内存只能容下5页，如何做硬盘外排序？

首先每次放进内存5个页，对5个页排序，写到磁盘的一个文件里。这样最后会有22个文件。

下一次开始做K路归并，把4个文件放进去BUFFER里，然后流式读文件。还余下的一个文件的位置是用来当PQ，每次输出一个最小的写进磁盘。这样搞完之后。就还有22/4 = 6个文件。

下一步同样，变成2个文件。最后合到一个有序文件。

描述一下如果是GROUP BY或者DISTINCT 可以怎么做？

先用一个PAGE 流式读入数据， 根据HASH FUNC 1把，余下B-1个PAGE描述B-1个PARTITION的输出流落盘。

随后根据每个PARTITION文件，我们再读进来所有PARTITION1 的数据，根据HASH FUNC 2 来在内存里构建HASHMAP。随后就可以DISTINCT了。依次做完所有的B-1个PARITION。

这里可以看到如果HASH FUNCTION 能很均匀这个表最大也只能是B*(B-1) 个page大小。

如果更大我们可能需要更多轮。

描述一下数据里JOIN 是怎么做的？

首先有最基本的NESTED JOIN，就是外层选一个页数较少的表，然后一次性把所有的外层表的页尽可能读到内存里。随后把内层表的页一页一页读进来，还要留一个也是找到相匹配的条目进行输出。

优化的做法是可以用SORT-MERGE JOIN。先分别对外层表和内层表按照JOIN KEY 要做好排序。那么最后只需要MERGE的时候，对条目进行输出即可。这种方式在JOIN KEY上已经建了索引，或者输出需要有序时被使用。

第三种做法是HASH JOIN

我们可以对2个表的数据分别PARTITION 到不同文件，用相同的HASH 函数。随后读出这2个文件，2重FOR循环。如果一次PARTITION还是没法全部读进内存。可以使用第2个HASH函数。

描述一下一个执行计划数据系统是怎么做的？

比较常见的是迭代模型，每一个关系函数会实现自己的NEXT方法，下层的NEXT函数 会被上层的算子调用。构建出自己的NEXT函数。而根节点的NEXT函数，就可以直接取到这个QUERY 要的一行行数据

物化模型则是把数据准备好一齐返回给上层，而迭代模型是流式的。

而矢量模型是一个折中，他是会暴露NEXT函数 之后是批量返回需要的数据。

描述一下几种常见的访问数据的方法？（access method）

最基本的就是顺序扫描。数据库维护一个当前扫完的页的指针。优化方式有，预取，缓存池绕过，统计信息检查（比如这页的最大值是300，你要查400以上的数据，就可以跳过该页），延迟物化，这里就是每个算子知道上层用不到哪些列，可以去更新OFFSET，让上层可以不用管他用不到的列信息。

其次是索引扫描，就是优化器会挑选最适合的索引去走索引文件。当然如果走非聚集索引，需要回表，这里有一个优化就是，把那些要回表的PAGE ID先存起来，然后把PAGE ID 排序，这样就可以顺序把需要的PAGE 都取好，读起来会比查一个找一个快很多。

还有一种是BITMAP SCAN，这里是会用多个索引，求交集之后再返回结果。

WHERE语句的判断是怎么实现的？

数据库底层会构建一个EXPREESION TREE，然后最后依次取算看树根最后是不是TRUE。当然这种方式是比较FLEXIBLE，但是缺点是比较慢。更加好的做法是类似于JIT编译，然后非常快的算出这些表达式。

执行层的并发说说看进程并发和线程并发的优缺点？

进程并发依赖OS调度器和共享内存，优点是一个坏的进程不会影响另一个。缺点是对CPU CACHE 局部性不友好。线程并发的缺点是需要DBMS自己来管理调度，同时一个线程挂了会影响整个系统。优点是快，上下文切换开销小很多，同时无需管理共享内存。（线程并发说的是不同的SQL同时执行，不是指一个QUERY利用多线程去执行）

INTRA-QUERY 和 INTER-QUERY 区别？

INTRA-QUERY是为了减少慢SQL的延迟。INTER-QUERY 是为了提升系统的吞吐，和减少总的延迟。

请你讲一下INTRA-QUERY并行是如何做的？

这里有几个方式 一种是intra-operator, 他是把一个数据集拆成一个个碎片，然后把相关的FUNCTION 开启多个WORKER作用在不同小碎片上，最后会有一个EXCHANGE OPERATOR来合并。这里的思想和MAP REDUCE很像。另一种是INTER-OPERATOR，其实就是利用PIPELINE的思想，使得下面的结果一边出来，上面就可以提前处理。这2个属于不同的线程，类似于PRODUCER CONSUMER

IO的并行又是如何做的呢？

一种是多磁盘的并行，底层利用RAID，对数据库是透明的。

另外一种就是做PARTITION，分为垂直切分，按照列切。或者水平切分，分布式数据库里的SHARD。

QUERY 是怎么从用户输入 到最后变成可执行的计划的？

首先SQL QUERY会经过 重写器，这里会根据一些固定的模式对QUERY做改写，随后会经过PARSER生成一颗语法树，语法树的节点去查system catalog会把一些人可以读懂的关键词 转换为系统内部的INTERNAL ID。 然后交给tree rewriter看下这颗树可不可以优化。到这里产生出了逻辑计划。逻辑计划结合一些基于统计样本的COST MODEL 再做一层优化生成出物理执行计划。

逻辑计划和物理计划的区别是？

逻辑计划就是一些代数算子生成的一颗语法树。表示这个SQL ，通过这些代数组合是等价的性质，可以去做优化，这里的优化通过一些静态规则和启发函数，可以再不用对DB的内容知道的情况下做出。而物理计划就是具体调用底层存储引擎的哪些API去实际取数据。这里需要知道DB的数据分布，根据抽样统计得到的信息估算出更好的获取数据的方案。

常用的逻辑计划优化的方式有哪些？

1. 谓词下放，可以提前缩小数据行范围，这样JOIN的时候量会少，会更快

2. 投影下放，这是提前缩小数据列范围，也是减少之后的空间使用，更多行可以放入内存，就会更快。

3. 表达式重写，这里有很多例子，比如无用表达式删除，合并谓词，连接消除等。

说一下物理计划的优化方式？

首先就是基于统计，数据库会对每个表计算一些统计信息。比如最常用的就是一个列的选择度。就是这个列的DISTINCT值。 然后如果假设这些值分布均匀我们是可以估计出所有谓词的选择度， 比如范围: sel(A >= a) = (Amax − a/(Amax − Amin))。如果不均匀，也有2种方法，一种是建立均匀的桶。 这里其实是一道算法问题。就是给你每个KEY 的FRENCY，你要装进10个桶，使得每个桶的SIZE 的差值最小。

另外一种方式是抽样。根据抽象数据去判断谓词的选择度。这个选择度在JOIN TABLE时非常重要，我们希望外层表越小越好。

下一步优化器 会枚举出所有的可能的执行计划，并且计算他们的COST，然后选择COST最小的一个。对OLTP来说，这通常是简单，因为只要选对最佳的INDEX就可以。

但是OLAP通常会有多关系JOIN，随着JOIN数量增多，计划数的可能呈指数上升。

IBM最开始引入只考虑LEFT-DEEP JOIN， 是为了更好的利用PIPELINE，这样可以不用把JOIN出来的结果序列化到磁盘。可以流式的去做。

接下来的可以枚举所有LEFT-DEEP TREE的顺序，枚举每个JOIN是用哪种JOIN算法，枚举每个表是用INDEX SCAN 还是SEQ SCAN。 然后用动态规划的方式取算出最小的代价的方式。如果要JOIN的表很多时，我们可以使用遗传算法来找到较优解。

一个SQL的子SQL是怎么优化的？

子SQL, SQL OPTIMIZER 会把它当做一个函数，所以并不会把优化像JOIN那样计算在里面，所以最好SQL不要含有子SQL。

简单介绍一下ACID？

A就是原子性，事务里的操作要么全做成了，要么全没做成。这个背后的机制可以使用LOG来实现，也可以通过SHADOW PAGING来实现。C是一致性，代表执行事务前如果状态是一致的，那么之后也是一致的。I是隔离性，虽然有很多事务会并行在做，但是每个提交的事务自己看上去会是只有自己在做。就是并行的事务不会相互影响。D就是可持久性，所有事务提交的数据不应该丢失。

操作冲突是什么？

有2个操作属于不同的事务，并且同时操作同一个OBJECT，其中有一个是写我们就定义为操作冲突。比如，读写冲突，会引发脏读。写写冲突会引起更新丢失，写读冲突会引起不可重复读。

如何判断一个事务语句执行顺序和串行执行是等价的呢？

把那2个事务的语句去做等价交换（就是对来自不同的事务的2个连续的不冲突的操作做交换）最后可以转换到serial schedule 就说明这个执行顺序是满足conflict seriablizable.

对2个事务交换操作是容易的。如果有更多事务，我们需要构建一个有向图。每当我们遇到一个来自Ta 的操作和一个来自Tb 的操作冲突，并且Ta的操作更早，那我们就加一条从Ta->Tb的有向边。 最后我们只要这个依赖图是否有环即可。

什么是 view serializability?

这种调度比conflict serializability 更加大，因为他可以包含一些被覆盖写的情况。比如1个事务读后写A，另一个事务写A， 第三个事务也写A. 我们把第二个事务插在第一个事务的2个操作中，在conflict serializability是会判定有环的。但是只要第三个事务最后写A，其实是无影响的。结果和1,2,3顺序执行一致。这种定义因为太过复杂所以目前还没有数据库实现。

介绍下什么是二阶段锁定 并且他的问题？

就是一个事务拿锁和还锁分为2个阶段，第一个阶段你可以拿，一旦你还了就到了第二个阶段，之后就不能再拿锁了。问题是2阶段锁定会造成级联ABORT. 比如你上来拿了锁A,B你还了A，第二个事务拿到A开始做事情了，然后你ABORT了。第二个事务也只能ABORT。因为由于你最后是ABORT，你对A的操作不应该泄漏出去。如果不级联ABORT，你就会脏读。当然还会引起死锁的问题。解决脏读问题可以靠严格二阶段锁定。同时二阶段锁定的集合不能还原出所有的是conflict serializable的情况，有些情况是合法的，但是二阶段锁定里不会产生。

那什么是严格二阶段锁定？

他在二阶段锁定基础定义，只在再事务结束时才释放所有锁。它可以保证一个值被这个事务写了，直到事务结束其他人才可以拿到这个OBJECT的锁。

死锁发生了怎么办？

有2种方法，1个是死锁检测。数据库系统会构建事务之间锁依赖的有向图，如果有环就代表有死锁了。当发现了环，他会选择一个要事务去让他ROLLBACK来打破这个环。这个被牺牲的事务可以ABORT或者重试。这中间是对检测死锁的频率，和事务的等待死锁解开时间的trade-off。

如何选择这样一个事务看，可以由很多的考虑维度。比如他之前被KILL了多少次，他占有了多少锁，他的启动时间，他已经执行了多少进度。

另外一种方式是死锁预防，分为wait-die 和 wound-wait， 2种策略

你可以分别讲下wait-die 和 wound-wait 这2种策略的区别吗？

这个语句的主语其实都是针对要申请锁的事务。而对手方是持有锁的事务。

前面一个单词代表主语优先级更高时候做的事情，后面是优先级低。而优先级高，就代表这个事务启动的早。

所以对于一个老事务要去拿新事务的锁在WAIT-DIE下，他会WAIT，在WOUND-WAIT下，他会让新事务回滚，直接抢了他的锁。

新事务要拿老事务的锁的话，在WAIT-DIE，会把自己回滚。在WOUND-WAIT下，会等老事务把锁还掉。

这里比较重要的是，当一个事务重启，必须要用他原来的TIMESTAMP。不然旧的变成新的，可以引发饥饿。

如果一个事务要更新10万行，那他要拿10万把锁吗？

不需要，这里涉及到锁的粒度。粒度可以是PAGE，可以是TUPLE，可以是TABLE，可以是ATTRIBUTE。这里会引入意向锁，可以提高并发度，以及减少实际需要的锁用量。在父节点上IS（意向共享锁），代表需要在之后需要更细粒度的S LOCK。 如果上的是IX，就意味在接下来更细粒度需要X LOCK。 SIX 锁就等价于上了S锁 加IX锁。2个规则是如果要上S或者IS锁，那么父节点必须要有IS锁。如果要上IX,X,SIX，那么父节点必须要有IX锁。

当获得太多的细粒度锁的时候，锁会升级为粗粒度的锁。

你知道有哪些乐观的CONCURRENCY CONTROL的协议？

最基本的是TO，也就是TIMESTAMP ORDERING， 他的基本做法就是每个事务在启动的时候会有一个时间戳，然后他们去读写一个OBJECT的时候会去CHECK自己的时间是不是最新的，如果有一个更新的，自己则要回滚。这种做法能保证CONFLICT serializable， 但是有unrecoverable 的缺点，以及长事务容易被短事务整饥饿。

如果所有事务都很快，而且冲突率很低，其实更好的做法是OCC。OCC 分为3个步骤，READ PHASE, VALIDATION PHASE, WRITE PHASE。核心思想就是先把数据库的内容读到自己的私有空间，要在提交时，去检测有没有和其他的事务有读写冲突，或者写读冲突。这里分为forward validation 和 backward validation，如果顺利，就可以进入write phase 把自己私有空间的内容刷进DB。OCC的问题是有复制数据的OVERHEAD，还有VALIDATION 和写是瓶颈，如果发生了ABORT，让费的操作比2PL更多（因为没法提前知道出了问题，直到VALIDATION PHASE）

简单介绍一下MVCC吗？

MVCC是一套很大的概念，核心思想是读不阻塞写，写不阻塞读。做法是一个值有多个版本。它分为4块组成。第一块是选择一种并发控制协议，比如可以是T/O, OCC, 或者2PL。

第二个如何来存版本，有3种方案，第一种是APPEND-ONLY STORAGE，

image.png

第二种是单独开一个表来存，叫TIME-TRAVEL STORGAE，他会把最新的改变更新进原表，把前一个版本的放到一个新表，然后多个旧版本用指针连接起来。

image.png

还有一种也是单独开一个表，但是里面存的是变化的DELTA，而不是完整的旧数据。

image.png

其次还要搭配GC，来回收那些已经不可见的版本。分为TUPLE级别的GC和事务级别的GC。

事务级别的GC就是事务在做完的时候直接回收掉那些已经不可见的版本。

TUPLE级别可以是有一个后台线程周期的去扫垃圾，也可以是工作线程再下次去读版本的时候顺便回收掉不可见的版本。

最后一个概念就是索引管理。我们知道我们有时会是根据索引去查数据，那么索引也必须链接到多版本数据的指针头。这里又分为逻辑指针，就是对每一个元素我们都给它一个唯一的ID，不管里面数据怎么变，这个ID不变，我们再在内存里维护一个MAP，表示这个ID对应的物理指针是什么。这样做的好处是，如果版本发生变化，只需要改这个MAP里的映射关系一处。

image.png

另一种做法是直接每个索引都会存实际的物理指针，少了一层映射层，可以更快，但是维护代价更大，设想有很多二级索引都维护了这个信息。所以一变，所有索引都要跟着变。

image.png

数据库的失败恢复是怎么做的？

这里主要分为2块，第一块是数据库要采取一些行动当事务正在运行的时候，来保证DBMS可以从失败恢复。第二块就是当数据库重启的时候需要采取一些动作来恢复之前的状态确保ACID的性质。

可以讲一下redo, undo log的关系吗？一定要使用这2个LOG嘛？

首先REDO LOG是用来对已提交的事务做恢复，UNDO LOG 是为了对未提交的事务做回滚。

第二个问题需要知道BUFFER POOL POLICY 的知识。这里有2个维度，一个是STEAL, NO-STEAL。 代表BUFFER POOL可不可以在事务未提交前，就把脏页刷到磁盘。如果可以的话，就会需要UNDO LOG。 还有一个维度是FORCE, NO-FORCE 代表强不强制事务在提交时一定要把事务涉及到的脏页全部刷盘。如果不强制就需要REDO LOG。

所以如果BUFFER POOL 用的是NO-STEAL, FORCE策略，就可以既不需要REDO LOG也不需要UNDO LOG。

如果一个LOG都不用，如何实现事务呢？

有一种方案叫SHADOW PAGING。首先所有的数据页会被组织成树状结构，会有一个根节点指针，然后页分为2种版本，一种是MASTER，代表当前DB的数据状态。另一种是SHADOW，代表正在做的事务的临时改写状态。如果COMMIT，那一刹那其实就是一个ROOT的指针从MASTER切换到SHADOW的过程。如果出了什么意外，只要GC把那些SHADOW页给回收掉，原来的数据是不会变的。这个方法的缺点是一次只能提交一个事务，或者一组事务捆绑起来提交，而且提交时要做很多事，所有修改写需要FLUSH，数据会变得破碎，基本上是随机读，性能比较差。

那性能好的做法是怎么样的？

这个就是依赖WAL，首先最重要的一点是随机读，随机写变为了顺序读，顺序写。所有事务做的操作会去记录WAL，共享一个LOG，添加在最后。当事务COMMIT时，只要确保LOG 刷盘了就不会丢数据。而且BUFFER POOL根据需要可以自行选择脏页刷到磁盘，因为即使后来事务回滚了，也可以通过LOG UNDO掉这些刷盘的数据。所以运行时性能非常好。缺点就是恢复时会慢一些，但是DB挂很少，所以是被广泛使用的方案。

WAL 什么时候会被刷盘？

一个是当一个WAL LOG BUFFER PAGE写满的时候，会触发一次刷盘。同时第二个页可以用来写，这样性能非常好，另外一种情况，就是过了一定的时间，也会触发一次刷盘。其次就是事务提交时会触发刷盘。

WAL里写的是什么？

LOG 分为3种格式，一种是物理日志，存的就是具体的页的位偏移改了什么。缺点是如果一个SQL改了10W条数据，那么就会有这么多的LOG信息。优点是更加细节，不易出错，更容易恢复。另一种是逻辑日志，基本就是把SQL语句给存下来。优点是磁盘占用空间小。缺点是并发事务时日志会不准，数据可能会不一致。而且恢复起来会更慢。

还有一种是半物理日志，他存的是具体的页的数据信息但是和页的数据组织无关。会更加通用，且易在上面做优化。可以其他下游系统去读取。

WAL 怎么回收？

DBMS会周期性的打CHECKPOINT， 凡是打了CHECKPOINT的位置在这之前已经COMMIT的TX一定是已经落盘了。所以关于这些的WAL就可以回收掉的。最简单的打CHECKPOINT的方式就是停掉所有TXN，然后开始刷盘，然后再日志上打一个CHECKPOINT记录。然后恢复停掉的TXN继续做。所有在CHECKPOINT后开始的事务，在CRASH前没提交，需要UNDO。在CRASH前提交了，需要REDO。

讲解一下ARIES是怎么做的？

首先ARIES 需要搭配WAL，也就是说BUFFER POOL的策略要是STEAL+ NO FORCE。随后每一个WAL里需要有一个LSN，在刷脏页的时候，我们需要确保LOG 先于PAGE落盘。怎么保证就是比较PAGE上的最新LSN是否小于等于flushed LSN，如果是的话才可落盘。每次WAL从LOG BUFFER 刷进磁盘，就需要更新FLUSHED LSN。事务在提交时，会把所有内存里的LOG 给刷进磁盘。因为这个是顺序写所以非常快。如果事务回滚了，我们需要利用这个事务的PREV LSN（代表这个事务里之前一行LOG是什么）来插入CLR 日志。CLR的日志目的是为了表示对这个事务的回滚我已经做了哪些。同时通过LOG里的UNDO NEXT LSN，来指向下一个应该UNDO的lsn 是多少。如果所有记录都回滚了，就可以插入一个TX-END。

下面说一下CHECKPOINT， 首先会打一个START-CHECKPOINT，随后对这个START之前到上一个START CHECKPOINT之后的日志，做一个统计，生成出ATT 和 DPT。然后，对START之后的那些，更新DPT，不更新ATT。把这个2个结果插入END-CHECKPOINT。再插入END-POINT的同时，去更新MASTER RECORD为START CHECKPOINT这行LOG的LSN。ATT的作用是记录当时还没结束的TXN，DPT的作用是记录当时内存里未刷盘的脏页（当然这个在REDO可幂等，即使后来刷盘了，也可以不用从内存中把它去掉）。

有了上述前置知识，我们可以来说下ARIES了。

ARIES分为三步，第一步是分析，目标是得到CRASH时刻的ATT和DPT，从MASTER RECORD开始读所有日志，然后更新ATT和DPT。第二步是根据DPT里最小的LSN 我们就可以把这之后的所有操作都在内存中REDO，如果有TXN-END，就可以更新ATT。第三步是就是余下的ATT表里都是没做完的TXN，需要UNDO，把他们UNDO掉。

结语

RDBMS 有3个硬骨头，分别是SQL优化，并发控制，失败恢复。
我自己用JAVA来模拟了并发控制和失败恢复在数据库层面是怎么做的,有兴趣的小伙伴可以来我的GITHUB CLONE下来玩。

之后我会补博客来说明这些项目。

• 第一个项目是实现事务的原子性和持久性的ARIES算法。
• 第二个项目是实现MV+2PL来实现各种隔离级别，来防止脏写，脏读，读偏斜，写偏斜，幻读。
• 第三个项目是基于第一个项目，实现2PC的悲观分布式事务
• 第四个项目是实现一个LSM TREE 的KV存储
• 第五个项目是基于第四个项目，实现OCC的乐观分布式事务