BCW: Buffer-Controlled Writes to HDDs for SSD-HDD Hybrid Storage Server
为了兼顾访问性能和硬件成本，目前有不少的存储系统都采用了混合存储（Hybrid Storage），使用 SSD 来提供微秒级访问，配合 HDD 来降低存储成本。在实现细节上，一般会使用 SSD 来服务用户的写操作（cache），然后通过后台操作批量将 SSD 存储的数据搬迁到 HDD 进行更长时间的存储。
阿里云的盘古存储系统采用了类似设计来实现混合存储，在观察了生产环境中的使用情况后，论文作者发现：系统对 SSD/HDD 的利用上存在明显的不均衡现象，SSD 经常被过度使用而 HDD 的利用率却相对较低，尤其是 write-intensive workload。
下表中四种负载分别来自于：（A）计算型任务；（B）存储型任务；（C、D）结构化存储。
在写负载持续增高的情况下，以 SSD 为主的混合存储系统会面临如下问题：
- SSD 寿命：持续的高负载会缩短 SSD 寿命，从数据上来看，SSD 的每日写入情况经常触及所设上限，即 DWPD (Drive Writes Per Day)。
- SSD 性能：在写入密集的情况下，大量的写请求可能会超过 SSD 的处理能力，导致请求在 SSD queue 中排队，引起长尾延时；除此之外，请求的增加也会更频繁地触发 SSD 的 GC，导致性能下降。
对于此问题，一个直接的解法是引入更多的 SSD，无论是加机器还是单机上增加 SSD，这都能降低单个 SSD 承担的压力，但会引入额外的硬件成本，性价比很低。
是否能够在不增加硬件且不降低系统性能的情况下解决此问题呢？
通过大量针对 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 进行处理。
为了更好地描述 HDD 的这一特性，论文中对此进行了建模，F、M、S 分别对应上述 fast/mid/slow 阶段，当进入 M/S 阶段后，需要经过 "sync"，才能使时延回到 F。对于不同型号的 HDD，模型参数表中的 L, W, F 会有差异，但均可通过事先测试来获取，具体可参见原文，此处不再赘述。
Design
Write-state Predictor
在模型的基础上，文中根据当前的 buffer 大小以及写入状态（F、M、S）构建了对应的预测状态机，进而设计了预测算法。
此算法中的 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)
基于状态预测算法，作者实现了写入控制算法（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。
Mixed IO scheduler (MIOS)
正如 BCW 中提到的，它需要外部算法根据其设置的 flag 来决定此时是否能将请求转发给 HDD，因此，整个设计上需要一个调度器，根据 HDD/SSD 的状态来进行综合调度，决定每一个写入请求最终由谁处理。
如图所示，本文设计的调度策略所参考的指标除了前述 HDD 的状态/flag 外，还引入了 SSD 队列长度 l(t)。调度算法如下：
算法的基本逻辑很容易理解：
- 当 flag 被设置时，HDD 一定处理 S 状态，此时请求只能由 SSD 处理。
- 当 HDD 处于 F/M 时，如果 SSD 并不忙（队列长度 l(t) 并非超过设置的阈值 L），交由 SSD 处理对性能最好。
关于阈值 L 的选择，文章给出的经验值为 1，Evaluation 部分也给出了相应的验证来说明这一点。
在基本逻辑之上，调度算法还被细化为 MIOS_E 和 MIOS_D，两者的区别在于当 SSD 不忙且 HDD 处于 F 状态时，前者会将请求转发给 HDD 以进一步地降低 SSD 的负载。
需要注意的是，MIOS 算法需要拥有对 HDD 的完全控制，所以当读请求到来时，BCW 算法会被挂起来处理此请求，此时不能再向该 HDD 写入数据。这也比较容易理解，当读请求到达时，HDD 的磁头可能就跑到了另外的地方，无法再保证连续写的要求。因此，对于 read-dominated workload，MIOS 并不适用。
Evaluation
- Baseline：纯 SSD 写入。
- MIOS_E
- MIOS_D
Production Workloads
论文使用了前述的 4 种 workload 对 MIOS 算法进行了详尽的实验，结果如下。
时延对比：无论是平均时延还是长尾时延，MIOS 都拥有更好的效果。
SSD 队列长度分布也体现了长尾延时的降低。
不同请求大小下的平均时延：对于大请求，MIOS 的效果比 baseline 更差，一方面是在写入大请求时，SSD 本身比 HDD 拥有更佳的性能（内部并行机制），另一方面则是大请求相对较少，被 SSD queue length 或 GC block 的概率也较低。
MIOS_E vs MIOS_D
因为 MIOS_E 允许在 SSD 不忙的情况下将请求转发给 HDD，所以相比 MIOS_D，它会转发更多的请求，但也会导致时延上升。这个现象对于 workload A 特别明显，从表 3 可知，相比其他三个 workload 而言，它对 SSD 的 workload 很低，这也使得在 MIOS_D 下，大部分请求仍旧由 SSD 进行处理，能够获得更好的性能，但在 MIOS_E 下，请求被转发给 HDD，导致了性能下降。
但这并不意味着 MIOS_E 毫无用武之地，当 SSD 的写入性能本身就一般的情况下，即使它的 queue length 并未表现出忙的特征，但实际写入的延时可能依旧较高，此时转发给 HDD 反而能获取更好的性能。作者尝试将 SSD 替换为 660p（原先为 960EVO，性能更佳）后，MIOS_E 表现非常好。
除了性能以外，因为 MIOS_E 会收到更多的 HDD 请求，从而算法中的 padding 数据也会增多，所以它相比 MIOS_D 会产生更多的空间浪费。另外，MIOS 算法将部分 SSD 负载搬迁到 HDD 上执行，会有效提高 HDD 的利用率，但仍需要确认：HDD 仍有足够能力来承担数据搬迁（SSD->HDD）任务。实验对此进行了验证，有兴趣的同学可以参考原文，此处不再赘述。
Write Intensity
由于 MIOS 利用了 HDD 连续写的特性，所以它非常适合 write-intensive workload，作者对此进行了补充测试（X 轴代表的是发送间隔，越小数据量越大）。
可以看到，当写压力很大的情况下（20-60us），SSD 的性能会受到排队和 GC 的影响，平均时延和长尾时延都要高于 MIOS。而当压力降低到可承受范围后，SSD 将保证稳定的写入性能，此时，MIOS_D 退化为纯 SSD 写入（因为 SSD 无忙特征），但 MIOS_E 依旧会转发部分请求至 HDD，所以相对之下会有更高的平均和长尾时延。
总结
总的来说，MIOS 充分利用了 HDD 在连续写场景下的时延周期特性，找到了一种在混合存储下保证微秒级写入和存储成本二者兼得的方法，尤其对于 write-intensive workload，未受到读请求打断的 MIOS 效果会非常好。
整体的设计还是非常容易理解的，但发现这一特性并设计出能够稳定运行的算法（生产环境必须），相信作者们花费了不少功夫。
