1. 概述

对于研发人员来讲，主要关注mysql的索引、SQL优化、事务、锁、分库分表，参数调优一般是DBA干的活。

2. MySQL的架构

3. 存储引擎

3.1 概述

研究记录怎么存储，怎么组织数据。

3.2 Page页

mysql的数据存在哪里？mysql的数据存储在磁盘中。数据是存储在一个个的Page里面的，Page是mysql的一个存储单元，是内外存交换的基本单元，每个Page大小16k。Page可以当做是一个大的数据结构。Page是加载到内存中使用的，mysql数据加载的单位是Page。下面是一个Page的示意图。
Page Header：页头。记录一些统计信息，56字节。包含页的左右兄弟指针、页空间使用情况等。所有的Page构成一个双向链表。
虚记录：一个Page中存储的记录在最小虚记录和最大虚记录之间。
最大虚记录：比页内最大主键还大；最小虚记录：比页内最小主键还小；
记录堆：存放记录。分为有效记录和已删除记录两种。所有被删除的记录（上图蓝色）会被管理起来，被删除的记录被自由空间链表串起来。自由空间链表就是已删除记录构成的链表。
未分配空间：Page中未使用的存储空间，插入新记录就往里面放。开始时一个Page都是未分配空间没有记录堆，随着记录的写入，不断产生记录堆。
Slot区：（上图白色部分）和mysql页内查找有关。（见下文【页内查找】）
Page Tailer：尾页。页面的最后部分，主要存储页面的校验信息，8字节。

3.2 页内记录维护

3.2.1 innodb索引的数据结构

innodb索引数据结构简图1
innodb索引数据结构简图2

注意数据页（叶子节点）和索引页（非叶子节点）都是双向链表。
innodb索引叶子节点数据结构简图
页内查找简图

页与页之间是双向链表，页内是单向链表

3.2.2 顺序保证

问题：数据的存储是按照主键顺序。那么这个顺序是如何保证的？物理有序？逻辑有序？
什么是物理有序：每个相邻元素物理地址连续。例如数组。优点是查询快，例如使用二分查找。缺点是增删慢，例如新增元素需要移动后面所有元素。
什么是逻辑有序：元素之间内存地址不连续。例如链表。增删快；查询慢，只能遍历。
显然mysql是逻辑有序。那么mysql的查询只能遍历吗？肯定不是，那么mysql的解决方案是什么？见【页内查找】

3.2.3 插入策略

研究的是如何高效利用Page空间。
优先使用自由空间链表，再使用未分配空间。 插入数据时先找自由空间链表，如果自由空间链表有节点，就将数据存进去；如果自由空间链表没有节点，就在未分配空间中申请一块区域将数据存进去。
记录有可能放不进去。例如自由空间链表最大的节点是1k，但是新插入的这条数据2k。如果自由空间链表中节点存不下欲插入的数据，就在未分配空间中申请一块空间将数据存储进去。
有可能存在磁盘空洞（磁盘碎片）。例如自由空间链表最小的节点是1k，但是新插入的这条数据是0.9k，那么剩下的0.1k空间就几乎不会被用到了。
所以说，数据库用久了总会存在磁盘碎片，需要整理磁盘，如果不整理，数据库性能就会下降。怎么整理：一主一从，删除从库，从库重新从主库拉数据，从库拉完之后删除主库，主库再从从库中拉取数据（很操蛋但是有效的方案）。

3.2.4 页内查找

上面说过，页之间双向链表，页内单向链表。
链表只能遍历，但是作为数据库，查询不能只遍历，尤其针对读多写少的业务，mysql对于查找有一套优化方案。优化方案关键在于Slot区域，使用的数据结构是跳表。使用的查询算法是二分查找+遍历。
- 红框部分是Slot区，这是一块连续的空间，一个Slot是8字节。每个slot指向链表中的一个节点，第一个slot指向链表头，也就是最小虚记录，最后一个slot指向链表尾，也就是最大虚记录。这样相当于将Page链表拆分成多个子链表。查询记录先在slot中做二分查找，找到slot之后再在子链表中做遍历。上图整体数据结构叫做跳表。

3.3 InnoDB存储引擎的磁盘、内存管理涉及到的技术点

3.3.1 概述

innodb的磁盘内存管理涉及到以下三方面技术
- 预分配内存（Buffer Pool 预分配内存池）
  - Page保存在磁盘，使用必须先加载到内存。在c语言中，使用内存先申请。在数据库中不能这么做，效率低，因此会预先申请一块内存空间以备存储磁盘中加载的Page。
- 数据加载单位（Page是Buffer Pool的最小单位，也是页面加载的最小单位）
  - 以Page为单位加载磁盘数据。即一次io加载一个Page，一次加载16k。
  - 一个Page中有一批记录，一次加载一个Page是为了提高io效率。加载一条记录，如果这条记录是热数据，那么这条记录两边的记录也可能是热数据，那么通过Page一次性加载到内存就提高了io效率。
- 数据内外存交换
  - 内存空间小于磁盘空间，如果内存中已经加载满Page，那么想要加载新的Page如何是好？这就涉及到innodb的内存管理，内存和磁盘的数据交换策略。
数据内外存交换示意图
- 涉及术语
  - Free list：空闲Page组成的链表。
  - Flush list：脏页列表。直译为刷盘列表。
  - Page hash表：维护内存Page和磁盘文件Page的映射关系。
  - LRU：一种数据淘汰算法；用于mysql内存数据淘汰。

3.3.2 预分配内存（内存池）

最简单。先分配一大块内存空间用于装载数据。

3.3.3 数据加载单位（内存页面管理）

怎么管理Page呢？通过页面映射和页面数据管理。
页面映射
- 指的是磁盘中Page和内存中Page的映射关系，就是磁盘中的某个Page该放到内存中的哪个区域。这个映射不是计算出来的，如果是计算出来的，那么磁盘中的某个Page应该放到内存中的哪块区域就固定死了，内存原本就比磁盘小，假设磁盘中有10000个Page，内存只够存放1000个Page，如果一对一映射固定死，那么磁盘中剩余9000个Page永远无法加载到内存，这岂不是操蛋了。所以页面映射的策略是内存哪里有空余，innodb就将磁盘中的Page加载到哪儿，即磁盘和内存的Page映射是动态的。
- 页面映射关系需要维护好。磁盘中Page不仅要写到内存，内存中的Page还会回写到磁盘（例如修改记录时）。
页面数据管理
- 内存中Page如果只是读，就不需要回写到磁盘；如果修改记录，内存中Page就需要回写到磁盘。这些操作就是页面数据管理。

3.3.4 数据内外存交换（数据淘汰）

内存加载满了Page，怎么加载新的Page呢？通过数据淘汰。

3.3.5 页面管理

涉及术语
- 空闲页：预加载内存中未被使用的部分。例如下图中预加载内存中的空白格子。
- 数据页
  - Clean Page：内存中Page和磁盘中Page完全相同。例如下图Page1。
  - Dirty Page (脏页)：内存中Page中有记录被修改，那么该Page需要被刷入磁盘。例如下图Page2。就是内存中发生更新的Page。
对于三种Page的组织管理，就是Innodb要解决的问题之一。

3.3.6 内存管理 – 内存页面淘汰

一般淘汰数据使用LRU，mysql也是。
LRU：淘汰最久未被使用的数据，即热数据保留，冷数据淘汰。
该算法的思想是一个链表头部是热数据，尾部是冷数据，删除尾部数据。实现原理是访问哪个数据，就将该数据放到表头。
从磁盘加载新Page时将内存中LRU链表的尾数据删除，新数据放到链表尾。
注意：如果不小心对mysql做了全表扫描，那么所有的数据都会轮询放到LRU表头，最后LRU中放的肯定是表中最后的数据，热数据就被淘汰了。如何避免这种热数据被淘汰？我可以想到两种思路：
- 访问时间+访问频率（LFU）。LFU是Redis中的。（Redis有使用）
- 两个URL表：将热数据放到第二张LRU表中，让全表扫描发生在第一张LRU表中。（mysql使用）

3.3.7 MySQL的LRU

mysql的数据淘汰策略是LRU。mysql的解决方案使用的是一个LRU链表的冷热分离，可以理解为使用的是两个LRU链表。
页面装载（到内存）以及页面（从内存）淘汰

磁盘中Page装载到内存的步骤：先从free list中找到一个空闲页 => 然后记录磁盘到内存该Page的映射关系 => Page链入LRU_old。
新装载的Page肯定是先到冷数据区，接下来该Page要么被淘汰，要么被移动到热数据区。

Page链入冷数据区从head写入，Page从冷数据区淘汰从tail淘汰。
Page从冷数据区移动到热数据区会写入到热数据区的head，Page从热数据区淘汰会从热数据区tail写入冷数据区的head。

装载Page的时会先去找空闲页，如果没有空闲页，就会先淘汰old尾部的Page => 再将磁盘的Page装载到lod尾部 => 再将尾部的Page移动到old的头。

LRU old中尾部的Page如果正在被读，那么Page中有记录被锁着，此时尾部的Page就不能被淘汰。LRU链的是数据页，那么数据页就包含clean page和dirty page，LRU中所有的dirty page组成一个Flush list。如果LRU old尾部的Page不能淘汰，那么就会从LRU Flush list中将第一个dirty page刷盘并释放，此时这块被释放的内存就可以用来加载新的数据了。这个步骤是：先刷盘（将脏页写回磁盘） => 该页移动到LRU old尾部 => 淘汰LRU（将LRU尾部的Page链到Free list头部）=> 从Free list中找空闲页 => …。上面的步骤中，“页面移动到LRU尾部”是多余的，因为放到尾部的目的是淘汰他，所以在mysql5.2之后该步移除，直接淘汰。
位置移动
- old到new
  - old区冷Page移动到new热数据区的时机：innodb_old_blocks_time参数，代表Page在old区的存活时间，如果old区Page存活时间大于该参数值，就有机会进入new区。
- new到old。热数据里最不热的是冷数据里最热的，所以从new tail移动到old head。
  - new区热数据移动到old冷数据区的移动方式：并不是new tail中的Page移动到old head，而是Midpoint指针的位置左移一Page。
LRU_new的操作
- 链表增删改效率很高，Page有访问就移动到表头貌似很合理。但是mysql中需要考虑锁Lock。移动需要加锁，为了减少加锁次数，mysql的设计思路是减少Page移动次数。这就又涉及到两个参数：freed_page_clock（Buffer Pool 淘汰的Page数）和LRU_new长度的1/4。
- 每发生一次Page淘汰，freed_page_clock的值就会+1，这是一个全局计数器。
- 当前时刻的freed_page_clock - 上次该Page移动到LRU_new header时的freed_page_clock数 > LRU_new 长度的1/4。这时，Page才会移动。