【概要】

根據(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)。最后作者測(cè)試了六個(gè)不同的benchmark，和baseline和兩個(gè)自動(dòng)流管理技術(shù)相比，分別平均減少了寫放大34.5%和21.6%。

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

1. 多流技術(shù)

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

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

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

手動(dòng)分流

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

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

自動(dòng)分流

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

表2 各種自動(dòng)分流策略一覽

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

FileStream——基于文件特征實(shí)現(xiàn)自動(dòng)分流

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

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

文件特征分析

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

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

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

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

不過，從圖中可以得到兩個(gè)信息：

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

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

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

圖1 RocksDB 文件的操作

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

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

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

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

【方法】

1. Mapper：初分流

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

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

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

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

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

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

在分配時(shí)選擇評(píng)分低的s分配給fo。其中，流編號(hào)為1到d。

2. Remapper：再分流

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

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

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ù)。首先計(jì)算一個(gè)系數(shù)proportion：

隨后計(jì)算d為：

【實(shí)驗(yàn)】

1.實(shí)驗(yàn)設(shè)置

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

實(shí)驗(yàn)測(cè)試了6個(gè)工作集，具體信息如下表：

實(shí)驗(yàn)比較了FileStream和四個(gè)方案的性能差異：

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

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

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

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

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

2.結(jié)果分析

WAF

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

Throughput

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

FileStream和其他策略相比，帶寬明顯更高。和AutoStream和LKStream相比，帶寬分別平均提高了21.9%和25.8%。因?yàn)閙apper把a(bǔ)ppend-only文件的數(shù)據(jù)分到不同的流中，比手動(dòng)分流分得更加徹底，所以FileStream的帶寬更好。

不同模塊的分析

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

T的分析

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

資源消耗分析

因?yàn)榫垲愔皇褂肬SM，所以對(duì)CPU的占用只有微弱的提升。同時(shí)內(nèi)存消耗不會(huì)超過50MB。

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

FileStream總結(jié)

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

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

實(shí)驗(yàn)顯示FileStream可以減少WAF、提高帶寬。

未來工作

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

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

致謝

感謝本次論文解讀者，來自華東師范大學(xué)的碩士生俞丁翠，主要研究方向?yàn)?a target="_blank">智能存儲(chǔ)。