? ?日志結構存儲在當今存儲系統(tǒng)中被廣泛使用,然而其中的垃圾回收會將有效數(shù)據(jù)重新寫入導致寫放大現(xiàn)象。現(xiàn)有最佳的數(shù)據(jù)放置策略是通過知道未來每個塊的無效時間進行數(shù)據(jù)放置,然而無法在現(xiàn)實中實現(xiàn)。本篇工作提出一個新型的數(shù)據(jù)放置策略SepBIT,通過推測每個塊的無效時間,來將無效時間相似的塊放在一起,從而減少寫放大并提高了I/O帶寬。SepBIT目前已經(jīng)被部署在了阿里云上。
01?背景
? ? 在基于日志結構存儲中,數(shù)據(jù)被分為很多個段,而段中含有很多個塊。當向其中寫入數(shù)據(jù)時,會以塊的粒度進行追加。當其中的數(shù)據(jù)進行更新的時候,也將會通過往后追加塊的方式寫入數(shù)據(jù)來實現(xiàn)異地更新。當一個段中數(shù)據(jù)寫滿的時候,數(shù)據(jù)將會寫到下一個段中。由于采用了異地更新,因此當存儲中的段都寫滿的時候,需要選擇其中一個段,將其中的有效數(shù)據(jù)重新寫入并進行擦除,通過這個方式來回收無效數(shù)據(jù)所占用的空間,這個過程就叫做垃圾回收(GC)。在這個過程中重新寫入的有效頁就是造成寫放大的原因。為了降低寫放大,現(xiàn)在最優(yōu)的數(shù)據(jù)放置策略是通過預先知道所有數(shù)據(jù)的失效信息,從而將失效時間相似的數(shù)據(jù)放到一起。然而這個策略在現(xiàn)實中無法實現(xiàn),這是因為1. 需要預先知道所有數(shù)據(jù)的失效時間是無法做到的;2. 同時需要維護很多可供寫入的段地址,因此會帶來很高的內(nèi)存和存儲開銷。同時此時的隨機寫會帶來性能下降。
02?動機
? ? 本文根據(jù)對阿里云和騰訊云真實負載的分析,探索其中有關于數(shù)據(jù)無效時間的發(fā)現(xiàn)。本文中的數(shù)據(jù)無效時間(壽命)定義為在兩次數(shù)據(jù)寫入中寫入的數(shù)據(jù)量。其中選取了騰訊云的4995個負載,以及從阿里云1000個負載中篩選的186個以寫為主的負載。本文得到了3個發(fā)現(xiàn):
1. 用戶寫入的數(shù)據(jù)通常壽命較短。
據(jù)統(tǒng)計,超過一半的負載中超過79.5%的數(shù)據(jù)壽命低于負載集大小的80%,同時47.6%的數(shù)據(jù)壽命低于負載集大小的10%。其中負載集大小的定義為數(shù)據(jù)邏輯地址的范圍。而通過GC重新寫入的數(shù)據(jù)往往壽命較長。
2. 頻繁更新的數(shù)據(jù)之間壽命差異較大。
發(fā)現(xiàn)2中統(tǒng)計了每個負載中更新頻率最高的20%的數(shù)據(jù),并分為四個區(qū)間1%,1-5%,5-10%和10-20%。據(jù)統(tǒng)計,有25%的負載中四個區(qū)間的變異系數(shù)(CV)分別為4.34,3.20,2.14和1.82,即他們之間壽命的差異性較大。其中變異系數(shù)的定義為(標準差/平均值)。這個發(fā)現(xiàn)也論證了現(xiàn)在有些根據(jù)數(shù)據(jù)更新頻繁程度進行數(shù)據(jù)放置的策略并不能夠很好的將具有相似失效時間的數(shù)據(jù)放到一起。
3. 很少更新的數(shù)據(jù)占主流,并且其中壽命的差距也很大。
發(fā)現(xiàn)3中將很少更新的數(shù)據(jù)定義為更新次數(shù)小于4次的數(shù)據(jù)。據(jù)統(tǒng)計,超過一半的負載中有超過72.4%的數(shù)據(jù)很少被更新。同時將很少更新數(shù)據(jù)通過無效時間劃分為五個區(qū)間,小于0.5倍的負載集大小,0.5-1倍的負載集大小,1-1.5倍的負載集大小,1.5-2倍的負載集大小和大于2倍的負載集大小。據(jù)統(tǒng)計其中25%的工作負載中,超過71.5%的數(shù)據(jù)的壽命低于0.5倍的負載集大小。位于其余四個區(qū)間壽命數(shù)據(jù)量的均值為24.9%,8.1%,3.3%和2.2%。這就表示對于很少更新的數(shù)據(jù),他們之間的壽命差異也較大。同樣證明了以數(shù)據(jù)更新頻繁度進行數(shù)據(jù)放置策略并不是十分有效的。
圖1:SepBIT的三個發(fā)現(xiàn)
03?SepBIT設計
????SepBIT是一個推測數(shù)據(jù)的無效時間來對數(shù)據(jù)進行放置的策略。根據(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ù)學模型和實驗真實負載運行的結果來進行論證推測方法的有效性。
1. 推測用戶數(shù)據(jù)的數(shù)據(jù)無效時間
圖3:推測用戶數(shù)據(jù)的數(shù)據(jù)無效時間
數(shù)學分析: V為上一次和這次用戶寫入之間的壽命,U為這一次和下一次用戶寫入之間的壽命。通過計算條件概率公式,當V<=V0時,U<=U0時的概率,證明當V小的時候U也較小。則條件概率公式為:
其中Pi為頁面滿足Zipf分布,即,其中α越大,則表示工作負載越傾斜。通過調(diào)整U0,V0和α觀察結果得出結論。
1)設定α為1時,將U0和V0的閾值在短壽命范圍內(nèi)進行波動,即0.25-4GB之間,發(fā)現(xiàn)得到的條件概率最低為77.1%。即證明了V小的時候,U大概率也是較小的。
2)設定U0為1GB時,調(diào)整α和V0,發(fā)現(xiàn)當負載越傾斜時,條件概率越大,結論才越成立。
圖4:通過數(shù)學分析推測用戶數(shù)據(jù)寫入無效時間的條件概率
負載分析:通過對真實負載進行運行,并對不同的V0和U0進行統(tǒng)計。發(fā)現(xiàn)在大多數(shù)的情況下條件概率都比較高。
圖5:通過負載分析推測用戶數(shù)據(jù)寫入無效時間的條件概率
2. 推測GC重寫入數(shù)據(jù)的數(shù)據(jù)無效時間
圖6:推測GC重寫入數(shù)據(jù)的數(shù)據(jù)無效時間
數(shù)學分析: g為上一次用戶寫入和這次GC重寫入之間的壽命,r為這一次GC重寫入和下一次用戶寫入之間的壽命,u為數(shù)據(jù)在上一次用戶寫入和下一次用戶寫入之間的壽命。通過計算條件概率公式,當u>=g=g0時,u<=g0+r0時的概率,證明壽命大于g0的數(shù)據(jù)剩余壽命(r)小于r0的概率。則條件概率公式為:
其中Pi也同樣滿足Zipf分布。通過調(diào)整g0,r0和α,得出結論如下。
1)設定α為1時,對于每一個r0來說,g0越小,條件概率越大。即不同年齡(g)的數(shù)據(jù),其剩余壽命(r)的概率不同,即證明可以通過g來推測r的大小。
2)設定r0為8GB時,調(diào)整α和g0。發(fā)現(xiàn),當負載越傾斜的時候,不同g0之間的條件概率差距越大,即越能夠根據(jù)g來推測r的大小。
圖7:通過數(shù)學分析推測GC數(shù)據(jù)寫入無效時間的條件概率
負載分析:通過對真實負載進行運行,并對不同的g0和r0進行統(tǒng)計。發(fā)現(xiàn)固定r0時,對于不同的g0,條件概率差距較大。故而可以證明推論,可以根據(jù)g來推測r的大小。
圖8:通過負載分析推測GC數(shù)據(jù)寫入無效時間的條件概率
最后,簡單介紹下SepBIT的工作流程。
1. 垃圾回收:當剩余空間達到閾值的時候,垃圾回收將被觸發(fā)。對于每個回收的1類段將計算該段的無效時間,每16個段計算一次平均段的無效時間作為閾值L。段中的有效數(shù)據(jù)將進行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?實驗效果
????論文作者團隊將SepBIT實現(xiàn)在了基于ZenFS的zoned storage模擬平臺上。其中后端使用的存儲介質(zhì)為Intel傲騰持久內(nèi)存。并在其中使用真實的阿里云和騰訊云負載進行測試。其中段的大小和垃圾回收閾值設置為512MB和15%。
????在實驗中,本文與8個基于溫度的數(shù)據(jù)放置策略進行比較,同時與無數(shù)據(jù)放置策略,本文的SepBIT和理想化的基于每個數(shù)據(jù)無效時間的FK進行比較。
????通過最后的實驗結果可以得出以下結論:
1.SepBIT對于不同GC策略、不同段大小下以及不同GC閾值下,均可以達到除FK以外最低的寫放大。
2.SepBIT對于數(shù)據(jù)無效時間的推測較為精準。
3.通過消融實驗,證明了SepBIT對于用戶數(shù)據(jù)和GC數(shù)據(jù)分類的有效性。
4.SepBIT在騰訊云負載下的表現(xiàn)也是最好的。
5.SepBIT在高傾斜度負載下降低了較多的寫放大。
6.SepBIT在大多數(shù)負載下對于內(nèi)存的開銷較低。
7.SepBIT對于大多數(shù)負載達到了較高的帶寬。
????基于空間限制,以下展示對于不同GC策略下,各個數(shù)據(jù)放置策略的寫放大比較,如圖9所示;以及SepBIT對于數(shù)據(jù)無效時間推測的準確性,如圖10所示,其中縱坐標為累計分布,橫坐標為垃圾回收時無效數(shù)據(jù)的比例,對于相同累計分布時,其無效數(shù)據(jù)比例越大說明預測越準確。
圖9:不同GC策略下,各數(shù)據(jù)放置策略的寫放大
圖10:不同策略對于數(shù)據(jù)無效時間推測的準確性
05?總結
????SepBIT通過對真實負載的分析發(fā)現(xiàn)了用戶寫數(shù)據(jù)和GC重寫入數(shù)據(jù)壽命的差異性,同時發(fā)現(xiàn)發(fā)現(xiàn)并驗證了根據(jù)數(shù)據(jù)過去壽命推測數(shù)據(jù)接下來壽命的有效性。進而通過將具有相似壽命的數(shù)據(jù)放在一起從而降低寫放大并提升I/O帶寬。
審核編輯:劉清
評論
查看更多