Page页分类

Buffer Pool 的底层采用链表数据结构管理Page。在InnoDB访问表记录和索引时会在Page页中缓存，以后使用可以减少磁盘IO操作，提升效率

• Page根据状态可以分为三种类型：
  
  - free page ： 空闲page，未被使用
  - clean page：被使用page，数据没有被修改过
  - dirty page：脏页，被使用page，数据被修改过，页中数据和磁盘的数据产生了不一致

Page页如何管理

针对上面所说的三种page类型，InnoDB通过三种链表结构来维护和管理

1. free list：表示空闲缓冲区，管理free page

   • Buffer Pool的初始化过程中，是先向操作系统申请连续的内存空间，然后把它划分成若干个【控制块&缓冲页】的键值对。
   • free链表是把所有空闲的缓冲页对应的控制块作为一个个的节点放到一个链表中，这个链表便称之为free链表
   • 基节点: free链表中只有一个基节点是不记录缓存页信息(单独申请空间)，它里面就存放了free链表的头节点的地址，尾节点的地址，还有free链表里当前有多少个节点
     
     磁盘加载页的流程:
     • 从free链表中取出一个空闲的控制块（对应缓冲页）
     • 把该缓冲页对应的控制块的信息填上（例如：页所在的表空间、页号之类的信息）
     • 把该缓冲页对应的free链表节点（即：控制块）从链表中移除。表示该缓冲页已经被使用了

   2. flush list：表示需要刷新到磁盘的缓冲区，管理dirty page，内部page按修改时间排序

      • InnoDB引擎为了提高处理效率，在每次修改缓冲页后，并不是立刻把修改刷新到磁盘上，而是在未来的某个时间点进行刷新操作. 所以需要使用到flush链表存储脏页，凡是被修改过的缓冲页对应的控制块都会作为节点加入到flush链表.
      • flush链表的结构与free链表的结构相似
        
        注: 脏页即存在于flush链表，也在LRU链表中，但是两种互不影响，LRU链表负责管理page的可用性和释放，而flush链表负责管理脏页的刷盘操作

   3. lru list：表示正在使用的缓冲区，管理clean page和dirty page，缓冲区以midpoint为基点，前面链表称为new列表区，存放经常访问的数据，占63%；后面的链表称为old列表区，存放使用较少数据，占37%
      普通LRU算法
      LRU = Least Recently Used（最近最少使用）: 就是末尾淘汰法，新数据从链表头部加入，释放空间时从末尾淘汰
      

      • 当要访问某个页时，如果不在Buffer Pool，需要把该页加载到缓冲池,并且把该缓冲页对应的控制
        块作为节点添加到LRU链表的头部。
      • 当要访问某个页时，如果在Buffer Pool中，则直接把该页对应的控制块移动到LRU链表的头部
      • 当需要释放空间时,从最末尾淘汰

      普通LRU链表的优缺点

      • 优点：所有最近使用的数据都在链表表头，最近未使用的数据都在链表表尾,保证热数据能最快被获取到。
      • 缺点
        • 如果发生全表扫描（比如：没有建立合适的索引 or 查询时使用select * 等），则有很大可能将真正的热数据淘汰掉
        • 由于MySQL中存在预读机制，很多预读的页都会被放到LRU链表的表头。如果这些预读的页都没有用到的话，这样，会导致很多尾部的缓冲页很快就会被淘汰。
          

      改进型LRU算法
      改性LRU：链表分为new和old两个部分，加入元素时并不是从表头插入，而是从中间midpoint位置插入(就是说从磁盘中新读出的数据会放在冷数据区的头部)，如果数据很快被访问，那么page就会向new列表头部移动，如果数据没有被访问，会逐步向old尾部移动，等待淘汰
      
      冷数据区的数据页什么时候会被转到到热数据区呢?

      • 如果该数据页在LRU链表中存在时间超过1s，就将其移动到链表头部 ( 链表指的是整个LRU链表)
      • 如果该数据页在LRU链表中存在的时间短于1s，其位置不变(由于全表扫描有一个特点，就是它对某个页的频繁访问总耗时会很短)
      • 1s这个时间是由参数 innodb_old_blocks_time 控制的