SoreyAlter's Blog

Appearance

缓冲管理 ​

复习提纲

1、缓冲区结构、frame/dirty/pin-count等概念的含义*

2、缓冲区置换算法*

3、缓冲区管理器的实现

缓冲区结构 ​

frame的参数

frame是缓冲区的一行，能够存放若干个块（一般就是一对一），缓存换出以frame为单位，读入以块为单位

  • Dirty：Frame中的块是否已经被修改
  • Pin-count：Frame的块的已经被请求并且还未释放的计数 ，即当前的用户数
    • 该标志位主要用于多进程读(不是读 写,因为读写会冲突)，计数大于等于0的frame不能被改写或释放.
    • 该标识位主要用于非抢占的架构,即 各进程(用户)平权,如果可以抢占则对于某些优先级高的请求则可以无视Pin-count标志强制进行改写
  • Others （Latch: 是否加锁）

请求块

  • 目标块不在缓冲区
    • 选择一个frame来置换
    • 若 frame 为脏，写回磁盘
    • 读入包含目标块并增加 Pin-count ，返回对应的地址
  • 目标块在缓冲区中
    • 增加 pin-count并返回地址

释放块

  • 请求者必须释放包含块的frame的pin-count
  • 请求者必须指明块是否被修改过

缓冲区置换算法 ​

  • 只有pin-count = 0 的 frame 可以被置换
  • 置换算法对I/O影响极大，取决于访问模式

理论最优算法

  • OPT 算法（Belady’s算法）
  • 理论上最佳的页面置换算法。它每次都置换以后永远也用不到的 页面，如果没有则淘汰最久以后再用到的页面。
  • OPT算法必须预先知道全部的页面访问序列，而这在实际 DBMS/OS中是无法实现的，因此仅有理论意义。
  • 在实验中作为算法性能上界加以对比

为何不使用 OS 缓冲区管理？

  • DBMS经常能预测访问模式(Access Pattern)
    • 可以使用更专门的缓冲区替换策略
    • 有利于pre-fetch策略的有效使用
  • DBMS需要强制写回磁盘能力（如WAL，写前日志） ，OS的缓冲写回一般通过记录写请求来实 现（来自不同应用），实际的磁盘修改推迟 ，因此不能保证写顺序

LRU ​

image.png

优点

  • 重复访问特定页时，该策略表现较好
  • 只需要O(1)的时间选择被置换的frame

缺点

  • 缓存污染(Sequential flooding)：一次连续访问大量之后不会再重复访问的页面，会把原本的链表全部冲出内存
  • 维护代价大：每次访问都会修改链表，而链表不支持随机访问
  • 如果访问不满足时间局部性，则性能较差
  • 只考虑最近一次访问，不考虑访问频率 —— 导致颠簸

LRU-K ​

如果某个frame的访问次数达到了K次以上，则 应当尽量不置换

  • 维护2个LRU链表
    • 访问次数小于K次的链表
    • 访问次数K次以上的链表
  • 优先按照LRU策略置换 小于K次的链表
  • 保证高频访问的页能够尽 量在buffer中

实验表明 ：K并非越大越好，LRU-2 性能较好

优点：在LRU的基础上考虑了访问频率

缺点：需要额外记录访问次数；K链表上的页面可能后续不再访问，但难以置换出去（老化：每隔一段时间将访问次数减半）

image.png

**LRU-2Q：**与LRU-2类似，不同之处在于访问1次的队列采 用FIFO，而不是LRU

Second-Chance FIFO ​

image.png

  • 相当于每个frame给了两次置换机会（复活一次），避免高频访问但最近一 轮没有被访问的frame被置换出buffer
  • 若被置为1的frame再次被访问，将其访问位重新置为0
  • 每个frame只需要1个额外bit，空间代价很低
  • 缺点：置换时需要移动多个元素，理论性能比LRU差

CLOCK ​

在second-chance基础上得到，为避免每次访问时的链表调整代价，将链表组织成环

  • 把Second-Chance FIFO组织成环形
  • current指针指向当前 frame；每个frame有一个 referenced 位，初始为1（而不是原本的0）
  • 当需要置换页时，从current开始检查
    • 若 pin-count > 0，current增加1（正在被访问）
    • 若 referenced = 1（已启动），则关闭它（= 0）并增加 current，保证 最近的不被替换（复活甲）
    • 若 pin-count = 0 且 referenced =0（关闭），则替换 该frame，同时 current 加1
  • 注意：Current指针只在置换时更新，访问命中时不改变Current指针

SSD 置换算法 ​

特点：读快写慢，写次数有限 ，减少缓存置换中对闪存的写是一 个重要指标

SSD-aware缓存算法

  • CFLRU (CASES’06，CASES’21 Test of Time Award)
    • Clean-first
  • LRU-WSR(IEEE Trans CE’08)
    • Clean-first + cold flag（复活甲）
    • 置换：clean > cold dirty > hot dirty
  • AD-LRU (DKE’10)
    • cold LRU list + hot LRU list
    • Dynamically adjust two LRUs

缓冲区管理的实现 ​

Buffer 中 Frame 的查找

  • 读磁盘块时：根据page_id确定在Buffer 中是否已经存在frame
  • 写磁盘块时：要根据frame_id快速找到文 件中对应的page_id
  1. 首先，要维护Buffer中所有frame的维护 信息（Buffer Control Blocks）
c
struct BCB {
    int page_id;
    int frame_id;
    int count;
    int time;
    /* int latch; */
    int dirty;
    BCB * next;
} BCB();
  1. 建立frame-page之间的索引 ，若用Hash Table，需要建立2个
    • BCB hTable[BufferSize] //page 2 frame
    • int hTable[BufferSize] //frame 2 page

image.png

Released under the GNU General Public License v3.0.

Copyright © 2024-present SoreyLong