【概要】

根據(jù)數(shù)據(jù)的壽命將數(shù)據(jù)存放在SSD的不同塊內(nèi)可以顯著提高SSD的GC效率、減少WAF、提高SSD的壽命和性能。多流技術(shù)（Multi-stream technology）可以設(shè)置數(shù)據(jù)放置策略從而減少WAF和數(shù)據(jù)碎片。本文提出了FileStream，利用聚類算法學(xué)習(xí)文件特征從而給文件分配數(shù)據(jù)流，使得相似壽命的數(shù)據(jù)存放在SSD的同一塊內(nèi)。最后作者測試了六個不同的benchmark，和baseline和兩個自動流管理技術(shù)相比，分別平均減少了寫放大34.5%和21.6%。

【背景與相關(guān)工作】

1. 多流技術(shù)

用戶可以在寫請求中傳遞一個hint（流ID，Stream ID），流ID不同的數(shù)據(jù)會被放在SSD的不同的地方（如不同的塊內(nèi)）。所以當(dāng)主機根據(jù)數(shù)據(jù)的壽命分配不同的流ID時，壽命不同的數(shù)據(jù)將被分開存放，從而提高GC效率。

目前，NVMe已經(jīng)添加了多流技術(shù)，而Linux 4.13內(nèi)核也增加了“write lifetime hints”來攜帶流ID。同時，多流技術(shù)不僅僅可以用于多流SSD，還可以用于其他設(shè)備如OpenChannel SSD、Zoned Namespace SSD。

2. 流ID分配的相關(guān)工作

手動分流

在應(yīng)用的代碼中實現(xiàn)一個固定的流分配策略（基于文件類型和一些內(nèi)部的機制）。缺點是無法適應(yīng)多樣的工作集和應(yīng)對工作集的特征的改變。同時，把這些策略應(yīng)用在生產(chǎn)中成本略高，因為需要修改應(yīng)用代碼或者內(nèi)核代碼。

表1 手動分流的相關(guān)論文

自動分流

不依賴于具體應(yīng)用進行流分配。如下表，現(xiàn)存的自動分流策略無法直接用在某些通用的工作集中，而且比不過手動分流。

表2 各種自動分流策略一覽

表3 自動分流的相關(guān)論文

FileStream——基于文件特征實現(xiàn)自動分流

1）動態(tài)適應(yīng)多樣的工作集

2）在Linux用戶態(tài)實現(xiàn)，除了傳遞stream ID之外，不會影響應(yīng)用和內(nèi)核。

文件特征分析

只附加寫的文件（Append-only File）

這類文件只會順序?qū)懭?，不允許修改舊數(shù)據(jù)，更新的數(shù)據(jù)會寫入一個新文件，如日志結(jié)構(gòu)的文件（例如RocksDB和Cassandra的寫前日志和數(shù)據(jù)文件，它們使用LSM樹進行管理）。

文件中的數(shù)據(jù)壽命很難通過LBA的訪問次數(shù)得出。一個文件的數(shù)據(jù)的LBA可能不連續(xù)，而且數(shù)據(jù)可能被其他文件覆寫。

文件中的數(shù)據(jù)的壽命和文件的類型有關(guān)，如下圖，數(shù)據(jù)文件有多個等級（L0~L3），低等級的文件在合并入高等級文件后會被刪除，所以它們的壽命更短。然而，文件的等級只能通過修改應(yīng)用代碼獲得，所以這種分流思路只能適用于手動分流。

不過，從圖中可以得到兩個信息：

① 這類文件從創(chuàng)建到結(jié)束寫入的時間很短，而且同時正寫入的文件很少，而同一文件的數(shù)據(jù)的壽命通常類似。同時，根據(jù)經(jīng)驗，不同時間使用同一流ID寫入SSD的數(shù)據(jù)通常不會寫入同一塊。

② 寫前日志的壽命比數(shù)據(jù)文件短，不同類型文件的壽命不同。

綜上，可以通過文件類型區(qū)分文件中的數(shù)據(jù)壽命。

圖1 RocksDB 文件的操作

就地更新的文件（In-place Update File）

這類文件允許隨機寫，允許文件內(nèi)更新數(shù)據(jù)，如關(guān)系數(shù)據(jù)庫中的數(shù)據(jù)文件（例如MySQL和PostgreSQL中的表文件）。這類文件的存在時間通常比較長，它們隨著表的創(chuàng)建和刪除而創(chuàng)建或刪除。

若對一個LBA的寫很頻繁，意味著大部分寫入這個LBA的數(shù)據(jù)壽命較短。下圖顯示了同一個表文件中LBA的訪問頻率相似，而不同表文件中LBA的訪問頻率不同。為了從文件的角度看待LBA的訪問頻率，作者提出USM（unit-size-modification）——文件被修改的次數(shù)比上文件的大小。對于這類文件，可以通過USM區(qū)分文件中的數(shù)據(jù)壽命。

圖2 在MySQL和PostgreSQL中的數(shù)據(jù)寫入

【方法】

1. Mapper：初分流

因為append-only文件從打開到結(jié)束寫入的時間很短，所以有必要在文件一打開就決定文件中數(shù)據(jù)的流ID，而此時我們并沒有很多文件的修改信息。FileStream的設(shè)計思路為，最小化同一流內(nèi)不同壽命的文件的寫入量。設(shè)具有同一個父路徑和擴展的文件為同類文件。

對于選定時刻的選定流內(nèi)的選定文件fi將來要寫入的數(shù)據(jù)量的計算方式如下：

設(shè)m(fi)是fi每秒的修改量，cd(fi)是fi的當(dāng)前已持續(xù)寫入的時間，wd(fi)是fi這類文件平均寫持續(xù)時間，amount(fi)是fi將來要寫入的數(shù)據(jù)量。則：

對于fi和新打開的文件fo之間的壽命差異計算如下：

設(shè)Fi是和fi同類型的文件，Ni是這類文件的數(shù)量，l(fa)是Fi中的文件的壽命。Fo、No和l(fb)的定義同理。dif(fi,fo)是fi和fo的壽命差異（最大值為1）。則：

綜上，設(shè)Fs為流s中正在寫入的文件集，對某一流s的評分如下：

在分配時選擇評分低的s分配給fo。其中，流編號為1到d。

2. Remapper：再分流

如果一個文件打開了T秒，則啟動remapper來根據(jù)文件的訪問情況分配新的流ID。此時可以認(rèn)為該文件是就地更新的文件，文件中的數(shù)據(jù)壽命可以根據(jù)USM決定。

作者每T秒啟動一個聚類算法（Kmeans++），為這類文件分配編號為d+1到N的流。（N是SSD允許的最大流編號）

3. Devider：決定mapper和remapper映射的流ID區(qū)間

divider每T秒調(diào)節(jié)d的大小。若mapper中處理的文件較多、更新較頻繁，則d更大。調(diào)節(jié)方式如下：

設(shè)FNm和FNr分別表示mapper和remapper管理的文件數(shù)量，MNm和MNr分別表示它們的文件修改總次數(shù)。首先計算一個系數(shù)proportion：

隨后計算d為：

【實驗】

1.實驗設(shè)置

本文在真實的多流SSD——SAMSUNG PM963 SSD（支持8流）上進行了測試。內(nèi)核4.13不支持傳入流ID信息，所以作者在內(nèi)核上打了補丁。

實驗測試了6個工作集，具體信息如下表：

實驗比較了FileStream和四個方案的性能差異：

①baseline：沒有多流技術(shù)

②AutoStream：根據(jù)LBA的訪問情況（連續(xù)性、更新頻次、時間）自動分流

③LKStream：通過相關(guān)的數(shù)據(jù)集的特點（I/O大小、I/O數(shù)目和帶寬），預(yù)測數(shù)據(jù)的溫度來進行分流

④ManualStream：手動分流。數(shù)據(jù)先根據(jù)文件類型區(qū)分，然后對于數(shù)據(jù)文件，根據(jù)文件的等級（對于RocksDB和Cassandra）或者更新頻次（對于MySQL、PostgreSQL和MongoDB）分流。

T被設(shè)置為60s。

2.結(jié)果分析

WAF

在幾乎所有策略中，F(xiàn)ileStream表現(xiàn)最好，甚至比手動分流還要好。和baseline、AutoStream和LKStream相比，F(xiàn)ileStream平均減少了WAF34.5%、22.3%和20.8%。Docker是一個混合了多類工作集的復(fù)雜工作集，F(xiàn)ileStream可以很好地區(qū)分不同的數(shù)據(jù)壽命，所以它的表現(xiàn)比其他策略更好。

Throughput

注：對于MySQL和PostgreSQL，使用每分鐘的事務(wù)數(shù)表示帶寬；對于RocksDB、Cassandra、MongoDB，使用每秒鐘操作數(shù)表示帶寬；對于Docker，使用IOPS表示帶寬。

FileStream和其他策略相比，帶寬明顯更高。和AutoStream和LKStream相比，帶寬分別平均提高了21.9%和25.8%。因為mapper把append-only文件的數(shù)據(jù)分到不同的流中，比手動分流分得更加徹底，所以FileStream的帶寬更好。

不同模塊的分析

圖中mapper+remapper表示mapper和remapper平均分配N流，從圖中可以看出來，此時并不能達到最優(yōu)，所以divider是很有必要的。

T的分析

從圖可知，60s并沒有達到最優(yōu)，后續(xù)或許可以進行動態(tài)調(diào)整。然而，WAF對T的變化并不敏感。

資源消耗分析

因為聚類只使用USM，所以對CPU的占用只有微弱的提升。同時內(nèi)存消耗不會超過50MB。

【總結(jié)與未來的工作】

FileStream總結(jié)

（1）使用mapper，基于流的使用情況和文件類型把新打開的文件分到不同的流中

（2）使用remapper，利用Kmeans++聚類，把文件分到不同類中

實驗顯示FileStream可以減少WAF、提高帶寬。

未來工作

（1）將FileStream擴展到更多的設(shè)備上，如Zoned Namespace SSD。

（2）當(dāng)文件內(nèi)的數(shù)據(jù)壽命不一致時，結(jié)合文件信息和LBA相關(guān)的信息進行進一步?jīng)Q策。

致謝

感謝本次論文解讀者，來自華東師范大學(xué)的碩士生俞丁翠，主要研究方向為智能存儲。