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 的每日寫入情況經常觸及所設上限，即 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 效果會非常好。
整體的設計還是非常容易了解的，但發現這一特性并設計出能夠穩定運作的算法（生産環境必須），相信作者們花費了不少功夫。