垃圾回收的概念其實(shí)是很簡(jiǎn)單的，太多了資料可以看看就會(huì)明白，主要的經(jīng)典算法就是Greedy policy，Cost-benefit policy, Cost-Age-Times(CAT)policy。這里我就簡(jiǎn)單說一下需要掌握的幾個(gè)關(guān)鍵性概念：

1、預(yù)留空間 OP(Over Provisioning) 和 WAF(Write Amplification Factor)

由于WAF的大小和copy 有效數(shù)據(jù)有關(guān)，想要減少WAF的值出發(fā)點(diǎn)是減少copy。

2、掌握垃圾回收，沿著以下線路進(jìn)行探索（1）GC的原因：塊最終會(huì)被寫滿，必須時(shí)刻保證有free page 來滿足新的寫入需求（2）GC的過程：When to GC 什么時(shí)候喚醒GC操作->Which block選擇作為victim block, 這里的選擇方法就是上述提到的經(jīng)典算法以及改進(jìn)->How many blocks將要被erase 擦除，只要涉及到擦除，就會(huì)和磨損平衡有關(guān)->How to 寫回這些有效數(shù)據(jù)，Where to 分配這些有效數(shù)據(jù)，這里稱之為Data redistribution policy數(shù)據(jù)再分配策略Where 來分配新請(qǐng)求寫入的數(shù)據(jù)

想要改進(jìn)GC的算法，最基本的簡(jiǎn)單的就是按照上述來思考。

現(xiàn)如今的都是在經(jīng)典算法上進(jìn)行改良。我在學(xué)習(xí)的時(shí)候做過三種算法的模擬，后來自己加了一個(gè)Two-block Policy 來實(shí)現(xiàn)block再分配，做了一個(gè)簡(jiǎn)簡(jiǎn)單單的改良，WAF寫放大，以及copy次數(shù)顯著減少。就是有兩類block,一類是host write block, 寫入的是從host發(fā)來的新數(shù)據(jù)；另一類是copy write block，寫入的是victim block上的有效數(shù)據(jù)。Z這樣簡(jiǎn)單的分類對(duì)后續(xù)學(xué)習(xí)磨損平衡很有幫助。包括那些經(jīng)常更新的數(shù)據(jù)還有不經(jīng)常更新的數(shù)據(jù)怎么來做處理都是學(xué)習(xí)和思考的點(diǎn)。

對(duì)Wear Leveling 磨損平衡的認(rèn)知：

在寫數(shù)據(jù)操作不斷更新的情況下，使得物理閃存塊的擦除操作頻繁發(fā)生，而每一個(gè)塊上的擦除操作次數(shù)不是無限的，是有一定壽命的，也就是經(jīng)常看到的Program/Erase Cycle 來衡量閃存的壽命。一個(gè)block擦除次數(shù)到達(dá)了一定的閾值，會(huì)使得這個(gè)塊報(bào)廢，降低閃存的壽命。磨損平衡的出發(fā)點(diǎn)是不能一直讓那幾個(gè)塊一直不斷的erase,應(yīng)該讓所有的block平攤這個(gè)任務(wù)，最好的理想狀態(tài)就是每個(gè)block的擦除次數(shù)是平均的，達(dá)到平衡的效果，以此來延長(zhǎng)閃存的壽命。

拿一張紙記筆記來說，如果不斷的更改內(nèi)容在一處，不斷的用橡皮擦erase,用不了幾次，這里就會(huì)破掉，因此每次擦除盡量在整張紙上找剛擦一兩次的，這會(huì)延長(zhǎng)紙張整體壽命。

關(guān)于閃存的預(yù)期壽命：

這個(gè)overhead是指文件系統(tǒng)和閃存管理數(shù)據(jù)結(jié)構(gòu)的開銷。

在看了很多論文以及材料的時(shí)候以下是常常會(huì)接觸到的概念：

在研究磨損平衡的時(shí)候把擦除次數(shù)Erase Counts多的塊稱之為old blocks，這類塊年歲已高，壽命即將到達(dá)尾聲，因此盡量不要讓他們?cè)俳?jīng)受擦除的折磨來長(zhǎng)命百歲，任務(wù)就給那些擦出次數(shù)少的塊成為young block，年輕力壯，可以幫老人們多多承擔(dān)擦除的任務(wù)。

前面有提到，擦除是由于用戶寫入數(shù)據(jù)不斷更新而造成的，那些不斷更新的數(shù)據(jù)稱之為hot data，具有high locality，相對(duì)比，不常更新的稱之為cold data。

在研究了經(jīng)典的CAT垃圾回收算法時(shí)，因?yàn)镃opy的有效數(shù)據(jù)可以是cold data 也可以是hot data，而不斷更新的新的請(qǐng)求數(shù)據(jù)，那些也可以是cold data和hot data，那么怎樣處理這些數(shù)據(jù)，怎么樣分配閃存的 物理塊，能夠減少copy的次數(shù)，能夠延長(zhǎng)閃存的壽命，這里就會(huì)啟發(fā)很多想法。

磨損平衡分為動(dòng)態(tài)和靜態(tài)兩種：

動(dòng)態(tài)磨損平衡：主要特點(diǎn)是下一次寫數(shù)據(jù)選擇那些擦除次數(shù)少的即young blocks來寫，但是那些存放cold data的塊的擦除次數(shù)是比存放hot data的少很多的，因此盡可能的把hot data 寫進(jìn)young blocks上，但是cold data不能一直占用擦出次數(shù)少的塊，會(huì)造成失衡，因此需要靜態(tài)磨損平衡，冷熱數(shù)據(jù)的分離對(duì)性能影響很大。

靜態(tài)磨損平衡：主要做的就是追蹤所有的好塊，把cold data從young blocks里面copy 到 older blocks中，這樣可以讓young blocks歇一歇。我們要記得磨損平衡不是為了減少copy次數(shù)，而是為了延閃存的壽命。

二者的比較動(dòng)態(tài)磨損平衡是低成本并且降低靜態(tài)磨損平衡的復(fù)雜度，靜態(tài)磨損平衡是最大化的延長(zhǎng)了壽命，所以要將二者結(jié)合。

磨損平衡的終極目標(biāo)就是：

Hot data -> young blocks

Cold data -> old blocks

Hot-Cold Swapping 技術(shù)

核心算法（結(jié)合CAT垃圾回收算法）：

每個(gè)block都記錄著對(duì)應(yīng)的擦出次數(shù)

定期檢查所有塊的擦出次數(shù)，這個(gè)激活期成為AP（Activation Period）

只要任何兩個(gè)塊的擦除次數(shù)之間的最大差異大于閾值，它們就會(huì)被交換

由于磨損平衡，會(huì)帶來的性能開銷會(huì)使得WAF增大。