这章我们会重点来讲，dbms 是如何来管理他的内存，使得页在disk 和 内存间切换。

空间控制：
→在磁盘上写入页面的位置。
→目标是将经常使用的页面保持在尽可能靠近磁盘的物理上。

时间控制：
→何时将页面读入内存，以及何时将页面写入磁盘。
→目标是最大限度地减少必须从磁盘读取数据的停顿次数。

meta data 分为2部分，一个是dirty flag， 另外就是pin count

当一个线程在读该页的时候，就会记录下pin count+1。

image.png

当有一个线程需要写page table的时候，需要加一个latch。

image.png

这里我来讲一下 lock 和 latch 的区别，这2个术语是在dbms里的特指。广义上他们是一个东西。但为了区分os的锁，和db的锁。所以在dbms里分为2个词汇。

Lock

•保护数据库逻辑内容免受其他事务的影响
•持有直到事务结束
•需要支持回滚
•保护元组（行），表，索引

Latch

•保护DBMS内部数据结构的关键部分不受其他线程的影响
•持有直到一个操作结束
•不需要支持回滚

page table VS page directory

page directory页面目录是从数据库文件中的页面ID到页面位置的映射。
→必须将所有更改记录在磁盘上以允许DBMS在重新启动时查找。

page table页表是从页面ID到缓冲池帧中页面副本的映射。
→这是内存中的数据结构，不需要存储在磁盘上。

buffer pool

缓冲池是从磁盘读取的页面的内存缓存。 DBMS总是知道得更多（从query plan），所以想要自己管理内存和页面

它是一个由固定大小页面数组组成的内存区域。 每个数组条目称为一个帧（frame）。 当DBMS请求页面时，将精确副本放入其中一个帧中

缓冲池维护的元数据：
•页表：内存中的哈希表，用于跟踪当前在内存中的页面。
•Dirty-flag：当线程修改页面时需要设置（需要回写）。
•（pin-counter)引脚计数器：触摸该页面的线程数。

优化：
•多个缓冲池：DBMS还可以有多个缓冲池用于不同目的。 这有助于减少latch争用并改善局部性

•预取：DBMS还可以通过根据查询计划预先获取页面进行优化。 通常在按顺序访问页面时完成。

image.png

•扫描共享：查询游标可以附加到其他游标并一起扫描页面。

image.png

q2开始的时候,会先和q1一起扫

image.png

缓存替换策略

LRU

最经典的缓存替换策略，最不经常使用的 就会被替换走。
也就是访问时间最旧的那个。

•维护上次访问每个页面的时间戳。
•DBMS选择使用最早的时间戳逐出页面。

时钟

LRU的近似，每页不需要单独的时间戳。
•每个页面都有一个参考位
•访问页面时，设置为1
使用“时钟指针”在循环缓冲区中组织页面
•扫描时检查页面位是否设置为1
•如果是，则设置为零，如果不是，则逐出
•时钟指针记住驱逐之间的位置

image.png

image.png

LRU和时钟替换策略的问题：

•LRU和Clock容易受到顺序泛洪的影响，其中缓冲池的内容由于顺序扫描而被破坏。
•由于顺序泛洪，LRU要替换的那个页面可能很重要。因为没有check 这个page是如何使用的，可能被误杀。

更好的方案：

•LRU-K：考虑最后K个参考的历史

3.1. 原理

LRU-K中的K代表最近使用的次数，因此LRU可以认为是LRU-1。LRU-K的主要目的是为了解决LRU算法“缓存污染”的问题，其核心思想是将“最近使用过1次”的判断标准扩展为“最近使用过K次”。

3.2. 实现

相比LRU，LRU-K需要多维护一个队列，用于记录所有缓存数据被访问的历史。只有当数据的访问次数达到K次的时候，才将数据放入缓存。当需要淘汰数据时，LRU-K会淘汰第K次访问时间距当前时间最大的数据。详细实现如下：

1. 数据第一次被访问，加入到访问历史列表；
2. 如果数据在访问历史列表里后没有达到K次访问，则按照一定规则（FIFO，LRU）淘汰；
3. 当访问历史队列中的数据访问次数达到K次后，将数据索引从历史队列删除，将数据移到缓存队列中，并缓存此数据，缓存队列重新按照时间排序；
4. 缓存数据队列中被再次访问后，重新排序；
5. 需要淘汰数据时，淘汰缓存队列中排在末尾的数据，即：淘汰“倒数第K次访问离现在最久”的数据。

3.3. 分析

LRU-K具有LRU的优点，同时能够避免LRU的缺点，实际应用中LRU-2是综合各种因素后最优的选择，LRU-3或者更大的K值命中率会高，但适应性差，需要大量的数据访问才能将历史访问记录清除掉。

•优先级提示：允许txns告诉缓冲池页面是否重要

•本地化（localization)：根据每个txn /查询选择要逐出的页面

DBMS根据每个txn /查询选择要逐出的页面。 这最大限度地减少了每个查询对缓冲池的污染。
→跟踪查询已访问的页面。
示例：Postgres维护一个专用于查询的小型环形缓冲区。

如何处理脏页

FAST：如果缓冲池中的页面不脏，那么DBMS可以简单地“删除”它。
SLOW：如果页面是脏的，则DBMS必须写回磁盘以确保其更改是持久的。

DBMS可以定期遍历页表并将脏页写入磁盘。
当安全地写入脏页时，DBMS可以逐出页面或者只是取消设置脏标志。
需要注意的是，在写入日志记录之前，我们不会去写脏页

其他缓冲区

出了元祖和索引的缓存之外，还要很多别的缓存区
这些其他内存池可能并不总是由磁盘支持
→ Sorting + Join Buffers
→ Query Caches
→ Maintenance Buffers
→ Log Buffers
→ Dictionary Caches

总结

数据库系统需要实现自己缓存层，而不是复用os的，因为他知道的更多比操作系统。
可以在分配和驱逐上做出更好的决定，同时可以实现pre fetching。