梳理数据库原理，编写笔记。

数据库原理笔记

0 链接

主要学习CYC2018的笔记：

数据库系统原理

博客码农阿宇的文章，以实例深入分析了MySQL的InnoDB的封锁原理，重点分析了可重复读隔离级别能否防幻读（我觉得update的时候为了避免丢失修改，要拿最新的快照，因此就引入了新插入的数据，然后再去读的化，就造成了幻影读）：

事务隔离级别中的可重复读能防幻读吗?

掘金上的一文对MVCC的ReadView机制有比较细致的介绍，有助于理解：

面试官：谈谈你对Mysql的MVCC的理解?

关于设计范式的知乎讨论：

如何理解关系型数据库的常见设计范式？

1 事务（Transaction）

1.1 概念

数据库事务（简称：事务）是数据库管理系统执行过程中的一个逻辑单位，由一个有限的数据库操作序列构成。

基本地，事务的执行要么全部执行成功，要么全部都没执行（如果执行了一半，就回滚撤销回全部都没执行的状态）。

比如说，转账支付事务：

1. 从张三的账户扣除100元；
2. 对李四的账户增加100元。

这两个操作，要么都执行成功，即转账成功；要么都没执行，即转账失败。如果执行了一半出错了，那必须回滚，要不然帐就对不上了。

具体地，事务需要满足ACID四大性质：

1.2 ACID

原子性（Atomicity）：事务作为一个整体被执行，包含在其中的对数据库的操作要么全部被执行，要么都不执行。

• 如上所述的例子，转账事务要么执行到位，要么就别执行，不可分割出来只完成一部分。

一致性（Consistency）：事务应确保数据库的状态从一个一致状态转变为另一个一致状态。一致状态的含义是数据库中的数据应满足完整性约束。

• 数据库修改前后的状态都应该是满足约束条件的，比如说：张三转账给李四，两人合起来的总金额应该是不变的，不能凭空多出钱，或者消失钱。

隔离性（Isolation）：多个事务并发执行时，一个事务的执行不应影响其他事务的执行。

• 张三给李四转账100元，王五也给李四转账200元，李四账上本来有300元。两个转账事务同时执行，都需要先读取李四的账户余额，然后加上转入金额算出新余额，最后把新余额写入数据库。如果没有满足隔离性，就会出现：两个并发事务都先“同时”读取李四的账户，发现余额是300元，于是“同时”计算转入金额后的新余额，分别在读到的余额上加了100元和200元，新余额结果为：400元和500元，最后“同时”写入数据库，实际最终写入的可能是400元也可能是500元。实际上应该是300+100+200=600元才对！
• 并发事务的“同时”实际上有细粒度的先后顺序。

持久性（Durability）：已被提交的事务对数据库的修改应该永久保存在数据库中。

• 转账的记录得保留存档，有据可查，不能数据库断电、重启了就没账目了。

1.3 ACID与正确性

实际上，ACID四个特性不是平级的并列关系，而是：

• 数据库执行结果的正确性，需要依靠：一致性（Consistency）；
  • 一致性依靠：
    • 原子性（Atomicity）；
    • 隔离性（Isolation）；
• 数据库系统崩溃后依然正确，需要依靠：持久性（Durability）

正如上述的例子，数据库需要把转账事务作为整体执行（原子性），而且事务之间不能互相产生干扰（隔离性），这样转账的结果才是正确的。

转账的结果需要记录下来，要不然数据库系统突然断电、出了故障，这笔转账就消失了。

2 并发一致性问题

并发一致性问题是并发环境 + 事务隔离性（Isolation）缺失的情况下会出现的问题。

具体地，是”一写三读“问题——一个写问题，三个读问题：

2.1 丢失修改

同记录，两个写。

并发事务T1、T2“同时”修改记录A，都“同时”读取了旧数据，将其修改为新数据，结果是后写入的覆盖掉了先写入的数据。先写入的修改内容就丢失了。

正确的情况是：一个事务完成修改后，另一个事务在此基础之上再进行修改，即，对相同记录的两个写事务需要相互隔离。

2.2 读脏数据

同记录，一读一写。

并发事务T1、T2，其中，T1修改记录A，T2需要读取记录A。结果并发执行的时候，T1刚修改A为一个结果，还有后续工作未完成。如果在尚未完成T1事务的情况下，T2去读了A，此时，如果T1事务后续操作执行出错，数据库系统就会回滚了T1事务。这样一来，T2读取的只是T1执行过程中的临时修改的数据，并不是结果数据。

正确的情况是：T1要么在T2事务完成前读取正确的老数据，要么在T2事务完成后读取正确的新数据，即，对相同记录的一读一写的两个事务需要相互隔离。

2.3 不可重复读

同记录，一读一写。

并发事务T1、T2，其中，T1修改记录A，T2反复读取记录A。结果并发执行的时候，T2先读取了记录A的旧数据，随后T1修改了记录A，此后T2读取到了记录A的新数据。T2发现，在同一个事务的执行过程中，读取到的记录A前后矛盾不一致。

正确的情况是：除非业务逻辑可接受这种情况，否则应该是正在被读取的记录不可以被修改，即，对相同记录的一读一写的两个事务需要相互隔离。

2.4 幻影读

同范围，一读一写。

与不可重复读类似，但不可重复读是因为读取了被修改的特定数据字段，而幻影读是因为统计的范围内有数据被修改。

并发事务T1、T2，其中，T1修改表A，T2反复统计表A。结果并发执行的时候，T2先统计了表A的数据（比如计数），随后T1修改了表A（比如说插入一行新数据），此后T2再统计表A的数据。T2发现，在同一个事务的执行过程中，对表A的数据的统计结果前后矛盾不一致，

正确的情况是：除非业务逻辑可接受这种情况，否则应该是正在被读取的表（范围）不可以被修改，即，对相同范围的一读一写的两个事务需要相互隔离。

3 封锁

要想实现并发一致性，就需要在并发环境下保证事务的隔离性。

解决方法就是封锁（Lock）。

3.1 封锁粒度

MySQL有行级锁和表级锁。

细粒度锁：

• 优：系统并发度高（因为只锁定有关的数据，锁定的数据少，发生争用的概率越低，系统并发程度就越高）；
• 缺：封锁开销大（相较于对整个表上一个锁，细粒度锁需要对涉及到的记录都上锁，锁的数量更多，上锁、释放锁、检查锁的开销也就成倍增多）。

粗粒度锁：

• 优：封锁开销小；
• 缺：系统并发度低。

3.2 封锁类型

3.2.1 读写锁

• 互斥锁（Exclusive），简写为 X 锁，又称写锁。
• 共享锁（Shared），简写为 S 锁，又称读锁。

读写锁兼容关系：

	X	S
X	No	No
S	No	Yes

• X锁排斥任何其他锁，S锁兼容S锁。

3.2.2 意图锁

意向锁有助于多粒度封锁。

对表A上X锁，不仅需要检查表级锁兼容情况，还需要检查表内每行有没有锁，代价很大。如果能够在表级记录下表内有没有锁，就很方便。

意图锁夹在读写锁的上级，设置细粒度读写锁时，要先设置粗粒度意向锁：

• 先获得表的IS锁，才能进一步设置行的S锁；
• 先获得表的IX锁，才能进一步设置行的X锁。

这样锁表的时候，看看表上的意向锁情况，就知道表内有没有行锁了。

意向锁与读写锁的兼容关系：

	X	IX	S	IS
X	No	No	No	No
IX	No	Yes	No	Yes
S	No	No	Yes	Yes
IS	No	Yes	Yes	Yes

• IS-IS, IS-IX, IX-IX都是兼容的，表级意向不需要互斥，要看具体的行有没有互斥（可能虽然是对同一个表的意向，但表内的读写的具体行是不相同的，没有产生互斥）；

3.3 封锁协议

3.3.1 一级封锁协议

协议内容：

• 写前加X锁，事务提交后释放；

存在问题：

• 读脏数据：读不需要上锁，因此可能读到写事务提交前的修改数据。

• 不可重复读：读不需要上锁，因此可能读到修改前、修改后的数据。

3.3.2 二级封锁协议

协议内容：

• 写前加X锁，事务提交后释放；
• 读前加S锁，读后立即释放；

存在问题：

• 读脏数据：已解决。

• 不可重复读：读后立即释放锁，因此可能读到修改前、修改后的数据（读-修改-读）。

3.3.3 三级封锁协议

协议内容：

• 写前加X锁，事务提交后释放；
• 读前加S锁，事务提交后释放；

存在问题：

• 读脏数据：已解决。

• 不可重复读：已解决。

3.3.4 两段锁协议

2PL(Two Phase Locking)。

事务分两个阶段进行加锁和解锁：

• 加锁阶段：从开始，到事务执行结束（commit或rollback），只加锁；
• 解锁阶段：事务执行结束后，只解锁。

两端所协议 ==> 可串行化调度。（反之则不一定成立）

可串行化调度表示事务并发执行的结果和串行执行的结果一样，意味着不会出现并发一致性问题。

MySQL 的 InnoDB 存储引擎采用两段锁协议，会根据隔离级别在需要的时候自动加锁，并且所有的锁都是在同一时刻被释放，这被称为隐式锁定。

4 隔离级别

4.1 四级别

未提交读（Read Uncommitted）：能读到未提交的修改。

提交读（Read Committed）：只能读到已提交的修改。

可重复读（Repeatable Read）：同一事务中多次读的结果一致。

可串行化（Serializable）：并发执行与串行调度结果一致，无并发一致性问题。

4.2 隔离级别与并发一致性问题

	脏读	不可重复读	幻影读
未提交读	有	有	有
提交读	无	有	有
可重复读	无	无	有
可串行化	无	无	无

• 可重复读隔离级别仍然有幻影读问题是因为，一般认为可重复读是对读的行上了锁，使之无法被修改，解决了可重复读问题，但无法阻止插入新的行，所以仍然有幻影读问题。

5 多版本并发控制（MVCC）

多版本并发控制（Multi-Version Concurrency Control, MVCC）是 MySQL 的 InnoDB 存储引擎实现隔离级别的一种具体方式，用于实现提交读和可重复读这两种隔离级别。而未提交读隔离级别总是读取最新的数据行，要求很低，无需使用 MVCC。可串行化隔离级别需要对所有读取的行都加锁，单纯使用 MVCC 无法实现。

5.1 基本思想

悲观锁：害怕被错误修改，老老实实上锁。但封锁的代价很高，大多数情况下是多数读、少数写，能不用锁就争取不用锁。

那怎么才能避免用锁呢？

乐观锁：MVCC类似CopyOnWrite的思想，使用了“版本”（Version）的概念：

• 读的时候就直接读现有版本；
• 写（Insert, Delete, Update，即增删改）的时候，把现有的数据行复制一份快照作为新版本，写事务对新版本快照进行修改，提交的时候把旧版本更新为新版本（新快照）。

5.2 实现

5.2.1 版本号

• SYS_ID：系统版本号，是一个递增的数字，每开始一个新的事务，系统版本号就会自动递增。
• TRX_ID ：事务版本号，事务开始时的系统版本号。

5.2.2 撤销日志（Undo log）

MVCC 的多版本指的是多个版本的快照，快照存储在 Undo 日志中，该日志通过回滚指针 ROLL_PTR 把一个数据行的所有快照连接起来。

对MySQL的插入和更新操作，会形成撤销日志：

INSERT INTO t(id, x) VALUES(1, "a");
UPDATE t SET x="b" WHERE id=1;
UPDATE t SET x="c" WHERE id=1;

因为没有以START TRANSACTION开头，MySQL根据AutoCommit机制，将每一句SQL作为一个事务来执行，形成的撤销日志形如：

version	id	x	TRX_ID	ROLL_PTR	DEL	备注
3	1	'c'	3	version 2	0	Record：目前的最新版本（即所有语句执行完成后的状态）
2	1	'b'	2	version 1	0	Undo Update：第3行执行前的版本（即第2次Update之前的状态）
1	1	'a'	1	version 0	0	Undo Update：第2行执行前的版本（即第1次Update之前的状态）
0	1					Undo Insert：第1行执行前的版本（即Insert之前的状态）

• 增删改：INSERT、UPDATE、DELETE操作会创建新日志，并记录事务版本号TRX_ID；
• 删除操作形成的新状态不易表示，因此用DEL字段来标记Delete操作；

5.2.3 ReadView

MVCC维护了一个ReadView结构，以列表的形式列举当前未提交的事务TRX_IDs={TRX_ID_1, TRX_ID_2, ...}，并且记录该列表的最小值TRX_ID_MIN和最大值TRX_ID_MAX。

事务执行读取操作前，会获取系统的TRX_ID_MIN和TRX_ID_MAX：

• 提交读级别，事务获取每次进行读取操作时，都会读取系统最新的TRX_ID_MIN和TRX_ID_MAX；

• 可重复读级别，事务开始时获取系统最新的TRX_ID_MIN和TRX_ID_MAX，此后不再更新。

在Select读取时，需要检验该数据行快照的TRX_ID与TRX_ID_MIN和TRX_ID_MAX的关系，判断是否可以读出来：

• 若TRX_ID < TRX_ID_MIN，则说明当前未提交的事务没有对该数据行创建新的版本快照，意味着对该数据行进行修改操作（或可重复读隔离），也就是说这个数据行可以正常读取使用。
• 若TRX_ID > TRX_ID_MAX，则说明该数据行在本事务启动后被修改过，因此不可使用。（我认为这种情况只会出现在可重复读，因为这等隔离级别的自事务启动时读取TRX_ID_MAX后就不再更新，有可能系统执行了其他事务，TRX_ID超过了其启动时读取的TRX_ID_MAX。为了满足可重复读，显然不应该读取该新版本数据行。）
• 若TRX_ID_MIN <= TRX_ID <= TRX_ID_MAX，则说明可能有未提交的事务对该数据行创建了新的版本快照，意味着可能对该数据行进行了修改操作（或可重复读隔离），那这就要根据事务的隔离级别来判断能不能读了：
  • 若提交读级别，则事务只肯读已提交的版本快照，那就要看这个版本有没有被提交。具体地，看这个TRX_ID在不在未提交事务列表TRX_IDs里：
    • 如果在，那么说明该数据行版本快照还未被提交，不可以读取使用；
    • 如果不在，那么说明该数据行版本快照已经被提交了，可以读取使用。（TRX_ID在这个范围中，不代表一定是未提交地，也有可能是已经其前后的事务还未提交，但该事务执行的比较快，已经提交了。因此，要根据未提交事务列表TRX_IDs来确认TRX_ID事务到底有没有提交。）
  • 若可重复读级别，则都不可读。因为此范围内的事务可能陆陆续续会提交，如果同意读取此范围内事务的已提交结果，前一次读到的结果完全有可能因为陆续提交的事务而被修改掉。

如果当前数据行版本快照不能读，就沿着Undo log的回滚指针ROLL_PTR再找更早的一个快照，再继续判断。

5.2.4 快照读与当前读

快照读

查操作（select）时快照中的数据，不需要加锁。

也可以手动对SELECT查询加S或X锁：

SELECT * FROM table WHERE ? lock in share mode;
SELECT * FROM table WHERE ? for update;

当前读

增删改操作（insert, delete, update）需要读取最新数据以便进行修改（否则就会出现丢失修改的并发一致性问题），因此需要加锁占有最新数据。

6 Next-Key Locks

MVCC可以解决通过读取指定的快照版本，可以解决不可重复读问题，但无法控制范围的变化，例如：insert, delete操作。MySQL的InnoDB存储引擎引入Next-Key Locks，与MVCC结合使用，在可重复读的隔离级别下，可以解决幻影读问题。

核心思想就是锁区间、锁范围。

6.1 Record Locks

锁单个记录。

锁定一个记录上的索引，而不是记录本身。

如果表没有设置索引，InnoDB 会自动在主键上创建隐藏的聚簇索引，因此 Record Locks 依然可以使用。

6.2 Gap Locks

锁开区间。

锁定索引之间的间隙，但是不包含索引本身。例如当一个事务执行以下语句，其它事务就不能在 t.c 中插入 15。

SELECT c FROM t WHERE c BETWEEN 10 and 20 FOR UPDATE;

6.3 Next-Key Locks

它是 Record Locks 和 Gap Locks 的结合，不仅锁定一个记录上的索引，也锁定索引之间的间隙。它锁定一个前开后闭区间，例如一个索引包含以下值：10, 11, 13, and 20，那么就需要锁定以下区间：

(-∞, 10]
(10, 11]
(11, 13]
(13, 20]
(20, +∞)

7 关系数据库设计理论

7.1 函数依赖

对于属性（表列）集合\(A = {A_1, A_2, ... A_n}\)。

函数依赖：\(A \to B\)，A函数决定B，B函数依赖A；

若如果能找到真子集\(A' \subsetneq A\)，且\(A' \to B\)，则\(A \to B\)是部分函数依赖，而\(A' \to B\)是完全函数依赖。

传递函数依赖：\(A \to B\)，\(B \to C\)，则\(A \to C\)是传递函数依赖。

键码：能够函数决定其他所有属性的最小属性集，称为键码。

比如说：学号\(No\)、姓名\(Name\)、班级\(Class\)；

\(\{No, Name\} \to \{Class\}\)是部分函数依赖，因为存在\(\{No\} \to \{Class\}\)这样的完全函数依赖。学号\(\{No\}\)因为能够完全决定剩下的所有属性，所以它就是键码。

7.2 异常

典型异常：

• 冗余数据：如果学生选课表里有姓名，那么学生选多门课，就会把相同的姓名重复存储很多遍。
• 修改异常：如果学生表里有姓名，学生选课表里也有姓名，那么改了学生表的姓名，学生选课表的姓名不会跟着改变，而会相互不一致。
• 删除异常：如果说我把学生信息和学生选课表混在一起存为一个学生信息与选课表，那么，如果把学生的选课都删掉，这个学生的信息也跟着消失了。
• 插入异常：如果说我把学生信息和学生选课表混在一起存为一个学生信息与选课表，那么，如果学生是新生，还没选课，就无法插入（无法只插入学生的个人信息）。

7.3 范式

7.3.1 第一范式（1NF）

禁止属性分解。

属性具有原子性，是不可分解的最小单元。

每列的属性\(A\)必须是不可再分的，不可以再划分子属性\(A_1, A_2, ... A_n\)，例如：如果出生日期是一个属性，就不可以再划分二级属性为年、月、日三个子属性来存。表列属性不能是层次结构的。

第一范式是对关系型数据库表的基本要求，满足第一范式，才有个表的样子。

7.3.2 第二范式（2NF）

禁止部分依赖。

2NF在1NF的基础之上，消除了非主属性对于键码的部分函数依赖。

也就是说，非主属性必须完全依赖于键码（全部主属性）。

通俗的说，非主属性部分函数依赖于键码，意味着该非主属性不需要全部主属性就能够决定了，即，部分主属性就足以函数决定该非主属性。这是2NF不允许的。

例如：学号SID、课程号CID、姓名SName、课名CName、分数Score。

• 学号、课程号是两个主属性，它们共同组成键码；
• 姓名、课名、分数是非主属性。
• 非主属性分数Score：有\(\{SID, CID\} \to Score\)，这说明分数Score完全函数依赖于键码，没问题。
• 非主属性姓名SName：因为\(SID \to SName\)，这意味着非主属性姓名SName部分依赖于键码。不满足2NF。
• 非主属性课程名CName：因为\(CID \to CName\)，这意味着非主属性课程名CName部分依赖于键码。不满足2NF。

具体地，非主属性必须完全依赖于键码。

7.3.3 第三范式（3NF）

禁止传递依赖。

3NF在2NF的基础之上，消除非主属性对于键码的传递函数依赖。

也就是说，非主属性相互之间没有任何依赖关系。

如果表的所有属性中包含属性\(A, B, C\)，存在传递依赖\(A \to B\)，\(B \to C\)。那么，应该用两张表拆开来，分为表1中只有\(A \to B\)，表2中记录\(B \to C\)。

例如：学号SID、院系号DID、院系名DName。

• \(SID \to DID\)、\(DID \to DName\)这就形成了\(SID \to DName\)的传递函数依赖。不满足3NF。
• 应该分开来，分为表1：{学号SID, 院系号DID}和表2：{院系号DID, 院系名DName}。

7.3.4 BCNF

禁止主属性之间的依赖。

BCNF在3NF的基础之上，消除主属性对于键码的部分与传递函数依赖。

键码内的主属性相互没有依赖关系。

例如：仓库、管理员、货物、数量。

• 仓库、管理员和货物是主属性，共同组成键码。
• 数量是非主属性。
• 但是，键码内部的主属性之间，存在依赖关系，如：由管理员+货物就可以确定仓库。