15445-04-MemoryManagement

一、缓冲池（Buffer Pool）

缓冲池是位于内存与磁盘之间的页面缓存区，用于临时存储数据库页面。
其本质是数据库内部的一块大内存区域，由固定大小的帧（frame）组成。

当数据库请求页面时：

• 若页面已在缓冲池中，则直接访问；
• 若页面不在，则从磁盘读取该页至空闲帧中。

缓冲池一般采用**写回缓存（write-back cache）机制：
被修改的脏页不会立即写回磁盘，而是暂时保留在内存中，等待后台刷新。
这与直写缓存（write-through cache）**不同。

缓冲池常见用途

• 元组存储与索引
• 排序与连接操作缓存
• 查询缓存与字典缓存
• 日志与维护缓冲区

部分结构可直接使用系统内存分配（如 malloc），不一定经过缓冲池管理。

磁盘上维护有页目录（page directory），用于记录页面 ID 与其在文件中的位置映射。
目录在数据库重启后用于恢复定位，通常在内存中也保留一份以减少访问延迟。

缓冲池元数据

缓冲池管理器需要维护多种元数据：

• 页表（Page Table）：
  内存中的哈希表，记录当前驻留在缓冲池中的页面。
  主要包含：
  • 页面 ID → 帧号映射
  • 脏标志（Dirty Flag）
  • 固定计数（Pin / Reference Counter）
  • 访问信息（访问事务、时间等）

若页面的固定计数 > 0，则不可被驱逐；
若所有页均被固定且缓冲池已满，则会触发“内存耗尽”错误。

页表与页目录的区别

名称	存储位置	功能
页目录（Page Directory）	磁盘	记录页面在物理文件中的位置，持久化保存。
页表（Page Table）	内存	记录页面在缓冲池中的帧号映射，仅驻留内存。

---

二、操作系统与数据库系统的区别

锁（Lock）与闩（Latch）

• 锁（Lock）：
  高层逻辑同步机制，用于保护数据库内容（如元组、表等），支持事务回滚，可被用户查询。

• 闩（Latch）：
  低层内部同步原语，用于保护数据库内部结构（如哈希表、内存区域），通常由互斥锁或条件变量实现，不支持回滚，仅在操作期间持有。

为什么不直接使用操作系统的缓存？

如果使用操作系统的页缓存（如 mmap），会带来以下问题：

1. 事务安全性差： 操作系统可能随时刷新脏页；
2. I/O 阻塞： DBMS 无法预知哪些页在内存中，可能因缺页而阻塞；
3. 错误处理困难： 访问无效页可能导致信号错误（如 SIGBUS）；
4. 性能问题： 内核结构竞争、TLB 失效（TLB shootdown）等。

虽然系统调用如 madvise、mlock、msync 能一定程度改善，但管理复杂。
数据库系统通常选择自行管理，以实现：

• 控制脏页写出顺序；
• 更高效的预取策略；
• 自定义替换算法；
• 线程/进程级调度优化。

结论： 操作系统不是数据库的朋友。

---

三、页面替换策略（Buffer Replacement Policies）

当缓冲池空间不足时，DBMS 需要决定驱逐哪一页。
驱逐策略目标包括：正确性、准确性、速度与低元数据开销。
固定页（Pinned Page）不可被驱逐。

一、LRU（最近最少使用）

维护每页最后访问时间戳，驱逐时间最久未访问的页。
可借助队列或链表排序，但维护代价高（尤其是时间戳更新开销大）。

二、CLOCK（时钟算法）

LRU 的近似实现，无需时间戳。
每页有一个引用位（reference bit）：

• 访问页面时置 1；
• 驱逐时，若为 1 → 清零并跳过；若为 0 → 驱逐。
  页面按环形结构组织，指针（clock hand）轮询。

三、LRU 与 CLOCK 的问题

二者容易受到顺序访问污染（Sequential Flooding）：
顺序扫描会快速替换整个缓冲池，使其他查询的页被逐出。

此外，它们不考虑访问频率：
若某页长期频繁访问但近期未访问，也可能被错误驱逐。

四、改进方法

1. LRU-K：
   记录最近 K 次访问时间，计算访问间隔，预测下次访问时间；
   需较大存储开销，并需维护“幽灵缓存”（Ghost Cache）记录最近驱逐页。

2. MySQL LRU-2 近似算法：
   采用两条链表（旧链表与年轻链表）；
   若访问的页在旧链表中，则移入年轻链表；驱逐从旧链表尾部进行。

3. 查询局部化（Localization per Query）：
   每个查询独立选择驱逐页，避免跨查询污染。

4. 优先级提示（Priority Hints）：
   查询根据执行上下文标注页面重要性。

五、ARC（Adaptive Replacement Cache）

由 IBM 研究院提出，结合 LRU 与 LFU 的自适应替换算法。
通过动态调整两种缓存区比例来适应访问模式变化。

• T1（近期访问表）： 最近访问过一次的页。
• T2（频繁访问表）： 至少访问过两次的页。
• 参数 p： 控制“时间局部性（Recency）”与“频率（Frequency）”的权衡。

六、脏页处理（Dirty Pages）

被修改的页需在驱逐前写回磁盘：

• 快速路径（Fast Path）： 非脏页，可直接释放；
• 慢速路径（Slow Path）： 脏页，需写盘同步。

为避免写盘瓶颈，可使用**后台写出（Background Writing）**机制：
周期性扫描页表并刷新脏页，写回成功后可清除脏标志或释放页。

---

四、磁盘 I/O 与操作系统缓存

操作系统与硬件会通过请求重排序与批处理优化磁盘带宽，
但不了解数据库请求的语义与优先级。

数据库 I/O 优先级决策因素

• 顺序 I/O 与随机 I/O
• 前台关键任务与后台任务
• 数据类型（表、索引、日志、临时数据）
• 事务信息
• 用户服务级别（SLA）

由于操作系统不了解这些上下文，常会干扰性能。
多数 DBMS 使用 Direct I/O（O_DIRECT） 绕过 OS 缓存，
避免重复缓存与策略冲突。

例如：PostgreSQL 依赖操作系统缓存，而其他系统多采用直接 I/O。

注意： fsync 默认可能静默忽略错误，并错误地标记页面为“已干净”。

---

总结：
数据库系统通常需要完全掌控自身的内存与磁盘管理。
操作系统的缓存与调度机制在数据库场景下往往低效甚至有害。
因此，现代 DBMS 通过缓冲池管理器独立实现缓存、替换与写出策略，以获得确定性与高性能。

Notes