并发控制

处理并发读/写访问的系统通常实现一个由两种锁类型组成的锁系统。这两种锁通常被称为共享锁（shared lock）和排他锁（exclusive lock），也叫读锁（read lock）和写锁（write lock）。

锁定策略是锁开销和数据安全性之间的平衡。

表锁（table lock）	行级锁（row lock）
开销小	开销大
并发度低	并发度高
只有没有人执行写操作时，其他读取的客户端才能获得读锁，读锁之间不会相互阻塞	允许多人同时编辑不同的行，而不会阻塞彼此

事务特性

ACID

原子性（atomicity）：一个事务必须被视为一个不可分割的工作单元
一致性（consistency）：事务不能破坏关系数据的完整性以及业务逻辑上的一致性
隔离性（isolation）：一个事务所做的修改在最终提交以前，对其他事务是不可见的。较低的隔离级别通常允许更高的并发性，并且开销也更低

隔离级别脏读不可重复读幻读加锁读

READ UNCOMMITTED 是是是否

READ COMMITTED 否是是否

REPEATABLE READ 否否是否

SERIALIZABLE 否否否是
- 未提交读（READ UNCOMMITTED）：一般不用。在事务中可以查看其他事务还没有提交的修改，存在脏读（dirty read）问题，即读取未提交的数据
- 提交读（READ COMMITTED）：大多数据库系统的默认隔离级别。在事务中可以查看其他事务提交的修改，存在不可重复读（nonrepeatable read）问题，即若别的事务在该事务的两次读取数据之间提交了修改操作，则该事务读到的两次数据可能不同，读的结果的行数不变或者减少，结果的内容发生变化，侧重表达读-读
- 可重复读（REPEATABLE READ）：InnoDB 默认的事务隔离级别。保证在同一个事务中多次读取相同行数据的结果是一样的，存在幻读（phantom read）问题，读的结果的行数变多，侧重表达读-写
- 可串行化（SERIALIZABLE）：很少使用。强制事务按序执行，不同事务之间不可能产生冲突
持久性（durability）：完成的事务对系统的影响是永久性的

隔离级别	脏读	不可重复读	幻读	加锁读
READ UNCOMMITTED	是	是	是	否
READ COMMITTED	否	是	是	否
REPEATABLE READ	否	否	是	否
SERIALIZABLE	否	否	否	是

事务日志

预写式日志（write-ahead logging）：存储引擎只更改内存中的数据副本，将更改的记录写入事务日志，最后由一个后台进程在某个时间去更新硬盘中的表。由于事务日志采用的是追加写操作，是在硬盘中一小块区域内的顺序 I/O，因此速度较快。

多版本并发控制

多版本并发控制（MVCC，Multiversion Concurrency Control）是行级锁的变种，避免多数情况下的加锁操作，维持一个数据的多个版本，解决读-写操作冲突的一个抽象概念，具体通过快照读实现。

实现

每个事务在启动时分配一个单向增长的事务 ID，读操作只读取该事务开始前的数据库快照。具体通过版本链，undo 日志，Read View 来实现。

版本链

数据表中的每行数据都包含隐藏字段 trx_id、db_roll_pointer，分别记录创建这条数据或最后一次修改该数据的事务 ID 和指向这条记录的上一个版本的回滚指针

每次对数据库记录进行改动，都会记录一条 undo 日志，每条 undo 日志都有 trx_id 和 roll_pointer 属性（INSERT 操作对应的 undo 日志没有该属性，因为该记录并没有更早的版本），将这些 undo 日志按 roll_pointer 连起来，串成一个链表，称为版本链。

Undo 日志

用于回滚时进行操作的恢复和快照读时实现独立的快照数据版本。

主要分为：

insert undo log：只在事务回滚时需要，并且在事务提交后可以被立即丢弃
update undo log：不仅在事务回滚时需要，在快照读时也需要，只有在快速读或事务回滚不涉及该日志时，对应的日志才会被 purge 线程统一清除

Read View

事务执行快照读的那一刻，会生成数据库系统当前的一个快照，主要用于做可见性判断，即判断该事务能够看到哪个版本的数据。

已提交读隔离级别下的事务在每次查询的开始都会生成一个独立的 ReadView，而可重复读隔离级别则在第一次读的时候生成一个 ReadView，之后的读都复用之前的 ReadView。

主要的属性：

trx_ids: 当前系统活跃（未提交）事务版本号集合
up_limit_id: 创建当前 read view 时，系统正处于活跃事务最小版本号
low_limit_id: 创建当前 read view 时，当前系统最大事务版本号+1
creator_trx_id: 创建当前 read view 的事务版本号

可见性判断条件：

bool changes_visible(trx_id_t id, const table_name_t& name) {
    // 断言，确保 id 大于 0
    ut_ad(id > 0);
    if (id < m_up_limit_id || id == m_creator_trx_id) {
        // 该数据是在当前事务开启之前就已经存在了的，或者该数据就是当前事务自己生成的，可以显示
        return(true);
    }
    // 检查事务 ID 在给定的表下是合理的
    check_trx_id_sanity(id, name);
    if (id >= m_low_limit_id) {
        // 该数据是在当前 read view 创建之后才产生的，不显示
        return(false);
    } else if (m_ids.empty()) {
        // 当前系统活跃的事务为空，那么所有的更改都是可见的
        return(true);
    }
    const ids_t::value_type* p = m_ids.data();
    // 判断 trx_id 是否在活跃事务中
    return(!std::binary_search(p, p + m_ids.size(), id));
}

举例

新增如下数据：

地址	id	name	trx_id	roll_pointer
0x123456	1	张三	50

ID 为 60 的事务进行修改 UPDATE table SET name='张三1' WHERE id=1，并进行了提交。ID 为 70 的事务进行了修改 UPDATE table SET name='张三2' WHERE id=1，但未提交。

此时 undo 日志的版本链如下：

地址	id	name	trx_id	roll_pointer
0x123458	1	张三2	70	0x123457
0x123457	1	张三1	60	0x123456
0x123456	1	张三	50

这时另一个事务发起了 select 语句要查询 id 为 1 的记录，先找到最近的一条记录，发现 trx_id = 70，位于 trx_ids 列表内，则沿着 roll_pointer 找到下一条，trx_id = 60，小于列表中的最小 id，直接访问结果为张三1。

提交 ID 为 70 的事务，ID 为 80 的事务进行了修改 UPDATE table SET name='张三3' WHERE id=1，但未提交。

此时 undo 日志的版本链如下：

地址	id	name	trx_id	roll_pointer
0x123459	1	张三3	80	0x123458
0x123458	1	张三2	70	0x123457
0x123457	1	张三1	60	0x123456
0x123456	1	张三	50

这时另一个事务发起了 select 语句要查询 id 为 1 的记录，此时根据隔离级别的不同，读取的结果不一样：

若为 RC 级别，会重新生成 Read View，trx_ids 中的值为 80，由于 80 位于 trx_id 中，不能访问，读到的数据为张三2
若为 RR 级别，Read View 不变，trx_ids 中的值仍为 70，读到的数据为张三1

主从复制简介

MySQL 提供了一种原生方式来将一个节点执行的写操作分发到其他节点，这被称为复制。主从复制的工作原理就是 slave 从库会从 master 主库读取 binary log events 进行数据同步。

主从复制过程分成四步：

从库生成两个线程，一个 I/O 线程，一个 SQL 线程
当从库连接主库时，主库会生成一个 二进制转储（binlog dump）线程，用来给从库 I/O 线程传 binlog
I/O 线程去请求主库的 binlog，并将得到的 binlog 日志写到 relay log（中继日志） 文件中。（在读取 binlog 的内容的操作中，会对主库的 binlog 加锁，当binlog读取完成并发送给从库后解锁）
从 SQL 线程会读取 relay log 文件中的日志，并解析成具体操作，来实现主从的操作一致，最终实现主从的数据一致

数据库范式

有 3 种：

1NF(第一范式)：属性不可再分。
2NF(第二范式)：1NF 的基础之上，消除了非主属性对于码的部分函数依赖。
3NF(第三范式)：3NF 在 2NF 的基础之上，消除了非主属性对于码的传递函数依赖。

函数依赖（functional dependency）：若在一张表中，在属性（或属性组）X 的值确定的情况下，必定能确定属性 Y 的值，那么就可以说 Y 函数依赖于 X，写作 X → Y。

部分函数依赖（partial functional dependency）：如果 X→Y，并且存在 X 的一个真子集 X0，使得 X0→Y，则称 Y 对 X 部分函数依赖。比如学生基本信息表 R 中（学号，身份证号，姓名）当然学号属性取值是唯一的，在 R 关系中，（学号，身份证号）->（姓名），（学号）->（姓名），（身份证号）->（姓名）；所以姓名部分函数依赖与（学号，身份证号）；

**完全函数依赖(Full functional dependency)**：在一个关系中，若某个非主属性数据项依赖于全部关键字称之为完全函数依赖。比如学生基本信息表 R（学号，班级，姓名）假设不同的班级学号有相同的，班级内学号不能相同，在 R 关系中，（学号，班级）->（姓名），但是（学号）->(姓名)不成立，（班级）->(姓名)不成立，所以姓名完全函数依赖与（学号，班级）；

传递函数依赖：在关系模式 R(U)中，设 X，Y，Z 是 U 的不同的属性子集，如果 X 确定 Y、Y 确定 Z，且有 X 不包含 Y，Y 不确定 X，（X∪Y）∩Z=空集合，则称 Z 传递函数依赖(transitive functional dependency) 于 X。传递函数依赖会导致数据冗余和异常。传递函数依赖的 Y 和 Z 子集往往同属于某一个事物，因此可将其合并放到一个表中。比如在关系 R(学号 , 姓名, 系名，系主任)中，学号 → 系名，系名 → 系主任，所以存在非主属性系主任对于学号的传递函数依赖。