經典Dual-pool 算法-高效Wear Leveling

原創內容,轉載請注明:  [http://www.od-music.com]  謝謝!

Dual-pool算法是比較經典的磨損平衡算法,目的是為了延長閃存的使用壽命。它實現了兩方面解決:第一是存儲冷數據來防止塊被磨損,因為頻繁更新的熱數據會是磨損增加;第二是直到磨損平衡生效時,先不要去管這些被處理的塊。

基本原則:

閃存塊的磨損不均勻是由于workload的空間局部性導致的。把page分為三類:free page,表示可以寫入數據的頁,live page 表示有效頁,dead page 表示無效頁。因為冷數據能夠較穩定的保存在塊中的有效頁上,而熱數據更新的快,不斷地更新會使原位的有效頁變為無效頁,就是會留下很多的 dead pages在塊中,在做垃圾回收的時候傾向于回收這些dead page多的塊,所以總是從那些存儲熱數據較多的塊中回收free page。寫入熱數據比寫入冷數據發生的頻率高,所以把這些熱數據存在特定的塊里面。但是這樣的現象會逐漸使得磨損的塊出現失衡。

Young block & Old block:前者是擦除次數少的年輕的塊,后者是擦出次數多的年老的塊,雙池算法核心實現下面的操作:

Cold-data migration:把冷數據從young blocks 遷移到old blocks

Hot-cold regulation: 發生冷數據遷移后,涉及到的塊,要防止老的塊被擦除,還要開始擦除年輕的塊。

從邏輯上把閃存塊分為兩組:熱池(hot pool)專門來存儲熱數據的塊和冷池(cold pool)專門來存儲冷數據的塊。在熱池中設置隊列在冷池中設置隊列隊列根據每個塊的擦除周期優先排序。關于優先的隊列Q,函數H+(Q)返回的是最大隊列頭塊,相反,函數H-(Q)返回的是最小隊列頭塊。關于塊B,函數EC(B),返回的是該塊的擦除周期。開始的時候,一個塊可以任意加入兩個池,用閾值TH來進行后續判定,TH值越小,磨損平衡效果越好。

Dirty Swap(DS)操作實現了上述的Cold-data migration和Hot-cold regulation,每次完成一個寫入操作的時候,要做一步檢查,是否該熱池的熱數據塊和冷池中的冷數據塊的擦除周期差異大于閾值,過程如下:

如果滿足以上條件,執行如下步驟:

 

 

 

 

 

 

 

 

 

 

Adaptive Pool Resizing:這部分是處理空間局部性的動態變化,對上面的基礎概念進行擴充。如果訪問模式一直不變化,上面的執行結果會帶來很好的效果。但是在實際的workload中,很難實現。冷熱數據的訪問不是一成不變的,僅僅使用DS是不行的??紤]到一個塊剛剛從冷池中遷移到熱池中,并不再存儲冷數據,假設塊中的熱數據恰巧變冷,隨著這個塊不再被擦除磨損,這個塊就在熱池中變得“沉默”,因為存儲冷數據使它的擦除周期變得相對較小,這個塊又開始不再被磨損擦除。所以,為了改進,定義了一種新的操作在熱池中:

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

考慮到有DS遷移至冷池中的塊,這個塊具有大的擦除周期,而有效擦除周期為0,DS把冷數據放置在塊里停止它被磨損擦除。一方面,如果冷數據一直保持,那么這個塊的有效擦除周期值就會維持在低值。另一方面,如果這個塊不再存儲冷數據,那么有效擦除周期就會增長的很快。通過引入的有效擦除周期的檢驗,這兩種情況能被明顯區分。

所以在完成一次寫入操作時,先進行DS操作,然后執行CPR,最后執行HPR。

對于超大規模閃存存儲系統而言, 這一提出的算法為磨損均衡問題提供了非常有力的解決。

分類目錄 技術文章, 閃存.
掃一掃二維碼或者微信搜索公眾號ssdfans關注(添加朋友->點最下面的公眾號->搜索ssdfans),可以經??吹絊SD技術和產業的文章(SSD Fans只推送干貨)。
ssdfans微信群介紹
技術討論群 覆蓋2000多位中國和世界華人圈SSD以及存儲技術精英
固件、軟件、測試群 固件、軟件和測試技術討論
異構計算群 討論人工智能和GPU、FPGA、CPU異構計算
ASIC-FPGA群 芯片和FPGA硬件技術討論群
閃存器件群 NAND、3D XPoint等固態存儲介質技術討論
企業級 企業級SSD、企業級存儲
銷售群 全國SSD供應商都在這里,砍砍價,會比某東便宜20%
工作求職群 存儲行業換工作,發招聘,要關注各大公司招聘信息,趕快來
高管群 各大SSD相關存儲公司高管和創始人、投資人

想加入這些群,請微信掃描下面二維碼,或搜索nanoarchplus,加阿呆為微信好友,介紹你的昵稱-單位-職務,注明群名,拉你進群。SSD業界需要什么幫助,也可以找阿呆聊。