技巧💡
如何管理数据在内存与磁盘之间的移动?
冯诺依曼结构的特性，计算机是无法直接处理硬盘中的数据的，需要先将其加载到内存中。
内存和磁盘的移动，主要有2个方面。
- 空间控制策略通过决定将 pages 写到磁盘的哪个位置，使得常常一起使用的 pages 能离得更近，从而提高 I/O 效率。
- 时间控制策略通过决定何时将 pages 读入内存，写回磁盘，使得读写的次数最小，从而提高 I/O 效率。
概念
frames
DBMS 启动时会使用malloc申请一片内存区域，我们将这段内存区域分成一个个固定大小的chunk并将这块区域划分成大小相同的 pages，为了与 disk pages 区别，通常称为 frames。
当 DBMS 请求一个 disk page 时，它首先需要被复制到 Buffer Pool 的一个 frame 中，且会把从磁盘中读取到的所有page放入到frame中。
磁盘page拷贝到buffer池的frame中，这个顺序是任意的，不一定要与磁盘中page的顺序一致。同时这就是很简单的拷贝，我们暂时不考虑压缩这种问题。这个page在磁盘中是什么样的，在内存中就什么样，没任何改变。同时我们对其他可能需要的page也同样调出到内存中。
pagetable
为了管理bufferpool 中的frames, 需要pagetable进行记录frames在内存的位置，引用数量，是否是脏页等信息。
DBMS 会维护一个 page table，page table所做的事情：
- 负责记录每个 page 在内存中的位置，
- Dirty Flag，这个flag给我我们当我们读取到这个page后，这个page有没有被修改过，甚至还要追踪是谁进行了这项修改。脏页
- 引用计数，记录当前正在使用、正在查询该page的线程数量。如果该page还在被引用的话，我们并不想让它写回到磁盘上。
page Directory与page table 有什么区别呢？💡
page directory是数据库文件中page id 到page位置的映射，我们对page Directory所做的改变必须持久化，所有变更必须记录到磁盘，重启后可以让 DBMS 找的page。
pagetable 是buffer池frame到硬盘page的映射，这不需要保存到磁盘上。是一种在内存中的、临时的映射表，无需在磁盘中备份。不用持久化，我们可以使用hashmap或hashtable实现。但是需要保障线程安全
并发访问？ 加latch
当被请求的 page 不在 page table 中时，DBMS 会先申请一个 latch（lock 的别名），表示该 entry 被占用，然后从 disk 中读取相关 page 到 buffer pool。 在我们想做任何事之前，必须保护pagetable不会被其他人污染或者覆盖。所以在读写之前，都要先在pagetable加latch，如果减少latch竞争呢？可以和HashMap类似的思想，如果有多个pagetable的话，就可以分散latch竞争了。
缓冲池优化
多缓冲池
为什么需要多缓冲池？减少 latch竞争💡
在访问、操作数据前，需要对pagetable进行加锁操作，避免污染或者数据被覆盖。
在多个线程争抢同一个latch的情况，他们会访问同一个page表，这就会导致多核处理器没法完全利用性能。因为关键部分会有争抢。
- mysql可以设置多缓冲池实例。
- 通过record id进行hash，确定哪个bufferpool
- 根据bufferpool中的pagetable,来确定frames的位置。
预读取、mmap
预读取，操作系统就可以帮助我们实现这种预读取处理。用mmap
扫描共享，(搭顺风车)
技巧💡
通俗的理解为搭别人的顺风车。复用从磁盘中获取的数据用于其他查询。这和结果缓存（result caching）效果相同。通俗理解：你办事情，我在结束的地方等你，等你办好，我也用你的结果，然后去办自己的事情。
游标共享：Oracle支持的，基于扫描共享的技术
Buffer Pool Bypass
解决问题: 缓冲池污染，当遇到扫描量非常大的查询时，如果将所需的 pages 从磁盘中一个一个的换入 Buffer Pool，将会造成buffer池的污染，因为这些 pages 通常只使用一次，而它们的进入将导致一些可能在未来更需要的 pages 被移除，因此一些 DBMS 做了相应的优化。
思路：分配一小块内存给那个线程，当他从磁盘中读取page时，不管这个page已经在buffer池中了还是不在，都要放在这一小块另开辟的内存中，当查询完成时就会释放掉这块内存，这样不会污染buffer池。
主流数据库都支持:
操作系统page缓存
数据库系统有缓冲池，操作系统也有硬盘与内存之间的缓存策略，这会导致一份数据（一份磁盘page）分别在操作系统和 DMBS 中的缓冲池被缓存两次。因此大多数 DBMS 都会使用 (O_DIRECT) 来告诉操作系统不要缓存这些数据，Postgresql是主流数据库中唯一使用了操作系统page缓存得数据库。
为什么这样做？
因为我们数据库缓冲池中有一份副本，而操作系统也缓存了一份磁盘page副本，在我们更新数据库缓冲池中的page后，操作系统缓存的那份page就是旧的，这显然是一份多余的数据。作为数据库系统，我们希望自主管理我们的page，不想让操作系统掺和。
另外，不同操作系统的page缓存策略也是不同的，同一种数据库有linux也有Windows版本，为了保证跨操作系统之间的一致性，这也需要数据库自己本身来管理一切。
替换策略
当缓冲池空间不足时，读入新的 pages 之前必然需要 DBMS 从缓冲池中移除一些pages。这与操作系统中的置换算法差不多。
需要注意的是，
替换策略，重点需要处理问题
缓冲池污染
如果写了一些需要全表扫描的查询语句（比如没有建立合适的索引或者没有WHERE子句的查询）。
预读
DBMS，会对页进行预读，这样也带来了一个问题，导致加载的页不一定都是被用到。为了区分哪些是热数据。将冷热页进行分离。预读的页，都放在冷数据区即可。
算法
LRU
最近最少使用。
基本思想就是追踪最后被访问的时间戳，我们仅需去看哪个时间戳最老，将其置换出去即可。
具体实现方面，操作系统页面置换LRU算法提到了使用栈来解决，当然这里也可以使用队列来实现，如果有人读写了这个page就将其从队列中剔除然后放在尾部，头部的page会被一个个换出。
Clock（时钟置换算法，近似LRU)
Clock是LRU的一种近似算法，无需追踪时间戳而是追踪标志位.
最开始，被换入的内存中的page标志位都是0，一旦被访问了就将其标志位置为1。当需要换出时，就像一个钟表一样顺时针或者逆时针旋转，如果发现指向的这个page标志位为1就将它改为0，然后旋转，发现标志位是0的下一个page，就将其换出。
无法解决缓冲池污染问题
解决缓冲池污染,即进阶的替换策略
LRU-K
LRU-K 保存每个 page 的最后 K 次访问时间戳，利用这些时间戳来估计它们下次被访问的时间，通常 K 取 1 就能获得很好的效果。
mysql的bufferpool就是使用这种方法
多缓存池
分散
优先级提示 Priority Hints
有时候 DBMS 知道每个 page 在查询执行过程中的上下文信息，因此它可以根据这些信息判断一个 page 是否重要。
脏页回刷
移除一个 dirty page 的成本要高于移除一般 page，因为前者需要写 disk，后者可以直接 drop，因此 DBMS 在移除 page 的时候也需要考虑到这部分的影响。除了直接在 Replacement Policies 中考虑，有的 DBMS 使用 Background Writing 的方式来处理。它们定期扫描 page table，发现 dirty page 就写入 disk，在 Replacement 发生时就无需考虑脏数据带来的问题。