Database基本知识整理

事务 Transaction

事务是之满足ACID特性的一组操作，可以Commit提交一个事务，也可以Rollback回滚所提交的事务。

stateDiagram

    State_1 --> Intermediate_State : insert, update, delete
    Intermediate_State --> State_2 : commit

    Intermediate_State --> State_1 : rollback or error
    State_2 --> State_1 : rollback or error

ACID

ACID 是4个单词的首字母缩写

Atomicity 原子性

如同在某一level下，原子是不可分割一样，事务被视为不可分割的最小的单元，事务的所有操作，要么全部成功，要么全部失败而回滚。

回滚可以通过回滚日志（Undo Log）来实现，回滚日志中记录着这条日志对应的事务所执行的所有修改操作，回滚的时候反向执行这些操作即可。

比如初始状态下，A有1000元，B有200元，现在A通过银行向B转账300元，那么这个操作分为两个部分

A: 1000 - 300 = 700
B: 200 + 300 = 500:

这两个操作要么都成功完成，要么都失败，不能只有A减掉300而B未增加300,这就是原子性。

Consistency 一致性

一致性是指数据库在事务执行前后都保持着一致的状态。在一致性状态下，所有事务对他那个一个数据的读取结果都是相同的。

还是上面那个例子，

转账事务完成前读取， A: 1000, B: 200
转账事务完成后读取， A: 700, B: 500

Isolation 隔离性

隔离是指不同的事务在最终完成之前，相互之间是不可见，对其它事务是没有影响的。

还是比如之前A要给B转账的例子，同时也有C要给B转账，C的初始假设是500元，要给B转账100元

那么有如下事务：

A转账B:

A: 1000 - 300 = 700
B: 200 + 300 = 500:

C转账B:

C: 500 - 100 = 400
B: 200 + 100 = 300:

这个B的状态就冲突了，这就不符合事务的隔离性。应当是10要么A的事务完成再处理C的事务，要么C先完成再处理A。

Durability 持久性

一旦事务提交，则其所做的修改将会永远保存到数据库中。即使系统发生崩溃，事务执行的结果也不能丢失。

系统发生奔溃可以用重做日志（Redo Log）进行恢复，从而实现持久性。与回滚日志记录数据的逻辑修改不同，重做日志记录的是数据页的物理修改。

ACID之间的关系

看起来，ACID之间似乎是平等的，但实际上是相互之间有一定关系的。

只有满足一致性，事务的执行结果才是正确的。
在无并发的情况下，事务串行执行，隔离性一定能够满足。此时只要能满足原子性，就一定能满足一致性。
在并发的情况下，多个事务并行执行，事务不仅要满足原子性，还需要满足隔离性，才能满足一致性。
事务满足持久化是为了能应对系统崩溃的情况。

如下图：

stateDiagram
    原子性 --> 一致性 : 并发/串行
    隔离性 --> 一致性 : 并发
    一致性 --> 执行结果正确

    持久性 --> 处理系统崩溃

AUTOCOMMIT

MySQL中默认采用AutoCommit自动提交，也就是说，在不显示的使用START TRANSACTION语句来表示一个事务的开始，那么每一条SQL语句都会被当作一个事务并自动进行提交。

并发的一致性问题

串行情况下，隔离性是很容易保障的。但是并发情况下，隔离性就较难保障了，隔离性没有保障的话，那么并发下的一致性也就没有保障了。这样就会出现很多并发下的一致性问题：

丢失修改

T1和T2两个事务都对同一个数据进行修改，T1先进行，T2后进行，T2的执行结果覆盖了T1的结果。过程可能如下：

sequenceDiagram
    T1 ->>+ Data: Read
    Data ->>- T1: 0

    T2 ->>+ Data: Read
    Data ->>- T2: 0

    T1 ->>+ Data: Write 10
    Data -->- T1: 10

    T2 ->>+ Data: Write 20
    Data -->- T2: 20

    T1 ->>+ Data: Read
    Data ->>- T1: 20

    T2 ->>+ Data: Read
    Data ->>- T2: 20

如此，T1的修改就丢失了

读脏数据

T1修改数据，T2随后读取这个数据。但是如果T1因为error而rollback，那么T2读取的数据就是脏数据了

sequenceDiagram
    T1 ->>+ Data : Read
    Data ->>- T1 : 10

    T1 ->>+ Data : Write 20
    Data -->- T1 : 20

    T2 ->>+ Data : Read
    Data ->>- T2 : 20

    T1 ->>+ Data : ROLLBACK
    Data -->- T1 : 10

不可重复读

不可重复读是指T2需要读两次数据，但是在两次读取这个数据之间，T1进行了修改，此时第二次读到的数据就与第一次的不一样了

sequenceDiagram
    T1 ->>+ Data : Read
    Data ->>- T1 : 10

    T2 ->>+ Data : Read
    Data ->>- T2 : 10

    T1 ->>+ Data : Write 20
    Data -->- T1 : 20

    T2 ->>+ Data : Read
    Data ->>- T2 : 20

幻影读

指T2在两次读取某段数据时，期间T1在这段数据中插入了新的数据，此时两次读取的结果不一致。

sequenceDiagram
    T1 ->>+ Data : COUNT(Product)
    Data ->>- T1 : 100

    T2 ->>+ Data : COUNT(Product)
    Data ->>- T2 : 100

    T1 ->>+ Data : INSERT Product

    T2 ->>+ Data : COUNT(Product)
    Data ->>- T2 : 101

并发锁

并发下产生不一致结果的问题，主要原因是没有满足事务的隔离性，解决方法是通过并发的控制来保证隔离性。并发的控制可以通过锁来实现，但是如果由客户端的用户自行来处理，那么比较麻烦，有时还不可行。好在数据库管理系统提供了事务的隔离级别，这样可以让用户以比较轻松的方式来处理并发下的一致性问题。

锁的粒度

MySQL中提供了两种粒度的锁：行级别锁和表级别锁。顾名思义，行级别锁只会锁住被修改的那行数据，而表级别所则会将被修改数据所在的表全部锁住。

使用的时候，应当只锁取需要修改的那部分数据，而不是所有的资源。锁的粒度越小，那么数据碰撞的概率越小，发生锁争抢的几率就越小，系统的并发性也就越高。但是加锁需要消耗资源，锁的各种操作都会增加系统的开销，因此锁的力度越小，那么需要的锁就越多，系统开销就会越大。所以，在选择锁的力度的时候，需要在系统开销与并发之间做权衡。

锁的类型

读写锁

互斥锁(Exclusive)，简写为 X，又称写锁。
共享锁(Shared), 简写为 S，又称读锁。

有以下两个规定

一个事务对数据对象A加了X锁，就可以对 A 进行读取和更新。加锁期间其它事务不能对 A 加任何锁。
一个事务对数据对象 A 加了 S 锁，可以对 A 进行读取操作，但是不能进行更新操作。加锁期间其它事务能对 A 加 S 锁，但是不能加 X 锁。

意向锁

使用意向锁（Intention Locks）可以更容易地支持多粒度的锁。

在存在行级锁和表级锁的情况下，事务 T 想要对表 A 加 X 锁，就需要先检测是否有其它事务对表 A 或者表 A 中的任意一行加了锁，那么就需要对表 A 的每一行都检测一次，这是非常耗时的。

意向锁在原来的 X/S 锁之上引入了 IX/IS，IX/IS 都是表锁，用来表示一个事务想要在表中的某个数据行上加 X 锁或 S 锁。有以下两个规定：

一个事务在获得某个数据行对象的 S 锁之前，必须先获得表的 IS 锁或者更强的锁；
一个事务在获得某个数据行对象的 X 锁之前，必须先获得表的 IX 锁。

通过引入意向锁，事务 T 想要对表 A 加 X 锁，只需要先检测是否有其它事务对表 A 加了 X/IX/S/IS 锁，如果加了就表示有其它事务正在使用这个表或者表中某一行的锁，因此事务 T 加 X 锁失败。

锁之间的互斥关系

N 表示排它， Y 表示可以兼容

	X	IX	S	IS
X	N	N	N	N
IX	N	Y	N	Y
S	N	N	Y	Y
IS	N	Y	Y	Y

解释如下：

任意 IS/IX 锁之间都是兼容的，因为它们只表示想要对表加锁，而不是真正加锁；
这里兼容关系针对的是表级锁，而表级的 IX 锁和行级的 X 锁兼容，两个事务可以对两个数据行加 X 锁。（事务 T1 想要对数据行 R1 加 X 锁，事务 T2 想要对同一个表的数据行 R2 加 X 锁，两个事务都需要对该表加 IX 锁，但是 IX 锁是兼容的，并且 IX 锁与行级的 X 锁也是兼容的，因此两个事务都能加锁成功，对同一个表中的两个数据行做修改。）

更新锁

更新 (U) 锁可以防止通常形式的死锁。一般更新模式由一个事务组成，此事务读取记录，获取资源（页或行）的共享 (S) 锁，然后修改行，此操作要求锁转换为排它 (X) 锁。

如果两个事务获得了资源上的共享模式锁，然后试图同时更新数据，则一个事务尝试将锁转换为排它 (X) 锁。共享模式到排它锁的转换必须等待一段时间，因为一个事务的排它锁与其它事务的共享模式锁不兼容；发生锁等待。第二个事务试图获取排它 (X) 锁以进行更新。由于两个事务都要转换为排它 (X) 锁，并且每个事务都等待另一个事务释放共享模式锁，因此发生死锁。

若要避免这种潜在的死锁问题，请使用更新 (U) 锁。一次只有一个事务可以获得资源的更新 (U) 锁。如果事务修改资源，则更新 (U) 锁转换为排它 (X) 锁。否则，锁转换为共享锁。

封锁协议

三级封锁协议

1、 一级锁协议

事务 T 要修改数据 A 时必须加 X 锁，直到 T 结束才释放锁。

可以解决丢失修改的问题，因为不能同时有多个事务对同一个数据进行修改，那么事务的修改就不会被覆盖。

sequenceDiagram
    T1 ->>+ A  : Lock-X
    A  -->  T1 : Locked

    T2 ->>+ A  : Lock-X
    A  -->  T2 : wait

    T1 ->>+ A  : Read
    A  ->>- T1 : 0

    T1 ->>+ A  : Write 10
    A  -->- T1 : 10

    T1 ->>  A  : Unlock
    A  -->- T1 : Unlocked

    A  -->  T2 : Locked

    T2 -->+ A  : Read
    A  -->- T2 : 10

    T2 ->>  A  : Unlock
    A  -->- T2 : Unlocked

2、 二级锁协议

在一级的基础上，要求读取数据 A 时必须加 S 锁，读取完马上释放 S 锁。

可以解决读脏数据问题，因为如果一个事务在对数据 A 进行修改，根据 1 级封锁协议，会加 X 锁，那么就不能再加 S 锁了，也就是不会读入数据。

sequenceDiagram
    T1 ->>+ A  : Lock-X
    A  -->  T1 : Locked

    T2 ->>+ A  : Lock-S
    A  -->  T2 : wait

    T1 ->>+ A  : Read
    A  ->>- T1 : 0

    T1 ->>+ A  : Write 10
    A  -->- T1 : 10

    T1 ->>  A  : Unlock
    A  -->- T1 : Unlocked

    A  -->  T2 : Locked

    T2 ->>+ A  : Read
    A  ->>- T2 : 10

    T2 ->>  A  : Unlock
    A  -->- T2 : Unlocked

3、 三级锁协议

在二级的基础上，要求读取数据 A 时必须加 S 锁，直到事务结束了才能释放 S 锁。

可以解决不可重复读的问题，因为读 A 时，其它事务不能对 A 加 X 锁，从而避免了在读的期间数据发生改变。

sequenceDiagram
    T1 ->>+ A  : Lock-S
    A  -->  T1 : Locked

    T2 ->>+ A  : Lock-X
    A  -->  T2 : wait

    T1 ->>+ A  : Read
    A  ->>- T1 : 0

    T1 ->>+ A  : Read
    A  ->>- T1 : 0

    T1 ->>  A  : Unlock
    A  -->- T1 : Unlocked

    A  -->  T2 : Locked

    T2 ->>+ A  : Read
    A  ->>- T2 : 0

    T2 ->>+ A  : Write 10
    A  -->- T2 : 10

    T2 ->>  A  : Unlock
    A  -->- T2 : Unlocked

两段锁协议

两段锁协议是指每个事务的执行可以分为两个阶段：生长阶段（加锁阶段）和衰退阶段（解锁阶段）。

加锁阶段：在该阶段可以进行加锁操作。在对任何数据进行读操作之前要申请并获得S锁，在进行写操作之前要申请并获得X锁。加锁不成功，则事务进入等待状态，直到加锁成功才继续执行。
解锁阶段：当事务释放了一个封锁以后，事务进入解锁阶段，在该阶段只能进行解锁操作不能再进行加锁操作。

两段封锁法可以这样来实现：事务开始后就处于加锁阶段，一直到执行ROLLBACK和COMMIT之前都是加锁阶段。ROLLBACK和COMMIT使事务进入解锁阶段，即在ROLLBACK和COMMIT模块中DBMS释放所有封锁。

两段锁协议是指所有事务必须分两个阶段对数据项加锁和解锁：

在对任何数据进行读、写操作之前，要申请并获得对该数据的封锁。
每个事务中，所有的封锁请求先于所有的解锁请求。

例如事务T1遵守两段锁协议，其封锁序列是：

sequenceDiagram
    T ->>+ A : Lock
    A -->  T : Locked

    T ->>+ A : Read
    A ->>- T : 0

    T ->>+ A : Write 100
    A -->- T : 100

    T ->>+ B : Lock
    B -->  T : Locked

    T ->>  A : Unlock
    A -->- T : Unlocked

    T ->>+ B : Read
    B ->>- T : 20

    T ->>  B : Unlock
    B -->- T : Unlocked

Lock A, Read A, A:=A+100, Write A, Lock B, Unlock A, Read B, Unlock B, Commit;

可以证明，若并发执行的所有事务均遵守两段锁协议，则对这些事务的任何并发调度策略都是可串行化的。

另外要注意两段锁协议和防止死锁的一次封锁法的异同之处。一次封锁法要求每个事务必须一次将所有要使用的数据全部加锁，否则就不能继续执行，因此一次封锁法遵守两段锁协议；但是两段锁协议并不要求事务必须一次将所有要使用的数据全部加锁，因此遵守两段锁协议的事务可能发生死锁。

MySQL的隐式锁与显示锁

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

InnoDB 也可以使用特定的语句进行显示锁定：

SELECT ... LOCK In SHARE MODE;
SELECT ... FOR UPDATE;

隔离级别

未提交隔离 (READ UNCOMMITTED)

事务中的修改，即使没有提交，对其它事务也是可见的。

提交读（READ COMMITTED）

一个事务只能读取已经提交的事务所做的修改。换句话说，一个事务所做的修改在提交之前对其它事务是不可见的。

可重复读（REPEATABLE READ）

保证在同一个事务中多次读取同一数据的结果是一样的

可串行化（SERIALIZABLE）

强制事务串行执行，这样多个事务互不干扰，不会出现并发一致性问题。

此隔离级别需要加锁实现，因为要使用加锁机制保证同一时间只有一个事务执行，也就是保证事务串行执行。

隔离级别可以解决的并发一致性的问题

	脏读	不可重复读	幻影读
未提交读	N	N	N
提交读	Y	N	N
可重复读	Y	Y	Y
可串行化	Y	Y	Y

多版本并发控制 MVCC

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

基本思想

加锁是为了解决多个事务同时执行时而引起的并发一致性问题的。在实际场景中，读操作是要多于写操作的，因此，引入了读写锁来避免不必要的加锁操作，允许多个事务同时读同一份数据。读写锁中，读和写这两个操作依然还是互斥的。 MVCC 利用了多版本的思想，写操作更新最新的版本快照，但是读操作则去读旧的版本快照，这样读和写之间就没有冲突了，有点类似于Copy-On-Write。

在 MVCC 中，事务的修改操作（DELETE，INSERT，UPDATE）会为数据行新增一个版本快照。

脏读和不可重复读最根本的原因是事务读取到其它事务未提交的修改。在事务进行读取操作时，为了解决脏读和不可重复读，MVCC规定只能读取已经提交的快照。当然，一个事务读取自身尚未提交的快照是不算脏读的。

版本号

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

Undo 日志

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

例如在 MySQL 创建一个表t，包含主键id和一个字段x。先插入一行数据，然后对这个数据进行两次跟新操作。

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机制，每条操作指令都会被当作一个事务来执行，所以上面的操作总共涉及到了三个事务。快照中，除了记录事务版本号 TRX_ID 和所做操作外，还记录了一个bit的DEL字段，用于标记是否被删除。

INSERT, UPDATE, DELETE 操作会创建一个日志，并将事务版本号 TRX_ID 写入其中。 DELETE 可以看作是一个特殊的 UPDATE, 还会额外将DEL字段置为1.

ReadView

MVCC 还维护了一个 ReadView 结构，主要包含了当前系统未提交的事务列表 TRX_IDs, 还有该列表的最小和最大的 TRX_ID, 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_MIN <= TRX_ID <= TRX_ID_MAX，需要根据隔离级别再进行判断：
- 提交读：如果 TRX_ID 在 TRX_IDs 列表中，表示该数据行快照对应的事务还未提交，则该快照不可使用。否则表示已经提交，可以使用。
- 可重复读：都不可以使用。因为如果可以使用的话，那么其它事务也可以读到这个数据行快照并进行修改，那么当前事务再去读这个数据行得到的值就会发生改变，也就是出现了不可重复读问题。

在数据行快照不可使用的情况下，需要沿着 Undo Log 的回滚指针 ROLL_PTR 找到下一个快照，再进行上面的判断。

快照读与当前读

快照读

MVCC 的 SELECT 操作是快照中的数据，不需要进行加锁操作。

SELECT * FROM table ...;

当前读

MVCC 其它会对数据库进行修改的操作（INSERT、UPDATE、DELETE）需要进行加锁操作，从而读取最新的数据。可以看到 MVCC 并不是完全不用加锁，而只是避免了 SELECT 的加锁操作。

在进行 SELECT 操作时，可以强制指定进行加锁操作。以下第一个语句需要加 S 锁，第二个需要加 X 锁。

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

InnoDB的Next-Key Locks

Next-Key Locks 是 MySQL 的 InnoDB 存储引擎的一种锁的实现。

MVCC 不能解决幻影读的问题，Next-Key Locks 就是为了解决这个问题而存在的。在可重复读 (REPEATABLE READ) 隔离级别下，使用 MVCC + Next-Key Locks 可以解决幻影读。

InnoDB 实现了三种行锁：

Record Locks

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

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

Gap Locks

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

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

Next-Key Locks

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

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

关系型数据库设计理论

函数依赖

记 A->B 表示 A 函数决定 B，也可以说 B 函数依赖于 A。

如果 {A1，A2，… ，An} 是关系的一个或多个属性的集合，该集合函数决定了关系的其它所有属性并且是最小的，那么该集合就称为键码。

对于 A->B，如果能找到 A 的真子集 A’，使得 A’-> B，那么 A->B 就是部分函数依赖，否则就是完全函数依赖。

对于 A->B，B->C，则 A->C 是一个传递函数依赖。

异常

以下的学生课程关系的函数依赖为 {Sno, Cname} -> {Sname, Sdept, Mname, Grade}，键码为 {Sno, Cname}。也就是说，确定学生和课程之后，就能确定其它信息。

Sno	Sname	Sdept	Mname	Cname	Grade
1	学生-1	学院-1	院长-1	课程-1	90
2	学生-2	学院-2	院长-2	课程-2	80
2	学生-2	学院-2	院长-2	课程-1	100
3	学生-3	学院-2	院长-2	课程-2	95

不符合范式的关系，会产生很多异常，主要有以下四种异常：

冗余数据：例如学生-2 出现了两次。
修改异常：修改了一个记录中的信息，但是另一个记录中相同的信息却没有被修改。
删除异常：删除一个信息，那么也会丢失其它信息。例如删除了课程-1 需要删除第一行和第三行，那么学生-1 的信息就会丢失。
插入异常：例如想要插入一个学生的信息，如果这个学生还没选课，那么就无法插入。

范式

范式理论是为了解决以上提到四种异常。

高级别范式的依赖于低级别的范式，1NF 是最低级别的范式。

第一范式 (1NF)

属性不可分。同一个对象的属性，需要在一张表中。

第二范式 (2NF)

每个非主属性完全函数依赖于键码。可以通过分解来满足。

分解前：

Sno	Sname	Sdept	Mname	Cname	Grade
1	学生-1	学院-1	院长-1	课程-1	90
2	学生-2	学院-2	院长-2	课程-2	80
2	学生-2	学院-2	院长-2	课程-1	100
3	学生-3	学院-2	院长-2	课程-2	95

以上学生课程关系中，{Sno, Cname} 为键码，有如下函数依赖：

Sno -> Sname, Sdept
Sdept -> Mname
Sno, Cname-> Grade

Grade 完全函数依赖于键码，它没有任何冗余数据，每个学生的每门课都有特定的成绩。

Sname, Sdept 和 Mname 都部分依赖于键码，当一个学生选修了多门课时，这些数据就会出现多次，造成大量冗余数据。

分解后：

关系-1：

Sno	Sname	Sdept	Mname
1	学生-1	学院-1	院长-1
2	学生-2	学院-2	院长-2
3	学生-3	学院-2	院长-2

有以下函数依赖：

Sno -> Sname, Sdept
Sdept -> Mname

关系-2：

Sno	Cname	Grade
1	课程-1	90
2	课程-2	80
2	课程-1	100
3	课程-2	95