? ?日志結(jié)構(gòu)存儲在當(dāng)今存儲系統(tǒng)中被廣泛使用，然而其中的垃圾回收會將有效數(shù)據(jù)重新寫入導(dǎo)致寫放大現(xiàn)象?，F(xiàn)有最佳的數(shù)據(jù)放置策略是通過知道未來每個塊的無效時間進(jìn)行數(shù)據(jù)放置，然而無法在現(xiàn)實中實現(xiàn)。本篇工作提出一個新型的數(shù)據(jù)放置策略SepBIT，通過推測每個塊的無效時間，來將無效時間相似的塊放在一起，從而減少寫放大并提高了I/O帶寬。SepBIT目前已經(jīng)被部署在了阿里云上。

01?背景

? ? 在基于日志結(jié)構(gòu)存儲中，數(shù)據(jù)被分為很多個段，而段中含有很多個塊。當(dāng)向其中寫入數(shù)據(jù)時，會以塊的粒度進(jìn)行追加。當(dāng)其中的數(shù)據(jù)進(jìn)行更新的時候，也將會通過往后追加塊的方式寫入數(shù)據(jù)來實現(xiàn)異地更新。當(dāng)一個段中數(shù)據(jù)寫滿的時候，數(shù)據(jù)將會寫到下一個段中。由于采用了異地更新，因此當(dāng)存儲中的段都寫滿的時候，需要選擇其中一個段，將其中的有效數(shù)據(jù)重新寫入并進(jìn)行擦除，通過這個方式來回收無效數(shù)據(jù)所占用的空間，這個過程就叫做垃圾回收(GC)。在這個過程中重新寫入的有效頁就是造成寫放大的原因。為了降低寫放大，現(xiàn)在最優(yōu)的數(shù)據(jù)放置策略是通過預(yù)先知道所有數(shù)據(jù)的失效信息，從而將失效時間相似的數(shù)據(jù)放到一起。然而這個策略在現(xiàn)實中無法實現(xiàn)，這是因為1. 需要預(yù)先知道所有數(shù)據(jù)的失效時間是無法做到的；2. 同時需要維護(hù)很多可供寫入的段地址，因此會帶來很高的內(nèi)存和存儲開銷。同時此時的隨機(jī)寫會帶來性能下降。

02?動機(jī)

? ? 本文根據(jù)對阿里云和騰訊云真實負(fù)載的分析，探索其中有關(guān)于數(shù)據(jù)無效時間的發(fā)現(xiàn)。本文中的數(shù)據(jù)無效時間（壽命）定義為在兩次數(shù)據(jù)寫入中寫入的數(shù)據(jù)量。其中選取了騰訊云的4995個負(fù)載，以及從阿里云1000個負(fù)載中篩選的186個以寫為主的負(fù)載。本文得到了3個發(fā)現(xiàn):

1. 用戶寫入的數(shù)據(jù)通常壽命較短。

據(jù)統(tǒng)計，超過一半的負(fù)載中超過79.5%的數(shù)據(jù)壽命低于負(fù)載集大小的80%，同時47.6%的數(shù)據(jù)壽命低于負(fù)載集大小的10%。其中負(fù)載集大小的定義為數(shù)據(jù)邏輯地址的范圍。而通過GC重新寫入的數(shù)據(jù)往往壽命較長。

2. 頻繁更新的數(shù)據(jù)之間壽命差異較大。

發(fā)現(xiàn)2中統(tǒng)計了每個負(fù)載中更新頻率最高的20%的數(shù)據(jù)，并分為四個區(qū)間1%，1-5%，5-10%和10-20%。據(jù)統(tǒng)計，有25%的負(fù)載中四個區(qū)間的變異系數(shù)（CV）分別為4.34，3.20，2.14和1.82，即他們之間壽命的差異性較大。其中變異系數(shù)的定義為(標(biāo)準(zhǔn)差/平均值)。這個發(fā)現(xiàn)也論證了現(xiàn)在有些根據(jù)數(shù)據(jù)更新頻繁程度進(jìn)行數(shù)據(jù)放置的策略并不能夠很好的將具有相似失效時間的數(shù)據(jù)放到一起。

3. 很少更新的數(shù)據(jù)占主流，并且其中壽命的差距也很大。

發(fā)現(xiàn)3中將很少更新的數(shù)據(jù)定義為更新次數(shù)小于4次的數(shù)據(jù)。據(jù)統(tǒng)計，超過一半的負(fù)載中有超過72.4%的數(shù)據(jù)很少被更新。同時將很少更新數(shù)據(jù)通過無效時間劃分為五個區(qū)間，小于0.5倍的負(fù)載集大小，0.5-1倍的負(fù)載集大小，1-1.5倍的負(fù)載集大小，1.5-2倍的負(fù)載集大小和大于2倍的負(fù)載集大小。據(jù)統(tǒng)計其中25%的工作負(fù)載中，超過71.5%的數(shù)據(jù)的壽命低于0.5倍的負(fù)載集大小。位于其余四個區(qū)間壽命數(shù)據(jù)量的均值為24.9%，8.1%，3.3%和2.2%。這就表示對于很少更新的數(shù)據(jù)，他們之間的壽命差異也較大。同樣證明了以數(shù)據(jù)更新頻繁度進(jìn)行數(shù)據(jù)放置策略并不是十分有效的。

圖1：SepBIT的三個發(fā)現(xiàn)

03?SepBIT設(shè)計

????SepBIT是一個推測數(shù)據(jù)的無效時間來對數(shù)據(jù)進(jìn)行放置的策略。根據(jù)發(fā)現(xiàn)1，SepBIT首先將數(shù)據(jù)分為用戶數(shù)據(jù)和GC寫入數(shù)據(jù)，因為它們之間的壽命差異較大。SepBIT將段分為六類，其中1類和2類用于分別存放壽命短和壽命長的用戶數(shù)據(jù)，3類-6類用于存放GC寫入的數(shù)據(jù)。其中3類存放的是通過GC寫入的1類中的數(shù)據(jù)，而4-6類則存放的是通過GC寫入的2類中的數(shù)據(jù)。

圖2：SepBIT工作流程圖

??? SepBIT通過對用戶數(shù)據(jù)上一次寫入與這一次寫入之間的壽命，來推測這一次數(shù)據(jù)寫入到下一次數(shù)據(jù)寫入的壽命。同時通過對GC重寫入數(shù)據(jù)與上一次用戶寫入數(shù)據(jù)的壽命，來推測下一次用戶寫入與這次GC重寫入數(shù)據(jù)之間的壽命。以下分別通過數(shù)學(xué)模型和實驗真實負(fù)載運(yùn)行的結(jié)果來進(jìn)行論證推測方法的有效性。

1. 推測用戶數(shù)據(jù)的數(shù)據(jù)無效時間

圖3：推測用戶數(shù)據(jù)的數(shù)據(jù)無效時間

數(shù)學(xué)分析: V為上一次和這次用戶寫入之間的壽命，U為這一次和下一次用戶寫入之間的壽命。通過計算條件概率公式，當(dāng)V<=V0時，U<=U0時的概率，證明當(dāng)V小的時候U也較小。則條件概率公式為：

其中Pi為頁面滿足Zipf分布，即，其中α越大，則表示工作負(fù)載越傾斜。通過調(diào)整U0,V0和α觀察結(jié)果得出結(jié)論。

1）設(shè)定α為1時，將U0和V0的閾值在短壽命范圍內(nèi)進(jìn)行波動，即0.25-4GB之間，發(fā)現(xiàn)得到的條件概率最低為77.1%。即證明了V小的時候，U大概率也是較小的。

2）設(shè)定U0為1GB時，調(diào)整α和V0，發(fā)現(xiàn)當(dāng)負(fù)載越傾斜時，條件概率越大，結(jié)論才越成立。

圖4：通過數(shù)學(xué)分析推測用戶數(shù)據(jù)寫入無效時間的條件概率

負(fù)載分析：通過對真實負(fù)載進(jìn)行運(yùn)行，并對不同的V0和U0進(jìn)行統(tǒng)計。發(fā)現(xiàn)在大多數(shù)的情況下條件概率都比較高。

圖5：通過負(fù)載分析推測用戶數(shù)據(jù)寫入無效時間的條件概率

2. 推測GC重寫入數(shù)據(jù)的數(shù)據(jù)無效時間

圖6：推測GC重寫入數(shù)據(jù)的數(shù)據(jù)無效時間

數(shù)學(xué)分析: g為上一次用戶寫入和這次GC重寫入之間的壽命，r為這一次GC重寫入和下一次用戶寫入之間的壽命,u為數(shù)據(jù)在上一次用戶寫入和下一次用戶寫入之間的壽命。通過計算條件概率公式，當(dāng)u>=g=g0時，u<=g0+r0時的概率，證明壽命大于g0的數(shù)據(jù)剩余壽命（r）小于r0的概率。則條件概率公式為：

其中Pi也同樣滿足Zipf分布。通過調(diào)整g0,r0和α，得出結(jié)論如下。

1）設(shè)定α為1時，對于每一個r0來說，g0越小，條件概率越大。即不同年齡（g）的數(shù)據(jù)，其剩余壽命（r）的概率不同，即證明可以通過g來推測r的大小。

2）設(shè)定r0為8GB時，調(diào)整α和g0。發(fā)現(xiàn)，當(dāng)負(fù)載越傾斜的時候，不同g0之間的條件概率差距越大，即越能夠根據(jù)g來推測r的大小。

圖7：通過數(shù)學(xué)分析推測GC數(shù)據(jù)寫入無效時間的條件概率

負(fù)載分析：通過對真實負(fù)載進(jìn)行運(yùn)行，并對不同的g0和r0進(jìn)行統(tǒng)計。發(fā)現(xiàn)固定r0時，對于不同的g0，條件概率差距較大。故而可以證明推論，可以根據(jù)g來推測r的大小。

圖8：通過負(fù)載分析推測GC數(shù)據(jù)寫入無效時間的條件概率

最后，簡單介紹下SepBIT的工作流程。

1. 垃圾回收：當(dāng)剩余空間達(dá)到閾值的時候，垃圾回收將被觸發(fā)。對于每個回收的1類段將計算該段的無效時間，每16個段計算一次平均段的無效時間作為閾值L。段中的有效數(shù)據(jù)將進(jìn)行GC重寫入。

2. 用戶寫入：對于用戶寫入數(shù)據(jù)，判斷其上一次的壽命是否低于閾值L，若低于則寫入1類段，否則寫入2類段。

3. GC重寫入：如果該數(shù)據(jù)是1類段中的數(shù)據(jù)，則寫入3類段中。否則判斷該數(shù)據(jù)的壽命。若其介于0-4L之間，則寫入4類段；若介于4L-16L之間，則寫入5類段；否則寫入6類段中。

04?實驗效果

????論文作者團(tuán)隊將SepBIT實現(xiàn)在了基于ZenFS的zoned storage模擬平臺上。其中后端使用的存儲介質(zhì)為Intel傲騰持久內(nèi)存。并在其中使用真實的阿里云和騰訊云負(fù)載進(jìn)行測試。其中段的大小和垃圾回收閾值設(shè)置為512MB和15%。

????在實驗中，本文與8個基于溫度的數(shù)據(jù)放置策略進(jìn)行比較，同時與無數(shù)據(jù)放置策略，本文的SepBIT和理想化的基于每個數(shù)據(jù)無效時間的FK進(jìn)行比較。

????通過最后的實驗結(jié)果可以得出以下結(jié)論：

1．SepBIT對于不同GC策略、不同段大小下以及不同GC閾值下，均可以達(dá)到除FK以外最低的寫放大。

2．SepBIT對于數(shù)據(jù)無效時間的推測較為精準(zhǔn)。

3．通過消融實驗，證明了SepBIT對于用戶數(shù)據(jù)和GC數(shù)據(jù)分類的有效性。

4．SepBIT在騰訊云負(fù)載下的表現(xiàn)也是最好的。

5．SepBIT在高傾斜度負(fù)載下降低了較多的寫放大。

6．SepBIT在大多數(shù)負(fù)載下對于內(nèi)存的開銷較低。

7．SepBIT對于大多數(shù)負(fù)載達(dá)到了較高的帶寬。

????基于空間限制，以下展示對于不同GC策略下，各個數(shù)據(jù)放置策略的寫放大比較，如圖9所示；以及SepBIT對于數(shù)據(jù)無效時間推測的準(zhǔn)確性，如圖10所示，其中縱坐標(biāo)為累計分布，橫坐標(biāo)為垃圾回收時無效數(shù)據(jù)的比例，對于相同累計分布時，其無效數(shù)據(jù)比例越大說明預(yù)測越準(zhǔn)確。

圖9：不同GC策略下，各數(shù)據(jù)放置策略的寫放大

圖10：不同策略對于數(shù)據(jù)無效時間推測的準(zhǔn)確性

05?總結(jié)

????SepBIT通過對真實負(fù)載的分析發(fā)現(xiàn)了用戶寫數(shù)據(jù)和GC重寫入數(shù)據(jù)壽命的差異性，同時發(fā)現(xiàn)發(fā)現(xiàn)并驗證了根據(jù)數(shù)據(jù)過去壽命推測數(shù)據(jù)接下來壽命的有效性。進(jìn)而通過將具有相似壽命的數(shù)據(jù)放在一起從而降低寫放大并提升I/O帶寬。

審核編輯：劉清