ACID简述
Atomicity、Durability实现之 （WAL+redo log）
Atomicity 、Isolation实现之 （锁 OR undo log+MVCC）
一、前言
主要是后台程序员都会和数据库打交道，最常用的关系型数据库是MySQL，最常用的存储引擎是InnoDB。InnoDB又以其支持事务而大量应用，事务的核心就是ACID。网上也有很多关于ACID的文章，但关于实现原理的较少，希望简述一下数据库事务的实现机制，对今后的应用有更大的启发。
二、ACID简述
Atomicity
Transactions are often composed of multiple statements. Atomicity guarantees that each transaction is treated as a single "unit", which either succeeds completely, or fails completely: if any of the statements constituting a transaction fails to complete, the entire transaction fails and the database is left unchanged. An atomic system must guarantee atomicity in each and every situation, including power failures, errors and crashes.
原子性保证每个事务都是最小不可分割的单元，要么全部成功，要么全部失败并恢复至事务未开始的样子。
Consistency
Consistency ensures that a transaction can only bring the database from one valid state to another, maintaining database invariants: any data written to the database must be valid according to all defined rules, including constraints, cascades, triggers, and any combination thereof. This prevents database corruption by an illegal transaction, but does not guarantee that a transaction is correct.
一致性指事务总是能使得数据库从一个一致性状态转移到另一种一致性状态
Isolation
Transactions are often executed concurrently (e.g., reading and writing to multiple tables at the same time). Isolation ensures that concurrent execution of transactions leaves the database in the same state that would have been obtained if the transactions were executed sequentially. Isolation is the main goal of concurrency control; depending on the method used, the effects of an incomplete transaction might not even be visible to other transactions.
隔离性指即使在并发的执行事务时，事务之间不会造成相互影响
Durability
Durability guarantees that once a transaction has been committed, it will remain committed even in the case of a system failure (e.g., power outage or crash). This usually means that completed transactions (or their effects) are recorded in non-volatile memory.
持久性是一旦事务提交，那么这个事务一定是生效的，即使后续遇到系统崩溃
网上很多文章提到数据库的乐观锁、悲观锁。而在我看来，这种分类过于浅显，没有触及到问题的本质核心。锁只是数据库为了达到ACID的一小部分，除此之外MVCC（多版本并发控制）及WAL（write ahead log）才是数据库事务的核心。一个数据系统中，数据应该是其次的，最重要的是记录数据的变更，即log。
三、WAL、redo log与Durability
数据库的最终数据是要落盘的，试想如果我想修改100张表里的10000条数据，如果每次修改都直接以落盘的形式处理，那么必定有大量的随机IO，如果使用机械磁盘那么一定存在大量的disk seek时间，数据库性能极低（我的另一篇文章：从磁盘到文件系统 很清晰的描述了为什么随机IO性能低）。为了能提高性能，我们希望能将这些改动缓存下来，统一处理，但问题是：如果这期间数据库崩溃了，那么这部分修改就丢失了，Durability就无法得到满足。
针对于此问题，InnoDB存储引擎引入了WAL技术（write-ahead logging）和redo log。
1、每次commit事务之前，先将要修改的数据信息存入redo log buffer，然后根据innodb_flush_log_at_trx_commit 的设置将redo log刷新至磁盘，写redo log至磁盘属于磁盘顺序写（因为只需append log到下一位置），因此redo log的落盘速度是非常快的。
2、MySQL在内存中执行此次update操作，即修改数据。
3、MySQL会周期或不周期性的刷新内存值到磁盘。
可以看到，一次update事务并不会立刻修改磁盘中的数据，而是记录修改信息，后期刷新至磁盘。所以步骤一以后，即使数据库崩溃，还可以根据落盘的redo log恢复已执行的事务，使得我们能获得Durability。
四、Isolation实现之 （锁 OR undo log+MVCC）
总是能在各种数据库事务文章中看到 未提交读、提交读、可重复读等字眼，而大部分文章将这个功能的实现归功于读写锁。锁是一种实现方式，但熟悉操作系统就会知道，锁是一种开销很大的并发控制手段，如无必要，尽量采用其他方式实现。
1）锁实现的Isolation
未提交读：一个update事务A只有在对数据修改时才加write lock，一旦写完马上释放write lock，即使事务A还没有提交。因此事务B在读取同一行时，才能读到事务A修改过的数据。
提交读：一个update事务A只有在对数据修改时才加write lock，但直到事务A commit时才释放写锁。因此，同时进行的事务B希望读取同一行数据时，会被事务A的write lock堵塞，所以解决了脏读的问题。
可重复读：这个隔离等级的条件下，除了执行提交读的写锁方式，还会在读取一行数据后，为这行数据添加read lock直至事务commit。例如，事务A读取ID=1这一行数据，然后为ID=1添加read lock。事务B同时希望update ID=1，此时获取写锁失败，因此在事务A执行完之前，没有其他任何事务可以对ID=1这一行做修改，因此解决了重复读的问题
虽然读写锁解决了Isolation问题，但锁会导致大量的堵塞，性能下降。某些时候会造成死锁，为了解决死锁，还要添加死锁探测机制，性能进一步下降，因此需要更高效的方式实现Isolation。
2）MVCC实现的Isolation
MVCC，多版本并发控制，的思路是：对每一行数据用log记录多个版本，每个版本的数据可能都不相同，然后根据事务的ID去寻找到适合他的那个版本数据，以此达到不同事务之间的隔离性。
如图所示，InnoDB每行数据除了用户定义的数据外，还包括TRX_ID（当前数据属于哪个事务ID）、ROLL_PTR（指向这一行数据undo log的指针）、delete bit（删除标记）。
如图，MVCC的前提下，事务A读取ID=1的行，数据库会检测事务A的事务ID，并在ROLL_PTR指向的undo log链中寻找合适的数据版本，并提取数据。通过MVCC，数据库可以使得事务的读取不需要很多读锁，提升了数据库的性能。当一个事务完成时，数据库会删除关于这条事务所有的undo log，若未完成事务数据库崩溃则根据undo log回滚，实现Atomicity。
新的问题来了：数据库是如何知道哪个版本是事务A可见的呢？
在实现上， InnoDB 为每个事务构造了一个数组，用来保存这个事务启动瞬间，所有活跃的事务ID。
1、如果undo log指向的是绿色部分的trx_id，说明该事务在事务A启动前已commit，那么其修改一定是事务A可见的数据
2、如果undo log指向的是红色部分的trx_id，说明该事务在事务A启动前还未开启，那么其修改一定是事务A不可见的。
3、如果undo log指向的是黄色部分的trx_id且这个trx_id在事务A启动时创建的活跃事务中，那么这个版本是事务A不可见的
通过以上的步骤可以取得适合事务A的版本数据（undo log），取出数据并返回，此时实现了事务的Isolation。
提交读：事务A执行每一条语句时，生成一份活跃事务表，根据这份表去获取数据，因此不会获取到脏数据（未提交事务引起的），但会有重复读问题（因为可以读取到commit的事务数据）
可重复读：事务A只有在事务开始时才生成一份活跃事务表，因此不会读取到事务A执行中commit的其它事务引起的数据变更，也就不存在重复读问题。
参考文章
ACID, MVCC vs Locks, Transaction Isolation Levels, and Concurrency
