[FAST'20] BCW

BCW: Buffer-Controlled Writes to HDDs for SSD-HDD Hybrid Storage Server

作者： Shucheng Wang, Ziyi Lu, and Qiang Cao, Wuhan National Laboratory for Optoelectronics, Key Laboratory of Information Storage System; Hong Jiang, Department of Computer Science and Engineering, University of Texas at Arlington; Jie Yao, School of Computer Science and Technology, Huazhong University of Science and Technology; Yuanyuan Dong and Puyuan Yang, Alibaba Group

为了兼顾访问性能和硬件成本，目前有不少的存储系统都采用了混合存储（Hybrid Storage），使用 SSD 来提供微秒级访问，配合 HDD 来降低存储成本。在实现细节上，一般会使用 SSD 来服务用户的写操作（cache），然后通过后台操作批量将 SSD 存储的数据搬迁到 HDD 进行更长时间的存储。

阿里云的盘古存储系统采用了类似设计来实现混合存储，在观察了生产环境中的使用情况后，论文作者发现：系统对 SSD/HDD 的利用上存在明显的不均衡现象，SSD 经常被过度使用而 HDD 的利用率却相对较低，尤其是 write-intensive workload。

下表中四种负载分别来自于：（A）计算型任务；（B）存储型任务；（C、D）结构化存储。

表一

在写负载持续增高的情况下，以 SSD 为主的混合存储系统会面临如下问题：

1. SSD 寿命：持续的高负载会缩短 SSD 寿命，从数据上来看，SSD 的每日写入情况经常触及所设上限，即 DWPD (Drive Writes Per Day)。

2. SSD 性能：在写入密集的情况下，大量的写请求可能会超过 SSD 的处理能力，导致请求在 SSD queue 中排队，引起长尾延时；除此之外，请求的增加也会更频繁地触发 SSD 的 GC，导致性能下降。

对于此问题，一个直接的解法是引入更多的 SSD，无论是加机器还是单机上增加 SSD，这都能降低单个 SSD 承担的压力，但会引入额外的硬件成本，性价比很低。

是否能够在不增加硬件且不降低系统性能的情况下解决此问题呢？

图一：在西部数据10TB HDD上写顺序写

通过大量针对 HDD 的实验，作者发现，在进行连续的顺序写时，HDD 的延时表现出了显著的周期性。在持续写入的时间线上，延时大致能划分为 fast -> slow -> mid 三个阶段，以 4K 大小的请求为例，fast 阶段持续 60ms，延时为 35us，然后是一个瞬时的 slow 阶段，延时为 12ms，接着的 mid 阶段持续 40ms，延时为 55us，之后则是 mid/slow 交替，直至某个时间点回到 fast（10TB 西数 HDD 上并没有展现完整的周期，但 8TB 西数 HDD 的测试上体现了这一点，下图）。

图二

可以看到，在 fast/mid 阶段，HDD 的延时在 us 级，这和 SSD 非常接近。引起这一现象的源头是 HDD 内部的 buffer 机制，HDD 会在其内置的 DRAM 中给写请求划分一块 buffer，当它将一个请求存入 buffer 后，它会向上层返回成功。而当 buffer 达到一定阈值后，HDD 会将 buffer 中的数据写入物理介质，这个刷盘过程会阻塞后续的写入，从而导致延时增大。除此之外，如果 HDD 持续 idle，它也会隐式地执行此操作来清空 buffer；另外 sync 的调用也可以触发 buffer 的刷盘。

这个发现为前述问题提供了一个解决思路： 如果我们能够预测 HDD 下一次写入的情况，在它能够提供微秒级延时时，将请求交由 HDD 进行处理。

图4

表2

为了更好地描述 HDD 的这一特性，论文中对此进行了建模，F、M、S 分别对应上述 fast/mid/slow 阶段，当进入 M/S 阶段后，需要经过 "sync"，才能使时延回到 F。对于不同型号的 HDD，模型参数表中的 L, W, F 会有差异，但均可通过事先测试来获取，具体可参见原文，此处不再赘述。

design

图5

在模型的基础上，文中根据当前的 buffer 大小以及写入状态（F、M、S）构建了对应的预测状态机，进而设计了预测算法。

Algo 1

此算法中的 ADW 是个持续累积值，需要由外部调用方（下文中的 BCW 算法）来进行清理，除此之外，算法逻辑比较清晰，此处也不展开描述了。

值得一提的是，作者对预测算法的准确性进行了验证：以 128K 为单位连续写入 100GB 数据，每写入 1GB 后就调用一次 sync 操作。结果显示，算法对 F、M、S 三种状态的预测准确率能够达到 99.5%、98.1% 和 60.3%。可见，对 F/M 的预测还是很准确的，对 S 状态的错误预测是因为算法更侧重于保证性能，毕竟从性能角度来看，相比将 S 预测为 F/M，把 F/M 预测为 S 会造成更严重的影响。

Buffer-Controlled Writes (BCW)

Algo 2

基于状态预测算法，作者实现了写入控制算法（BCW），以尽可能保证所有的用户请求都在 HDD 处于微秒时延的状态（F/M）时被写入。

这个算法同样不能独立工作，仍需要外部算法在 HDD 处于微秒时延时向写入队列转发请求，算法中通过 flagHDD 来告知外部算法是否可以转发。

BCW 的一个主要设计在于其写入 padding 数据的逻辑：

• PS padding：由于预测算法会在 F/M 状态下的 ADW 接近 Wf 或 Wm 时返回 S 状态，BCW 根据此可以得知，buffer 即将被填满，所以它通过主动地构造 PS padding 数据（较大，64KB）来触发 slow 写入，直到某次写入的时延对应的状态不再为 S，BCW 即认为当前 HDD buffer 以恢复到能够以微秒时延写入数据的状态，它会重置 ADW。

• PF padding：考虑到低负载的情况下，HDD 可能不会收到任何写入请求（可能 SSD 足够处理），为了保证算法的稳定性，BCW 会在非 S 状态时不断写入 PF padding（较小，4KB）。算法中仅在预测状态为 M 的情况下进行此操作，这是因为当 sync 或者 HDD 内部隐式 flush 被执行后，buffer 会进入到稳定的 F 状态，此时无需做任何的 padding。

图6

正如 BCW 中提到的，它需要外部算法根据其设置的 flag 来决定此时是否能将请求转发给 HDD，因此，整个设计上需要一个调度器，根据 HDD/SSD 的状态来进行综合调度，决定每一个写入请求最终由谁处理。

如图所示，本文设计的调度策略所参考的指标除了前述 HDD 的状态/flag 外，还引入了 SSD 队列长度 l(t)。调度算法如下：

algo 3

算法的基本逻辑很容易理解：

• 当 flag 被设置时，HDD 一定处理 S 状态，此时请求只能由 SSD 处理。

• 当 HDD 处于 F/M 时，如果 SSD 并不忙（队列长度 l(t) 并非超过设置的阈值 L），交由 SSD 处理对性能最好。

关于阈值 L 的选择，文章给出的经验值为 1，Evaluation 部分也给出了相应的验证来说明这一点。

图10

在基本逻辑之上，调度算法还被细化为 MIOS_E 和 MIOS_D，两者的区别在于当 SSD 不忙且 HDD 处于 F 状态时，前者会将请求转发给 HDD 以进一步地降低 SSD 的负载。

需要注意的是，MIOS 算法需要拥有对 HDD 的完全控制，所以当读请求到来时，BCW 算法会被挂起来处理此请求，此时不能再向该 HDD 写入数据。这也比较容易理解，当读请求到达时，HDD 的磁头可能就跑到了另外的地方，无法再保证连续写的要求。因此，对于 read-dominated workload，MIOS 并不适用。

我的思考