下面主要介绍 MySQL 中的一些实现，包括 Redo Log、Undo Log。
Redo Log
一个事务如果要修改一张表中的多条记录，记录都分布在不同的 Page 中。如果事务每一次都直接写磁盘，相当于随机 I/O，性能非常差。
所以先写日志，再把内存中的数据异步的刷到磁盘中。日志是顺序追加的，所以写日志是顺序 I/O，所以性能相比于随机 I/O 有很大的提升。
异步刷盘策略
在 MySQL InnoDB 中，不光数据写入到磁盘是异步的，而且从内存写入到 Redo Log 也是异步的。MySQL innodb_flush_log_at_trx_commit 参数可以控制 Redo Log 的刷盘策略，分别是：
- 0：每秒钟刷一次盘（默认）。
- 1：每次提交事务都会将内存中的数据刷到 Redo Log 中。
- 2：不刷盘，根据 innodb_flush_log_at_timeout 决定刷盘频率。
1 是最安全的，却也是性能最低的。InnoDB 选择 0 作为默认值，就是安全性和性能之间做出一个平衡。
物理结构
因为磁盘是按块设备，所以 MySQL 日志也是按照块（Log Block）去读写的。每一个 Log Block 都是固定大小，即 512 字节。
而且因为日志可以看作是无限增长的文件，所以在具体实现时，Redo Log 是固定大小的（可以看作是一个循环队列，后面的块会覆盖最前面的块）。
Physiological Logging
在 Log Block 中的日志采用何种方式去存储呢？这也是一个问题。
MySQL 中采用的是物理和逻辑相结合的方式。以 Page 为单位记录日志，每一个日志里面再采取逻辑记法（记录 Page 中的哪一行被修改了），这种叫做 Physiological Logging。
纯逻辑和物理记法的缺点。
- 纯逻辑记法：就是直接将 SQL 语句记录在日志中。而需要修改的记录可能被分散在多个 Page 中，如果涉及到多个 Page 的修改，修改到一半系统宕机。那么恢复的时候很难知道哪个 Page 写成功了，哪个写失败了。
- 纯物理记法：就是记录每一个 Page 在哪一个字节被修改了什么。因为 InnoDB 中采用 B+ 树存储数据，如果增加一条记录就需要修改前后指针，会产生多条物理日志。
Redo Log Block
每一个 Log Block 都包含头部、数据部分、Check sum 三部分。所以每一个 Log Block 只能存储 496 字节的数据。
字段解释如下：
- Block No：每一个 Log Block 的唯一编号，可以由 LSN 换算得到。
- Data Len：日志的实际大小。
- First Rec Group：第一条日志的起始位置，可能上一条日志非常大导致上一个 Log Block 没有存下，日志的部分数据到了当前 Block。
- Checkpoint No：当前 Block 进行 Check point 时对应的 LSN。
在一个事务中（以 TxID 作为唯一标识），可能有多条 SQL 语句，每一个语句是一个逻辑事务。逻辑事务由多个物理事务组成（同一个 Page 上的修改作为一个物理事务，一个物理事务构成一条日志，以 LSN 作为编号）。
用一个事务中的 LSN 日志也会通过链表连接起来，并且会标识这个 LSN 日志属于哪一个 TxID。
ARIES 算法
由于并发的特性，所以在多个事务同时存在时写入的 LSN日志条目，在 Redo Log 中是交替存在的，这意味着未提交的的事务也在 Redo Log 中。
ARIES 算法分为三个阶段：
- 分析阶段：确定哪些数据页是脏页，确定哪些事务未提交。
- 进行 Redo：重放 Redo Log 中的日志，将为刷盘的日志输入磁盘中。
- 进行 Undo：将未提交的事务进行回滚。
分析阶段
分析阶段有两个目标，确定哪些数据页是脏页，确定哪些事务未提交。
Fuzzy Checkpoint
ARIES 的 Checkpoint 机制，就是每隔一段事件将内存中的数据生成一个快照。因为请求是一直发生的，但是不能阻塞住系统，不接受客户端的请求（这种方法叫做 Sharp Checkpoint），一次性将数据全部刷入磁盘。
所以需要用到 Fuzzy Checkpoint，即维护两个表：活跃事务表和脏页表。
- 活跃事务表记录当前所有未提交的事务集合，每一个事务维护了一个关键变量 lastLSN，即该事务产生的最后一条日志 LSN。
- 脏页表记录当前所有未刷盘的 Page 集合（包括提交和未提交的事务），维护了一个关键变量 recoveryLSN，即导致该页为脏页的最早 LSN。
每一次 Fuzzy Checkpoint 都将生成活跃事务表和脏页表的快照，形成一条 Checkpoint 日志记入 Redo Log。
确定脏页
从 Redo Log 的最后一个 Checkpoint 开始扫描，维护一个脏页集合。
遇到 Redo 日志操作的是一个新的 Page，就把它加入到脏页集合中。脏页集合是只增不减的。
可能脏页集合中的有一些 Page 已经不是脏页了，但因为 Redo Log 是幂等的，所以重复执行是没有关系的。
确定未提交事务
从 Redo Log 的最后一个 Checkpoint 开始扫描，维护一个未提交事务集合。
当扫描到事务结束的标志时，从未提交事务集合中移出事务。
当扫描到新的事务开始时，加入未提交事务集合。
进行 Redo
取所有脏页的 recoveryLSN 最小值为 firstLSN，从 firstLSN 开始一直到 Redo Log 末尾，进行重放日志并且刷入磁盘。
Redo Log 的幂等性
如何使得 Redo Log 是幂等的？
方法就是 Page 有一个字段是 pageLSN，记录了最后一次修改对应的 LSN。在重放日志的时候，只有当日志 LSN 大于 pageLSN 时，才进行重放，否则会直接跳过。
进行 Undo
因为已经有了未提交事务的集合，所以从 Redo Log 从后向前扫描，找到未提交日志的所有 LSN（每一条日志都有一个 prevLSN 字段，方便从后向前扫描）。
对于未提交事务的日志，都生成一条逆向的 SQL 语句来执行，追加到 Redo Log 尾部。所以所有的回滚，实际上都是反向操作的提交。
Undo Log
Page 刷盘分为两个维度，四种策略：
- FORCE 和 NO-FORCE：指的是事务的实际写入发生在提交之后。当事务提交后，要求数据必须同时完成写入则称为 FORCE，如果不强制数据必须同时完成写入则称为 NO-FORCE。现实中绝大多数数据库采用的都是 NO-FORCE 策略，因为只要有了日志，变动数据随时可以持久化，从优化磁盘 I/O 性能考虑，没有必要强制数据写入立即进行。
- STEAL 和 NO-STEAL：在事务提交前，允许数据提前写入则称为 STEAL，不允许则称为 NO-STEAL。从优化磁盘 I/O 性能考虑，允许数据提前写入，有利于利用空闲 I/O 资源，也有利于节省数据库缓存区的内存。
MVCC
MVCC 多版本并发控制是一种读优化策略，MVCC 的基本思路是对数据库的任何修改都不会直接覆盖之前的数据，而是产生一个新版副本与老版本共存，以此达到读取时可以完全不加锁的目的。
- 如果隔离级别是可重复读：读取小于等于当前事务 ID 的最大版本。
- 如果隔离级别是读已提交：读取最新版本。
读未提交直接修改原始数据即可，不需要版本。
MVCC 拷贝出来的记录是记录在 Undo Log 中的。因为事务有唯一的 ID 并且从小到大依次递增，Undo Log 中维护了事务从旧到新的每一个版本，版本之间通过链表连接。
MySQL 中正常的不加锁查询语句为快照读；加锁的语句为当前读，读取的是最新的版本。
Undo Log 结构
Undo Log 维护了记录的历史版本，当事务提交之后就可以就可以删除了。在 Page 中有一个 rollback_ptr 字段，用于指向历史版本。历史版本可以通过 rollback_ptr 字段，相互的串联起来。
将 Undo Log 写入 Redo Log
对于一个事务来说，可能会修改多个数据，因此会产生多个 Undo Log。
可以将 Undo Log 也当作数据写入到 Redo Log 中，以此实现 Undo Log 的异步刷盘写入操作，并且还支持 Undo Log 的错误恢复。
Bin Log
Bin Log 也用于记录日志，但是 Bin Log 是 MySQL Server 层面的（Redo Log 和 Undo Log 都是 InnoDB 层级的）。
Bin Log 主要用于主从复制，它有以下特点：
- 并发事务对于 Bin Log 的写入是串行互斥的。
- Bin Log 中记录的日志是逻辑 SQL 语句。
- Bin Log 中记录的日志只有已经提交的事务（如果在写入 Bin Log 时宕机则截断不完整的部分）。
- Bin Log 中，同一事务中的日志是连续的（在事务提交时，将所有的日志记录到 Bin Log 中）。
MySQL 中的事务是否成功提交，以 Bin Log 为主，先记录 Bin Log 再记录 Redo Log。
Bin Log 中的事务已经提交，则认为这个事务提交（如果 Redo Log 中该事务没有提交，则补全提交命令）。
主从复制方式
MySQL 中有三种主从复制方式：同步复制、异步复制、半同步复制。
