壽增3倍的磨損平衡算法思想.pdf

《壽增3倍的磨損平衡算法思想.pdf》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。

1、1壽增三倍的固態(tài)硬盤磨損平衡算法思想【原創(chuàng)】瑞耐斯技術(shù)兵哥本文前面部分介紹磨損平衡產(chǎn)生的背景以及常用的算法思想，后半部分介紹了一種可以壽增三倍的磨損平衡算法：Non-Blance算法，高手可以直接跳過(guò)前面部分。為了讓閃存擁有更長(zhǎng)久的生命周期，避免一些塊（Block）被頻繁擦除而迅速成為壞塊，而另一些塊則因極少擦除這樣不均衡的擦寫而導(dǎo)致SSD整體生命周期縮短的弊端，閃存從業(yè)者提出了多種磨損平衡算法（Wear-Levelling）和垃圾回收（GarbageCollection）策略來(lái)規(guī)避這些問(wèn)題的產(chǎn)生。磨損平衡算法產(chǎn)生的背景磨損平衡算法是基于閃存的基本特征而產(chǎn)生：1、不支

2、持本地更新（outplace-update，即不能在原數(shù)據(jù)位置進(jìn)行覆蓋寫入或者直接更改，更改數(shù)據(jù)需要將更改后的數(shù)據(jù)搬遷至新的可用的page，原有位置的page被標(biāo)示為無(wú)效頁(yè)，必須要先擦除無(wú)效頁(yè)才能在原位置重新寫入數(shù)據(jù)）；2、以page為單位寫入，以Block為單位擦除，擦除Block需要先將可用page中的數(shù)據(jù)搬遷，那么，當(dāng)有大量的Block可以被選擇擦除時(shí)，搬遷哪些Block中的page并重新利用就關(guān)系到對(duì)不同Block的擦除次數(shù)；3、每個(gè)Block有擦除次數(shù)限制，經(jīng)常被擦除的Block會(huì)很快成為“壞塊（badblock）”因此，只有均衡每個(gè)Block的擦除次數(shù)，才

3、能讓閃存具有更長(zhǎng)的使用壽命。FTL通常將page分為三種類型：有效頁(yè)（validpage）、無(wú)效頁(yè)（Invilidpage）、可用頁(yè)（Freepage）,若物理頁(yè)有邏輯地址相對(duì)應(yīng)則表明該頁(yè)的數(shù)據(jù)是有效的，稱為有效頁(yè)，反之，稱為無(wú)效頁(yè)，當(dāng)垃圾回收運(yùn)行后，無(wú)效頁(yè)被Erase，成為可用頁(yè)，此時(shí)，才可以重新被寫入數(shù)據(jù)。舉例來(lái)說(shuō)，當(dāng)邏輯地址A（假設(shè)對(duì)應(yīng)物理地址1）數(shù)據(jù)需要被修改，無(wú)法直接對(duì)A地址的數(shù)據(jù)修改，需要將A地址數(shù)據(jù)讀取到cache中進(jìn)行修改，然后將修改好的數(shù)據(jù)寫入新的物理地址（假設(shè)物理地址6），同時(shí)將邏輯地址A對(duì)應(yīng)到物理地址6，TRIM將物理地址1標(biāo)為無(wú)效頁(yè)，當(dāng)可用頁(yè)越

4、來(lái)越少時(shí)，就會(huì)啟動(dòng)垃圾回收（GarbageCollection）,將無(wú)效頁(yè)進(jìn)行Erase，重新變成可用頁(yè)，此時(shí)，問(wèn)題就來(lái)了：由于Erase是以Block為單位，如果需要擦除的Block中仍然包含有效頁(yè)，那么就需要先將有效頁(yè)進(jìn)行搬遷，然后才能擦除，那么，是對(duì)包含有效頁(yè)最少的Block進(jìn)行擦除還是對(duì)雖然包含有效頁(yè)較多但擦除次數(shù)較少的Block進(jìn)行擦除？是否考慮有效塊冷數(shù)據(jù)所在Block的擦除次數(shù)？還是有他條件的對(duì)某些Block進(jìn)行擦除？由于這些垃圾回收直接關(guān)系到Block的擦除次數(shù)，因此，如何做到每個(gè)Block都能夠被平均的擦除，而不是對(duì)某些包含熱點(diǎn)數(shù)據(jù)的Block經(jīng)常被

5、擦除，而另一些Block則極少被擦除，磨損平衡算法正是在此背景下產(chǎn)生。2垃圾回收策略所謂的磨損平衡是指在執(zhí)行垃圾回收的過(guò)程中，對(duì)哪些Block執(zhí)行垃圾回收，用什么樣的機(jī)制進(jìn)行回收才能保證每個(gè)Block被擦除的次數(shù)接近均衡。簡(jiǎn)單的回收策略可以縮短計(jì)算回收Block所需的時(shí)間，但會(huì)導(dǎo)致每個(gè)Block磨損的不均衡。復(fù)雜的回收策略均衡了算法，但導(dǎo)致系統(tǒng)效能降低，因此，好的回收策略需要平衡系統(tǒng)效能和磨損次數(shù)之間的微妙關(guān)系。垃圾回收策略從最基本的Greedy算法（選擇包含最少有效頁(yè)的Block來(lái)回收）到逐步演進(jìn)的cost-Benefit算法（考慮的Block的擦除頻率，也就是冷熱

6、數(shù)據(jù)的影響），公式如下：再到CAT回收算法，在cost-benefit的基礎(chǔ)上考慮了Block的擦除次數(shù)因素，需要回收的Block由決定，選擇所得值最小的Block來(lái)回收）。公式如下：進(jìn)而CICL算法則更進(jìn)一步進(jìn)行了優(yōu)化，需要回收的Block由Block中的有效page數(shù)與所有Block擦除次數(shù)是否平均兩個(gè)因素來(lái)決定，l為決定這兩個(gè)因素的權(quán)重，如果所有Block的平均擦除次數(shù)相同，則l為0，選擇需要回收的Block時(shí)只需要考慮Block中的有效page數(shù)即可，否則，就需要考慮此兩種因素。公式如下：基于上述垃圾回收策略的基礎(chǔ)思想，各家Controller廠商演變出多種多

7、樣的各不相同垃圾回收算法，以及冷熱數(shù)據(jù)的分析方法。被動(dòng)回收策略和主動(dòng)回收策略3垃圾回收有兩個(gè)重要的問(wèn)題需要考慮：回收無(wú)效Block的時(shí)機(jī)以及每次回收的數(shù)量。因此，又關(guān)系到兩種回收策略：主動(dòng)回收策略與被動(dòng)回收策略。被動(dòng)回收策略是當(dāng)接收到寫入請(qǐng)求時(shí)，系統(tǒng)根據(jù)目前狀況判斷是否執(zhí)行垃圾回收，此策略模式下，系統(tǒng)通常會(huì)對(duì)可用空間設(shè)定一個(gè)臨界值，當(dāng)可用空間小于臨界值時(shí)開(kāi)始執(zhí)行垃圾回收。每次需要回收多少空間則有Firmware工程師自己定義。這種磨損的弊端在于：當(dāng)執(zhí)行垃圾回收時(shí)，寫入請(qǐng)求會(huì)被延遲，每次需要執(zhí)行回收的Block數(shù)量越多，延遲的時(shí)間就越長(zhǎng)，外在表現(xiàn)為寫入