CMU15445-05-Bufferpool

DBMS的目标（时空控制角度)

1. 空间控制

2. 1. 空间控制的目标是使经常一起使用的页面在磁盘上物理上尽可能靠近。

3. 时间控制

4. 1. 何时将页面读入内存以及何时将其写入磁盘。时间控制旨在最大限度地减少从磁盘读取数据的暂停次数。

Lock vs. Latches

1. Lock

2. 1. 锁是一种更高级别的逻辑原语，用于保护数据库的内容（例如元组、表、数据库）免受其他事务的影响。事务将在其整个期间保持锁定。数据库系统可以向用户公开在运行查询时持有的锁。锁需要能够回滚更改。

3. Latches

4. 1. 闩锁是一种低级保护原语，DBMS用于其内部数据结构（例如哈希表、内存区域）中的关键部分。闩锁仅在操作期间保持。闩锁不需要能够回滚更改。

Buffer Pool

buffer pool是从磁盘读取的一个page缓存

它本质上是在数据库内部分配的一个大内存区域，用于存储从磁盘获取的pages。

页面置换算法

内存的大小有限，不可能将所有磁盘文件都加载到内存中，当buffer pool满了之后，再想从磁盘读页面的时候就需要将已经缓存到buffer pool的页面踢出。那选择将哪些页面踢出就很讲究了，核心目标就是尽可能的cache命中，选择踢出哪些页面的策略就叫做页面置换算法。

• • 有哪些页面置换算法？
    LRU：踢出最久没有使用过的页面
    CLOCK：踢出较久没有使用过的页面
  • LRU怎么实现？
    双向链表，每次使用一个页面就将这个页面插入到链表的头部，每次都淘汰链表尾部的页面。可以加一个hash table，用于以O(1)的时间复杂度查找cache是否命中
  • LRU有什么问题？
    最近使用的页面真的之后更可能使用到吗？
    Sequential flooding：比如一次scan需要读很多页面，这些页面基本都只用这一次，但是会把很多“热数据页”挤出buffer pool。