search

AlexiaChen / AlexiaChen.github.io

My Blog https://github.com/AlexiaChen/AlexiaChen.github.io/issues
88 stars 11 forks source link

数据库事务实现原理 #101

Open AlexiaChen opened 4 years ago

AlexiaChen commented 4 years ago

数据库事务实现原理

之前写过《程序员应该知道的数据库知识》，原本是打算把事务实现写在那里的，但是发现篇幅太长，所以需要拿出来单独写成一篇。

Redo Log

数据库事务有ACID四个核心属性，之前说过，再提一下:

这四个属性中，D比较容易，最简单，C主要是上层的各种规则来约束，也相对简单。但是A和I牵扯到并发问题，崩溃恢复（掉电保护），是事务实现的核心难点。

说到事务实现原理，就要提到ARIES算法(Algorithms for recovery and isolation expoliting semantics),这个算法是由早年IBM的几个研究员提出的算法集合，论文名字叫《ARIES： A Transaction Recovery method supporting Fine-Granularity Locking and Partial Rollback Using Write-Ahead Logging》，这个论文影响深远，DB2，MySQL，InnoDB，SQL Server，Oracle在事务的实现的很多方面都吸取了该思想。

然后，你也看到论文标题了，重点就是事务的恢复和回滚，而且是用WAL(Write-Ahead logging)这种技术思想来实现的，WAL的思想影响深远流行，你在LevelDB，RocksDB的源码里都能看到，甚至是Raft共识算法中的副本状态机的模型也是基于这种思想。这论文主要讨论的是事务的A，I，D这三个属性。所以接下来会分析事务的A,I,D三个属性，C这个属性一般是上层保证，就暂时不分析了。=，先说最简单的D，D要涉及OS的I/O问题。

Write-Ahead logging

WAL又叫写前日志，或者叫预写日志，看它名字，你就知道它只是一种指导思想。

一个事务要修改多张表的多条记录，多条记录分散在不同的Page里，这个Page就是之前文章提到的数据页，是逻辑上的，InnoDB默认16KB，不同的Page对应到磁盘的不同位置。如果每个事务都直接写磁盘，一次事务提交就要多次磁盘的随机读写（即使有B+树降低I/O次数的保证），性能达不到要求。

怎么办？如果不写磁盘，在内存中进行事务commit提交，然后通过后台线程异步把内存中的数据写入磁盘中这样会遇到问题，就是机器在宕机，系统崩溃的时候，内存中的数据还没有来得及刷盘，数据就丢失或者损坏了，而且没有历史记录来做恢复和回滚。

所以就有了WAL的思路，先在内存中commit事务，然后写日志，然后后台线程把内存中的数据异步刷到磁盘，日志是AOF(Append-Only File),只管在文件尾追加内容，顺序写，性能很高，从而避免了一个事务发生多次磁盘随机读写的问题。也就是WAL是先写日志，再写数据到数据库文件落盘。

因为WAL只是指导思想，对应到InnoDB中，WAL就是Redo Log，就是重做日志，可以对历史进行重放。在InnoDB中，不光事务修改的数据库表数据是异步刷盘的，连Redo Log也是异步刷盘到AOF中的。在事务commit后，Redo Log模块先写入到内存中的Redo Log Buffer，然后异步刷到磁盘上的Redo Log文件中。

所以，InnoDB有个关键参数，innodb_flush_log_at_trx_commit控制Redo Log的刷盘策略，就是在Redo Log Buffer中每提交多少个事务就刷一次盘到Redo Log文件，显然，每提交一个事务就刷一次盘这个最安全（不会丢数据），但是性能最差。

                              Client
                                |
                            commit tx
                                |

memory     Redo Log Buffer      +   | Page1 | Page2| ... | PageN |    内存事务提交

                |                               |
            Async Flush Disk               Async Flush Disk
                |                               |
-------------------------------------------------------------------------------
                |                               |

disk        Redo Log File(AOF,WAL)          | Page1 | Page2 | ... | PageN |
                                                  数据库的物理存储

以上就是简单的InnoDB异步刷盘文本示意图。

Redo Log的逻辑与物理结构

知道了Redo Log的设计思想，那么来看看它的详细结构，这部分跟实现相关。

从逻辑上说，日志就是一个流式数据，日志源源不断追加，永无结束。但从物理上说，日志不可能无限追加，因为是物理世界，主要是以下两点:

所以，下面需要分析下Redo Log的逻辑结构和物理结构的差异，从逻辑上看，Redo Log不断追加的写入特性，就是一个序列递增，所以有了LSN(Log Sequence Number)的概念，LSN是逻辑上日志按照时间顺序从小到大的编号写入。在InnoDB中，LSN是一个64位整数，取的是从数据库安装启动开始，到当前所写入的总的日志字节数。因为不同的事务有大小，每个事务产生的日志数据量是不一样的，所以日志的追加是变长的记录，因此LSN是单调递增，但是递增不均匀。


|--LSN 0-247--|------LSN 248-LSN539------|-LSN 540-686-|-------LSN 687-1451---|

Redo Log的逻辑结构

|---Log Block 1(512 bytes)---|---Log Block 2(512 bytes)---|....................|

Redo Log的物理结构

从物理上看，一个固定大小的Redo Log File，每个512字节是一个Block，循环使用。很显然，可以根据对应的LSN换算出所属的Block。反过来，也很容易算出第一条日志在什么位置。

Physiological Logging

翻译过来就是生理式日志。

知道了Redo Log的整体结构，进一步需要分析每个Log Block里面Log的存储格式。这个问题比较关键，是实现数据库事务的核心。

(PageID, offset1, len1, old_value1, changed_value1)

(PageID, offset2, len2, old_value1, changed_value2)

前两种格式都是逻辑格式，最后一个是物理格式。Redo Log采用的是逻辑和物理的综合，就是先以Page为单位记录日志，每个Page里面再采用逻辑格式(记录Page里的哪一行被修改了)。这种格式就是Physiological Logging。

为什么要采用这种混合式的日志呢？

所以纯粹的逻辑日志宕机后不好恢复，但是物理日志又太大，Physiological Logging综合了两个优点。当然，如果自己写玩具数据库的WAL，暂时可以不用这么复杂，越简单越好，WAL是可以简化很多的。

I/O写入的原子性

要实现事务的原子性，也就是ACID中的A，就先得考虑磁盘I/O的原子性。一个Log Block是512字节。假设OS的一次write往磁盘上写入一个Log Block(512 bytes)，如果写到一半机器宕机(或者写完没有调用fsync)后再重启，那么写入写入成功的字节数是0，还是0-512之间的任意一个字节数？

这个问题其实没有答案，与OS底层和磁盘的机制有关，如果底层保证了512字节的写入原子性，上层是不需要关心的。否则上层就得考虑这个问题，方法可以通过在WAL日志中加入checksum解决。通过checksum能判断宕机重启后Log Block是否完整。如果不完整，就可以丢弃这个Log Block，对WAL日志文件来说就是做截断操作。

除了WAL日志写入有原子性问题，实体数据写入得原子性问题更大。一个Page有16KB，往磁盘上刷盘，如果刷到一半系统宕机再重启，请问这个Page是什么状态？在这种情况下，Page就是一个被损坏的Page。但是，既然有了WAL日志，不能用WAL恢复这个Page吗？答案：不能。

因为WAL也恢复不了。因为MySQL的Redo Log是Physiological Logging，里面只是一个对Page的修改的逻辑操作，Redo Log记录了哪些地方修改了，但是不知道哪个地方损坏了。另外，即使为了这个Page加了Page的checksum，也只能判断Page是否损坏，但无法修复，只能丢弃，有两个解决办法：

Redo Log Block的结构

Log Block需要有checksum字段，另外海域一些头部字段。事务可大可小，可能一个Block可以存储好几个事务的操作记录，有可能一个事务的操作记录占用好几个Block。所以在Block里面，得有字段记录这种offset。

以下展示了Block得结构，header部分有12字节，尾部checksum有4个字节。所以一个Block的payload只能存496字节的操作记录数据。

|---Block 1---|---Block 2---|---Block 3---|---Block 4---|---Block N---|

  1. Block No(4 bytes)
  2. Data Length(2 bytes)
  3. First Rec Group(2 bytes)
  4. CheckPoint No(4 bytes)
  5. LSN 100, Log Data
  6. LSN 289, Log Data
  7. .... (496 bytes)
  8. Checksum tailer(4 bytes)

header部分四个字段：

事务，LSN与Log Block的关系

了解了Redo Log的结构，下面从一个事务的commit开始分析，看事务和对应的Redo Log之间的关联关系。假设一个事务代码如下:

start transaction
    update row1 TableA
    delete row1 TableA
    insert row2 TableB
commit

其产生的日志，我们如下：


逻辑事务 -> update row1 TableA ->  Page 1(Mtr 1) -> 第一部分日志 -> LSN 268
逻辑事务 -> delete row1 TableA -> Page 1(Mtr 1) -> 第一部分日志 -> LSN 268
逻辑事务 -> insert row2 TableB -> Page 2(Mtr2) -> 第二部分日志 -> LSN 550

|---Block 1(512 bytes, 0 - 511)(LSN 268)---|---Block 2(512 bytes, 512 - 1023)(LSN 550)---|---Block 3---|---Block 4---|---Block N---|

SQL层乃至应用层所说的事务都是逻辑事务，具体的底层实现是“物理事务”，也叫做Mini Transaction(Mtr)。在逻辑层面，事务是三条SQL语句，设计两张表A，B。在物理层面，该事务可能是修改了两个Page，Page 1和Page 2，也可能更多Page，每个Page的修改对应一个Mtr。每个Mtr生产一部分日志，生成一个LSN。

由上示意图，这个逻辑事务产生了两段日志和两个LSN。分别存储到了Block 1和Block 2里，这两段日志可能是连续的，也可能不是连续的（中间插入的可能是其他事务的日志，因为事务并发顺序写日志文件）。所以在实际上，一个逻辑事务对应的日志大概率是不连续的，但一个Mtr对应的日志是连续的，不然就不会由LSN了。

下面展示下两个逻辑事务在磁盘的Redo Log文件中的位置结构，LSN单调递增:

逻辑事务A -> LSN 268 && LSN 550
逻辑事务B -> LSN 382 && LSN 760

|---Block 1(512 bytes, 0 - 511 byte)(LSN 268, LSN 382)---|---Block 2(512 bytes, 512 - 1023 byte)(LSN 550, LSN 760)---|---Block 3---|---Block 4---|---Block N---|

每个一个事务都会有一个唯一的ID，是一个单调递增的整数，每个事务都会关联一个自己的LSN链表，这样就可以通过逻辑的LSN链表拿到这个事务在Redo Log中的文件偏移读取并整合事务的操作日志。记住一点，LSN就是一个Mtr在某个Page上的操作记录数据在Redo Log文件中的字节偏移数。

事务的回滚与崩溃恢复

到这里，不得不提到IBM他们搞出来的经典论文，ARIES，前几节提到过，涉及到事务的RollBack与Recovery。

未提交的事务的日志也在Redo Log中

通过之前的分析，可以看到不同事务的日志在Redo Log中是交叉存在的，这意味着未提交(uncommited)事务也在Redo Log中。因为日志是交叉存在的，没有办法把已提交的（commited）事务的日志和未提交(uncommited)事务的人分开，或者说前者刷到磁盘的Redo Log上，后者没刷。从上面交叉存在的例子中，比如事务A提交了，但是事务B还没有提交，但是事务A中间夹杂了事务B的LSN 382，LSN 382肯定会被连带刷到Redo Log的磁盘上，也就是事务B已经被刷了一部分了。

所以这个是ARIES算法的一个关键点，不管事务有没有提交，其日志都会被记录到Redo Log上。当崩溃后再恢复的时候会把Redo Log重放一遍，提交的事务和未提交的事务都被重放了，从而让数据库恢复到了宕机那一瞬间的状态，这叫做Repeating History。

重放完成后，再把宕机之前未完成的事务找出来。这个就有问题，怎么把宕机之前未完成的事务全部找出来？那么就需要检查点（Check Point）的辅助了，把未完成的事务找出来后，逐一利用Undo Log回滚事务。

把RollBack 转化成 Commit

回滚是把未提交的事务的Redo Log删除吗？ 显然不是，Redo Log是Append only file，记录了就记录了，不应该修改，因为是流式的，有点像BTC的UTXO模型一样的叠加记录。这里是用了一个巧妙的方法，把回滚转化为提交。CQRS的存储层也是类似的思想。

举个例子，Client提交了Rollback，数据库并没有更改之前的数据，而是以相反的方向顺序做反向操作，生成对应的反向操作语句，然后Commit。这是逻辑层面上的回滚，不是物理层的。

start transaction
    update table1 set a = "newvalue"
    delete table2 where xxx = "condition"
    insert table3 values("value")
    rollback
    ...
end transaction

把上面逻辑事务语句反向转化为以下commit为回滚事务：

start transaction
    update table1 set a = "newvalue"
    delete table2 where xxx = "condition"
    insert table3 values("value")

    delete table3 where xxx = "value"
    insert table2 values("condition")
    update table1 set a = oldvalue
    commit
end transaction

以上转化是一个正常的逻辑事务回滚场景，机器正常运行，没有宕机，但是如果宕机，也是一样的，如果宕机，事务执行了一半，在重启和回滚的时候，也并不是删除之前的部分，而是以相反的操作把这个事务补齐对应的那一部分，然后commit。

start transaction
    update table1 set a = "newvalue"
    delete table2 where xxx = "condition"
    ...
    ...
    ...
end transaction

如果只执行了2条语句，那么生成后的commit事务为:

start transaction
    update table1 set a = "newvalue"
    delete table2 where xxx = "condition"

    insert table2 values("condition")
    update table1 set a = oldvalue
    commit
end transaction

这样一来，事务的回滚就简化了些，不需要修改之前的数据，也不需要改Redo Log。相当于没有了“回滚”，全部都是commit。对于Redo Log来说，就是不断低顺序写append。这种逆向操作的SQL语句对应到Redo Log里面叫做Compensation Log Record（CLR），会和正常操作的SQL的Log区分开。

ARIES恢复算法

本质就是处理未commit的事务（在进行中的事务）当在宕机的时候，处理这些事务的回滚的算法。

该算法分为3个阶段：

  1. 阶段1： 分析阶段

分析阶段要解决两个核心问题。

第一，确定哪些数据页是脏页，为阶段2的Redo做准备（确定哪些事务被提交，但是未被刷盘）。发生宕机时，虽然被提交的事务已经提交了，但是只是Redo Log在磁盘上，其对应的数据Page是否已经刷到磁盘不得而知。如何找出从CheckPoint到crash之前，所有未被刷盘的Page呢？

第二， 确定哪些事务未提交，为阶段3的Undo做准备。未提交的事务的日志也写入了Redo Log，但是只是事务的一部分日志在Redo Log中，因为Redo Log也不是随时都在刷盘的。如何判断这些未提交的事务，然后对其进行回滚呢？

这就要谈到ARIES的CheckPoint机制。CheckPoint是每个一段时间对内存中的数据拍一个“快照”，或者说把内存中的数据“一次性”地刷到磁盘上。但实际做不到！因为在把内存中所有的脏页往磁盘上刷的时候，数据库可能还在不断地接受客户端的请求，这些脏页一直在更新。除非把系统阻塞住，不再接受请求，这时内存中的Redo Log也不再增长，然后一次性地把所有脏页刷到磁盘中，这叫Sharp Checkpoint。

但是Sharp CheckPoint的应用场景很窄，因为这降低了系统的可用性，系统不应该停下来，所以用的更多的是Fuzzy CheckPoint，具体怎么做？

在内存中，维护了两个关键的表：活跃事务表和脏页表。

活跃事务表示当前所有未提交事务的集合，每个事务维护了一个关键变量lastLSN，是该事务产生的日志中最后一条日志的LSN。（两个字段：tx_id 和 lastLSN）。

脏页表示当前所有未刷盘到磁盘上的Page的集合（包括已提交和未提交事务），recoveryLSN是导致该Page为脏页的最早的LSN。比如一个Page本来是clean的（内存和磁盘上数据一致），然后事务1修改了它，对应的LSN是LSN1。之后事务2，事务3又修改了它，对应的LSN分别是LSN2,LSN3，这里的recoveryLSN取的就是LSN1（两个字段：page_no和recoveryLSN）

所谓的Fuzzy Checkpoint，就是对这两个关键表做了一个Checkpoint，而不是对数据本身做Checkpoint。这点非常重要，因为Page本身很多，数据量大，做快照刷盘压力大，但这两张表记录的全是ID，数据量小，容易做快照。

所以，每一次Fuzzy Checkpoint，就把两个表的数据生成一个快照，形成一条Checkpoint日志，记入Redo Log。

基于这两个关键表的Checkpoint，可以求两个问题了：

找到最近一次（lastest）在Redo Log中的Checkpoint，查看这个检查点在哪些事务的区间内（通过活跃事务表拿到），先暂时把这些事务初始化纳入到一个未提交的事务集合A中，从检查点开始，遍历Redo Log到末尾（也就是crash点）。

在遍历的过程中，如果有遇到某个事务的结束符，那么就将这个事务从从集合A中删除，如果遇到某个事务的开始符，就把这个事务加入到集合A中，最终直到末尾。

找到最近一次（latest）在Redo Log中的Checkpoint，查看这个检查点有哪些脏页（通过脏页表拿到），把脏页表的page项初始化到脏页集合B中，从检查点开始遍历到Redo Log末尾，一旦遇到Redo Log操作的是新Page（集合B中找不到），就把它加入脏页集合，注意了，这样的遍历算法，只会让集合B只增不减，这是与之前的集合A不一样的地方，当然可能有一种特例，就是一些脏页其实已经不是脏页了，但是暂时认为它是脏页也没关系，因为Redo Log是核心是不可变数据结构的重放，是幂等的。

  1. 阶段2：进行Redo

假设之前在分析阶段得到的脏页集合是集合B，那么在这个集合B中，可能都是真的脏页，也有可能是已经刷盘的脏页，不过都没关系，取集合中所有脏页的recoveryLSN的最小值min(recoveryLSN,....)，得到firstLSN。从firstLSN遍历Redo Log到末尾，把每条Redo Log对应的Page全部重新刷一次磁盘。

关键如何做到幂等？磁盘上的每一个Page有一个关键字段：pageLSN。这个LSN记录的是这个Page刷盘时最后一次修改它的日志对应的LSN。如果重放日志时，日志的LSN < pageLSN, 则不修改日志对应的Page，略过此条日志。

比如某个Page被多个事务先后修改了三次，在Redo Log的时间线上，分别对应LSN为600， 900， 1000。当前内存中，该Page的pageLSN就是1000，因为还没有来得及刷盘，所以磁盘中的该Page的pageLSN是900。现在，宕机重启，所以从firstLSN，也就是LSN=600的地方开始重放，从磁盘读取出来的LSN为600， 900，都小于等于900，所以600 对应的两一条日志被略过，900对应的修改就会重做一遍，作用到该Page上。

这点与TCP接收端对数据包的判重差不多，对发送的数据包从小到大有一个编号（seq number），接收方一方发现收到的编号比之前的还小，就skip掉。

Redo完成后，就保证了所有的脏页都成功地写入到了磁盘，干净页也有可能重新写一次，这点是没关系的。

  1. 阶段3：进行Undo

在阶段1的时候，已经找到了未提交事务的集合A。从最后一条日志逆向遍历，因为每条日志都有一个prevLSN字段，所以可以沿着每个事务各自的日志链一直回溯，最终到某个事务的第一条日志

所谓的Undo，是指每遇到一条属于某事务的Log，就生成一条逆向的SQL语句来执行，其执行对应的Redo Log是之前提到的CLR（早已经被写入进Redo Log）。

要生成逆向的SQL语句，需要记录对应的历史版本数据。这点稍后说明。

Redo的起点位置与Undo的起点位置没有必然的先后关系，因为Redo的起点对应的是所有脏页的最小LSN，Undo对应的是所有未提交事务的起始LSN，两者不是一个概念。

在进行Undo操作的时候，还可能会遇到一个问题，回滚到一半，宕机重启，需要再回滚，要进行“回滚的回滚”。

假设，要回滚一个未提交的事务T，其有三条日志LSN，分别是600， 900， 1000.第一次重启宕机，首先对LSN=1000进行回滚，比如生成对应的LSN=1200的日志，这条日志里会有一个字段叫UndoNxtLSN，记录的是其对应的被回滚的日志的前一条日志（LSN=900）。这样当再一次宕机重启时，遇到LSN=1200的CLR，首先会忽略这条日志，然后看到UndoNxtLSN=900， 会直接定位到LSN=900的日志，为其生成对应的CLR日志LSN=1600，然后继续回滚， LSN=1700的CLR日志，回滚的是LSN=600.

这样以来，不管出现几次宕机，重启后最终都能保证回滚日志和之前的日志一一对应，不会出现“回滚嵌套”问题。

到此为止，已经对事务的原子性（A）和持久性（D）有了一个大概的了解。后面会讨论I的实现，再次对Redo Log做一个总结：

Undo Log

Undo Log 是否一定需要

说到Undo Log，很多人想到的只是“事务回滚”。事务回滚有四种场景：

对于这四种场景，ARIES算法都兼顾到了，并没有区别，除了ARIES算法，是否还有其他的方法可以做事务回滚，或者说，Undo Log真的需要吗？

回滚就是取消已经执行的操作，无论是物理上还是逻辑上，达到目的即可。假设Page的数据都在内存里，每个事务执行，都只在内存中修改数据，必须等到事务Commit之后，再写Redo Log，再把Page数据刷盘。在这种策略下，不需要Undo Log也可以实现，这种策略直接用了内存断电消失的特性，磁盘上存储的肯定都是已提交的数据，宕机重启，内存中还未完成的事务自然一笔勾销了。简而言之就是，未提交的事务不会进入Redo Log，全部在内存里！InnoDB的是未提交的事务也会进入Redo Log。注意，这两种策略完全不一样！好像后者这样的策略更简单无脑啊，为什么基本不常用呢？

把这个展开就是4种Page刷盘的策略：

先来说下Force， No Force， Steal ， No Steal的意思

Force是指已经提交的事务必须强制写入磁盘，No force是指已经提交的事务可以保留在内存里，暂时不用写入磁盘。Steal是指未提交的事务也能写入，如果事务需要回滚，再更改磁盘上的数据。No Steal是指未提交的事务不能写入磁盘，只能在内存中操作，等到事务提交完，再一次性写入磁盘。

策略四非常灵活，配置不得当的话，可能会造成事务丢失，在这种策略下，为了实现事务的AD属性，才有了如此复杂的Redo Log和Undo Log机制，也才有了ARIES算法，一切都是为了工业界的可行。

Undo Log之MVCC

Undo Log除了事务的回滚，还有两个核心作用：

在传统的多线程中，并发读写的策略一般是3种：

以上三种策略并发度越来越高，InnoDB就是采用了CoW的思想，是在Undo Log里实现的。每个事务修改记录之前，都会先把该记录拷贝一份出来，拷贝出来的这个备份就存在Undo Log里。因为事务又唯一的编号ID，ID从小到大递增，每修改一次，就是一个新的版本，类似git历史，因此Undo Log维护了数据的从旧到新的每一个版本，每个版本之间的记录通过链表串联。

也正是因为每条记录都有多个版本，才比较容易实现事务ACID中的I隔离性，事务要并发，多个事务要读写同一条记录，为了实现隔离级别。就不能让事务读取到正在修改的数据，只能读取历史版本。

也正是因为有了MVCC这种特性，通常select语句都是不加锁的，读取的全是数据的历史版本，支撑高并发查询。这种读，专业叫“快照读”(snapshot read)，与之对应的是“当前读”

以下是快照读与当前读对应的SQL语句：

Undo Log不是Log

了解了Undo Log之后，接下来进一步看Undo Log的结构。其实Undo Log比较有误导性，严格来说它不是Log，而是数据。为什么？

对于insert记录，没有历史版本数据，因此insert的Undo Log只记录了该记录的主键ID，当事务commit后，该Undo Log就可以删除了。

对于update，delete记录，因为MVCC的存在，其历史版本数据可能还被当前未提交的其他事务所引用，一旦未提交的事务提交了，其对应的Undo Log就可以删除了。

而对于update delete，由MVCC控制，所以Undo Log是类似于通过指针串联起来的last data -> ver 3 data -> ver 2 data -> ver 1 data。 每个节点记录对应的修改事务的tx id。别说，真是大道归一，区块链，git版本控制，DDD中的event sourcing都有这样的思想，只是解决的问题不在一个层面而已。

Undo Log与Redo Log的联系

Undo Log本身也要写入磁盘，但一个事务修改多条记录，会产生多条Undo Log，不可能同步写入磁盘，所以遇到了开始说到WAL时的问题。如何解决Undo Log需要多次写入磁盘的性能问题？

Redo Log记录的是对数据的修改，凡是对数据的修改，都必须记入Redo Log。可能把Undo Log当作数据，在内存中记录Undo Log，异步刷盘，宕机重启时，用Redo Log恢复Undo Log。

比如用一个事务区间来举例：

start transaction
  update Table A row1
  delete Table A  row2
  insert Table B  row3
commit

那么把Undo Log和Redo Log加进去，大概是这样写的日志：

start transaction
  // 写Undo Log1： 备份row1行数据（update）
  update Table A row1
  // 再写Redo Log1
  // 写Undo Log2： 备份row2行数据(insert),因为Undo是delete的逆向操作
  delete Table A row2
  // 写Redo Log2
  // 写Undo Log3：该row3行数据的主键ID（delete），因为Undo是insert的逆向操作
  insert Table B row3
  // 写Redo Log3
commit

在以上实例中，所有Undo Log和Redo Log的写入都可以只写在内存中进行，只要保证commit语句之后Redo Log一定落盘即可，Undo Log可以一直保留在内存中，之后异步刷盘。

各种锁

MVCC解决了快照读和写之间的问题，但是对于写和写之间，当前读和写之间的并发，MVCC就无能为力了，这时就需要用到锁。

在MySQL的官方文档中，介绍了InnoDB的7种锁：

这种分类方法比较迷惑，因为他们不是正交的，比如记录锁可能是共享锁也可能是排它锁。间隙锁也可能是共享锁或者排它锁。

  1. 表（S和X锁）， 行（S和X锁）

共享锁和排他锁是读写锁的另一种说法，共享锁即“读锁”，读读之间并发。排他锁就是“写锁”，读写和写写不能并发。InnoDB通常加锁的粒度是行，所以有对应的行共享锁，行排他锁，但是有些场景会在表的粒度加锁，比如DDL语句（ALTER， DROP语句什么的）

  1. 意向锁（IS锁，IX锁）

有了之前提到的两把锁，为什么还有意向锁呢？假设事务A给表中的某一行记录加了一把行级排他锁，现在事务B由于DDL语句要给整张表加表级排他锁，事务B要怎么处理？显然事务B加锁不会成功，因为表中的某一行正在被事务A修改中，事务B一定要做出这个判断，它需要遍历表中的每一行，看是否某行被加了行级排他锁，只要发现有行级排他锁，就意味着整个表加了表排他锁。

但是！这样判断的效率太低了，无法实用，而意向锁就是为了解决这个锁判断效率问题产生的，意向锁是专门加在表上，在行上没有意向锁，意向锁实际上是表（S,X锁）和行锁（S，X锁）之间的桥梁，通过意向锁加快表和行之间的判断。

举个例子：事务A要给某张表加入一个意向S锁，就暗示接下来要给表中的某一行加S锁。事务A要给某张表加入一个意向X锁，就暗示接下来要给表中某一行加X锁。反过来说就是，一个事务要给表中的某一行加S锁，那么它首先必须先获得这张表的IS锁。行X锁同理！

所以，IX锁，IS锁之间都不互斥，可以并发获得。IX锁，IS锁只是和表级的S和X锁互斥。

  1. 自增锁

它是一种表级锁，专门针对AUTO_INCREMENT的列。为什么需要这种类型的锁？先看以下事务：

start_transaction
    insert table1 values(xxx,xxx,xx)
    insert table1 values(xx, xx, xx)
    select xxx from table1 where xxx
commit

想象一下一上事务处于并发状态，假设表table1中某一列是自增的，连续insert两条记录，再select出来，在同一个事务内自增的一列取值应该是连续的，比如第一次insert，自增列的取值是6，第二次insert应该是7.如果不加入自增锁，另外的并发事务可能会在这两条insert中间插入一条记录，那么第二次的insert可能就是8，select出来是8当然明显不对，不符合AUTO_INCREMENT原则。

  1. 间隙锁，临键锁和插入意向锁

间隙锁的各种算法非常复杂，是否加锁和事务隔离级别密切相关，所以可能要借助分析工具来查看。

BinLog与主从复制

BinLog与Redo Log的主要差异

在MySQL中，Redo Log是记录事务的执行日志，Binlog也记录日志，但是它们两要非常大的差别。首先MySQL是支持多存储引擎的数据库，InnoDB只是其中一种（最重要的一种）。Redo Log和Undo Log都是存储引擎里面实现的机制，但是Binlog却是MySQL层独有的机制。

不同于Redo 和Undo Log用来实现事务，Binlog的主要用途就是做主从复制，如果是单机，没有主从复制，可以不打开Binlog。当然，在互联网应用中，Binlog有了第二个用途：一个应用进程把自己伪装成Slave，监听Master的Binlog，然后把数据库的变更以消息的形式推送出来，业务系统可以消费消息，执行对应的业务逻辑，比如更新缓存什么的，或者同步数据到ElasticSearch之类的异构数据库中。阿里开源的Canal和国外的Databus都是这样的中间件。

与Redo Log一样，Binlog也有自己的刷盘策略，由参数sync_binlog控制，0就是事务提交后不主动刷盘，依靠操作系统自身的刷盘机制可能会丢失数据。1是每提交一个事务，刷一次盘。n是每提交n个事务刷一次盘。

显然0和n都不安全。为了不丢失数据，一般都建议双1保证，就是sync_binlog和innodb_flush_log_at_trx_commit的值都取为1。当然这个东西也看业务类型，看你数据的重要程度，有一些数据丢失一部分也可以，金融相关的数据就不能这样做了。

Diff RedoLog Binlog
日志格式 物理 逻辑
同一个事务的日志是否连续 否 是
是否可以并发写入 是 否
未提交的事务日志是否写入 是 否
已回滚的事务日志是否写入 是 否

从上表可以看出来，Binlog比Redo Log要简单的多，在不宕机的情况下，未提交的事务，回滚事务都不会写入Binlog。（宕机情况后面再分析）

同时，Binlog的日志是连续线性串行的，这样会造成一个问题，Binlog全局只有一份，任何表的事务都会排序进入这里，每个事务都需要串行写入，这里性能上有问题。因此在，MySQL 5.6的Group Commit之前，各类第三方都在优化这个问题。Group Commit的思路也简单，虽然从逻辑上看Binlog必须串行地写入，但是不需要提交一个事务刷一次盘，而是把事务的提交和刷盘放到不同的线程里，刷盘时可以对多个已经提交的事务同时刷盘，串行还是串行，但是批量化了。

内部的“分布式事务”（内部XA） - BinLog与Redo Log的一致性问题

一个事务既要写Binlog，也要写Redo Log，如何保证两份日志文件的数据的原子性？这涉及到一个双文件的双写一致性问题，一个写成功，写另一个的时候发生宕机，重启如何处理？

在讨论这个问题之前，先说一下Binlog自身写入的原子性问题：Binlog刷盘到一半，还没有返回，出现宕机了。这个问题和之前的Redo Log的写入原子性是同样的问题，都是写文件，都是通过类似于Checksum的办法，或者BinLog中有结束标记，来判断出这是部分的，不完整的BinLog，把最后一段截断掉。对于数据库的Client来说，此时宕机，事务肯定是没有成功提交的，所以截掉也没有问题（先写日志，再写数据）。

那这两个不同的日志数据如何保证一致性呢？这个问题有点类似分布式事务，分布式事务无非就是在不同的机器节点上写不同的文件，现在只是这不同的文件在一个机器上了，可以几乎近似于分布式的事务的问题。都会产生不一致。所以如果熟悉分布式事务提交原理的，应该就知道两阶段提交（2 Phase Commit），对，这里也是用2PC。

下面就详细说一下这里的2PC的具体细节做法：

2PC一个显著特点就是，分段完成任务，当然3PC也是一样的。在Prepare阶段就把99%的工作做完了，就等最后一阶段的收尾，所以在第二阶段只要不宕机，就可以提交成功，但是如果发生宕机，如何恢复？

既然要维护Binlog和Redo Log这两个数据文件的一致性，那么从逻辑上看，肯定要以其中一个数据文件为基准，也就是向谁“看齐”的问题。

从以上的内部XA来看，在这里，显然是以Binlog为基准，让Redo Log向Binlog靠拢，也就是让Redo Log跟Binlog保持一致：

三种主从复制方式

MySQL支持三种主从复制方式：

这样可以看出，似乎半同步机制是最好的，确实是，但是它是不是就不丢数据了呢？不是的，半同步复制为了系统的可用性，有可能会退化成异步复制。因为Master不可能无限等待Slave，当超过某个时间，Slave还没有回复ACK时，Master就会切换为异步复制。参数rpl_semi_sync_master_wait_slave_count可以设置在半同步模式下，需要等待几个Slave的ACK，才认为事务提交成功。默认是1。

所以这样来看，除了同步复制，都可能在主从切换的时候丢数据，数据Commit了，但是在新的Master上找不到了！业务上一般的做法是牺牲一致性来换取可用性，就是用半同步复制将就着用吧，在主从切换的时候，忍受少量的数据丢失（最好是同机房），后续人工介入修复。

但是如果主从复制的延迟太大，切换到Slave，丢失数据太多，也难以接受。为了降低主从复制的延迟，MySQL的并行复制应运而生，这个技术在跨机房的情况下，尤其必要！

如果还想深入，可以参考一个数据库内核从业人员的文章，怎么保证主从一致，当然，有点标题党了，实质是Master必须进行“双一”设置，从库非“双一”：《MySQL如何在非“双一”时保证数据不丢失？》。 当然，根据评论，MySQL在MGR模式（MySQL 5.7.17）下是可以做到Master不用“双一”，MGR就是解决异步和半同步复制丢失数据的问题的，这是MySQL的一个整体高可用方案。

注意：以上提到的都是MySQL非MGR模式下的。

并行复制

并行复制是为了尽可能降低主从复制延迟，传统的主从复制原理大概分两个阶段：

可见传统的复制过程，无论Log的传输还是回放过程都是单线程的。而并行复制，就是把回放阶段并行化了，传输过程还是单线程的，为什么传输不用多线程？多线程传输还要重新排序和重组，复杂度高，可能得不偿失。

所以，所谓的并行复制不如说并行回放，其难点在于事务的并行提交。Binlog本身是全局一份的，同一个MySQL的实例，不同库，不同表的事务都在Binlog里面串行排列，并行回放就是一次性地从RelayLog中拿出多个事务，并行执行。这就涉及到了什么样的事务可以并行，什么不可以。就是检查事务有没有修改相同的数据。这里非常复杂。比如有commit_id的概念，id相同意味着可以并发，不同也不意味着不可以并发。

这里复杂，不多说了。

EOF

Lumia1020 commented 4 years ago

非常棒的文章

imchao9 commented 1 year ago

非常棒的文章！