1. 数据库缓存作用

  1.    介绍数据库系统里哪些module使用了数据库缓存(存储系统buffer pool, 日志系统redo buffer), 和对于这两个系统的意义<br />       在大多数情况下，数据库系统不能直接在进行操作，不能在不将数据放入内存的情况下对它们进行读写。所以需要尽量将常用的数据存储在缓存中来减少因从磁盘读取数据而导致的停顿，方便快速地读取。<br />       在数据库中，存储系统的Buffer pool和日志系统的Redo Log Buffer用到了缓存机制。Buffer pool是数据库内部分配的一个内存区域，用于存储从磁盘读取的页面，通过内存的速度来弥补磁盘速度较慢对数据库性能的影响。Redo Log Buffer用来存储重做日志缓冲，并定时将重做日志缓冲刷新到日志文件。

2. 缓冲池

2.1缓存架构

介绍一下缓冲池大致的数据结构
InnoDB底层采⽤B-tree将数据存储在磁盘上，构成B-tree的原⼦单位为Page，通常每次的IO访问操作都 是以Page为单位进⾏的，倘若每次⽤户的读写请求都直接访问磁盘，这将会带来⾮常⼤的性能开销，因此 需要⼀层缓存来保存就近访问过的Page，以减少直接访问磁盘带来的性能瓶颈，这层缓存在InnoDB中被称为Buffer Pool。Buffer Pool是InnoDB中⾮常重要的模块，⽤户请求所产⽣的数据交互都需要依赖于 Buffer Pool，包括各种CRUD操作。 InnoDB在启动时将⼀块连续的内存⼤⼩划分给Buffer Pool来使⽤，并将其划分为多个Buffer Pool Instance来更好地管理这块内存，每个Instance的⼤⼩都是相等的，通过算法保证⼀个Page只会在⼀个特 定的Instance中，利⽤划分为多个Instance的模式提升了Buffer Pool的并发性能。
2.1.1 Buffer Pool的初始化
在InnoDB启动时，按照srv_buf_pool_instances的数量来并⾏初始化各个Buffer Pool Instance，会将⼀段连续的内存分配给Buffer Pool Instance使⽤，⽽这段连续的内存⼜被划分为多个Chunks，每个chunk 的⼤⼩默认为128M。在每个Buffer Pool Instance中都有包含⾃⼰的锁，mutex，Buffer chunks，各个页，链表等（如下⾯所介绍），每个Instance之间都是独⽴的，⽀持多线程并发访问。
在每个Buffer Pool Instance初始化时，还会初始化三个链表，分别为Free list，LRU List以及Flush List，还有⼀个关键的Hash Table Page Hash，这些数据结构的具体作⽤如下：
• Free List：如其名，Free List中存放的都是未曾使⽤的空闲Page，InnoDB需要Page时从Free List 中获取，如果Free List为空，即没有任何空闲Page，则会从LRU List和Flush List中通过淘汰旧Page 和Flush脏Page来回收Page。在InnoDB初始化时，会将Buffer chunks中的所有Page加⼊到Free List中。
• LRU List：所有从数据⽂件中新读取进来的Page都会缓存在LRU List，并通过LRU策略对这些Page 进⾏管理。LRU List实际划分为Young和Old两个部分，其中Young区保存的是较热的数据，Old区保 存的是刚从数据⽂件中读取出来的数据，如果LRU List的⻓度⼩于512，则不会将其拆分为Young和 Old区。当InnoDB读取Page时，⾸先会从当前Buffer Pool Instance的page_hash查找，并分为三种 情况来处理：
a. 如果在page_hash找到，即Page在LRU List中，则会判断Page是在Old区还是Young区，如果是 在Old区，在读取完Page后会把它添加到Young区的链表头部；
b. 如果在page_hash找到，并且Page在Young区，需要判断Page所在Young区的位置，只有Page处于Young区总⻓度⼤约1/4的位置之后，才会将其添加到Young区的链表头部；
c. 如果未能在page_hash找到，则需要去数据⽂件中读取Page，并将其添加到Old区的头部。
• LRU List采⽤了⾮常精细的LRU淘汰策略来管理Page，并且⽤这些机制避免了频繁对LRU 链表的调 整，提升了访问效率。
• Flush List：所有被修改过且还没来得及被flush到磁盘上的Page，都会被保存在这个链表 中。所有保存在Flush List上的数据都会在LRU List中，但在LRU List中的数据不⼀定都在Flush List 中。在Flush List上的每个Page都会保存其最早修改的lsn，即oldest_modification，虽然⼀个Page 可能被修改多次，但只记录最早的修改。Flush List上的Page会按照其各⾃的oldest_modification进 ⾏降序排序，链表尾部保存oldest_modification最⼩的Page，在需要从Flush List中回收Page时，从 尾部开始回收，这些被回收的Page⼜会被重新加⼊到Free List中去。Flush list会有专⻔的后台线程 Page cleaner线程来进⾏清理，将脏页flush到磁盘，以完成对数据的真正持久化，⽽对应这些脏页数 据修改的Redo，也将可以被清理，同时便于Checkpoint进⾏推进。
· Page Hash：所以在Buffer Pool中的Page都会放在这个Hash Table中，在读取Page时，通过这个 page_hash能直接找到LRU List中的page，避免扫描整个LRU List，极⼤提升了Page的访问效率， 如果Page不在page_hash中，就需要从磁盘读取这个Page了。
2.1.2 Buffer Pool的读写请求处理
当⽤户在客户端发起⼀个CRUD操作时，在InnoDB中都会转化为对应的Page访问，查询对应读请求，⽽增删改则对应写请求，读写请求都需要通过Buffer Pool这⼀层才能真正完成其操作，但两者会有些许不同， 接下来我们会详细讨论⼀下这个过程。
读请求：
1. 根据Space ID和Page NO计算Page在哪个Buffer Pool Instance中
2. 从Page Hash中读取该Page，若读取到直接到第5步，未能读取到，则继续
3. 从磁盘中读取对应的Page
4. 从Free List中获取Free Page，并将磁盘上读取中的数据进⾏填充
5. 如果Page已经在Buffer Pool中，则根据LRU策略调整其在List上的位置，如果是新Page则将其添加到LRU List的Old区
6. 将Page返回给⽤户线程
7. 返回客户端
写请求：
8. 根据Space ID和Page No计算Page在哪个Buffer Pool Instance中
9. 从Page Hash中读取该Page，若读取到直接到第5步，未能读取到，则继续
10. 从磁盘中读取对应的Page
11. 从Free List中获取Free Page，并将磁盘上读取中的数据进⾏填充
12. 如果Page已经在Buffer Pool中，则根据LRU策略调整其在List上的位置，如果是新Page则将其添加 到LRU List的Old区
13. 将Page返回给⽤户线程
14. ⽤户线程对Page进⾏修改，并调整Flush List，如果是已经在Buffer Pool中的Page，需要修改其 new_modification_lsn，如果是新Page，则直接将其添加到Flush List的头部
15. 返回客户端

2.2缓存置换策略（除钉住页之外，参考cmu15-445课程，钉住页参考

(加入一个纲领)
2.2.1 基础策略
2.2.1.1Clock
在CLOCK策略中，每个page都有一个reference bit。在一开始，reference bit都设置为0。当这个page被访问，它的reference bit则设为1。当buffer满了，需要驱逐page时，有一个指针可以检查reference bit：如果该reference bit是1，则将其设为0；如果不是，则驱逐它。
2.2.1.2LRU
LRU策略维护了每个page最后被访问的时间戳。这个时间戳可以存储在一个单独的数据结构中，如队列，以便进行排序和提高效率。DBMS会选择驱逐具有最老时间戳的page。此外，page按排序顺序保存，以减少驱逐时的排序时间。
2.2.2优化策略
2.2.2.1LRU-K
LRU和CLOCK有一点不足：在顺序扫描时可能导致缓冲池的内容被破坏，即顺序扫描时，所以读取到的页面的时间戳可能并不能反映我们真正想要的页面。LRU-K算法可以在一定程度上弥补Clock和LRU算法的不足。其中，K是指对单个page对应缓存数据的访问次数。当访问次数达到K次后，将数据索引从历史队列移到缓存队列。LRU-K算法以时间戳的形式跟踪最后K次访问的历史，并计算访问之间的时间间隔。这个历史记录被用来预测下一次访问一个页面的时间。访问间隔时间最长的page被认为是最近最少被使用的page，会被优先驱逐。
2.2.2.2 高级策略
Localization：DBMS在每个事务/查询的基础上选择要驱逐哪些页面，而不是从全局的角度。这样可以将每个查询对buffer pool的污染降到最低。
Priority Hints：用索引可以得知查询是如何进行扫描以及哪些page被访问，利用这些信息判断该移除哪些page。

2.2.3 对脏页和钉住页的处理
脏页：
要判断哪个page该被移除，有Fast和Slow两种方法。Fast方法是找到一个未被标记为dirty的page，将其移除。Slow方法是，如果page被标记为ditry，那么在该空间重新用于新的page之前，将这个page安全的写回磁盘。在Fast方法和Slow方法之间的权衡是，DBMS可以定期巡视页表，并将脏页写入磁盘。当一个脏页安全写入后，DBMS可以驱逐该页，或者直接解除脏标志。需要注意的是，在脏页的日志记录被写入之前，不要写脏页。
钉住页：钉住页即不能被安全地写回磁盘的页。如果page A内有一个混写指针指向page B，那么page B就是一个被钉住的页，因为假设我们跟踪A中的指针，它指向缓冲区，但原本在缓冲区的B已经被写回磁盘了，此时这个指针就成为悬挂指针。所以将page 写回磁盘之前要进行“解混写“，确保它没有被钉住。

3. 重做日志缓冲（redo log buffer）

3.1重做日志缓冲
和大多数关系型数据库一样，InnoDB记录了对数据文件的物理更改，并保证总是日志先行，也就是所谓的WAL，即在持久化数据文件前，保证之前的重做日志已经写到磁盘。InnoDB存储引擎会将事务执行过程拆分为若干个Mini Transaction（mtr），InnoDB的重做日志都是通过mtr产生的。重做日志用来实现事务的持久性。重做日志缓冲用于存放重做日志信息，其是易失性的。
3.2重做日志缓冲刷新策略
InnoDB首先将重做日志信息放入重做日志缓冲区，然后按一定频率（一般每秒一次）将其刷新到重做日志文件。一般情况下，重做日志缓冲池不需要设置得很大，8MB足以满足绝大部分的应用。在下列三种情况下，重做日志缓冲中的内容会被刷新到磁盘的重做日志文件中：
a.Master Thread每一秒将重做日志缓冲刷新到重做日志文件；
b.每个事务提交时会将重做日志缓冲刷新到重做日志文件；
c.当重做日志缓冲池剩余空间小于1/2时，重做日志缓冲刷新到重做日志文件。
为了确保每次日志都写入重做日志文件，每次将重做日志缓冲写入重做日志文件后，InnoDB存储引擎都需要调用一次fsync操作。fsync的效率取决于磁盘的性能。