最近读了一本不错的讲mysql的书MySQL是怎样运行的，借这个契机总结一下自己的InnoDB相关的知识。

MySQL整体架构

关注的第一个问题，数据记录是怎么存储的？

表空间和表

一个数据库对应一个目录

表结构存储

表名.frm

表数据存储

1.使用系统表空间 - 所有数据存储在指定文件(一个或多个)自动扩展大小

2.使用独立表空间 - 为每个表生成“表名.ibd ”文件，ibd文件存储表中的数据和索引

表空间结构(数据文件)

从大到小的逻辑概念是，表空间->段(segment)->区(extent)->页->记录。大家熟知的常识是数据被组织成一颗b+ tree，为了优化单次io的效率，引入了页的概念，io以页为单位。一个表可能有很多页，为了范围扫描的时候尽量是顺序io，引入了区的概念，区里面的页面是连续的。b+ tree的内节点和叶子节点如果混放，也可能会破坏顺序io，所以又引入段的概念，内节点是一个段，叶子节点是一个段。不过还有其他类型的段比如回滚段。

下面图中FSP_HDR描述表空间属性和本组256个区的属性，XDES描述本组256个区的属性，INODE描述段的属性

上面的图是独立表空间的结构，系统表空间的结构和独立表空间基本类似，只不过由于整个MySQL进程只有一个系统表空间，在系统表空间中会额外记录一些有关整个系统信息的页面，所以会比独立表空间多出一些记录这些信息的页面。

段结构

段不对应表空间中某一个连续的物理区域，而是一个逻辑上的概念，由若干个零散的页面以及一些完整的区组成。

上图是段属性描述结构

插入数据的时候需要，段->区->页，寻找一个页来插入记录。为了存储效率减少碎片会把区分成Free, Not Full, Full 几种类型，然后用链表串起来，用于这几个链表定位的基础节点就是上图蓝色部分。段中完整的区之外零散的页面由灰色部分管理，描述的是页面的页号。

区结构

对于16KB的页来说，连续的64个页就是一个区，也就是说一个区默认占用1MB空间大小。不论是系统表空间还是独立表空间，都可以看成是由若干个区组成的，每256个区被划分成一组

对应段里面对区的管理，区被组织成链表所以有List Node结构。Page State Bitmap表示页面是否空闲的状态。

页结构

出于io效率考虑，页是mysql一次io操作的最小单位，而不是记录，页的大小一般是16k。

1.File Header存放checksum，页号，页类型等页的全局信息，最重要的是会存放上一页和下一页的页号这样就组成了b+ tree需要的链表结构

2.Page Header存放页面状态，比如记录数量，还未使用的最小地址，页面在b+ tree中的层级等

3.File Trailer用来做页面完整性校验，保证刷盘时没有出意外

4.Infimum+supremum存放最大最小两条虚拟记录

5.User Records数据记录存入的过程就是不断找Free Space申请空间的过程

每条记录之间也会形成链表结构，依靠的是记录头的next_record字段。

记录删除不是物理删除，否则挪动其它记录代价很大，因此在记录头上有个delete_mask。比较自然的做法是删除的记录会从有效记录的链表中拿掉，被删除的记录也组成一个垃圾链表，新记录插入的时候可以重用。

每条记录在本页中会有一个逻辑位置，是记录头中的heap_no。

数据记录的大致状况如下图

6.Page Directory用来加速页内记录查找。具体做法是把记录按相邻关系分成很多组，每组最后一条数据头部n_owned属性记录该组记录数，并把每组最后一条数据的地址偏移量记录到页目录。查找的时候通过页目录二分查找到记录对应的组，然后再组内顺序查找。

页内部的记录会严格主键自增么？

应该不会，否则不顺序插入时移动的代价太高，应该只有链表上的逻辑顺序。但页面之间的顺序应该会保持。

数据记录行

有多种格式，看一下compact格式的

1.变长字段长度列表描述对应变长列的长度，按列的逆序放置，只存非null列的内容。

2.为了节省空间对null值做特殊处理，null值列表按位图的方式存放。

3.每行数据的最大长度是有限制的，而每个页的大小限制是16k，如果有超大字段导致溢出，会溢出到其他的页，数据行会存一部分数据和一个指向其他地址的指针

关注的第二个问题，记录存储和b+ tree的关系？

B+ Tree索引

在不考虑索引的情况下页和数据记录已经组织成链表结构

加入和数据页类似的目录项页组织成b+ tree之后就变成下面这样，

目录项和数据记录以比较相似的方式组织称目录项页，主要的区别是record_type不同，再者就是没有数据记录里面那么多列。

使用主键进行排序，叶子节点直接存储所有数据列的就是聚簇索引。

用其他列C2进行排序，叶子节点只存储C2+PK两个列的值的b+ tree是二级索引，二级索引查询要多一次回表操作。

存储碎片问题

删除空间重用的过程

1.每当新插入记录时，首先判断PAGE_FREE指向的头节点代表的已删除记录占用的存储空间是否足够容纳这条新插入的记录，如果不可以容纳，就直接向页面中申请新的空间来存储这条记录

2.如果可以容纳，那么直接重用这条已删除记录的存储空间，并且把PAGE_FREE指向垃圾链表中的下一条已删除记。个人理解这一步会造成记录逻辑顺序和物理顺序不同。

3.如果新插入的那条记录占用的存储空间大小小于垃圾链表的头节点占用的存储空间大小，那就意味头节点对应的记录占用的存储空间里有一部分空间用不到，这部分空间就被称之为碎片空间

4.当页面快满时，如果再插入一条记录，此时页面中并不能分配一条完整记录的空间，这时候会首先看一看PAGE_GARBAGE的空间和剩余可利用的空间加起来是不是可以容纳下这条记录，如果可以的话，InnoDB会尝试重新组织页内的记录，重新组织的过程就是先开辟一个临时页面，把页面内的记录依次插入一遍，因为依次插入时并不会产生碎片，之后再把临时页面的内容复制到本页面，这样就可以把那些碎片空间都解放出来（很显然重新组织页面内的记录比较耗费性能）

所以碎片产生原因是删除数据就会导致页（page）中出现空白空间，大量随机的DELETE操作，必然会在数据文件中造成不连续的空白空间。而当插入数据时,这些空白空间则会被利用起来.于是造成了数据的存储位置不连续。物理存储顺序与逻辑上的排序顺序不同,这种就是数据碎片。update操作除了原地的之外，也有可能产生这种问题。

不是说数据记录先存储在内存中的么？

内存存储

所有读写操作都走磁盘io并不经济，所以mysql会有缓存叫做Buffer Pool。

1.如上图，Buffer Pool是一块连续的内存空间用来存储数据页，这些数据页和表空间(文件系统)的数据页应该是一样的。

2.控制块描述对应页的控制信息包括该页所属的表空间编号、页号、缓存页在Buffer Pool中的地址、链表节点信息、一些锁信息以及LSN信息

3.我们需要知道哪些页面是空闲的，哪些页面是脏的需要flush，所以就有了两个链表，这两个链表都是通过控制块存的指针来组成

4.读数据页的时候会先从Buffer Pool里面找，需要一个hash map来快速查找，key是表空间号 + 页号(这也是inno db定位页的统一坐标)，value是缓存页地址

5.Buffer Pool空间有限，所以需要用lru来管理，简单的lru碰到预读和范围扫描这些范围读取的场景都会相当于无效，所以可以对lru分区成old和young，对于范围扫描先加载到old，对于old区访问小于一定时间间隔才到young。对于young区的热数据也不需要每次访问都移动，进一步分区只有较不频繁的分区被访问才移动。

6.可以使用多个Buffer Pool提高多线程性能。

应该有个write ahead log吧？

redo log

redo log就是inno db中的write ahead log，把事务提交是的随机io变成redo log的顺序io+异步刷盘时的批量io。redo log的特点是顺序写，占用空间小主要记录存储表空间ID、页号、偏移量以及需要更新的值。

之前比较naive的想法是记录个sql就行了，但实际上会比较复杂，redo log更像一个前后的状态变更，比如插入一条数据可能会更新多个索引，对于每个索引有可能造成b tree分裂这种情况会更新多个页面。如果纯按物理状态变更的方式来记日志可能会记相当多的信息，比如File Header、Page Header、Page Directory等等部分，所以感觉inno db采用的是物理+逻辑得折中方案，比如下面这个MLOG_COMP_REC_INSERT类型的redo log

向某个索引对应的B+树中插入一条记录的这个过程必须是原子的但又可能涉及到多个页的修改产生多条redo log，这些日志被编成一个组称作一个Mini-Transaction。

redo log也被组织成页的形式，不同的是页的大小是512字节，写入的时候也是先写内存在合适的时机刷盘，在内存的时候也是连续的内存空间被组织成log buffer。并发事务的redo log是可能交替写入的，写入过程可以看下图。

有一个较为重要的属性叫Log Sequence Number(LSN)，代表系统写入的redo日志量的总和，也是当前写入日志的逻辑时间。

undo log

之前一直有疑问为什么需要undo log，如果只是为了回滚事务状态，为啥不能直接用redo log反向操作？现在我理解主要原因是(1)事务能并发，用结构单一的redo log回溯可能复杂度较高，undo log有事务维度的数据结构比较好处理(2)更重要的是需要支持mvcc，所以需要不同的数据结构

数据记录维度

数据记录有几个和undo log相关的字段

1.trx_id，事务id，注意数据记录只有一个事务id字段，意味着唯一占用，对数据记录的操作应该是整个事务内加锁的。之前猜测mysql mvcc遇到写写并发然后类似于乐观锁的方式让一个事务失败是错误的。

2.roll_pointer，数据记录指向undo log的指针。

insert，update，delete在undo log上的表现很不相同，所以要分开看

insert日志结构

insert操作对应的undo操作是删除就好，而删除也只是状态位和链表处理，即使insert过程中产生了页分裂，也不需要把之前的页合并回去。

delete日志结构

delete操作分两个阶段，第一阶段只更新状态位在事务提交阶段才会更新delete链表，如果要回滚只需要考虑第一阶段的影响。

old trx_id,old roll_pointer，关联之前的undo log形成一个链表，方便后面回溯。

update日志结构

update操作分更新主键和不更新主键的情况，不更新主键又根据被更新列的存储空间是否发生变化而不同。(1)如果更新列存储空间不变就可以做就地更新 (2)如果列的大小发生改变就需要先删除(状态位+链表)，再插入 (3)更新主键也是先删除再插入，但插入位置可能不是当前页了

不更新主键的日志结构如下，和delete的undo log类似

更新主键的日志会是两条，TRX_UNDO_DEL_MARK_REC和TRX_UNDO_INSERT_REC，之所以会这样是因为相当于产生了两条记录，两条记录的状态都需要跟踪

MVCC

事务这块有个不完备的总结就是基本都是靠版本号来做可见性控制。我们从一个观察者事务的角度来看mvcc。观察者事务有一个ReaderView的概念，在一个ReaderView里面包含 (1)m_ids 生成reader view时所有活跃的读写事务列表 (2)min_trx_id m_ids中的最小值 (3)max_trx_id 表示生成ReadView时系统中应该分配给下一个事务的id值。(4)creator_trx_id 表示生成该ReadView的事务的事务id，也就是当前观察者的事务id

比如观察者看到的版本链是这样的，

读取记录的时候的过程大约是，

1.顺着版本链由新到旧的方向逐个比较trx_id

2.如果trx_id和观察者事务相同，意味着当前事务做的修改当然可见。

3.如果trx_id< min_trx_id，说明这个修改版本早在当前reader view创建前就提交了所以可见，算是个读已提交的行为。

4.如果trx_id>= max_trx_id，说明修改版本产生在reader view生成之后，这种情况不可见。

5.如果min_trx_id<=trx_id<max_trx_id，这种情况需要比较trx_id和m_ids，如果trx_id在m_ids中，说明创建ReadView时生成该版本的事务还是活跃的，该版本不可以被访问。

6.通过调整创建reader view的策略来达成read commit或者repeatable read隔离级别。read commit在每次读的时候创建reader view而repeatable read仅仅在观察者事务开始的时候创建reader view。

7.再强调一次防止写写冲突是通过事务时间内对记录加锁实现的。

Insert Buffer

1.大量insert的时候主键可能是顺序insert的，但是二级索引并不一定，这样会产生大量随机io。

2.如果二级索引非唯一索引就可以引入insert buffer先缓冲一批二级索引的写入然后在某个时间批量刷盘。

3.不能是唯一索引的原因是唯一索引判断重复需要走二级索引，大量非顺序插入时同样会产生随机io，做insert buffer失去了优化的意义。

4.如果宕机没有同步到二级索引的insert buffer里面的数据恢复需要不少时间。

表连接原理

简单理解表连接就是一个多重for循环

  
for each row in t1 {   #此处表示遍历满足对t1单表查询结果集中的每一条记录
    
    for each row in t2 {   #此处表示对于某条t1表的记录来说，遍历满足对t2单表查询结果集中的每一条记录
    
        for each row in t3 {   #此处表示对于某条t1和t2表的记录组合来说，对t3表进行单表查询
            if row satisfies join conditions, send to client
        }
    }
}

代入到实际点的场景就是对驱动表t1的每条记录去t2表查询符合条件的记录，这样每次访问t2表都会把t2表的数据从磁盘加载到内存，代价相当大。

Block Nested-Loop Join，引入了join buffer，join buffer就是执行连接查询前申请的一块固定大小的内存，先把若干条驱动表结果集中的记录装在这个join buffer中，然后开始扫描被驱动表，每一条被驱动表的记录一次性和join buffer中的多条驱动表记录做匹配，因为匹配的过程都是在内存中完成的，所以这样可以显著减少被驱动表的I/O代价。

总觉得查询计划还是挺神奇的，怎么运作的呢？

查询优化

信息收集

1.统计表的行数，按照一定算法（并不是纯粹随机的）选取几个叶子节点页面，计算每个页面中主键值记录数量，然后计算平均一个页面中主键值的记录数量乘以全部叶子节点的数量就算是该表的n_rows值

2.聚簇索引占用页面数和其它索引占用的页面数，从数据字典里(SYS_INDEXES)找到表的各个索引对应的根页面位置，找到叶子节点和非叶子节点对应的几个链表的头，然后统计对应的区的数量和零散页面的数量。简单说就是可以从数据结构的概要信息中拿到。

子查询优化

1.物化，子查询直观的逻辑是直接执行子查询然后放内存里面，但是有可能遇到内存放不下的情况所以引入了临时表，会根据数据集大小选择内存存储或者磁盘存储，这个过程也可以叫物化。

2.子查询转连接，操作方法可能有子查询的表直接上提进行连接，建立临时表去重再进行连接，对于有大量重复记录的进行松散扫描等等。

运行态

后台线程

1.Master Thread - 核心的后台线程，主要负责将缓冲池中的数据异步刷新到磁盘，保证数据的一致性，包括脏页的刷新、合并插入缓冲（INSERT BUFFER）、UNDO页的回收等

2.IO Thread - InnoDB 1.0版本之前共有4个IOThread，分别是write、read、insert buffer和log IO thread。

3.Purge Thread - 事务被提交后，其所使用的undolog可能不再需要，因此需要PurgeThread来回收已经使用并分配的undo页。

4.Page Cleaner Thread - 是在InnoDB1.2.x版本中引入的。其作用是将之前版本中脏页的刷新操作都放入到单独的线程中来完成。而其目的是为了减轻原MasterThread的工作及对于用户查询线程的阻塞，进一步提高InnoDB存储引擎的性能。

Master Thread

1.0.x版本之前的master thread的主要逻辑如下，后续版本做了优化，主要是之前写死的地方做了灵活优化，把刷脏页的操作分离到其它线程

1.整体逻辑有两个循环，约1秒一次的的循环和10秒一次的循环

2.每秒一次的操作大致有，undo log刷盘，合并insert buffer，刷盘buffer pool 100个脏页，如果没有没用活动会切换到background loop

3.每10秒的操作大致有，刷盘100个脏页，合并至多5个insert buffer，undo log刷盘，删除无用的undo log页，刷盘100个或者10个脏页

4.background loop，如果没有用户活动(数据库空闲时)，删除20个无用的undo页，合并20个insert buffer，不断刷新100个页

Binlog相关

3阶段提交

1.事务提交过程中涉及到redo log，binlog，以及事务状态等多个资源协调，所以很自然的是多阶段提交的过程，但是这个和分布式事务的3pc还是有区别的。

2.简单理解就是1阶段写redo log，2阶段写binlog而且如果2阶段成功一定会进行第3阶段，3阶段写事务状态。

3.可以参考文章MySQL Group commit 并行复制原理

Group Commit

1.目的很简单为了提升io性能，对redo log，binlog刷盘做批量io优化。但同时带来的另外一个优化是在slave端可以做并发复制。

2.每个group内的事务是可以并行的是因为mysql把一个时间点内就绪的事务分成一个group，就绪的事务必然没有资源依赖了，所以也可以判断group内的事务没有互相依赖。依赖判断主要还是基于timestamp来做的，也叫做logical lock。

3.mysql 8.0引入write set机制来判断事务间的依赖，感觉是在判断事务读写记录有没有交集，提供比logical lock更好的并发性。参考Fastest Parallel replication method in MySQL 8

4.可以参考文章 MySQL组提交并行复制原理

Binlog Server

1.可以参考kingbus里面的文档

2.binlog server个人理解主要场景还是在mysql replication体系提供binlog复制

3.本质上说binlog server是一个没有存储引擎的mysql，也类似于mysql配上black hole引擎

4.binlog server延迟比实际mysql小，所以在多级mysql同步体系里面可以解决大延迟的问题

5.binlog server在facebook可以搭配hdfs存储引擎，解决binlog存储时间短占空间的问题

6.binlog server还可以替代从库，因为同步快。然后新主从binlog server追上数据就可以工作

并发优化

参考https://zhuanlan.zhihu.com/p/151397269 以及后面的系列
mysql5.6的问题是对b tree有结构修改，比如update时候分裂，会有整个index级别的X排他锁，阻塞所有读操作，并发度底
mysql8.0引入index级别的sx意向锁不阻塞读，update分裂的时候加index sx锁，并且只在分裂节点和它的parent node加x排他锁。这样不阻塞读，但是单个index多个update分裂无法并发
8.0需要index sx锁是因为b tree搜索路径自顶向下而加锁路径自底向上容易死锁。polar db的优化是去掉index sx锁，b tree node上加一个指向分裂产生的新节点的指针把分裂过程做成两阶段，每阶段只加锁一个节点，中间状态合法(父节点查不到再用分裂指针查一次)。这样就做到了多个smo的并发。
下一个问题是多个并发读都会访问根节点并加S锁，在多核架构下多核S锁会互相invalidate cache line会造成10%-20%的性能损失。这个问题学术界有一些解法，但都不是很完美。

2021年8月22日星期日

InnoDB总结