Efficiently Reclaiming Space in a Log Structured Store

这篇文章提出了一种名为 MDC 的清理方法，它能减少写放大，并且实现简单且高效，原文请看 这里

清理的成本

对于 append-only 的架构来讲，数据存储通常是一个个的 segments，所谓的清理，其实就是将 segment 中活跃的 page （或者叫frame）收集起来，然后写到新的 segment 中，当旧的 segment 中不再有活跃的 page 时就可以删除了，那么这个过程的成本是多少呢？

假设 \( E \) 是 segment 的空白率（即：垃圾），读取一个 segment 来清理的需要读出 \( E * S \) 个空白页，这里的 \( S \) 表示segment 中总的页面数，要写入 S 个页面的新数据的话，那么 \( 1 / E \) 个 segment 必须被清理（例如：\( E \) 是 3/8，那么要写入 8 个新的页面，那么至少要读取 \( 1 / E \) 个段，即：16个页面才能凑够8个新的页面，其中 6个是垃圾），对于每个 segment 的写入，必须有 \( (1 - E) * S \) 个页面需要移动到新的地方，因此清理一个 segment 总的 I/O 成本 \( Cost_{seg} \) 是

$$ Cost_{seg} = \frac{1}{E}reads + \frac{1}{E}(1 - E)writes + 1 = \frac{2}{E} $$

其中 \( \frac{1}{E} \) 就是 \( S\)， 很明显清理 segment 的写放大\( Wamp\)是 \( \frac{1}{E}(1 - E) \)

相对的我们把 \( F \) 叫做填充率，表示当前所有数据中有效页面的占比，清理的效率强依赖于 \( F \)，越小的 \( F\) 意味着有更多的空闲空间可以清理，显然当 \( E >= (1 - F) \) 时（这里 \(1 - F \) 就是所有数据的空白率）清理这个 segment 的成本更小

最小下降成本

我们利用“下降成本“这个概念来建立不同更新频率的segment的清理优先级，我们知道，随着频繁的更新，清理页面的成本也会降低，如果清理的成本能够随时间快速下降的话，那么我们应该等一段时间，否则我们应该优先清理那么清理成本不会大幅减小的segment

问题是需要确定最优的处理顺序，毕竟它们的处理成本在随着时间不断的下降。我们假设对象 \(i\)在时间\(t_n\)时的处理成本为\(c_i(t_n)\)，同时假设成本的变化率为常量 \(\frac{dc_i(t)}{dt}\)，对 segment 的清理来说，这可以看作是一个“近似”，因此在\(t_0\)时\(i\)的清理成本就是\(c_i(t_0)\)，那么对于任意时间\(t_i\)，对象\(i\)的清理成本就是

$$ c_i(t_i) \approx c_i(t_0) + \frac{dc_i(t_0)}{dt}(t_i - t_0) $$ 那么处理 \(k\) 个对象的成本就是

$$ Cost_{total} = \sum_{i=1}^{k} c_i(t_i) \approx \sum_{i = 1}^{k} c_i(t_0) + \sum_{i = 1}^{k} \frac{dc_i(t_0)}{dt} (t_i - t_0) $$

对于segment的清理来说，随着时间的变化成本是降低的，因此\(\frac{dc(t)}{dt}\) 是负的，这将简化对于成本下降的讨论，即由 \(- \frac{dc(t)}{dt}\) 表示成本下降，因此上面的式子可以重写为

$$ Cost_{total} = \sum_{i=1}^{k} c_i(t_i) \approx \sum_{i = 1}^{k} c_i(t_0) - \sum_{i = 1}^{k} - \frac{dc_i(t_0)}{dt} (t_i - t_0) $$

不难看出，当右边的第二个求和最大时 \( Cost_{total} \) 才是最小的，那么它什么情况下求和最大呢？我们想要的是“最大的下降成本 ✖️ 最长的时间间隔“，根据 最大性引理（Maximality Lemma），给定两个正数的集合 \(X\) 和 \(Y\) 且 \(||X|| = ||Y||\) （范数） 要使

$$ \sum_{i=1}^{k} x_iy_i $$

最大，那么 \( X = {x_i}\) 和 \(Y = {y_i}\) 需要有相同的顺序，即： \( x_i \geq y_j\) 当且仅当 \(y_i \geq y_j\) ，具体证明见原文的附录

因此，最好是在最后清理 最大下降率 的对象（这样成本最低），相反，应该最先清理 最小下降率 的对象（尽快腾出空间），这很符合直觉！

Segment 清理

前面提到的结论的前提是 “将segment 的清理的成本变化率视为常量“，但实际上这个变化率并不是常量，因此这个结果只是一个一阶近似（即：定性）。我们需要对每个segment的成本微分（求导），还是用 \(E\) 表示空白率，然后 \(U_{pf}\)表示segment中页面的更新频率，根据前面的成本公式

$$ Cost = \frac{2}{E} = 2E^{-1} $$

那么成本下降就是

$$ \frac{d(Cost)}{du} = (\frac{-2}{E^2})(\frac{dE}{du}) $$

为了获得每次更新时 \(E\) 的变化是多少（即 \(\frac{dE}{du}\))，我们需要乘上每次更新时活跃页面的数量，令 \(U_{pf}\)表示每个页面的更新频率，那么每个segment的更新频率就是：当前的页面数量✖️ \(U_{pf}\)，因此

$$ \frac{dE}{du} \quad \alpha \quad (1 - E)U_{pf}\Delta E $$

这里 \(\Delta E\) 表示每次更新时 \( E\) 的变化，因此

$$ \frac{d(Cost)}{du} \quad \alpha \quad \frac{-2(1 - E)}{E^2}U_{pf}\Delta E $$

更新频率

我们的清理方法总体上是将页面按照更新频率划分到segment，为了实现这个，我们需要一个简单的办法来估算更新频率，但是密集的收集页面的更新频率开销太大，因此这里使用某种形式的“age”作为近似，来估算页面的更新频率

对于一个 segment，我们定义 \(u_{now}\) 为当前的 tick，而 \(u_{p1}\) 为 segment 的最后一次更新的 tick，\(u_{p2}\) 为 segment 的最后一次更新的前一次更新的 tick，那么 \(u_{now} - u_{p1}\) 就是更新的周期，但这个非常不准确，因此两个周期来作为更新的平均值，那么这个段的更新频率就是

$$ U_{pf} = \frac{2}{u_{now} - u_{p2}} $$

也就是说，从 \(u_{p2}\) 到 \(u_{now}\) 这个 segment 有 2 次更新，并且相同更新次数的情况下 \(u_{now} - u_{p2}\) 越大，那么 \(U_{pf}\)就越小，这就是前面提到的 某种形式的 “age“ 作为近似；当然这个式子可以扩展来包含更多的更新，例如

$$ U_{pf} = \frac{n}{u_{now} - u_{pn}} $$

但\(U_{pf}\) 会变化，我们想要跟踪这些变化的话就不能平均太多的更新？？？（会失真🤔），因此我们使用两个周期作为\(U_{pf}\) 的评价值，那么我们的估算成本下降的函数就是

$$ \frac{d(Cost)}{du} \quad \alpha \quad \frac{-2(1 - E)}{E^2} * \frac{2}{u_{now} - u_{p2}} * \Delta E $$

更新和 \(\Delta E\)

\(\Delta E\) 是更新segment中一个页面时 \(E\) 的变化率，对于固定大小的页面来说 \(E\) 的变化就是 \(1/P\) 其中 \(P\) 是segment中的页面数量，这样最小成本下降函数就是

$$ \frac{d(Cost)}{du} \quad \alpha \quad \frac{-2(1 - E)}{E^2} * \frac{2}{u_{now} - u_{p2}} * \frac{1}{P} $$

由于页面大小固定，因此在segment中\(P\)是一个常量，因此对segment的清理顺序没有影响

当页面数量可变时，情况就变得复杂了。加上一个segment的长度是\(B\)字节，那么 \(\Delta E \) 或许是 \(Size_P/B\)，但问题是我们如何使用 \(Size_P\) 呢？因为我们并不知道下一个要更新的页面的大小，然而，我们可以通过计算还没更新过的页面的大小的平均大小来近似

令\(C\)表示还未更新的页面的数量，\(A\)表示大小为\(B\)的segment中的空闲空间，那么未更新页面大小的平均之就是 \((B - A) / C\)（即\(Size_P\)），这样更一般的成本下降函数就是

$$ \frac{d(Cost)}{du} \quad \alpha \quad \frac{-2(1 - E)}{E^2} * \frac{2}{u_{now} - u_{up2}} * \frac{(B - A) / C}{B} $$

成本信息

segment 相关信息

根据前面的分析，我们发现对于最小下降成本的式子有些信息是常量，例如： \(B\) （即：segment 的大小），而有些则会随着时间而变化，并且不同的segment也不一样，对于这些信息我们需要为每个segment单独获取：

全局信息

变形后的下降成本

由于 \(E\) 表示 segment 中页面的空白率，结合上面收集的信息，那么有 \(E = A/B\)，这样上面的下降成本式子就变成了

$$ - \frac{d(Cost)}{du} \quad \alpha \quad \frac{2(1 - A/B)}{(A/B)^2} * \frac{2}{u_{now} - u_{up2}} * \frac{(B - A) / C}{B} $$

注意：这里将 \(-\) 移到了左边。然后约分并去掉常数项2，就得到了下面的式子

$$ - \frac{d(Cost)}{du} \quad \alpha \quad (\frac{B-A}{A})^2 * \frac{1}{C * (u_{now} - u_{up2})} $$

维护segment信息

\(A\) 和 \(C\)

那么问题来了，对于变长的页面，\(C\)的初始值该设置为多少呢？？？但在虽然，但是，实际上在应用时，我们其实并不关系它如何变化，只需要清理是知道它的值，而这个值其实就是活跃的页面数量

更新频率

更新分为两种情况，用户写和垃圾回收写，我们的目标是对于这两者尽量保证更新记录的精确

垃圾回收写 每个GC的页面都带有 \(u_{p2}\)，而GC要写入的页面自身的\(u_{p2}\)则是这些GC页面的\(u_{p2}\) 的平均值，这个值的粗糙程度取决于我们如何按照更新频率来分隔页面（见 根据更新频率分割 ）

用户写 这个又分为两种情况

首次写： 由于还没有更新，因此\(u_{p2}\)可以被设置为任意值，对于批量写来说，我们将 \(u_{p2}\) 设置为最旧的值，说人话就是：初始设置为0，首次就刷一批页面的话，例如 3 个，每个都有一个tick，那么取第一个作为\(u_{p2}\)，剩余情况就又下面的 非首次写 处理

非首次写： 我们假设有一个先前的 \(u_{p1}\) 是 \(u_{now}\) 和 \(u_{p2}\)的中间值，当有新的更新时 \(u_{p1}\)就会变成新的 \(u_{p2}\)，因此

$$ new(u_{p2}) = old(u_{p2}) + \frac{u_{now} - old(u_{p2})}{2} $$

很显然，可以使用两个变量滚动实现，而这里使用上面的假设，或许这就是“目标”🤔

根据更新频率分割

根据原文第3节的结论，将冷热数据分布到不同的segment可以降低清理的成本，因此在将页面刷入到segment时可以先对页面根据 \(u_{p2}\)排序，这样自然的将不同更新频率的页面分布到不同的 segment，从而降低清理成本。原文中表示对用户写也这样做，而实际上，用户写的page根本没有\(u_{p2}\)，而垃圾回收写时，写入新segment的页面的\(u_{p2}\)来自需要GC的segment

人话版总结

本文先分析了GC时的I/O开销，随后分析了不同的I/O分布的特点，发现“冷热分离”时清理的成本最低，因此建立一个叫做 MDC （Minimum Declining Cost) 的清理策略，并且分析（最大性引理）得出，应该优先清理 decline rate 小的 segment，接下来分析出如何计算 decline rate，提出一种类似“age”的方法即：使用\(u_{p2}\) 来计算 decline rate，随后，确定了计算 decline rate 所需的变量的计算（获取）方法，得到最后的下降成本公式

$$ - \frac{d(Cost)}{du} \quad \alpha \quad (\frac{B-A}{A})^2 * \frac{1}{C * (u_{now} - u_{up2})} $$

例子

当GC触发时，MDC 需要收集所有segment （已经clean的除外）的信息，为每一个 segment 计算 decline_rate，同时也可以加入自定义的因子（例如：写放大）保存为 score，然后对 score 排序，根据外部设定的条件决定清理 score 靠前的多少个 segment （例如：如果还记录了活跃页面的总大小，那么可以只要靠前的score能凑出一个新的 segment大小就完成 GC）

需要注意的是 \(u_{now}\) 和 \(u_{p2}\) 的本质是更新的计数，因此可以使用 segment 的编号，对于用户写，segment 的 \(u_{p2}\) 就是自己的编号，而GC写 segment 的\(u_{p2}\) 就是要清理的 segment 的\(u_{p2}\) 的平均值

简单来说 MDC 就是用于挑选segment的一个策略，以确保小的写放大和低的清理成本