安装目录插件，阅读体验更佳！！！
参考：https://www.jianshu.com/p/a40ec70d9365

第一部分：【数据库理论基础】数据库历史演进与未来展望

一、时间轴

1. 导航型数据库：

• IDS数据库（网状模型，1964年，GE）
  优点：更接近现实、性能良好；
  缺点：结构复杂，存取路径对用户不透明

• IMS数据库（层次模型，1966年，IBM）
  优点：数据结构简单、查询效率高
  缺点：不适用于现实世界、查询必须依赖父节点

2. 关系型数据库：（1977年第一次数据库大战）

• IBMSystem R（1974年，IBM）
• Ingres（1977年）
• Oracle（1979年，关系型数据库商业化开启）
• IBM DB2（1983年，IBM）
• Sybase SQL Server（1987年，Sybase和微软合作）
• MS SQL Server（1989年，微软买下了Sybase的代码版权）
• PostgreSQL（1989年）
• MySQL（1995年）
• MonetDB（2004年）
• CStore（2004年）

3. NoSQL：（第二次数据库大战）

• 问题：传统关系型数据库采用集中式架构，没法解决传统互联网时代的可扩展和高并发问题，因而数据库逐渐进入分布式和云时代，先说下分布式系统（这是一个比较古老的领域，直到最近一二十年才有机会从理论走向大规模工程实践）
• 对于OLTP(online transaction processing) - 主要解决事务的处理能力。NoSQL弱一致性，缺乏标准化；扩展性好，灵活- SQL 扩展性查，预定义schema；强一致性
• 对于OLAP(online analytical processing) - 主要解决事务的查询分析能力。MapReduce 用于数据分析，不是一个完整的数据库系统，催生了Spark，Hive
• Distributed/ Cloud DBMS ~2000s传统数据库有扩展性，和高并发问题

分布式系统：

• Google GFS（2003年，解决分布式文件系统的问题）

• Google MapReduce（2004年，解决如果在分布式文件系统和分布式KVS上面如何做分布式计算和分析的问题）

• Google BigTable（2006年，解决分布式KV存储问题， 弱化了强一致性，以换取强扩展性）

  • 谷歌之所以产生这三个系统，是因为数据强一致性对系统的水平扩展，以及海量数据爆发式增长的分析能力出现了断层，为了解决这个问题，将数据强一致性的需求给弱化了，换来能够使用分布式的集群来做水平扩展，谷歌这三个件发布后，衍生出了NoSQL，也即Not Only SQL，针对非结构化、半结构化的海量数据的处理系统，出现了这第一代SQL

• HadooP（2005年，这个项目初衷就是要做出谷歌这三大件的开源实现）

• Amazon Dynamo（2007年，涉及思想是P2P技术，因为没有保证强一致性，没有成为主流Spark（2009年）

• OceanBase（2010年，国内分布式数据库的翘楚）

• Windows Azure Storage（2011年，微软）

• Google Spanner（2012年，标志着分布式数据库进入第二代）

• Amazon Aurora（2015年，运行在公有云上，将计算与存储分离，从而实现存储能力的可扩展，设计思想the log is the database，和Google Spanner成为第二代的两个流派）

• TiDB（2016年，国产数据库）

• ByteSQL、ByteNDB（2020年，字节跳动）

二、百家争鸣 - 各种数据库版本与名家

百家争鸣

三、星辰大海 - 数据库未来的发展方向

• Hardware：软硬件一体的研发
• Deployment：多写架构,AI/ML (Adaptive Columnar/Row store switch,Adaptive Indexing,Adaptive Query Optimization)，Edge 边缘计算,Cloud 云计算 与安全
• Scalability：事务处理，查询优化，高可用
• Data Model：多种存储方式，多种查询接口，标准 （SQL, KV, Doc, Graph, Time-series)，OLTP/OLAP融合

第二部分：【数据库理论基础】SQL 查询引擎概述-关系模型与查询优化

一、SQL 语句分类

关系模型->关系代数（过程式）->SQL（声明式）

SQL 语句分类

二、查询流程概述

SQL->AST->Logical Plan Tree->Physical Plan Tree

查询流程

三、基于规则的查询优化

基于关系代数等价性进行逻辑变换，减少无用开销

• 关系代数等价：关系代数表达式生成相同的结果集
• 依据关系代数的等价交换原则做一些逻辑变换
• 谓词下推：1) 尽可能早地进行过滤；2) 分解复杂的谓词条件，下推；3) 分解连接条件，笛卡尔积转Join计算
• 投影下推：提前做投影，去除不需要的列信息
• 排序、Limit、聚合下推
• 投影消除：如果子集投影和投影操作相同，则消除投影操作
• 排序消除：如果子集结果排序和排序操作相同，则消除排序操作

四、基于代价的查询优化

基于统计信息进行代价搜索，选择最优的物理执行计划

第三部分：【数据库理论基础】SQL 查询引擎概述 - 执行引擎

一、查询流程和表达式

1. 查询流程

查询的过程：SQL语句->查询计划->查询结果

2. 查询计划

查询计划描述了执行的动作，通过以下方式进行描述

1. 运算符（Operator）：Projection\TopK\Sort\Filter(Select)\HashJoin\Aggregation\TableScan...
2. 表达式（Expression）：R.id, S.id, S.age \ age >= 20 \ COUNT(S.id) + 1, AVG(S.age) <= 50 \ R.id = S.id \ ...
3. 运算符中包含表达式

查询计划示例图

3. 表达式（Expression）

3.1 表达式类型：常量，元组属性引用，标量函数，聚合函数

• 常量（Constant）：表达式中的常量值
• 元组属性引用（Tuple Atribute Ref）：引用表中某个属性的值
• 标量函数（Scalar Function）：比较（,!=,>=,<=,in..）；逻辑 （AND,OR, XOR, NOT..）；算术 (AND, SUB, MUL, DIV, MOD ..)；内置函数（Buildin Function）；自定义函数（UDF）
• 聚合函数（Agg Function）：COUNT，MAX, MIN, SUM, AVG

表达式示例

3.2 表达式求值

整体是自底向上求值，分为 元组属性求值、标量函数求值、聚合函数求值 三种：

• 元组属性求值：输入一个元组，输出元组中对应属性的值；
• 标量函数求值：Row Style 输入一个元组，输出一个标量；Block Style 输入一个 Block，输出一个 vector；
• 聚合函数求值：Initialize 初始化聚合状态；Update 根据当前的 Tuple 更新聚合状态；Finalize 计算聚合最终状态

聚合函数求值示例

二、常见运算符

表达式和运算符都是查询计划的一部分，但是运算符内容比较多，所以单独放一个章节

1. 排序（Sorting）

排序是查询执行中的基本算法，在多个场景中使用，Order by, group by, sortmerge join
排序类型：1) 内存排序(In-memory sorting) 快排、堆排、归并排序等；2) 外部归并排序( External Merge sorting) IO代价评估、两路外部归并、K路外部归并。

2. 聚合（Aggregation）

聚合定义：将多个元组按照指定的聚合函数，生成一组聚合结果 。聚合经常和分组（Grouping）操作配合使用，在组内聚合。
聚合的实现方式：流式聚合；哈希聚合。（具体使用什么方式是优化器来决定的）

流式聚合操作流程：

• 对元组按照分组表达式求值，按结果排序；
• 顺序扫描，对每个元组进行聚合表达式求值。

流式聚合适用场景：

• 聚合前数据已经按照分组表达式有序
  • 分组列上存在索引
  • 上游运算符按照分组列做了排序
• 要求聚合后的数据按照分组表达式有序

流式聚合操作示例

哈希聚合操作流程：

• 将元组以分组值为key，判断hashtable是否存在该key对应的聚合结果。
• 如果存在，则将元组按照聚合函数合并到聚合结果中 (Update)
• 如果不存在，则以元组的分组值为Key在HashTable中创建一条新记录 (Initialize)，再合并元组到初始化的聚合结果中 (Update）

哈希聚合操作示例

3. 连接（Join）

连接定义：将多表中符合条件的行连接成一行。
为什么需要Join？：在数据库建模阶段，将不同的实体创建独立的表；在查询阶段，获取具有关联关系的多个表的数据。
Join类型：分为 Inner join，Left Outer Join， Right Outer Join。
实现算法：Nested Loop Join，Sort Merge Join，Hash Join

• Join-Nested Loop Join：最简单，两次 for 循环遍历两个表。实现简单，适用于等值和非等值的Join条件，但是性能较差

Nested Loop Join 示例

• Join-Sort Merge Join：两个阶段：Sort阶段和Merge阶段，先将两个表按照 Join Key 进行排序，然后顺序扫描排序后的表，根据 Join 条件作出 Merge 的输出。要求输入表在 Join Key 上有序、输出结果要求在 Join Key 上有序

Sort Merge Join 示例

• Join-Hash Join(1)：两个阶段：Build阶段和Probe阶段，先扫描左表创建内存 Hash Table，然后扫描右表，查询 Join Key 在 Hash Table 中是否存在并输出结果。要求输入表在 Join Key 上无序，分布均衡、对输出结果没有顺序要求、等值Join条件。一般情况下将小表作为左表。

Hash Join 示例

• Join-Grace Hash Join(2)：两个阶段：Parition阶段和Probe阶段，先分别扫描左表和右表，按照 Hash Key 映射到不同分区，然后分别扫描两表对应的分区，做内存 Join。适用于小表的数据量太大无法在内存中创建Hash Table的情况。

Grace Hash Join 示例

4. 访问路径（Access Path）

访问路径：从关系表中读取数据的方式 (从存储中读取数据)，分为：Sequential Scan 全表扫描；Index Scan 索引扫描；Multi-Index Scan 多索引联合扫描。
具体采用哪种访问路径由优化器决定。
索引覆盖：索引中包含了全部要访问的字段，无需扫描表本身。

访问路径示例

三、执行模型

1. 火山模型（Vocano Model）：又称迭代模型（Iterator Model）

是当前的主流执行模型：每个 Operator 通过 Next(row) 函数向上层 Operator 返回数据；每个 Next(row) 调用返回一行数据；数据从下层逐层返回上层，像火山一样。
优点：占用内存少，便于输出控制，按需返回数据
缺点：Next 调用次数多，开销大
改进：Next(batch) 批数据调用返回；Operator 内部对批数据进行并行处理（SIMD）

火山模型示例

2. 并行执行模型

为什么并行执行：降低时延，提升吞吐，提升资源利用率。
包括单机并行和多机（分布式）并行
并行执行的类型：查询间并行 Intra-Query Parallelism、查询内并行 Inter-Query Parallelism（Operator 内并行 Intra Operator、Operator 间并行 Inter Operator）
Operator 内并行：需要引入 Exchange 运算符

并行执行模型示例。虚线即为并行分割方式

3. Exchange运算符

Exchange Operator 用于在并行执行时对数据进行重分布

• 输入流数量（N）；输出流数量（M）
• 常见的 Exchange Operator 类型：Gather(N:1)；Split(1:M)；Repartition(N:M)；Brodcast(N:M)

Exchange Operator 类型示例

4. 并行聚合(repartition类似map-reduce)

并行聚合示例。左侧为常规的数据流操作，右侧表示第一次 LocalAgg 的结果太大导致没办法放到内存中进行直接操作，因此需要进行重分布后，再次进行聚合；第二次是直接可以 Gather 的，因为上次重分布会把相同的 Key 放到同一个分区中。

5. 并行连接(broadcast类似spark的广播变量)

并行连接示例。左侧场景有限，要求 R 是小表。对于大表，则需要先拆分，再广播进行分区连接

第四部分：【数据库理论基础】数据库存储和索引概述

一、数据库存储

1. 什么是数据库存储引擎

1.1 定义

存储引擎就是如何存储数据、如何检索数据和如何更新数据等技术的实现方法

1.2 组成

权限及完成性管理器、事务管理器、文件管理器、缓冲区管理器

1.3 存储引擎的数据结构

• 数据文件（Data Files）：存储数据库自身
• 数据字典（Data Dictionary）：存储关于数据库结构的元数据
• 索引（Index）：提供对数据项的快速访问

数据库引擎示例

2. 插入和检索一条记录

2.1 插入

1. 数据库客户端发送请求
2. 查询处理器使用数据字典和统计信息生成最优执行计划
3. 调用事务管理相关逻辑，例如加锁，分配事务号和时间戳，冲突检测等
4. 调用文件管理器写入WAL
5. 向缓存区管理器插入数据和索引

2.2 检索

1. 数据库客户端发送请求
2. 查询处理器使用数据字典和统计信息生成最优执行计划，使
   用索引或者做全表扫描
3. 调用事务管理相关逻辑，例如加锁，分配事务号和时间戳
4. 向缓存区管理器查询索引或者数据的缓存
5. 调用文件管理器查询索引或者数据，并写入缓存区管理器

3. 数据库存储与分类

3.1 数据组织形式

• 行存
• 列存
• 行列混合存(PAX格式、Spaner中采用；OceanBase的列组也可以看做这种形式)

3.2 数据粒度

• Page粒度：将多行记录聚合为一个 Page，数据和索引都是按照 Page 的粒度进行访问。存在读写放大；元数据少。如 MySQL, PostgreSQL等)
• Tuple粒度：单行记录就是最小访问单元，内存数据库、可以基于字节寻址的NVM数据库通常采用此粒度（ByteNDB）。读写放大小, 但元数据多，内部的节点也会多很多。

3.3 存储位置

• 本地：成本高，受限单机容量等缺点。
• 远端(计算存储分区)：Share-Disk、Share-Storage。

3.4 数据集位置

• 内存：数据集全部在内存中，WAL只是作为故障恢复使用，再利用 Checkpoint 加速恢复。常见于内存数据库，适合需要高性能且数据量不大的表。如Azure 中的 Hekaton。
• 磁盘/NVM：数据集全部在持久化介质中，内存只是起到缓存的作用，不影响正确性。

4. 常用存储结构

4.1 基于B+树的 In-Place updates

定义：数据和索引都存储在文件系统中，通过B+树索引某个元组，原地进行 insert/update/delete 等操作。
缺点：需要额外的软件设计来维护文件的一致性。比如更新16KB的数据，在底层文件系统是4KB为单位分四次写入的，但是写入4KB后掉电崩溃了，就会导致别的数据还没更新，16KB的Page数据被损坏。InnerDB 使用 DoubleWrite 来处理这个问题。
Mysql 和 PostgreSQL 都是采用此方式

In-Place updates

4,2 基于B+树的 Copy-on-Write updates

定义：数据和索引都存储在文件系统中，通过B+树索引某个元组，采用 Copy on Write 的方式进行 insert/update/delete 等操作。
Copy on Write：更新时，先拷贝一份原数据做更新，然后替换原数据。
MongoDB 采用此方式

Copy-on-Write updates

4,3 LSM的追加与合并

使用RocksDB作为数据库的本地存储。
LSM优点是写入很快，但是存在读放大问题。
TiDB等在使用。

4,4 LSM的KV分离实现

为了进一步减少LSM的写放大，提高系统性能，在写 Log 之后，将指针插入索引，索引里面存元数据的指针。
ByteNDB 中的 TerakKV，ByteNDB for MemDB(Log Is Database)

LSM实现示例

二、数据库索引

1. 索引概述

定义：索引是为了加速对表中数据行的检索而创建的一种存储结构，索引是针对表而建立的，每个索引Entry中都会含有逻辑指针，以便加速检索物理数据
索引的作用：索引就是用来减少IO数量，加速数据的查找。仅仅把表示关系的元组随机存入各级存储是不够的，例如如下的查询：SELECT FROM T WHERE id=1 必须遍历每个存储块才能找到id=1的数据行

2. 索引的划分

2.1 按数据的物理存储划分

聚集索引：索引键的顺序和表记录的物理顺序一致，查询快，一旦具有第一个索引值的纪录被找到，具有连续索引值的记录也一定物理的紧跟其后；更新慢，因为需要维护物理节点的顺序。
非聚集索引：索引键记录的是表中的逻辑顺序，但记录的物理顺序和索引的顺序不一致。更新快，查询慢。

2.2 索引键的覆盖范围

稠密索引：为每个索引键都建立索引项
稀疏索引：只为部分索引键建立索引项，只有聚集索引才能使用稀疏索引（因为需要找到索引后遍历数据块，因此对物理顺序有要求）。

2.3 按索引键的特征划分

主键索引：建立在主键上的索引被称为主键索引，一张数据表只能有一个主键索引，索引列值不允许有空值，通常在创建表时一起创建
唯一索引：建立在UNIQUE字段上的索引被称为唯一索引，一张表可以有多个唯一索引，索引列值允许为空，列值中出现多个空值不会发生重复冲突
普通索引/非唯一索引：建立在普通字段上的索引被称为普通索引

2.4 按索引键的数量划分

单列索引：索引键只包含数据行的一列
多列索引：索引键由数据行的多列组成，比如把数据看成多维的，比如地理位置

3. 常用索引结构

3.1 Hash索引

优点：点查询效率高
缺点：1) 主键被Hash后，物理上是随机分布，不支持范围查询；2) 不支持模糊查询，例如 >，<, LIKE 等（需要索引的全部信息来计算hash）；3) 对于多列索引，不支持部分字段的前缀查询；4) 重复值较多时，性能可能很差；5) 查询层无法利用索引的排序来提升性能。

3.2 B-Tree索引

优点：1) 出度大，且叶子节点不包含表数据，树的高度小，所以单次请求涉及的磁盘IO次数少；2) 任何关键字的查询必须走从根节点到叶子节点，查询路径长度相同，所以查询效率稳定；3) 从符合条件的某个叶子节点开始遍历即可，所以范围查询效率高。
缺点：随着新数据的插入，叶子节点会慢慢分裂，逻辑上连续的叶子节点在物理上往往不连续，甚至分离的很远，所以B-Tree最大的问题就是会产生大量的随机IO，影响性能。

3.3 LSM(Log-Structured Merge Tree)

由于随机读写比顺序读写慢很多，而LSM通过 内存插入 与 磁盘的顺序写 来达到最优的写性能，从而大幅提升写操作，代价是牺牲一定的读性能。随着小树越来越多，读的性能可能会越来越差，一次需要在适当的时候将磁盘中的小树进行Merge，多棵小树变为一棵大树
优点：写性能很好，例如基于LSM树实现的HBase的写性能比MySQL高了一个数量级。
缺点：读性能一般，后台Compaction启动时，可能会影响前台的IO。

3.4 Bitmap位图索引

比如对于查询 Select * From table Where Gender='Male' And Marital='Married'; table 指的是员工信息表。
对于性别列来说，只有两种取值，且各占50%，如果使用B-Tree索引，需要读取到一半的数据，区分度低，因此此时没有必要使用B-Tree索引。

优点：1) 当 Select Count(XXX) 时，可以直接访问索引中的一个位图就快速得出统计数据；2) 当根据键值做 And Or 等查询时，直接用索引的位图进行与或运算，快速得出结果行数据。
缺点：不适用于取值范围很广、或者频繁更新的列。

三、存储与索引的发展趋势

1. 存储发展趋势

1.1 云原生的分布式存储

云原生数据库运行在容器中，具备快速部署、快速扩缩容的能力；计算和存储都需要具备云原生能力。
云原生的核心是通过虚拟化技术带来池化资源，实现弹性、高可用、高效运维。

1.2. 行列混存（HTAP）

HTAP（混合事务 / 分析处理，Hybrid Transactional/Analytical Processing）
物联网、大数据、⻛控等纵多领域有实时更新和查询的需求，HTAP数据库能够在一份数据上同时支撑业务系统运行OLTP和OLAP，避免在传统架构中，在线与离线数据库之间大量的数据交互，是数据库未来重要的发展方向

1.3 基于新硬件的高性能存储

需求：高吞吐、低延时数据库需求迫切，(NVM/RDMA等新硬件设计的数据库)
互联网金融、电商、O2O、零售等行业，核心交易系统对高吞吐、低时延数据库的需求越来越迫切，基于NVM/RDMA等新硬件设计的数据库，已在国内外大厂被广泛研究和应用

1.4. 数据自动分级存储

利用已有的云服务，提高性能，降低成本

2. 索引发展趋势

2.1 无锁高并发

传统B+树难以使用CPU多核能力，高并发的情况下，锁粒度大导致性能无法提升。
B-Tree在数据库领域被广泛地用作索引，传统的B-Tree并发控制算法加锁粒度大，高并发访问下，性能较差，所以业界产生了许多基于B-Tree进行高并发改造的树形索引

2.2 BW-Tree

基于B+-Tree，将 Insert、Split 和 Merge 等操作通过多个原子操作来实现无锁。
每个Page 管理的是 Base Page + Delta Record，来实现多版本。

2.3 Blink-Tree

基于B+-Tree，内部节点增加了一个指向右兄弟的指针。
支持在不持有锁的状态下，从根节点访问到叶子结点，只对需要修改的节点加锁，是自底向上、自左向右的加锁方式。读写冲突的概率小。（对于B+-Tree来说，我们的Update和Sort对于一个叶子节点进行操作即可，节点分裂和合并的操作占比很小）

2.4 ART(自适应前缀树)

采用路径压缩的方式来减少内存的占用。
通过在 Node 上增加 Lock 和 Version，遍历过程中最多同时对两个索引节点进行加锁，加锁的范围小，能够支持高并发。
点查询性能高、范围查询性能低。

2.5 Mass-Tree

从结构上来说，Mass Tree 是由一层或者多层的 B+-Tree 组成的 Trie 树。
通过在 Node 上增加 Lock 和 Version，在 Insert 和 Split 时最多对 Current 和 Parent Node 加锁来支持高并发访问。

2.6 分布式化

计算存储分离，且存储分布式化的趋势下，分布式索引是多写架构的关键技术，且能打破单机在容量和可靠性等方面的限制。这是多写架构的关键技术。

第五部分：【数据库理论基础】数据库事务概述

一、认识事务

1. 为什么需要事务

事务需求举例

2. 什么是数据库事务

定义：数据库管理系统执行过程的一个逻辑单位，由一个有限的数据库操作序列构成
目的：为数据库数据提供一致性能力，这种一致性哪怕是在异常状态下也成立；当多个应用并发访问数据库时，提供一种隔离方法，防止彼此的操作互相干扰；为数据库系统提供了一个从异常恢复到正常状态的方法。

3. 事务的基本特性

ACID：Atomic、Consistency、Isolation、Durability
Atomic：原子性。操作要么都成功，要么都失败
Consistency：一致性。数据库数据从一个状态变化为另一个状态，无论是否异常，数据都保持一致性（比如转账场景，AB两方的账户总额永远是一致的）。
Isolation：隔离性。允许多个并发事务同时对数据库数据进行读写和修改，且互相不影响，看起来像是串行执行一样，并且不会出现数据不一致。
Durability：持久性。数据库数据操纵是持久化操作，只要执行成功，就需要落盘持久化保证。

如何保证ACID

二、并发控制

1. 再谈Isolation

Isolation定义：就是数据库允许多个并发事务同时对数据进行读写和修改的能力，且互相之间不影响，看起来像串行执行一样，并且不会出现由于事务交叉执行而导致的数据不一致。

Isolation举例。左图为问题定义，以及该问题的一致性定义；右图为串行执行的示例

并行执行示例一-正确的事务调度

并行执行示例二-错误的事务调度

如何判断一个事务调度是正确的？：如果一个并发事务的调度执行结果能和多种串行执行的其中一个结果相等，我们认为这是一个正确的调度，称之为 serializable schedule。

2. 并发问题与隔离级别

2.1 并发异象

并发导致的并发异象：脏读(Dirty Read, Read Uncommitted data)，脏写(Dirty Write, Overwrite Uncommitted data)，不可重复读(Unrepeatable Read)，幻读(Phantom Read)

• 脏读：前一个事务执行，修改了数据A，未Commit情况下另一个事务读取到了修改后的A数据，结果前一个事务执行了回滚，导致第二个事务出现并发异象。
• 脏写：前一个事务执行，修改了数据A，未Commit情况下另一个事务执行写操作，修改了A和B然后Commit，执行完成后，前一个事务继续修改B，导致A和B结果异常。
• 不可重复读：前一个事务执行，读取数据A，接着另一个事务修改了A数据并Commit，前一个事务后续继续读取A数据，导致前一个事务对于A数据的两次读取结果不同，导致并发异象。
• 幻读：第一个事务先筛选读取了一些数据，操作过程中，第二个事务新插入一行数据并Commit，在第一个事务中以相同的筛选条件读取到的数据个数与第一次读取不同，导致并发异象。

2.2 四大隔离级别

如果能避免所有的并发时产⽣的异象，则可以得到serializable schedule。在真实场景中，有时候并不需要如此高的一致性，因此根据场景可以牺牲一些一致性来提高整体的性能，根据并发异象，定义出4大隔离级别。

4大隔离级别。第四行最后一列应该是 Not Possible（图片写错了）

2.3 并发冲突

并发产生的异象，本质上是出现了冲突：
W-W冲突：两个事务先后修改了同一个数据库的相同 object。
W-R冲突：事务T1修改某个 object 之后（未提交），事务T2对修改的 object 进行了读操作。
R-W冲突：事务T1读取了某个 object 或者某个 range 之后，事务T2对所读取的 object 或者 range 进行了修改。

2.4 序列化图

序列化图的定义：
序列化图是用有向图的方式表示事务相互之间的冲突依赖关系，图中每个节点表示一个事务，有向边表示存在一种依赖关系。

基于序列化图的并发异象定义：
我们将事务对不同object的依赖关系表示到同一张序列化图中，所谓异象就是找不到正确的序列化顺序，即存在某种环。

2.5 MVCC，引出SI隔离级别（Snapshot Isolation）

为了提高数据库的并发性能，提出了MVCC（Multi-Version Concurrency Control）来实现读写互不阻塞，从而提高数据库的并发性能。
在MVCC下，定义出一种新的隔离级别——SI（Snapshot Isolation）：用 ts 表示事务的执行顺序（对事务进行排序）；事务的读从已经committed的快照中读取数据；SI允许事务使用很旧的ts执行，从而不被任何写操作阻塞，可以读一个历史数据。
SI的并发异象——Write Skew

3. 并发控制的概念

为了解决上述并发异象，引出并发控制。
定义：所谓的并发控制，就是一种保证并发执行的事务在某一种隔离级别上能够正确执行。达到要求的数据一致性目的的事务调度机制。

4. 并发控制的分类

按照乐观程度划分：从悲观到乐观，分别有基于Lock，基于TS，基于验证的并发控制协议。
单版本VS多版本：从悲观到乐观，多版本下分别有MV2PL，MVTO，MVOCC几种并发控制协议实现。

5. 常见的并发控制协议

5.1 2PL

锁的分类：S-Lock（共享锁，读锁）；X-Lock（互斥锁，写锁）
锁的兼容性：只有S-Lock和S-Lock互相兼容，其余情况均不兼容。
两阶段：Growing Phase（事务申请所需要的所有锁，加锁失败则等待）和 Shrinking Phase（释放Growing阶段获取的锁，不允许再请求新锁）

2PL占用锁的趋势。第一阶段只能获取锁，不能释放锁，第二阶段必须释放锁，不能获取锁，否则会出现并发异象

死锁处理之死锁检测（Deadlock Detection）

wait-for 图示例

根据wait-for图就事务等待关系。当出现环时表示出现了死锁。系统后台定时监测 wait-for 图，如果发现环则选择合适的事务 abort。

死锁处理之死锁预防（Deadlock Prevention）
当事务去请求一个已经被持有的锁时，数据库系统为了防止死锁，杀死一个事务，这种防患于未然的方式不需要 wait-for 图，但是提高了被杀死的比率。

• Wound-Wait模式：抢占式，杀死比自己新的事务，否则等待。
• Wait-Die模式：非抢占式，如果自己比别的事务新，则自杀，否则等待。

5.2 T/O

T/O 的核心思想就是利用时间戳来决定事务之间的等价执行顺序：如果TS(Ti)<TS(Tj)，那么数据库必须保证实际的schedule先执行Ti，后执行Tj的结果等价。
(1) 数据元数据：
W-TS(X)：最后一次写X发生的时间戳；
R-TS(X)：最后一次读X发生的时间戳。
(2) 读：
TTS<W-TS(X)：该对象对该事务不可见，abort事务，取一个新的时间戳重新开始（不能读到未来值）
TTS>W-TS(X)：该对象对该事务可见，更新R-TS(X)=max(TTS,R-TS(X))，为了满足 repeatable read，可以保留一份X的值。
(3) 写：
TTS<W-TS(X) || TTS<R-TS(X)：abort 事务，重新开始（意味着写过时）
TTS>W-TS(X) && TTS>R-TS(X)：更新事务X，W-TS(X)=TTS，如果有必要，可以保留X的副本，保证Ti结束前能够读到相同的X。

Basic T/O优点：不会造成死锁，无事务需要等待；如果单个事务设计数据不多，不同事务之间冲突较小的OLTP，可以节省2PL控制锁的额外成本，提高并发。
Basic T/O缺点：长事务容易与短事务冲突而饿死；复制数据、维护、更新时间戳存在额外的成本；可能产生不可恢复的schedule。

T/O 不可恢复 schedule 举例：T2读取A操作B并完成提交，由于T1 abort 导致 T2 执行结果是错误的，但是没有副本可供恢复

5.3 OCC

OCC 是比T/O更为乐观的并发控制协议，默认各个事务之间不会冲突，因此直接为每个事务复制一个私有空间来并发执行读写操作，在最终commit时，才进行冲突判定。
Optimistic Consurrency Control（OCC）：同样是基于时间戳对事务进行排序；所有读取的数据都复制到私有空间中，所有的修改都在私有空间中进行；分为 Read Phase，Validate Phase 和 Write Phase 三个阶段。
Validate Phase：进行验证的阶段，负责判定该事务是否与其他并发事务存在冲突。向前验证（验证该事务开始到提交之间已经提交的事务）和向后验证（验证该事务开始到提交之间还未提交的事务）。

NDB体系下的内存数据库使用的就是MVOCC的版本控制协议

三、日志及恢复

1. 数据库恢复

定义：就是在数据库出现故障后，对数据库的数据进⾏恢复，并可以满⾜⼀致性要求：

• Durability Of Update：已经commit事务的修改，故障恢复后仍然存在
• Failure Atomic：失败事务的所有修改都不可⻅（主要指事务commit时，commit半途掉电或者失败导致需要回滚所有之前的落盘操作）

2. Buffer Pool 机制

定义：修改数据库数据时，是对缓存的修改，最后再将修改后的数据写回到持久化存储，这个过程称为 buffer pool 管理机制。

• 告知用户事务已经提交成功前，相应的数据必须已经持久化——Durability Of Update
• 如果事务终止，任何数据修改都不应该持久化——Failure Atomic（主要指事务commit时，commit半途掉电或者失败导致需要回滚所有之前的落盘操作）

Buffer Pool 机制举例（No Force: redo 日志，Steal: undo 日志）

在 Durability Of Update 要求下，如果事务提交成功，则必须完成数据持久化，如果告知用户前不必须完成持久化数据，则需要引入 redo 日志记录操作，用于异常情况下的操作回放保证数据持久化的一致性；
在 Failure Atomic 要求下，数据必须一致性下盘(即No-Steal机制)，但是如果某个事务的数据过多，下盘无法保证一致性，则为Steal机制，需要引入 Undo 日志，在异常恢复后通过 undo log 恢复失败的事务，保证事务回滚一致性。

基于redo log 和 undo log 的其他组合机制

最常用的Buffer Pool 机制是WAL机制

3. WAL 机制

3.1 WAL

定义：Write-Ahead Log 指的是 DBMS 出了维护正常的数据文件外，还额外维护一个日志文件，记录做所有事务对DBMS数据的完整修改记录，这些记录能够帮助数据库在恢复数据时执行 undo/redo。
目的：因为传统磁盘的顺序访问性能远远好于随机访问，WAL机制意图利用顺序写Log来记录对数据库的操作，每次修改数据内容前，先顺序写Log来提高性能。

3.2 WAL Protocol——Steal + No-Force 机制

1. DBMS先将事务的操作记录放在内存中
2. 在数据落盘前，所有⽇志必须先落盘(redo日志)
3. 在操作⽇志落盘后，事务被认为已经提交成功(此时redo已落盘, 就可以返回给用户. 但数据还未落盘)
4. 数据库数据异步落盘(redo日志提前落盘, 数据异步落盘)

3.3 日志内容

• 事务开始需要写 BEGIN 日志，事务结束需要写 COMMIT 日志
• Transaction ID（事务ID）
• Object ID（数据记录ID）
• Before Value（修改前的值，用于 Undo 操作）
• After Value（修改后的值，用于 Redo 操作）

3.4 问题及解决

问题：WAL机制下，随着操作无限增长，在故障恢复时则需要读取更多的日志，执行更多的恢复和回滚操作。
目的：避免日志无限增长，恢复时读取所有的日志，加速恢复。
手段：checkpoint

4. checkpoint

周期性地将所有的数据也持久化到存储设备中，然后在日志中写入一条 CHECKPOINT。恢复时只关注最后一条 CHECKPOINT 之后的日志数据进行 undo 和 redo。

checkpoint 前的 redo 日志, 其数据已落盘, redo 日志就无需再保存, 节省了磁盘空间.

mysql的三种日志: redo log, undo log, binlog

四、分布式事务

1. 数据库架构发展

数据库架构发展

单机 -(读扩展)-> 读写分离 -(写扩展)-> 多写分布式数据库

2. XA分布式数据库原理

定义：XA规范是由 X/Open 组织提出的分布式事务处理规范，主要定义了事务管理器 TM 和局部资源管理器 RM 之间的接口。

XA分布式规范

3. 分布式事务提交协议—2PC

2PC示例

2PC分布式协议的一些问题点如下，此处不详细讲述
同步阻塞：本地事务在 prepare 阶段锁定资源，如果有其他的事务也要修改账户信息，必须等待前面的事务完成，导致系统性能下降。
协调节点故障：如果第一个阶段 prepare 成功了，但是第二个阶段协调节点发出 commit 指令之前宕机了，所有服务的数据均处于锁定状态，事务将无限期地等待。
数据不一致：如果第一阶段 prepare 成功了，但是第二阶段协调节点向某个结点发送 commit 命令时失败，就会导致数据不一致。

我的另一个针对分布式事务的笔记

第六部分：【MySQL 数据库运维】一条 SQL 的生命历程

一、整体执行过程

SQL 整体执行过程

连接器 -> 查询缓存 -> 分析器 -> 优化器 -> 执行器 -> 修改前记录写入undo log -> 写入redo log(prepare状态) -> 写入binlog -> 写入redo log(commit 状态)

二、组件介绍

1 连接器

连接器负责连接和管理连接。

• 长连接: 连接成功后, 每次执行都用同一个连接
• 短连接: 每次执行完都断开连接, 下次执行新建一个连接
• 空闲连接会进入sleep状态，live timeout 默认为 8小时，没有操作则断连。

2 缓存器

判断SQL是否在缓存中，如果存在则直接返回。
缓存失效场景：1) SQL不一致；2) 存在不确定的函数调用(now()等)；3) 不使用任何表查询(没有from)；4) 查询 mysql\information_schema\performance_schema 等表不走缓存；5) 在存储的函数、触发器或事件的主体内执行的查询；6) 表发生更改则该表全部缓存失效(insert update delete truncate alter drop等)；

3 分析器

词法分析：判定词法，根据关键字进行拆分
语法分析：判定语法，是否符合mysql的语法规范

4 优化器

使用统计信息来估算最佳的索引，根据执行计划选择最优的选择，匹配合适的方案，匹配最优的索引。
未使用最优索引的优化方法：可以通过 analyze table 重新计算表的统计信息；可以 force index 来强制选取索引；可以删除不好的索引或者新建一个更优的索引；调整sql来让优化器能够选取最优索引。

5 执行器

执行器调用对应的存储引擎执行sql。表的查询权限检查是在此阶段进行的。

6 存储引擎层

6.1 redolog

redo log 是 InnoDB 引擎特有的
redo log 是物理日志，记录“某个数据页上面做了什么修改”
redo log 是循环写的，空间固定，会用完，用完则复用原来的内存空间

6.2 binlog

bin log 是 MySQL 的 server 所实现的，所有的引擎均可使用
bin log 是逻辑 日志，记录语句的原始逻辑，比如 “给 ID=2 这一行的 c 字段加 1”
bin log 是可以追加写入的。单个文件到达一定的大小会切换下一个文件进行写入，不会覆盖之前的日志

6.3 InnoDB 内部执行流程

InnoDB 内部执行流程

三、SQL 执行举例

排序使用 sort buffer，如果内存空间足够，则 1 次回表；如果内存不足，则先回表读取排序字段排序，之后返回数据时进行第 2 次回表。

四、Q&A

1. Undo log 存储在哪里？需不需要落盘？需要的话啥时候落盘？所有表的undo log都是集中存放，还是以表为维度划分文件？

在InnoDB的实现里面，Undo log本质上不是Log，而是隶属于Undo Tablespace的页面，Undo Tablespace和正常表空间一样，修改都通过redo log记录，所以从落盘的角度，和正常表页面是一样的，都是背景线程定期从缓冲区里面将脏页刷盘。
Undo log落盘时机不重要，因为它用redo管理；undo log是集中存放的

2. MySQL查询优化器是如何估算代价的，会考虑哪些因素？这个分析过程自身的代价又是怎么去平衡的？

考虑的因素主要是cpu计算开销和IO开销，IO分随机IO和顺序IO，是一个很复杂的计算量化标准，具体可以看下李海翔的《数据库查询优化器的艺术:原理解析与SQL性能优化》，后续我们课程也会涉及

3. 如何判断一个事务真正的执行成功了，通过生成relog还是binlog？

事务提交成功最简单的标志就是commit命令执行成功，但commit命令会触发redo log 进入prepare->写binlog -〉redo log进入commit状态，binlog是server层的东西，作为两阶段事物提交的是协调者，如果redo处于prepare状态无binlog，则回滚；如果处于prepare状态，有binlog则commit

4. 一个事务里的多条 SQL 是如何同步给从库的？为什么优先用 row 格式的 binlog？如果一下子改很多行，会不会瞬间存储压力比较大？

binlog 有几种模式：statement(记录一条条的sql语句，从库进行操作重放)、row(记录一行行数据变更的event，打包event给从库进行数据修改，要么成功要么失败)、Mixed（自动模式）
目前我们线上使用的都是row模式，一致性更好，dbus等依赖

5. 如果MySQL在一个事务中crash，InnoDB是如何保证redo log和binlog的一致性的？

简单来讲，binlog和redo log的一致性保证靠的是一个内部的二阶段提交协议：

• 写入redo log，处于prepare状态
• 写binlog
• 修改redo log状态为commit
  非常详细的流程可以参考 这里。

6. 如果线上MySQL不小心执行了一条“邪恶”的SQL，造成必须停服恢复数据，如何保证停服时间最短？

这种情况应该是说恶意用户准备”删库跑路“，如果不小心碰到了这种情况，需要从备份数据里面恢复（PITR可以到秒级），恢复时间长短和数据量相关。

7. 如果MySQL一个事务在prepare成功后crash，怎么恢复数据？

在prepare阶段crash后，事务会回滚，此时还没生成 binlog。

8. MySQL 的 Planner/Optimizer 会倾向于选择稳定的代价（比如对一些查询，固定访问某个索引）还是一定选择 cost 上更优的代价？这个过程是否需要 DBA 介入？

MySQL的Optimizer是基于cost的选择方式，过程不需要人为干预，他会根据索引和表的统计信息计算cost，选择最优索引。可以通过explain format = json .... 查看具体细节。
如果有两个索引存在重复索引的情况，同样的语句在两个索引之间来回切换导致业务不可控，此时要么优化索引，要么手动使用Hint（也要注意，索引的变更，也要记得更新下带hint的查询，否则可能会导致SQL报错）

9. MySQL 的 secondary index 需不需要维护多版本？怎么样才能保证让他访问到正确版本的数据？

没有多版本，锁和多版本主要是基于主键实现的

10. 同一条sql查询语句在主库和从库执行的时候可能走不同索引吗？

可能的，走什么索引是优化器根据统计信息做的决策，同个SQL在同个实例多次执行都可能走不一样的索引

11. 事务回滚，写 undo log，修改了数据页的内容，这个时候会写redo log吗？

是的，undo也是数据页，内存中也在innodb_buffer_pool中管理，所以他的变更，也被视为一种page的变更记录redo，所以如果事务回滚，那么redo相当于会写两遍

12. 用唯一索引和用主键更新某一条记录会有性能区别吗？

理论上来说有区别，主键直接定位记录，唯一索引先定位主键再定位记录，实际情况下差别很小

13. 编程语言的 mysql-driver 客户端和 MySQL Server 之间交互传输的请求和结果使用的是什么格式的？文本还是二进制？会使用压缩算法吗？

mysql有自己的二进制协议，见 https://dev.mysql.com/doc/internals/en/client-server-protocol.html

14. 怎么理解物理日志和逻辑日志？

物理日志是物理存储的更改日志，也就是page，逻辑日志是数据的逻辑更改的日志，逻辑日志记录某行记录逻辑结构从什么改成什么，物理日志是磁盘上从什么样改成了什么样

15. 写入redo log，undo log、bin log、B+树的顺序是什么呢？redo log和undo log分别会在什么时候发挥作用呢？redo log和bin log可以合并吗？

redo log的目的是为了保证数据库写入数据的持久性，undo log是为了用来做事务的回滚操作，保证事务的原子性。同时可以用来构建数据修改之前的版本，支持多版本读。
binlog是MySQL server层的日志，redo log是MySQL innodb层的日志，不可以合并

16. RDS的proxy层做了什么？在整个执行流程中哪个环节？

SQL转发/限流/流量转发/相关监控等，driver之后数据库之前
client->driver->dbproxy-DB实例

17. Mysql MVCC怎么解决 write skew、lost update？

write skew、lost update：指的是两个事务在并发写操作上发生的异常，均读到旧数据并更新为新数据，导致其中一个更新被覆盖。
select for update方式

18. 删除（delete）数据的时候，有无索引有区别吗？

有区别，没有索引的删除就会扫描全表。删除数据最好几十条、几百条的删除。一次性删除上万条数据会导致主从延迟较大。

19. 存在 binlog 写成功，事务回滚的情况吗？

没有

20. 数据删除后，会不会造成磁盘碎片，mysql会在什么时机做数据合并压缩吗？

会造成磁盘碎片，mysql不会合并压缩，但是会合并数据页，并留有空白数据页，后续会恢复使用。

第七部分：【MySQL 数据库运维】MySQL 生态系统构建介绍

第八部分：【MySQL 数据库运维】MySQL Online DDL 详解

第九部分：【MySQL 数据库运维】MySQL 高可用架构设计与实现

第十部分：【MySQL 数据库运维】MySQL 复制的前世今生

第十一部分：【MySQL 数据库运维】MySQL 的锁与最佳实践

第十二部分：【MySQL 数据库内核深度解析】MySQL 8.0 执行器深度解析

第十三部分：【MySQL 数据库内核深度解析】MySQL Binlog 格式及机制深度解析

第十四部分：【MySQL 数据库内核深度解析】InnoDB B+ Tree 管理机制深度解析

第十五部分：【MySQL 数据库内核深度解析】InnoDB REDO 日志机制深度解析

第十六部分：【MySQL 数据库内核深度解析】InnoDB 事务与隔离级别深度解析

第十七部分：【MySQL 数据库内核深度解析】MySQL 8.0 Undo Log 机制深入解析

第十八部分：【MySQL 数据库内核深度解析】InnoDB 存储物理格式深度解析