论文阅读：针对闪存的成本感知的缓冲区管理策略（DASFAA 2015）

2016-08-19

目录 [+]

1. Abstract
2. Introduction
3. 问题的定义
4. 成本模型
5. 实现细节
1. 数据结构和算法
References

原文：Jiang Z, Zhang Y, Wang J, et al. A cost-aware buffer management policy for flash-based storage devices[C]. International Conference on Database Systems for Advanced Applications. Springer International Publishing, 2015: 175-190. [下载]

1. Abstract

由于读写的不对称性，传统的基于磁盘的缓冲区管理策略在闪存中并不能达到最优。这篇文章提出了一种针对闪存的名叫 CARF 的成本感知的缓冲区管理策略。提出了一种新颖的低开销的能够准确地确定驱逐页的成本模型。而且，这个成本模型能区分读写操作，还有更好的扫描抵抗力(scan resistance)。基于人工的trace和基准测试的trace表明，CARF的性能比当前最好的闪存管理策略还要高27.9%。

2. Introduction

传统的基于磁盘的缓冲区管理策略利用了请求的时间局部性来减少磁盘访问。所以传统的缓冲区管理的主要目标是减少缺页率。然而，在闪存中，由于闪存固有的读写不对称性，最小化缺页率并不一定能带来更好的 I0 性能。所以我们应该用总的 IO 开销来衡量基于闪存的存储器的缓冲区管理策略的有效性，而不是以命中率作为主要标准。

除了 FOR[1]，前人的研究中没有使用成本感知的替换策略。FOR 和它的近似版本 FOR+ 提供了一个考虑了页面状态和将来操作的页面权重指标来选择牺牲页(victim page)。但是他的权重指标的有很大的计算开销。为了解决这个问题，这篇文章提出了名叫 Cost-aware Algorithm combining Recency and Frequency (CARF) 的成本感知的缓冲区替换策略。这个成本模型的计算开销很低，所以很实用。我们根据这个模型实现了轻量级的数据结构。

本篇文章的贡献如下：

提出了针对闪存的成本感知的缓冲区管理策略CARF，该策略利用准确的页面权重指标来选择牺牲页。
综合考虑访问频率(frequency)和距离上一次访问的时间间隔(recency)来设计一种新颖的成本模型作为权重指标。
实现了低开销和扫描抵抗能力强的CARF。

3. 问题的定义

符号说明

$ C_r/C_w $：一个读写操作的平均开销。

$ N_r/N_w $：读写操作的总数

$ R $：闪存的IO不对称性因子

$ m $：缓冲区大小

$ N $：DBMS中页大数量

$ t_i $：指定页的第i个请求的时间。

$x_i$：指定页的第i个时间跨度

$t_c$：当前的全局时间。

闪存设备的IO模型

总的 IO 开销 $ Cost_{io} = C_r ∗ N_r + C_w ∗ N_w = C_r ∗ (N_r + R ∗ N_w) \tag{1}$

frequency和recency的结合

根据前人的研究[1][2]，一个好的缓冲区管理策略应该综合考虑距离上一次访问的时间间隔(recency)和访问频率(frequency)来充分利用空间和时间的局部性。为了实现这个目录，这篇文章建立了一个闪存模型来衡量缓冲区中每个页面的热度(hotness)，然后根据flash的IO模型和这个成本模型来设计一个替换算法。符号说明如下：

$ Request Sequence $：访问页面的一个序列。

$ Global Time$：系统开始以来的请求的页面的数量。

$ Time Set $：假设在请求序列中页面p有k个请求，第i个请求在全局时间 $t_i^P$。定义页面p的时间集合(time set)为$T = {t_1^P,t_2^P,…,t_k^P}$。这个时间集合反映了该页的访问频率。

$Time Span$：假设页面p的时间集合$T={t_1,t_2,…,t_k}$，那么 $t_i $ 的时间跨度就是请求时间$t_i$和当前系统时间的间隔。记为：$x_i = t_c − t_i(1 ≤ i ≤ k)$。时间跨度反映了一个页面距离上一次访问的时间间隔。

假设页面p的时间集合$T = {t_1,t_2,…,t_k}, (t_1<t_2<…<t_k ≤t_c)$，那么该页面的权重(page weight)可以根据下面的公式计算得到：

$$ PW_t(p)= \sum_{i=1}^n W_x(i) = \sum_{i=1}^n W(t_c-t_i) \tag{2}$$

函数 w(x) 是用来计算时间间隔x在当前时间下对页面权重的贡献。

4. 成本模型

定义了一个 RF 模型来计算页面权重，RF 模型为 CARF 定义了基本的权重指标，这里没有考虑读写不对称性。

如果在$t_c$时刻，需要从缓冲区中驱逐一个页，只需要计算缓冲区中每个页的权重，然后驱逐权重最低的页。权重函数的选择需要很慎重，它决定了 recency 和 frequency 对页面权重贡献的比例。一个好的权重函数应该有下面的属性：

$∀x ∈ N, W(x) > 0.$ 也就是说，任意页面的权重应该是大于0的。
$∀x ∈ N,W(x)’ ≤ 0.$ 也就是说，任意页面的权重应该是单调不增的，因为时间跨度越长，说明该页面越有可能不被访问。
$W(0) = c.$ 这里c是常量。也就是说当时间跨度为0的时候，权重应该是个常数。

如果用公式(2)计算权重的话，需要很大的开销去记录请求信息。所以这里利用了迭代的思想，利用 $t_{i-1}$ 时刻的结果来计算 $t_i$ 时刻的结果。

引理1：如果 W(x) 满足，$∀x, y ∈ N,W(x+y) = W(x) ∗ W(y)$，那么 $PW_t(p)$ 可以由 $ PW_{t_{i−1}}(p) $ 计算出。

由引理1我们可以得到下面的引理。

引理2：

$$ PW_{t_i}(p) = W(0) +W(y_i) ∗PW_{t_{i−1}}(p) $$

结合引理1和上面提到的权重函数的属性，发现下面的公式满足要求：

$$　W(x) = a＾x, (0 < a ≤ 1)　\tag{3}　$$

当 a=1 时，W(x) = 1。这时 recency 对权重没有贡献，当前模型也就变成了 LFU。

当 a ∈ (0,0.5] 时，W(x) 满足 $∀i,W(i) > \sum_{j=i+1}^{oo}W(j)$。这时 frequency 对权重没有贡献，当前模型也就变成了 LRU。

当 a ∈ (0.5,1) 时，recency 和 frequency 对权重都有贡献。

5. 实现细节

这里将 RF 模型和 IO 模型相结合。IO模型考虑了读写不对称性，成本模型考虑到了页面的权重。为了在计算页面权重时，考虑到读写不对称性，需要像前人的研究一样考虑页面的状态。如果一个页面上一次访问时是干净的，这一次被修改了，那么它会对权重有一个很大的贡献。用一个 Lastdirty 标签来维持给定页面在上一次访问时的状态。最后定义一个 asymmetry 函数来表示读写不对称性对页面权重的影响。

$$ R_{t_c}(p)=\begin{cases}R, & \text{lastdirty(p) = false∧ modified at tc}\\1, & \text{otherwise}\end{cases}$$

基于以上的考虑，需要记录下面的信息来帮助计算页面的权重：

Lasttime(p): 上一次请求页面p的时间。
Lastweight(p): 页面p在上一次请求时的权重。
Lastdirty(p): 页面p在上一次请求中是否被修改。

因此，

$$ FPW_{t_c}(p) = R_{t_c}(p) ∗ [W(0) +W(t_c − Lasttime(p)) ∗ Lastweight(p)] \tag{4}$$

当缓冲区满的时候就可以根据公式4来选择权重最小的页面去驱逐。

如果直接用公式4并不是很恰当，因为当缓冲区慢的时候，每一个时间步长之后所有页面的权重都要更新。由 W(x) 的属性，可以得到：

引理3： 任何的页面p和q，如果$ FPW_{t_c} (p) > FPW_{t_c} (q) $ 且p和q在$t_c$之后都没被访问，那么$ ∀t > tc, FPW_t(p) > FPW_t(q)$

因为，如果两个页面都没有被访问过，他们之间的相对顺序不会改变，所以我们只需要改变被访问的权重就行了。

数据结构和算法

可以用最小堆来实现CARF算法，每次要发生替换的时候，就用新的页面来替换堆的根部的页面，然后自顶向下地调整堆来维持 Lastweight 的顺序。每次命中的时候，命中页的权重会被更新，然后自顶向下地更新这个子堆。这样选择驱逐页的时间复杂度是O(1)，还需要O(log m)的时间复杂度去调整堆，这个时间复杂度比LFU好，比LRU差。因此，我们需要在考虑页面权重的时候减少时间复杂度。

可以通过 RF 模型的竞争分析来解决这个问题。

定理1：当 a=1 时，RF 模型不是竞争的；当 a∈[0.5,1) 时，RF模型是 $　m-1+\lceil \frac{log(1-a)}{log(a)} \rceil-competitive$

定理2：假设页面 p 的最近一次访问是在 t 时刻，那么存在一个最小的时间 $ T_{min} = \lceil \frac{lg(1-a)}{lg(a)} \rceil $，只要 $ t_c-t>T_{min} $，无论 $ PW_t(p) 多大，PW_{t_c}(p) < 1 $ 总是成立。

那么我们可以根据定理2来解决这个问题，因为 W(0)=1，所以当一个页面的权重大于 1 时，那么它最近的请求肯定是在 $T_{min}$ 的时间单元內。所以我们只要维持 $T_{min}$ 的页面到优先队列中。可以把缓冲区分为两个部分来减少计算开销。上层队列是一个最小堆，下层队列是 $m−T_{min}$个页面按LRU方式组织成的链表。

References

[1] Lv, Y., Cui, B., He, B., Chen, X.: Operation-aware buffer management in flashbased systems. In: SIGMOD, pp. 13–24 (2011)

[2] Effelsberg, W., Harder, T.: Principles of database buffer management. TODS 9(4),560–595 (1984)